運搬経路(配送最適化)問題
顧客の集合$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')
出力
運搬車ごとの頂点対のリスト
python
# 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)]]
python
# pandas.DataFrame
from ortoolpy.optimization import Vrp
Vrp('data/node1.csv','data/edge1.csv',2,3)
| car | 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 |
python
# サンプルデータ
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 をインストールしてください。 - コストは整数にしてください。
python
print(vrp(g, nv, capa, method='ortools'))
結果
[[(0, 1), (1, 4), (4, 0)], [(0, 2), (2, 5), (5, 3), (3, 0)]]