조합 최적화 - 일반적인 문제 - 운송 경로 (배송 최적화) 문제

일반적인 문제와 실행 방법

운반 경로 (배송 최적화) 문제

고객 집합 $V=\{0, 1,\dots, n\}$(단 $0$는 루트의 기점이 되는 저장소를 나타낸다)와 운반차 집합 $M=\{1,\dots, m\}$가 주어진다. 각 운반차는 저장소에서 출발하여 할당된 고객 집합을 둘러싸고 배송을 하고 저장소로 돌아온다. 각 고객 $i\in V$에 대한 서비스 수요량은 $a_i(\ge 0)$, 각 운반차 $k\in M$의 최대 적재량은 $u(\ge 0)$이며 고객 $ i$와 고객 $j$ 사이의 이동 비용은 $c_{ij}(\ge 0)$로 한다. 각 고객의 수요는 1대로 1회의 방문으로 채워진다고 한다. 이동 비용이 최소화되도록 모든 운반 차량의 경로를 찾아라.

VRP(Vehicle Routing Problem)라고도 한다.

배송 최적화를 배송 계획과 같이 XX 최적화를 XX 계획이라고 부르는 경우가 많지만, XX 계획은 오래된 호칭이 된다.

실행 방법

usage

Signature: vrp(g, nv, capa, demand='demand', cost='cost', method=None)
Docstring:
運搬経路問題
入力
    g: グラフ(node:demand, edge:cost)
    nv: 運搬車数
    capa: 運搬車容量
    demand: 需要の属性文字
    cost: 費用の属性文字
    method: 計算方法(ex. 'ortools')
出力
    運搬車ごとの頂点対のリスト

파이썬

# CSVデータ
import pandas as pd, networkx as nx
from ortoolpy import vrp, graph_from_table, networkx_draw
tbn = pd.read_csv('data/node1.csv')
tbe = pd.read_csv('data/edge1.csv')
g = graph_from_table(tbn, tbe)[0].to_directed()
networkx_draw(g)
nv, capa = 2, 3 # 車両数、車両容量
print(vrp(g, nv, capa))

결과

[[(0, 3), (2, 0), (3, 5), (5, 2)], [(0, 4), (1, 0), (4, 1)]]

파이썬

# pandas.DataFrame
from ortoolpy.optimization import Vrp
Vrp('data/node1.csv','data/edge1.csv',2,3)

자동차
num
node1
node2
cost




0
0
0
0
3
10


1
0
1
0
2
10


2
0
2
3
5
1


3
0
3
5
2
1


4
1
0
0
4
10


5
1
1
0
1
10


6
1
2
4
1
1



파이썬

# サンプルデータ
import networkx as nx
from ortoolpy import vrp
nc, nv, capa = 5, 2, 3 # 顧客数、車両数、車両容量
g = nx.DiGraph()
g.add_node(0, demand=0)
g.add_nodes_from(range(1, nc + 1), demand=1)
g.add_edges_from([(0, i) for i in range(1, nc + 1)], cost=10)
g.add_edges_from([(i, 0) for i in range(1, nc + 1)], cost=10)
for i, j, t in ((1, 3, 16), (3, 5, 1), (5, 2, 1), (2, 4, 18), (4, 1, 1)):
    g.add_edge(i, j, cost=t)
    g.add_edge(j, i, cost=t)
print(vrp(g, nv, capa))

결과

[[(0, 3), (2, 0), (3, 5), (5, 2)], [(0, 4), (1, 0), (4, 1)]]

Google OR-Tools 솔버를 사용하는 방법

method='ortools' 를 붙이면 Google OR-Tools 의 솔버(근사해법)를 사용합니다.

주의

pip install ortools에서 Google OR-Tools를 설치하십시오.

비용은 정수여야 합니다.

파이썬

print(vrp(g, nv, capa, method='ortools'))

결과

[[(0, 1), (1, 4), (4, 0)], [(0, 2), (2, 5), (5, 3), (3, 0)]]

데이터

data/node1.csv

data/edge1.csv