配送計画ソルバーとその使用法

METROとは

METRO (MEta Truck Routing Optimizer: 以下METRO)は,配送計画問題に特化した最適化ソルバーである. METROは,配送計画問題に特化したメタヒューリスティクス(metaheuristics)を用いることによって, 大規模な問題に対しても短時間で良好な解を探索することができるように設計されている.

ここでは,配送最適化ソルバーMETRO を,Python言語から直接よび出して求解するためのモジュール vrp_d_1m1_t_model.py の使用法について解説する. このモジュールは,すべてPythonで書かれたクラスで構成されており,ユーザーが書き換え可能である. なお,Pythonのバージョンは3.5以上を仮定する.

METROで扱うのは,ソフト時間枠制約付き時刻依存移動時間・費用配送計画問題であり,以下の仮定を持つ.

  • デポは1つとし,そこに運搬車が時刻 $0$ に待機しているものとする.
  • 総費用は運搬車の移動に関連する費用(移動費用)と顧客への訪問時刻と運搬車の帰還時刻に関連する費用(ペナルティ費用)の和とする.
  • 1つのルートに含まれる顧客の需要量の合計は,運搬車の積載容量を超えない.
  • 運搬車の台数は事前に与えられており,積載容量と帰還時刻に対するペナルティ関数が与えられている.
  • 顧客の集合は事前に与えられており,運搬車が到着時刻する時刻に対するペナルティ関数が与えられている.このペナルティ関数は,時間枠(最早到着時刻と最遅到着時刻の組)を一般化したものであり,到着時刻に対する任意の区分的線形関数として与える.
  • 点(デポと顧客の総称)間には,移動時間ならびに移動費用を表す関数が与えられている.移動時間と移動費用も任意の区分的線形関数とする.

METROのPythonモジュールにおける基本クラスには,以下のものがある.

  • モデル Model
  • 顧客 Customer
  • 運搬車 Vehicle
  • 区分的線形関数 Piecewise
  • 枝 Edge

このモジュールには,無限大を表す定数としてInf ($=1000000.0$)が定義されているので, モデルの記述で大きな数を表す際には,Infと記述することが可能になる.

準備

描画には、以下のパッケージが必要(pipでインストール可能)

実行ファイルvrp_d_1m1_t-Macはダウンロード後に

chmod +x vrp_d_1m1_t-Mac

と実行パーミッションを追加

地図の利用にはmapboxのtokenが必要 https://www.mapbox.com/

区分的線形関数クラス

区分的線形関数のクラスのコンストラクタの引数は以下の通り.

  • nameは区分的線形関数の名前であり,文字列で与える.
  • xは,区分的線形関数の $x$座標のリストを表す非負の整数のリストである.なお,$x$ 座標は単調増加な値をもつことを仮定しており, この条件を破っている場合には,TypeError が発生する.同じ数が2つ続くことも許さないことに注意されたい.
  • yは,区分的線形関数の $y$座標のリストを表す非負の整数(浮動小数点数)のリストである.リストxと長さが異なる場合には,TypeErrorが発生する.

リストxの最初の要素が $0$ より大きい場合には,[0,x[0]]の区間の値は無限大と設定される.

コンストラクタで入力された区分的線形関数の情報は,segment属性に保管されている.これは,

(区分を表すデータ) = (左端点) (右端点) (傾き) (切片)

のリストであり,print関数の返値もこの情報である.

また,区分的線形関数クラスには,確認用に関数をmatplotlibで描画するメソッドdrawGraphが準備されている.

class Piecewise[source]

Piecewise(name='', x=None, y=None)

Piecewise linear function class. Domain [0,1000000.0]

Piecewiseクラスの使用例

f=Piecewise(x=[6,10,20,25],y=[5,0,0,6])
print(f.segment)
f.drawGraph()
[('0', '6', '0.0', '1000000.0'), ('6', '10', '-1.25', '12.5'), ('10', '20', '0.0', '0.0'), ('20', '25', '1.2', '-24.0'), ('25', '1000000.0', '0.0', '1000000.0')]
f=Piecewise(x=[10,11,12,13],y=[0,0,1,1])
print(f)
f.drawGraph()
5 0 10 0.0 1000000.0 10 11 0.0 0.0 11 12 1.0 -11.0 12 13 0.0 1.0 13 1000000.0 0.0 1000000.0

時間枠クラス

時間枠クラスTimeWindowsのコンストラクタの引数は timewindow であり,種類によって以下の意味をもつ.

  • 整数もしくは浮動小数点数:納期を表す.その時刻までは0,それ以降だと無限大になる区分的線形関数を定義する.
  • 2つ組のタプル (x1,x2): 時間枠 [x1,x2]
  • 4つ組のタプル x1,x2,a1,a2): 早着違反係数がa1,遅延違反係数a2のソフトな時間枠[x1,x2]
  • 区分的線形関数クラス Piecewiseのインスタンス
  • None: 時間枠制約なし

時間枠クラスTimeWindowsのpiecewise属性は,時間枠を表す区分的線形関数を保持する.

class TimeWindow[source]

TimeWindow(timewindow)

時間枠を区分線形関数で表現する

Attributes

piecewise : Piecewise 区分線形関数

Example

t = TimeWindow((3,5,1,10)) t.piecewise.drawGraph()

TimeWindowクラスの使用例

tw1 = TimeWindow(10)
print(tw1)
tw1.piecewise.drawGraph()
2 0 10 0.0 0.0 10 1000000.0 0.0 1000000.0
tw1 = TimeWindow((10,50))
print(tw1)
tw1.piecewise.drawGraph()
3 0 10 0.0 1000000.0 10 50 0.0 0.0 50 1000000.0 0.0 1000000.0
tw1 = TimeWindow(Piecewise(x=[1,2,3,4],y=[10,1,0,10]))
print(tw1)
tw1.piecewise.drawGraph()
5 0 1 0.0 1000000.0 1 2 -9.0 19.0 2 3 -1.0 3.0 3 4 10.0 -30.0 4 1000000.0 0.0 1000000.0

準備に必要なクラス

class CustomerFreight[source]

CustomerFreight(*args)

class VehicleFreight[source]

VehicleFreight(**kwargs)

class CustomerTimeCost[source]

CustomerTimeCost(**kwargs)

枝の時間・費用クラス

class EdgeTimeCost[source]

EdgeTimeCost(traveltime, travelcost)

運搬車の時間・費用クラス

class VehicleTimeCost[source]

VehicleTimeCost(**kwargs)

距離クラス

class VehicleDistance[source]

VehicleDistance(**kwargs)

顧客クラス

顧客クラスのコンストラクタの引数の名前と意味は以下の通り.

  • nameは顧客の名前を文字列もしくは非負の整数値で与える.なお,内部表現は文字列であるので,非負の整数値を与えた場合には,自動的に文字列に変換される. 同じ名前を与えた場合には,前に入力したものの上に上書きされる.また,名前を省略した場合には,自動的に通し番号を表す名前が付けられる.

  • demandは,顧客の荷量を表す量を整数もしくは浮動小数点数のタプルとして与える. 既定値は $(0,)$ である(タプルであることに注意). demandの要素は負の値を許し,正の値は顧客上での荷物の積み込み(pickup), 負の値は荷物の積み降ろし(delivery)を表す.

  • timewindowは,顧客への到着時刻に対する時間枠をあたえる. 最早到着時刻と最遅到着時刻の組(非負の整数もしくは浮動小数点数のタプル)で与えたときには,時間枠を表す区分的線形関数になる. また,最早到着時刻,最遅到着時刻,最早時刻より前の到着ペナルティ,最遅時刻より後の到着のペナルティの4つ組として入力することもできる. 一般的には,区分的線形関数(piecewise linear function:後述)で到着時刻に対するペナルティを定義することができる. 規定値は None であり,これは時間枠がないことを表す.

  • servicetimeは,顧客上でのサービス時間を非負の整数で与える.既定値は$0$である.

