Travelling Salesman Problem

외판원 문제(travelling salesman problem, TSP)에 대한 자세한 내용은 블로그에서 참고해보시기 바랍니다.

이강우 & 김정자. (2012). EXCEL 2010 경영과학. 한경사, 390.

Table 1. Example

	1(Yard)	2(A)	3(B)	4(C)	5(D)
1(Yard)	-	4.0	4.0	4.7	5.0
2(A)	0.0	-	1.3	2.5	1.7
3(B)	0.0	1.3	-	1.0	2.0
4(C)	0.0	2.5	1.0	-	2.0
5(D)	0.0	1.7	1.4	2.0	-

외판원 문제를 정식화하면 $n$개의 도시가 있을 때 인덱스 $i$와 $j$는 $n$개 만큼있으며 파리미터는 거리 $c_{ij}$, 의사결정변수로 $x_{ij}$와 $u_{i}$가 있으며 Miller-Tucker-Zemlin (MTZ) 공식은 다음과 같습니다.

\[\begin{split}x_{ij} = \begin{cases} 1, \; \text{if the edge $(i,j)$ is included in the Hamilton cycle}\\ 0, \; \text{otherwise} \end{cases}\end{split}\]

\[u_{i} = \text{order city $i$ is visited}\]

위의 의사결정변수와 파라미터를 이용하여 총 거리의 합을 최소화하는 정수 계획법은 다음과 같습니다.

\[\begin{split}\begin{align*} & \text{minimize } & & \sum_{i=1}^{n} \sum_{j=1}^{n} c_{ij}x_{ij} \\[1ex] & \text{subject to } & \, & \sum_{i=1}^{n} x_{ij} = 1, & \quad & \forall j = 1, \dots, n\\[1ex] & & \, & \sum_{j=1}^{n} x_{ij} = 1, & \quad & \forall j = 1, \dots, n\\[1ex] & & \, & u_{i} - u_{j} \le N(1-x_{ij})-1 & \quad & \forall i = 2, \dots, n, j=2, \dots, n\\[1ex] \end{align*}\end{split}\]

import os
import sys

# Add the parent directory for importing custom library
sys.path.append('../')

from pulp import *
from ortools.utils import output

n = 5

costs = [
    [100, 4.0, 4.0, 4.7, 5.0],
    [0.0, 1000, 1.3, 2.5, 1.7],
    [0.0, 1.3, 100, 1.0, 1.4],
    [0.0, 2.5, 1.0, 100, 2.0],
    [0.0, 1.7, 1.4, 2.0, 100],
]

prob = LpProblem('Traveling Salesman Problem', LpMinimize)

indexs = [(i, j) for i in range(n) for j in range(n)]

x = LpVariable.dicts('x', indexs, lowBound=0, cat='Binary')

prob += lpSum([costs[i][j]*x[i, j] for i, j in indexs])

for j in range(n):
    prob += lpSum([x[i, j] for i in range(n)]) == 1
    
for i in range(n):
    prob += lpSum([x[i, j] for j in range(n)]) == 1
    
prob.solve()
print(value(prob.objective))

for i in prob.variables():
    if i.varValue == 1:
        print(i.name, '=', i.varValue)

---------------------------------------------------------------------------
ModuleNotFoundError                       Traceback (most recent call last)
Cell In[2], line 1
----> 1 from pulp import *
      2 from ortools.utils import output
      4 n = 5

ModuleNotFoundError: No module named 'pulp'

from pulp import *

# Initialize travelling salesman problem
prob = LpProblem('Travelling Salesman', LpMinimize)

n = len(cities)
indexs = [(i, j) for i in range(n) for j in range(n) if i != j]

# Creating decision variables
x = LpVariable.dicts('x', indexs, cat='Binary')
u = LpVariable.dicts('u', list(range(n)), lowBound=0, upBound=n-1, cat='Continuous')

# Objective function
prob += lpSum([cities[i][j] * x[(i,j)] for i, j in indexs])

# Constraints
for i in range(n):
    prob += lpSum([x[(i,j)] for j in range(n) if i != j]) == 1
    
for j in range(n):
    prob += lpSum([x[(i,j)] for i in range(n) if i != j]) == 1
    
for i in range(1, n):
    for j in range(1, n):
        if i != j:
            prob += u[i] - u[j] + n * x[(i,j)] <= n - 1

# Solve problem
prob.solve()
print(value(prob.objective))

for i in prob.variables():
    if i.name[0] == 'u':
        print(i.name, '=', i.varValue)
    elif i.varValue != 0:
        print(i.name, '=', i.varValue)

---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
<ipython-input-12-eb891054b2dc> in <module>
      4 prob = LpProblem('Travelling Salesman', LpMinimize)
      5 
----> 6 n = len(cities)
      7 indexs = [(i, j) for i in range(n) for j in range(n) if i != j]
      8 

NameError: name 'cities' is not defined

\[\begin{split}x_{ij} = \begin{cases} 1, \; \text{if the edge $(i,j)$ is included in the Hamilton cycle}\\ 0, \; \text{otherwise} \end{cases}\end{split}\]

\[u_{i} = \text{order city $i$ is visited}\]

위의 의사결정변수와 파라미터를 이용하여 총 거리의 합을 최소화하는 정수 계획법은 다음과 같습니다.

\[\begin{split}\begin{align*} & \text{minimize } & & \sum_{i=1}^{n} \sum_{j=1}^{n} c_{ij}x_{ij} \\[1ex] & \text{subject to } & \, & \sum_{i=1}^{n} x_{ij} = 1, & \quad & \forall j = 1, \dots, n\\[1ex] & & \, & \sum_{j=1}^{n} x_{ij} = 1, & \quad & \forall j = 1, \dots, n\\[1ex] & & \, & u_{i} - u_{j} \le N(1-x_{ij})-1 & \quad & \forall i = 2, \dots, n, j=2, \dots, n\\[1ex] \end{align*}\end{split}\]

목적함수는 식(1)과 같습니다. 제약식은 다음과 같습니다. 제약식(2)과 (3)은 각 도시 $j$로 들어오는 도시는 1개가 되어야만 하고 각 도시 $i$에서 출발하는 도시는 1개가 되어야 한다는 걸 나타냅니다. 제약식(3)은 부등식 제약조건(inequality constraints)으로 MTZ 공식입니다. $x_{ij}=1$일 때, $(i,j)$에 대한 두 도시 사이는 순서는 $u_{j} \ge u_{i}$를 뜻합니다. 제약식(4)와 (5)는 의사결정변수 $x_{ij}$는 $0$과 $1$ 값만 가질 수 있는 이진변수이고, $u_{i}$는 $0$보다 크거나 같고 $n-1$보다 작거나 같은 값을 가질 수 있는 변수를 나타냅니다.