차량 경로 문제#

차량 경로 문제(vehicle routing problem, VRP)는 Dantzig and Ramser (1959 )에 의해 제안되었으며 이후 다양한 연구가 진행되어 왔습니다. VRP의 기본 가정은 \(n\)개의 목적지에 \(k\)대 차량이 단일 물류 창고를 중심으로 최소비용 또는 최소거리로 운송할 수 있는 경로를 구하는 문제입니다.

SOVLING A VEHICLE ROUTING PROBLEM#

Mathematical Modeling#

\[\begin{split}x_{ij} = \begin{cases} 1, \; \text{if $i$ is supplied before $j$ by vehicle $k$,}\\ 0, \; \text{otherwise} \end{cases}\end{split}\]

위의 의사결정변수와 파라미터를 이용하여 총 거리의 합을 최소화하는 정수 계획법의 목적함수는 식(1)과 같습니다.

\[\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] & & \, & \sum_{i=1}^{n} x_{i0} = K, & \quad \\[1ex] & & \, & \sum_{j=1}^{n} x_{0j} = K, & \quad \\[1ex] \end{align*}\end{split}\]
from utils import GenerateCities

coords, cities = GenerateCities(100, 100, 10, 42).generate()
cities

---------------------------------------------------------------------------
ModuleNotFoundError                       Traceback (most recent call last)
Cell In[1], line 1
----> 1 from utils import GenerateCities
      3 coords, cities = GenerateCities(100, 100, 10, 42).generate()
      4 cities

ModuleNotFoundError: No module named 'utils'

Mixed Integer Programming using PuLP#

이제 파이썬을 활용하여 외판원 문제의 최적해를 구해보겠습니다. 파이썬을 활용한 경영과학(MS/OR)은 추후 기초부터 포스팅을 할 예정입니다.

from pulp import *

# Initialize vehicle routing problem
prob = LpProblem('Vehicle Routing', LpMinimize)

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

# Creating decision variables
x = LpVariable.dicts('x', indices, 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 indices])

# Constraints
for i in range(n):
    if i != 0:
        prob += lpSum([x[(i,j)] for j in range(n) if i != j]) == 1
    
for j in range(n):
    if j != 0:
        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] + len(cities) * x[(i,j)] <= len(cities) - 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)

296.0
u_1 = 9.0
u_2 = 1.0
u_3 = 3.0
u_4 = 2.0
u_5 = 0.0
u_6 = 4.0
u_7 = 8.0
u_8 = 6.0
u_9 = 7.0
x_(0,_5) = 1.0
x_(1,_0) = 1.0
x_(2,_4) = 1.0
x_(3,_6) = 1.0
x_(4,_3) = 1.0
x_(5,_2) = 1.0
x_(6,_8) = 1.0
x_(7,_1) = 1.0
x_(8,_9) = 1.0
x_(9,_7) = 1.0

CONCLUSION#

차량 경로 문제는

해당 포스트는 지속적으로 업데이트 할 예정이니 오타, 틀린부분, 파이써닉(pythonic)하지 못한 코드가 있을 경우 지적해주시면 수정하도록 하겠습니다.

REFERENCES#

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

  2. Rasmussen, R. (2011). TSP in Spreadsheets–a Guided Tour. International Review of Economics Education, 10(1), 94-116.

  3. Hillier, F. S. & Lieberman, G. J. (2013). Introduction to Operations Research. McGraw-Hill Science, Engineering & Mathematics.

  4. Bello, I., Pham, H., Le, Q. V., Norouzi, M., & Bengio, S. (2016). Neural Combinatorial Optimization with Reinforcement Learning. arXiv preprint arXiv:1611.09940.