顧客クラスのstat属性は,最適化された顧客の情報を保持する.

class Customer_[source]

Customer_(name, **kwargs)

客オブジェクトを生成するクラス

Attributes

stat : dictionary 得られた解での客の情報

class Customer[source]

Customer(name, **kwargs) :: Customer_

客オブジェクトを生成するクラス

Attributes

stat : dictionary 得られた解での客の情報

Customer.__init__[source]

Customer.__init__(name, **kwargs)

Parameters

name : str 客の名前

kwargs : dictionary

- "demand" : tuple, default (0,)
    客の需要量(多次元も可能).正の値は集荷,負の値は配達.

- "timewindow" : int,float,tuple,Piecewise,default None
    客の時間枠

- "servicetime" : int, default 0
    客でのサービス時間

Customerクラスの使用例

c1 = Customer("Customer1", demand = (5,), timewindow=(10,30), servicetime = 10 )
print(c1)
Customer Customer1: {'demand': (5,), 'timewindow': (10, 30), 'servicetime': 10}

枝クラス

枝クラスのコンストラクタの引数は以下の通り.

  • nfrom は枝の始点を表す点の名前を文字列もしくは非負の整数値で与える.デポを表す場合には文字列"depot"で与える.
  • ntoは枝の終点を表す点の名前を文字列もしくは非負の整数値で与える.デポを表す場合には文字列"depot"で与える.
  • distanceは,地点間の移動距離を与える.
  • traveltime,travelcostは,それぞれ移動時間,移動費用を表す数値もしくは,区分的線形関数を与える. 注意: 移動時間はFIFO(first-in first-out)性をもつ必要がある. 言い換えれば,後から出発した運搬車が先に出発した運搬車を追い越してしまうような移動時間を設定することは禁止されている(解を得ることができない).

class Edge_[source]

Edge_(nfrom, nto, **kwargs)

枝オブジェクトを生成するクラス

class Edge[source]

Edge(nfrom, nto, distance, traveltime, travelcost=None) :: Edge_

枝オブジェクトを生成するクラス

Edge.__init__[source]

Edge.__init__(nfrom, nto, distance, traveltime, travelcost=None)

Parameters

  • distance : float
  • traveltime : int,float,Piecewise
  • travelcost : int,float,Piecewise,None,default None

Edgeクラスの使用例

e1  = Edge("depot", "Customer1", 10., 3, 1000)
print(e1)
Edge ('depot', 'Customer1'): {'distance': 10.0, 'traveltime': 3, 'travelcost': 1000}

運搬車クラス

運搬車クラスのコンストラクタの引数は以下の通り.

  • nameは運搬車の名前を文字列で与える. 同じ名前を与えた場合には,前に入力したものの上に上書きされる.また,名前を省略した場合には,自動的に通し番号を表す名前が付けられる.

  • capacityは資源の容量(使用可能量の上限)を整数もしくは浮動小数点数のタプルで与える. リストで与える場合には,顧客インスタンスのdemandと同じ長さのリストにする必要がある. 長さが異なるリストの場合にはエラーになる.

  • timewindowは,運搬車のデポへの帰還時刻に対する時間枠を与える. 最早到着時刻と最遅到着時刻の組(非負の整数もしくは浮動小数点数のタプル)で与えたときには,時間枠を表す区分的線形関数になる. また,最早到着時刻,最遅到着時刻,最早時刻より前の到着ペナルティ,最遅時刻より後の到着のペナルティの4つ組として入力することもできる. 一般的には,区分的線形関数(piecewise linear function:後述)で到着時刻に対するペナルティを定義することができる. 規定値は None であり,これは時間枠がないことを表す.

  • maxdistanceは最大走行距離であり,既定値は10000000である.

運搬車クラスのrouting属性は,最適化されたルートに含まれる点のリスト(最初と最後は"depot")である.

class Vehicle_[source]

Vehicle_(name, **kwargs)

車両オブジェクトを生成するクラス

Attributes

routing : list 得られた巡回路 consumed : dictionary 得られた巡回路の情報

class Vehicle[source]

Vehicle(name, **kwargs) :: Vehicle_

車両オブジェクトを生成するクラス

Attributes

routing : list 得られた巡回路 consumed : dictionary 得られた巡回路の情報

Vehicle.__init__[source]

Vehicle.__init__(name, **kwargs)

Parameters

name : str 客の名前 kwargs : dictionary

  • "capacity" : tuple 車両の容量
  • "timewindow" : int,float,tuple,Piecewise,default None デポへの帰還時刻に対する時間枠
  • "max_distance" : float,default 10000000 車両の最大移動距離
  • "dummy" : boolean,default False prize機能におけるダミーの車両か否か

Vehicleクラスの使用例

v1 =Vehicle("Vehicle 1", capacity=(5,100), timwwindow=(100,200), max_distance=1000)
print(v1)
Vehicle Vehicle 1: {'capacity': (5, 100), 'timwwindow': (100, 200), 'max_distance': 1000}

ソルバークラス

class Solver[source]

Solver(**kwargs)

モデルクラス

  • optimizeはモデルの最適化を行う.返値は総費用と結果の状態(Status)である.
状態の定数 説明
0 最適化成功
1 求解中にユーザがCtrl-Cを入力したことによって強制終了した.
2 初期解ファイルの読み込みに失敗した.
3 ログファイルの書き込みに失敗した.
4 入力データの書式にエラーがある.
5 メモリの確保に失敗した.
6 実行ファイルのよび出しに失敗した.
7 スケジュールが決定できない.(移動費用がFIFO性を満たしていないことや,ペナルティが大きすぎて実行可能解が見つからないことが原因である.)
8 出力用のファイルを開けない.
9 モデルの入力は完了しているが,まだ最適化されていない.
負の値 その他のエラー

optimizeの引数は以下の通り.

  • RandomSeedは乱数系列の種を設定する.既定値は0.
  • TimeLimitは最大計算時間 (秒) を設定する.既定値は 5秒.
  • IterLimitは反復回数の上限を設定する. 既定値は 100.
  • InitSolは,前回最適化の探索を行った際の最良解を初期値とした探索を開始したいときのファイル名を与える.
  • Verboseは,詳細な出力を出したいときTrueに設定する.既定値はFalse.
  • Solcsvは,解を出力するファイル名を指定する.既定値は"vrp_solution.csv”.

モデルインスタンスは以下の属性をもつ.

  • customersは,モデルに含まれる顧客名をキー,顧客インスタンスを値とした辞書である.
  • vehiclesは,モデルに含まれる運搬車名をキー,運搬車資源インスタンスを値とした辞書である.
  • customersLは,顧客インスタンスのリストである.
  • vehiclesLは,運搬車インスタンスのリストである.

class Model_[source]

Model_(name=None, resources=None)

配送計画モデルクラス

Parameters

name : str モデルの名前 resources : tuple 使用する機能

Model_.optimize[source]

Model_.optimize(**kwargs)

最適化ソルバの実行

Parameters

kwargs : dictionary

  • "TimeLimit" : int タイムリミット(秒)
  • "RandomSeed" : int 乱数の種
  • "IterLimit" : int 局所探索法の最大実行回数
  • "InitSol" : str 初期解を与える場合,そのファイル名
  • "OutputFlag" : boolean
  • "Solcsv" : str
  • "Verbose" : boolean 詳細な出力をするか否か
  • "TwoOpt" : 0,1
  • "NCross" : int
  • "Logfile" : str ログファイルの名前

class Model[source]

Model(name) :: Model_

配送計画モデルクラス

Parameters

name : str モデルの名前 resources : tuple 使用する機能

例題1 ランダムな点

使用可能な機能:距離,容量制約1M1, 時間枠

n=50 #客数

import random
random.seed(1)

C={} # 客の座標を保存する辞書
TW={} # 客の時間枠を保存する辞書
demand={} # 客の要求量(正の値は集荷,負の値は配達)
S={} # 客のサービス時間

TW2={}

for i in range(n):
    name="c"+str(i)
    x=random.randint(-500,500)
    y=random.randint(-500,500)
    C[name]=(x,y)
    e= random.randint(0,3000)
    l=e+random.randint(0,4000-e)
    TW[name]=(e,l)
    
    #e=random.randint(0,3000)
    #l=e #+random.randint(0,4000-e)
    
    #TW2[name]=(e,l)
        
    if random.randint(0,1) == 0:
        demand[name]=random.randint(1,5)
    else:
        demand[name]=random.randint(-5,-1)
    S[name]=random.randint(10,20)
TW["c1"] = (0,1)
C["depot"]=(0,0)
#print("Customer",C)
#print("Time Window",TW)
#print("Demand",demand)
#print("Service Time",S)

#距離計算用
def distance(t1,t2):
    return ((t1[0]-t2[0])**2+(t1[1]-t2[1])**2)**(0.5)

## 車両数と容量の設定
m=7 # number of vehicles
capacity=30 # capacity of vehicle


model = Model("example-vrp_d_1m1_tw") # モデルインスタンスの生成

# 客インスタンスの生成
for i in C:
    if i == "depot":
        continue
    model += Customer(i,demand=(demand[i],random.randint(0,1)),timewindow=TW[i],servicetime=S[i])

    #model += Customer(i,demand=(demand[i],),timewindow=TW2[i],servicetime=S[i])

# 車両インスタンスの生成
for k in range(m):
    if k >= int(m/2):
        model += Vehicle("v"+str(k),capacity=(capacity/10,0))
    else:
        model += Vehicle("v"+str(k),capacity=(capacity/10,n))
# 枝インスタンスの生成
for i in C:
    for j in C:
        if i!=j:
            dist = time = distance(C[i],C[j])
            model += Edge(i,j,dist,time)

# 最適化の実行
obj, status=model.optimize(IterLimit=1000,TimeLimit=2,Verbose=True,OutputFlag=False)
print("obj=",obj, "Status=",status)
# 得られた解の表示
try:
    for v in model.vehiclesL:
        print()
        print(v)
        print(list(map(lambda x:x.name,v.routing[1:-1])))    
except:
    print("route is None!")
    pass
Status= 0
Feasbiel solution is not found
obj= 1010820.67 Status= 0

Vehicle v0: {'capacity': (3.0, 50)}
2091.292251 = {'distance': 2076.292251, 'freight_1M1': 15.0, 'timecost': 0.0}
['c46', 'c35', 'c7', 'c14', 'c36', 'c23', 'c47', 'c20', 'c28', 'c32']

Vehicle v1: {'capacity': (3.0, 50)}
2323.254083 = {'distance': 2293.254083, 'freight_1M1': 30.0, 'timecost': 0.0}
['c45', 'c16', 'c5', 'c17', 'c21', 'c19', 'c9', 'c27', 'c48', 'c42', 'c38']

Vehicle v2: {'capacity': (3.0, 50)}
1393.401063 = {'distance': 1377.401063, 'freight_1M1': 16.0, 'timecost': 0.0}
['c6', 'c29', 'c39', 'c25', 'c40', 'c13', 'c11']

Vehicle v3: {'capacity': (3.0, 0)}
1001812.41398 = {'distance': 1786.41398, 'freight_1M1': 26.0, 'timecost': 1000000.0}
['c1', 'c49', 'c3', 'c24', 'c8', 'c30', 'c2', 'c37', 'c44', 'c10', 'c12']

Vehicle v4: {'capacity': (3.0, 0)}
269.37988 = {'distance': 267.37988, 'freight_1M1': 2.0, 'timecost': 0.0}
['c15']

Vehicle v5: {'capacity': (3.0, 0)}
2422.466665 = {'distance': 2406.466665, 'freight_1M1': 16.0, 'timecost': 0.0}
['c0', 'c31', 'c26', 'c33', 'c43', 'c41', 'c4']

Vehicle v6: {'capacity': (3.0, 0)}
508.462998 = {'distance': 504.462998, 'freight_1M1': 4.0, 'timecost': 0.0}
['c34', 'c22', 'c18']

得られた解の描画

import networkx as nx
import matplotlib.pyplot as plt
G=nx.DiGraph()
for v in model.vehiclesL:
   prev=None
   for j in v.routing[1:-1]:
       if prev == None:                
           G.add_edge("depot",j.name)
       else:
           G.add_edge(prev.name,j.name)
       prev= j 
   G.add_edge(prev.name,"depot")
    
fig=plt.figure(figsize=(9,9))    
nx.draw_networkx(G,pos=C,nodelist=[i for i in G.nodes() if i != "depot"],node_color="yellow",node_size=50,with_labels=True,edge_color="k",width=1)
nx.draw_networkx(G,pos=C,nodelist=["depot"],node_color="blue",node_shape='s',alpha=0.5,node_size=50,with_labels=True,edge_color="k",width=1)
plt.show()

得られた解の詳細な情報

for v in model.vehiclesL:
   print()
   print(v)
   keys=v.routing[1].stat.keys()
   print("customer,",", ".join(keys))
   for c in v.routing[1:-1]:
       print(c.name+", ",c.data["demand"],",",end="")
       for k in keys:
           print(c.stat[k],end=",")
       print()
Vehicle v0: {'capacity': (3.0, 50)}
2091.292251 = {'distance': 2076.292251, 'freight_1M1': 15.0, 'timecost': 0.0}
customer, distance, freight_1M1_0, freight_1M1_1, arrival, service, departure, timecost, travelcost
c46,  (-1, 1) ,435.000000,-1.000000,1.000000,435.000000,872.000000,890.000000,0.000000,0.000000,
c35,  (3, 1) ,939.286625,3.000000,1.000000,1394.286625,1394.286625,1408.286625,0.000000,0.000000,
c7,  (2, 0) ,997.424392,2.000000,0.000000,1466.424392,1704.000000,1724.000000,0.000000,0.000000,
c14,  (-1, 1) ,1195.585943,-1.000000,1.000000,1922.161550,1922.161550,1941.161550,0.000000,0.000000,
c36,  (1, 1) ,1328.043483,1.000000,1.000000,2073.619091,2073.619091,2091.619091,0.000000,0.000000,
c23,  (1, 0) ,1423.819263,1.000000,0.000000,2187.394870,2602.000000,2620.000000,0.000000,0.000000,
c47,  (-5, 1) ,1469.862720,-5.000000,1.000000,2666.043458,2666.043458,2680.043458,0.000000,0.000000,
c20,  (5, 0) ,1585.556281,5.000000,0.000000,2795.737018,2795.737018,2811.737018,0.000000,0.000000,
c28,  (1, 0) ,1762.126381,1.000000,0.000000,2988.307118,2988.307118,3002.307118,0.000000,0.000000,
c32,  (5, 0) ,1872.008135,5.000000,0.000000,3112.188873,3112.188873,3129.188873,0.000000,0.000000,

Vehicle v1: {'capacity': (3.0, 50)}
2323.254083 = {'distance': 2293.254083, 'freight_1M1': 30.0, 'timecost': 0.0}
customer, distance, freight_1M1_0, freight_1M1_1, arrival, service, departure, timecost, travelcost
c45,  (2, 0) ,496.910455,2.000000,0.000000,496.910455,496.910455,508.910455,0.000000,0.000000,
c16,  (4, 0) ,568.499560,4.000000,0.000000,580.499560,817.000000,835.000000,0.000000,0.000000,
c5,  (4, 1) ,859.858445,4.000000,1.000000,1126.358885,1728.000000,1745.000000,0.000000,0.000000,
c17,  (-3, 1) ,991.956893,-3.000000,1.000000,1877.098448,2366.000000,2386.000000,0.000000,0.000000,
c21,  (-5, 1) ,1194.897771,-5.000000,1.000000,2588.940878,2588.940878,2606.940878,0.000000,0.000000,
c19,  (-5, 0) ,1245.107332,-5.000000,0.000000,2657.150439,2657.150439,2674.150439,0.000000,0.000000,
c9,  (-3, 1) ,1299.448845,-3.000000,1.000000,2728.491952,2745.000000,2764.000000,0.000000,0.000000,
c27,  (-3, 0) ,1426.200571,-3.000000,0.000000,2890.751726,2890.751726,2907.751726,0.000000,0.000000,
c48,  (-4, 1) ,1738.283893,-4.000000,1.000000,3219.835048,3219.835048,3238.835048,0.000000,0.000000,
c42,  (3, 1) ,1774.684442,3.000000,1.000000,3275.235597,3275.235597,3291.235597,0.000000,0.000000,
c38,  (4, 1) ,1817.823752,4.000000,1.000000,3334.374907,3334.374907,3347.374907,0.000000,0.000000,

Vehicle v2: {'capacity': (3.0, 50)}
1393.401063 = {'distance': 1377.401063, 'freight_1M1': 16.0, 'timecost': 0.0}
customer, distance, freight_1M1_0, freight_1M1_1, arrival, service, departure, timecost, travelcost
c6,  (4, 0) ,270.185122,4.000000,0.000000,270.185122,1415.000000,1429.000000,0.000000,0.000000,
c29,  (-5, 1) ,475.148533,-5.000000,1.000000,1633.963411,1724.000000,1738.000000,0.000000,0.000000,
c39,  (-1, 1) ,728.328311,-1.000000,1.000000,1991.179778,1991.179778,2004.179778,0.000000,0.000000,
c25,  (-5, 0) ,867.011403,-5.000000,0.000000,2142.862870,2142.862870,2161.862870,0.000000,0.000000,
c40,  (-1, 0) ,967.733794,-1.000000,0.000000,2262.585261,2727.000000,2744.000000,0.000000,0.000000,
c13,  (-3, 1) ,984.226216,-3.000000,1.000000,2760.492423,2760.492423,2777.492423,0.000000,0.000000,
c11,  (3, 1) ,1125.240400,3.000000,1.000000,2918.506606,2918.506606,2936.506606,0.000000,0.000000,

Vehicle v3: {'capacity': (3.0, 0)}
1001812.41398 = {'distance': 1786.41398, 'freight_1M1': 26.0, 'timecost': 1000000.0}
customer, distance, freight_1M1_0, freight_1M1_1, arrival, service, departure, timecost, travelcost
c1,  (4, 0) ,167.863039,4.000000,0.000000,167.863039,167.863039,177.863039,1000000.000000,0.000000,
c49,  (4, 1) ,313.472105,4.000000,1.000000,323.472105,427.000000,438.000000,0.000000,0.000000,
c3,  (3, 1) ,490.573771,3.000000,1.000000,615.101666,937.000000,947.000000,0.000000,0.000000,
c24,  (1, 0) ,583.223649,1.000000,0.000000,1039.649879,1045.000000,1055.000000,0.000000,0.000000,
c8,  (-1, 0) ,658.761719,-1.000000,0.000000,1130.538070,1214.000000,1230.000000,0.000000,0.000000,
c30,  (-5, 0) ,882.567439,-5.000000,0.000000,1453.805719,2089.000000,2102.000000,0.000000,0.000000,
c2,  (4, 0) ,990.794053,4.000000,0.000000,2210.226614,2210.226614,2224.226614,0.000000,0.000000,
c37,  (5, 1) ,1012.007256,5.000000,1.000000,2245.439818,2245.439818,2262.439818,0.000000,0.000000,
c44,  (-1, 0) ,1061.585477,-1.000000,0.000000,2312.018039,2814.000000,2827.000000,0.000000,0.000000,
c10,  (-1, 1) ,1121.585477,-1.000000,1.000000,2887.000000,2887.000000,2897.000000,0.000000,0.000000,
c12,  (4, 0) ,1327.752885,4.000000,0.000000,3103.167408,3103.167408,3123.167408,0.000000,0.000000,

Vehicle v4: {'capacity': (3.0, 0)}
269.37988 = {'distance': 267.37988, 'freight_1M1': 2.0, 'timecost': 0.0}
customer, distance, freight_1M1_0, freight_1M1_1, arrival, service, departure, timecost, travelcost
c15,  (5, 0) ,133.689940,5.000000,0.000000,133.689940,2650.000000,2663.000000,0.000000,0.000000,

Vehicle v5: {'capacity': (3.0, 0)}
2422.466665 = {'distance': 2406.466665, 'freight_1M1': 16.0, 'timecost': 0.0}
customer, distance, freight_1M1_0, freight_1M1_1, arrival, service, departure, timecost, travelcost
c0,  (4, 1) ,372.146477,4.000000,1.000000,372.146477,372.146477,389.146477,0.000000,0.000000,
c31,  (4, 0) ,584.601178,4.000000,0.000000,601.601178,601.601178,619.601178,0.000000,0.000000,
c26,  (2, 1) ,763.924907,2.000000,1.000000,798.924907,1189.000000,1203.000000,0.000000,0.000000,
c33,  (-1, 0) ,952.012653,-1.000000,0.000000,1391.087745,2656.000000,2671.000000,0.000000,0.000000,
c43,  (-1, 0) ,1216.201979,-1.000000,0.000000,2935.189326,2935.189326,2950.189326,0.000000,0.000000,
c41,  (-5, 0) ,1426.254353,-5.000000,0.000000,3160.241700,3160.241700,3172.241700,0.000000,0.000000,
c4,  (4, 0) ,1733.295067,4.000000,0.000000,3479.282414,3479.282414,3499.282414,0.000000,0.000000,

Vehicle v6: {'capacity': (3.0, 0)}
508.462998 = {'distance': 504.462998, 'freight_1M1': 4.0, 'timecost': 0.0}
customer, distance, freight_1M1_0, freight_1M1_1, arrival, service, departure, timecost, travelcost
c34,  (-4, 1) ,227.905682,-4.000000,1.000000,227.905682,1746.000000,1759.000000,0.000000,0.000000,
c22,  (-1, 0) ,350.167696,-1.000000,0.000000,1881.262014,2508.000000,2518.000000,0.000000,0.000000,
c18,  (-1, 0) ,367.167696,-1.000000,0.000000,2535.000000,2987.000000,2999.000000,0.000000,0.000000,

例題2 格子点(時間枠の設定)

"""
example 2
     - 格子座標上の5点  A(1, 1), B(1, 4), C(2, 0), D(2, 2), E(4, 4) および デポ(0, 0) の問題
     - 車両数は2台 それぞれ容量が10とする.
     - 作業時間(荷役時間等)にかかる時間は2とする.
     - 移動時間と移動コストは距離に等しいものとする.

         - 顧客の需要,時間枠制約は以下の通り

            需要   時間枠制約    
         A:   10   (0, 5)                              # 0 から 5 の間に運ばなければならない
         B:    5   (5, 9, 1, 2)                        # 5 から 9 の間はコスト0, それ以前に到着した場合は傾き1に比例したコスト,それ以後は傾き2に比例したコストがかかる
         C:    3   Piecewise(x=[0,10,Inf],y=[5,0,0])   # 10 以後はコスト0, それ以前は早く到着した分に比例してコストがかかる
         D:    2   None                                # 制約なし
         E:    1   None                                # 制約なし

     - 求解時間は10秒とする.
"""

C = {"A":(1, 1), "B":(1, 4), "C":(2, 0), "D":(2, 2), "E":(4, 4)}    #顧客の座標
D = {"A":10, "B":5, "C":3, "D":2, "E":1}    #顧客の需要
TW= {"A":(0,5), "B":(5,9,1,2), "C":Piecewise(x=[0,10,Inf],y=[5,0,0]), "D":None, "E":None}   #顧客の時間枠制約
Depot = (0,0)   #デポの座標

#マンハッタン距離(格子座標上の距離)を計算する関数
def distance(t1,t2):
    return abs(t1[0]-t2[0])+abs(t1[1]-t2[1])

#モデルインスタンスの作成
model = Model("sample2")

#車両の追加(name:"v1", capa:10)
model += Vehicle("v1",capacity = (10,),timewindow=(0,15),max_distance=30 )
#model += Vehicle("v2",capacity = (10,),timewindow=(0,15),max_distance=30  ) #ルートが得られない!
model += Vehicle("v2",capacity = (10,),timewindow=(0,25),max_distance=30  )
#model += Vehicle("dummy", capacity=(0,), dummy = True) #prize機能?

#顧客の追加 (name:i, demand:D[i], timewindow:TW[i], servicetime:2)
for i in C:
    model +=  Customer(i,demand = (D[i],), timewindow= TW[i], servicetime= 2)

#距離時間テーブルの作成
for i in C:
    dist = time = distance(Depot,C[i])
    model += Edge("depot",i,dist,time)  
    model += Edge(i,"depot",dist,time)
    for j in C:
        if i!=j:
            dist = time = distance(C[i],C[j])   
            model += Edge(i,j,dist,time)

# 最適化の実行
obj, status=model.optimize(IterLimit=1000,TimeLimit=1,Verbose=True,OutputFlag=False,Solcsv="vrp_solution.csv")
print("obj=",obj, "Status=",status)
# 得られた解の表示
try:
    for v in model.vehiclesL:
        print()
        print(v)
        print(list(map(lambda x:x.name,v.routing[1:-1])))    
except:
    print("route is None!")
    pass

for v in model.vehiclesL:
   print()
   print(v)
   keys=v.routing[1].stat.keys()
   print("customer,",", ".join(keys))
   for c in v.routing[1:-1]:
       print(c.name+", ",c.data["demand"],",",end="")
       for k in keys:
           print(c.stat[k],end=",")
       print()
Status= 0
Feasbiel solution is not found
obj= 21.0 Status= 0

Vehicle v1: {'capacity': (10,), 'timewindow': (0, 15), 'max_distance': 30}
4.0 = {'distance': 4.0, 'freight_1M1': 0.0, 'timecost': 0.0}
['A']

Vehicle v2: {'capacity': (10,), 'timewindow': (0, 25), 'max_distance': 30}
17.0 = {'distance': 16.0, 'freight_1M1': 1.0, 'timecost': 0.0}
['B', 'E', 'D', 'C']

Vehicle v1: {'capacity': (10,), 'timewindow': (0, 15), 'max_distance': 30}
4.0 = {'distance': 4.0, 'freight_1M1': 0.0, 'timecost': 0.0}
customer, distance, freight_1M1_0, arrival, service, departure, timecost, travelcost
A,  (10,) ,2.000000,10.000000,2.000000,2.000000,4.000000,0.000000,0.000000,

Vehicle v2: {'capacity': (10,), 'timewindow': (0, 25), 'max_distance': 30}
17.0 = {'distance': 16.0, 'freight_1M1': 1.0, 'timecost': 0.0}
customer, distance, freight_1M1_0, arrival, service, departure, timecost, travelcost
B,  (5,) ,5.000000,5.000000,5.000000,5.000000,7.000000,0.000000,0.000000,
E,  (1,) ,8.000000,1.000000,10.000000,10.000000,12.000000,0.000000,0.000000,
D,  (2,) ,12.000000,2.000000,16.000000,16.000000,18.000000,0.000000,0.000000,
C,  (3,) ,14.000000,3.000000,20.000000,20.000000,22.000000,0.000000,0.000000,
C["depot"] =(0,0)
G=nx.DiGraph()
for v in model.vehiclesL:
   prev=None
   for j in v.routing[1:-1]:
       if prev == None:                
           G.add_edge("depot",j.name)
       else:
           G.add_edge(prev.name,j.name)
       prev= j 
   G.add_edge(prev.name,"depot")
    
fig=plt.figure(figsize=(9,9))    
nx.draw_networkx(G,pos=C,nodelist=[i for i in G.nodes() if i != "depot"],node_color="yellow",node_size=50,with_labels=True,edge_color="k",width=1)
nx.draw_networkx(G,pos=C,nodelist=["depot"],node_color="blue",node_shape='s',alpha=0.5,node_size=50,with_labels=True,edge_color="k",width=1)
plt.show()

例題3 デポ発着の積み込みと積み降ろし

需要量が正の場合には積み込み(pickup),負の場合には積み降ろし(delivery)になる.

"""
example 3
     - 格子座標上の5点  A(1, 1), B(1, 4), C(2, 0), D(2, 2), E(4, 4) および デポ(0, 0) の問題
     - 車両数は2台 それぞれ容量が100とする.
     - 作業時間(荷役時間等)にかかる時間は2とする.
     - 移動時間と移動コストは距離に等しいものとする.

         - 顧客の需要,時間枠制約は以下の通り

            需要   時間枠制約    
         A:   10   (0, 5)                              # 0 から 5 の間に運ばなければならない
         B:    5   (5, 9, 1, 2)                        # 5 から 9 の間はコスト0, それ以前に到着した場合は傾き1に比例したコスト,それ以後は傾き2に比例したコストがかかる
         C:    3   none                                # 制約なし
         D:    2   None                                #制約なし
         E:    1   None                                #制約なし

     - 求解時間は10秒とする.
"""

C = {"A":(1, 1), "B":(1, 4), "C":(2, 0), "D":(2, 2), "E":(4, 4)}    #顧客の座標
D = {"A":100, "B":80, "C":20, "D":-20, "E":-80}    #顧客の需要
TW= {"A":(0,5), "B":(5,9,1,2), "C":None, "D":None, "E":None}   #顧客の時間枠制約
Depot = (0,0)   #デポの座標

#マンハッタン距離(格子座標上の距離)を計算する関数
def distance(t1,t2):
    return abs(t1[0]-t2[0])+abs(t1[1]-t2[1])

#モデルインスタンスの作成
model = Model("sample2")

#車両の追加(name:"v1", capa:10)
model += Vehicle("v1",capacity = (100,) )

model += Vehicle("v2",capacity = (100,) )
#model += Vehicle("dummy", capacity=(0,), dummy = True) #prize機能?

#顧客の追加 (name:i, demand:D[i], timewindow:TW[i], servicetime:2)
for i in C:
    model +=  Customer(i,demand = (D[i],), timewindow= TW[i], servicetime= 2)

#距離時間テーブルの作成
for i in C:
    dist = time = distance(Depot,C[i])
    model += Edge("depot",i,dist,time)  
    model += Edge(i,"depot",dist,time)
    for j in C:
        if i!=j:
            dist = time = distance(C[i],C[j])   
            model += Edge(i,j,dist,time)

# 最適化の実行
obj, status=model.optimize(IterLimit=1000,TimeLimit=1,Verbose=True,OutputFlag=False)
print("obj=",obj, "Status=",status)
# 得られた解の表示
try:
    for v in model.vehiclesL:
        print()
        print(v)
        print(list(map(lambda x:x.name,v.routing[1:-1])))    
except:
    print("route is None!")
    pass

for v in model.vehiclesL:
   print()
   print(v)
   keys=v.routing[1].stat.keys()
   print("customer,",", ".join(keys))
   for c in v.routing[1:-1]:
       print(c.name+", ",c.data["demand"],",",end="")
       for k in keys:
           print(c.stat[k],end=",")
       print()
Status= 0
Feasbiel solution is not found
obj= 30.0 Status= 0

Vehicle v1: {'capacity': (100,)}
26.0 = {'distance': 18.0, 'freight_1M1': 0.0, 'timecost': 8.0}
['E', 'B', 'D', 'C']

Vehicle v2: {'capacity': (100,)}
4.0 = {'distance': 4.0, 'freight_1M1': 0.0, 'timecost': 0.0}
['A']

Vehicle v1: {'capacity': (100,)}
26.0 = {'distance': 18.0, 'freight_1M1': 0.0, 'timecost': 8.0}
customer, distance, freight_1M1_0, arrival, service, departure, timecost, travelcost
E,  (-80,) ,8.000000,-80.000000,8.000000,8.000000,10.000000,0.000000,0.000000,
B,  (80,) ,11.000000,80.000000,13.000000,13.000000,15.000000,8.000000,0.000000,
D,  (-20,) ,14.000000,-20.000000,18.000000,18.000000,20.000000,0.000000,0.000000,
C,  (20,) ,16.000000,20.000000,22.000000,22.000000,24.000000,0.000000,0.000000,

Vehicle v2: {'capacity': (100,)}
4.0 = {'distance': 4.0, 'freight_1M1': 0.0, 'timecost': 0.0}
customer, distance, freight_1M1_0, arrival, service, departure, timecost, travelcost
A,  (100,) ,2.000000,100.000000,2.000000,2.000000,4.000000,0.000000,0.000000,
C["depot"] =(0,0)
G=nx.DiGraph()
for v in model.vehiclesL:
   prev=None
   for j in v.routing[1:-1]:
       if prev == None:                
           G.add_edge("depot",j.name)
       else:
           G.add_edge(prev.name,j.name)
       prev= j 
   G.add_edge(prev.name,"depot")
    
fig=plt.figure(figsize=(9,9))    
nx.draw_networkx(G,pos=C,nodelist=[i for i in G.nodes() if i != "depot"],node_color="yellow",node_size=50,with_labels=True,edge_color="k",width=1)
nx.draw_networkx(G,pos=C,nodelist=["depot"],node_color="blue",node_shape='s',alpha=0.5,node_size=50,with_labels=True,edge_color="k",width=1)
plt.show()

例題4 複数の尺度(次元)をもつ需要量と容量

需要と容量をベクトル(タプル)で入力する.重量と容積の2つの尺度を考える.

また,4トンと10トンのトラックを定義し,顧客BとEは,10トンでは入れないことを3次元目のダミーの需要で定義する.

"""
example 4
     - 格子座標上の5点  A(1, 1), B(1, 4), C(2, 0), D(2, 2), E(4, 4) および デポ(0, 0) の問題
     - 車両数は2台 
     - 作業時間(荷役時間等)にかかる時間は2とする.
     - 移動時間と移動コストは距離に等しいものとする.

         - 顧客の需要,時間枠制約は以下の通り

            需要   時間枠制約    
         A:   10   (0, 5)                              # 0 から 5 の間に運ばなければならない
         B:    5   (5, 9, 1, 2)                        # 5 から 9 の間はコスト0, それ以前に到着した場合は傾き1に比例したコスト,それ以後は傾き2に比例したコストがかかる
         C:    3   none                                # 制約なし
         D:    2   None                                # 制約なし
         E:    1   None                                # 制約なし

     - 求解時間は10秒とする.
"""

C = {"A":(1, 1), "B":(1, 4), "C":(2, 0), "D":(2, 2), "E":(4, 4)}    #顧客の座標
D = {"A":(40,1.,0), "B":(30,2.5,1000), "C":(20,1.6,0), "D":(20,0.8,0), "E":(10,0.1,1000)}    #顧客の需要
TW= {"A":(0,5), "B":(5,9,1,2), "C":None, "D":None, "E":None}   #顧客の時間枠制約
Depot = (0,0)   #デポの座標

#マンハッタン距離(格子座標上の距離)を計算する関数
def distance(t1,t2):
    return abs(t1[0]-t2[0])+abs(t1[1]-t2[1])

#モデルインスタンスの作成
model = Model("sample2")

#車両の追加(name:"v1", capa:10)
model += Vehicle("10トン",capacity = (100,5.,0) )
model += Vehicle("4トン",capacity = (40,3.,10000) )
#model += Vehicle("dummy", capacity=(0,), dummy = True) #prize機能?

#顧客の追加 (name:i, demand:D[i], timewindow:TW[i], servicetime:2)
for i in C:
    model +=  Customer(i,demand = D[i], timewindow= TW[i], servicetime= 2)

#距離時間テーブルの作成
for i in C:
    dist = time = distance(Depot,C[i])
    model += Edge("depot",i,dist,time)  
    model += Edge(i,"depot",dist,time)
    for j in C:
        if i!=j:
            dist = time = distance(C[i],C[j])   
            model += Edge(i,j,dist,time)

# 最適化の実行
obj, status=model.optimize(IterLimit=1000,TimeLimit=1,Verbose=True,OutputFlag=False)
print("obj=",obj, "Status=",status)
# 得られた解の表示
try:
    for v in model.vehiclesL:
        print()
        print(v)
        print(list(map(lambda x:x.name,v.routing[1:-1])))    
except:
    print("route is None!")
    pass

for v in model.vehiclesL:
   print()
   print(v)
   keys=v.routing[1].stat.keys()
   print("customer,",", ".join(keys))
   for c in v.routing[1:-1]:
       print(c.name+", ",c.data["demand"],",",end="")
       for k in keys:
           print(c.stat[k],end=",")
       print()
Status= 0
obj= 24.0 Status= 0

Vehicle 10トン: {'capacity': (100, 5.0, 0)}
8.0 = {'distance': 8.0, 'freight_1M1': 0.0, 'timecost': 0.0}
['A', 'D', 'C']

Vehicle 4トン: {'capacity': (40, 3.0, 10000)}
16.0 = {'distance': 16.0, 'freight_1M1': 0.0, 'timecost': 0.0}
['B', 'E']

Vehicle 10トン: {'capacity': (100, 5.0, 0)}
8.0 = {'distance': 8.0, 'freight_1M1': 0.0, 'timecost': 0.0}
customer, distance, freight_1M1_0, freight_1M1_1, freight_1M1_2, arrival, service, departure, timecost, travelcost
A,  (40, 1.0, 0) ,2.000000,40.000000,1.000000,0.000000,2.000000,2.000000,4.000000,0.000000,0.000000,
D,  (20, 0.8, 0) ,4.000000,20.000000,0.800000,0.000000,6.000000,6.000000,8.000000,0.000000,0.000000,
C,  (20, 1.6, 0) ,6.000000,20.000000,1.600000,0.000000,10.000000,10.000000,12.000000,0.000000,0.000000,

Vehicle 4トン: {'capacity': (40, 3.0, 10000)}
16.0 = {'distance': 16.0, 'freight_1M1': 0.0, 'timecost': 0.0}
customer, distance, freight_1M1_0, freight_1M1_1, freight_1M1_2, arrival, service, departure, timecost, travelcost
B,  (30, 2.5, 1000) ,5.000000,30.000000,2.500000,1000.000000,5.000000,5.000000,7.000000,0.000000,0.000000,
E,  (10, 0.1, 1000) ,8.000000,10.000000,0.100000,1000.000000,10.000000,10.000000,12.000000,0.000000,0.000000,
model.vehiclesL[0].routing[1].stat
{'distance': '2.000000',
 'freight_1M1_0': '40.000000',
 'freight_1M1_1': '1.000000',
 'freight_1M1_2': '0.000000',
 'arrival': '2.000000',
 'service': '2.000000',
 'departure': '4.000000',
 'timecost': '0.000000',
 'travelcost': '0.000000'}
C["depot"] =(0,0)
G=nx.DiGraph()
for v in model.vehiclesL:
   prev=None
   for j in v.routing[1:-1]:
       if prev == None:                
           G.add_edge("depot",j.name)
       else:
           G.add_edge(prev.name,j.name)
       prev= j 
   G.add_edge(prev.name,"depot")
    
fig=plt.figure(figsize=(9,9))    
nx.draw_networkx(G,pos=C,nodelist=[i for i in G.nodes() if i != "depot"],node_color="yellow",node_size=50,with_labels=True,edge_color="k",width=1)
nx.draw_networkx(G,pos=C,nodelist=["depot"],node_color="blue",node_shape='s',alpha=0.5,node_size=50,with_labels=True,edge_color="k",width=1)
plt.show()

例題5 デポ以外での積み込み・積み降ろし

AからCへ10単位,EからDへ20単位,EからBへ10単位の需要を運びたい.

AからCの積み込み・積み降ろしを2次元目で表し,積み込み地点で-1000降ろし,積み降ろし地点で1000積み込むものとする.1台のトラックの2次元目の容量を1000にすると,強制的にAの次にCに行く. 実際の需要量は.,1次元目で表し,Aで10単位増えCで10単位減るように設定する.

EからD,EからBも同様に,3次元目,4次元目のダミーの容量を設定する.これらは,1台のトラックで処理できるので,1台のトラック(4トン車)の3次元目と4次元目の容量を1000とする.

"""
example 4
     - 格子座標上の5点  A(1, 1), B(1, 4), C(2, 0), D(2, 2), E(4, 4) および デポ(0, 0) の問題
     - 車両数は2台 
     - 作業時間(荷役時間等)にかかる時間は2とする.
     - 移動時間と移動コストは距離に等しいものとする.

         - 顧客の需要,時間枠制約は以下の通り

            需要   時間枠制約    
         A:   10   (0, 5)                              # 0 から 5 の間に運ばなければならない
         B:    5   (5, 9, 1, 2)                        # 5 から 9 の間はコスト0, それ以前に到着した場合は傾き1に比例したコスト,それ以後は傾き2に比例したコストがかかる
         C:    3   none                                # 制約なし
         D:    2   None                                # 制約なし
         E:    1   None                                # 制約なし

     - 求解時間は10秒とする.
"""

C = {"A":(1, 1), "B":(1, 4), "C":(2, 0), "D":(2, 2), "E":(4, 4)}    #顧客の座標
D = {"A":(10,-1000,0,0), "B":(-10,0,0,1000), "C":(-10,1000,0,0), "D":(-20,0,1000,0), "E":(30,0,-1000,-1000)}    #顧客の需要
TW= {"A":(0,5), "B":(5,9,1,2), "C":None, "D":None, "E":None}   #顧客の時間枠制約
Depot = (0,0)   #デポの座標

#マンハッタン距離(格子座標上の距離)を計算する関数
def distance(t1,t2):
    return abs(t1[0]-t2[0])+abs(t1[1]-t2[1])

#モデルインスタンスの作成
model = Model("sample2")

#車両の追加(name:"v1", capa:10)
model += Vehicle("4トン",capacity = (40,0,1000,1000) )
model += Vehicle("1トン",capacity = (10,1000,0,0) )

#顧客の追加 (name:i, demand:D[i], timewindow:TW[i], servicetime:2)
for i in C:
    model +=  Customer(i,demand = D[i], timewindow= TW[i], servicetime= 2)

#距離時間テーブルの作成
for i in C:
    dist = time = distance(Depot,C[i])
    model += Edge("depot",i,dist,time)  
    model += Edge(i,"depot",dist,time)
    for j in C:
        if i!=j:
            dist = time = distance(C[i],C[j])   
            model += Edge(i,j,dist,time)

# 最適化の実行
obj, status=model.optimize(IterLimit=1000,TimeLimit=3,Verbose=True,OutputFlag=False)
print("obj=",obj, "Status=",status)
# 得られた解の表示
try:
    for v in model.vehiclesL:
        print()
        print(v)
        print(list(map(lambda x:x.name,v.routing[1:-1])))    
except:
    print("route is None!")
    pass

for v in model.vehiclesL:
   print()
   print(v)
   keys=v.routing[1].stat.keys()
   print("customer,",", ".join(keys))
   for c in v.routing[1:-1]:
       print(c.name+", ",c.data["demand"],",",end="")
       for k in keys:
           print(c.stat[k],end=",")
       print()
Status= 0
Feasbiel solution is not found
obj= 62.0 Status= 0

Vehicle 4トン: {'capacity': (40, 0, 1000, 1000)}
46.0 = {'distance': 18.0, 'freight_1M1': 20.0, 'timecost': 8.0}
['E', 'B', 'D']

Vehicle 1トン: {'capacity': (10, 1000, 0, 0)}
16.0 = {'distance': 6.0, 'freight_1M1': 10.0, 'timecost': 0.0}
['A', 'C']

Vehicle 4トン: {'capacity': (40, 0, 1000, 1000)}
46.0 = {'distance': 18.0, 'freight_1M1': 20.0, 'timecost': 8.0}
customer, distance, freight_1M1_0, freight_1M1_1, freight_1M1_2, freight_1M1_3, arrival, service, departure, timecost, travelcost
E,  (30, 0, -1000, -1000) ,8.000000,30.000000,0.000000,-1000.000000,-1000.000000,8.000000,8.000000,10.000000,0.000000,0.000000,
B,  (-10, 0, 0, 1000) ,11.000000,-10.000000,0.000000,0.000000,1000.000000,13.000000,13.000000,15.000000,8.000000,0.000000,
D,  (-20, 0, 1000, 0) ,14.000000,-20.000000,0.000000,1000.000000,0.000000,18.000000,18.000000,20.000000,0.000000,0.000000,

Vehicle 1トン: {'capacity': (10, 1000, 0, 0)}
16.0 = {'distance': 6.0, 'freight_1M1': 10.0, 'timecost': 0.0}
customer, distance, freight_1M1_0, freight_1M1_1, freight_1M1_2, freight_1M1_3, arrival, service, departure, timecost, travelcost
A,  (10, -1000, 0, 0) ,2.000000,10.000000,-1000.000000,0.000000,0.000000,2.000000,2.000000,4.000000,0.000000,0.000000,
C,  (-10, 1000, 0, 0) ,4.000000,-10.000000,1000.000000,0.000000,0.000000,6.000000,6.000000,8.000000,0.000000,0.000000,
C["depot"] =(0,0)
G=nx.DiGraph()
for v in model.vehiclesL:
   prev=None
   for j in v.routing[1:-1]:
       if prev == None:                
           G.add_edge("depot",j.name)
       else:
           G.add_edge(prev.name,j.name)
       prev= j 
   G.add_edge(prev.name,"depot")
    
fig=plt.figure(figsize=(9,9))    
nx.draw_networkx(G,pos=C,nodelist=[i for i in G.nodes() if i != "depot"],node_color="yellow",node_size=50,with_labels=True,edge_color="k",width=1)
nx.draw_networkx(G,pos=C,nodelist=["depot"],node_color="blue",node_shape='s',alpha=0.5,node_size=50,with_labels=True,edge_color="k",width=1)
plt.show()

GUI構築のための基本データ形式

GUIはstreamlitを用いて構築する.以下ではそのために用いる関数を紹介する.

データは,フォルダ名をfolderで指定して、その直下に customer.csv, vehicle.csv, cost.csvを置く。

cost.csvがない場合には、直線距離で代用する.

サンプルデータを読み込んでデータフレームを準備する.

サンプルデータと列の意味は,以下の通り.

顧客データ customer.csv

  • name: 顧客名(0番がデポ)
  • address: 顧客の住所(ソルバーでは未使用); GUI内で緯度・経度を求めるために用いる.
  • weight: 需要の重量;正の値は積み込み,負の値は積み降ろしを表す.
  • volume: 需要の容量;正の値は積み込み,負の値は積み降ろしを表す.
  • time: 顧客上での作業時間(分)
  • maxVehicle: 顧客に入庫可能な運搬車のサイズ
  • early: 最早作業開始時刻
  • late: 最遅作業開始時刻
  • zipcode: 郵便番号(ソルバーでは未使用); GUI内で緯度・経度を求めるために用いる.
  • latitude: 緯度
  • longitude: 経度

運搬車データ vehicle.csv

  • name: 運搬車名
  • size: 運搬車のサイズ(顧客への入庫可否の判定に用いる.)
  • maxWeight: 最大積載重量
  • maxVolume: 最大積載容量
  • maxTime: 最大稼働時間(分)
  • start: デポ発時刻
  • costPerKm: 1kmあたりの移動費用(現在のバージョンでは未使用)

費用データ cost.csv

  • from_node: 枝の発点
  • to_node: 枝の着点
  • distance: 移動距離
  • cost: 移動費用
  • time: 移動時間(分);ソルバー内の計算は秒単位で行う.
cust_df = pd.read_csv(folder + "customer.csv", index_col=0, dtype={"zipcode": str})
vehicle_df = pd.read_csv(folder+"vehicle.csv", index_col=0)
# 費用テーブルがフォルダ内にある場合には、cost_flagをTrueにしておく。
try:
    cost_df = pd.read_csv(folder+"cost.csv", index_col=0)
    cost_flag = True
except:
    cost_flag = False
cust_df.head()
name address weight volume time maxVehicle early late zipcode latitude longitude
0 早稲田工務店 東京都新宿区西早稲田3-6-4 0 0.0 0.0 11 1999/9/28 10:20 1999/9/28 16:30 1690051 35.710803 139.716295
1 ファニチャー 東京都目黒区鷹番1-1-4 1000 21.0 43.0 11 1999/9/28 10:00 1999/9/28 13:30 1520004 35.627530 139.686359
2 ニイミ洋食器店 東京都台東区松が谷1-1-1 1000 21.0 51.0 11 1999/9/28 13:30 1999/9/28 15:30 1110036 35.714782 139.787182
3 IVYアンティークギャラリー 東京都墨田区業平1-5-3 150 2.2 18.0 11 1999/9/28 8:00 1999/9/28 13:40 1300002 35.707575 139.813241
4 アピス 東京都台東区小島2-8-14 200 4.4 21.0 11 1999/9/28 9:00 1999/9/28 14:30 1110056 35.705245 139.783069
vehicle_df.head()
name size maxWeight maxVolume maxTime start costPerKm
ID
0 10tトラック 11 10000 50 800 1999-09-28 08:00:00 300
1 4tトラック 4 4000 30 800 1999-09-28 08:00:00 200
2 10t 11 10000 60 500 1999-09-28 08:00:00 300
3 10t 10 10000 60 800 1999-09-28 08:00:00 250
4 10t 11 10000 60 800 1999-09-28 08:00:00 300
cost_df.head()
from_node to_node distance cost time
0 0 1 9.646236 964.623621 14.469354
1 0 2 6.415337 641.533660 9.623005
2 0 3 8.760543 876.054284 13.140814
3 0 4 6.060668 606.066823 9.091002
4 0 5 14.823106 1482.310559 22.234658

基本データを準備する関数 prepare_data

prepare_data[source]

prepare_data(cust_df, vehicle_df)

準備を行う関数

prepara_date関数の使用例

CustDic, VehiDic, start, early, late, early_vehicle, late_vehicle, ratio, width = prepare_data(cust_df, vehicle_df)
print("基準時刻",start)
基準時刻 1999-09-28 08:00:00

費用計算関数 make_cost

費用データフレーム cost.csvがない場合には,大圏距離をもとに以下の関数を用いいて計算することができる.

make_cost関数の引数は,以下の通り.

  • CustDic: 顧客情報を保持した辞書(prepare_dateで準備)
  • cost_per_km: 1kmあたりの費用;既定値は100.
  • km_per_hour: 時速;既定値は40.

返値は,列に"distance","time","cost"をもつデータフレームである.

distance[source]

distance(origin, destination)

2地点間の直線距離を計算するための関数

make_cost[source]

make_cost(CustDic, cost_per_km=100.0, km_per_hour=40.0)

費用データフレームを生成する関数

make_cost関数の使用例

cost_df = make_cost(CustDic)
cost_df.head()
#cost_df.to_csv(folder+"cost.csv")
from_node to_node distance cost time
0 0 1 9.646236 964.623621 14.469354
1 0 2 6.415337 641.533660 9.623005
2 0 3 8.760543 876.054284 13.140814
3 0 4 6.060668 606.066823 9.091002
4 0 5 14.823106 1482.310559 22.234658

最適化を行う関数 solve

最適化を実行し、目的関数値とモデルオブジェクトを返す。

  • max_cpu:最大計算時間;既定値は10.
  • tw_penelty: 時間枠逸脱のペナルティ;既定値は "inf".ソフト時間枠にしたい場合には,1秒あたりの逸脱ペナルティを表す正の数値を入れる.

solve[source]

solve(CustDic, VehiDic, cust_df, early, late, early_vehicle, late_vehicle, start, cost_df=None, max_cpu=10, tw_penalty='inf')

最適化を実行する関数 Arguments: max_cpu:最大計算時間 tw_penelty: 時間枠逸脱のペナルティ distance_weight ...

solveの実行例

obj, status, model = solve(CustDic, VehiDic, cust_df,  early, late, early_vehicle, late_vehicle, start, cost_df, max_cpu=1, tw_penalty="inf")
print(obj)
Status= 0
Feasbiel solution is not found
77165.58

実行可能性を判定する関数 check_feasibility

需要量(現在は、重量のみ)の実行可能性の判定を行う。

check_feasibility[source]

check_feasibility(model, VehiDic)

実行可能性の判定関数 トラックの辞書VehiDicとモデルオブジェクトに格納されているルート・顧客情報を用いる。 重量のみで判定し、積載量を超過している場合には、出力する。

check_feasibilityの使用例

Falseが返れば実行不能、Trueが返れば実行可能。

check_feasibility(model, VehiDic)
True

発時刻を遅らせる関数 time_shift

トラックの発時刻を、時間枠を破らない範囲で遅らせる関数.最適化を実行した後に呼び出すことができる.

返値は,発時刻を遅らせたモデルオブジェクト

time_shift[source]

time_shift(model, CustDic, VehiDic, start, early_vehicle, late_vehicle)

各トラックの発時刻を時間枠を破らない限りなるべく後ろにずらす関数

time_shift関数の使用例

時間枠を逸脱した場合にのみ,顧客情報を表示する.

model = time_shift(model, CustDic, VehiDic, start, early_vehicle, late_vehicle)

ルートのデータフレームを生成する関数 make_route_df

与えたルート番号(文字列)のデータフレームを生成する。

make_route_df[source]

make_route_df(v, model, CustDic, start)

モデルmodelとトラック名(IDの文字列)を与えると、ルートのデータフレームを返す関数

make_route_dfの使用例

make_route_df("1", model, CustDic, start)
index name early late arrival departure distance weight(1) weight(2) maxVehicle
0 0 0: 早稲田工務店(depot) 08:00:00 21:20:00 - 14:50:17 0 -0 -0 -
1 1 6: 山本商店 1999-09-28 08:40:00 1999-09-28 15:00:00 15:00:00 16:01:00 9.7 1000 21 11
2 2 0: 早稲田工務店 (return) 08:00:00 21:20:00 16:10:42 - 19.4 0 0 -

ルートデータを保存する関数 save_route

全てのルートのデータを保存.

save_route[source]

save_route(model, CustDic, VehiDic)

全てのルートのデータフレームを生成し、csvファイルに保管する関数

save_routeの使用例

save_route(model, CustDic, VehiDic)

描画関数 make_fig

地図上に全てのルートを描画する関数。返値はPlotlyの図オブジェクト。

make_fig[source]

make_fig(model, cust_df, CustDic, ratio, width)

ルートを地図上に描画する関数

make_figの使用例

make_fig_route関数

1つのルート(データフレームで与える)を地図上に描画する関数

fig = make_fig(model, cust_df, CustDic, ratio, width)
#plotly.offline.plot(fig);
Image("../figure/make_fig.png")