配送計画システムMETRO

配送計画システム METRO とその使用法

はじめに

配送計画モデルは，我が国では最も普及しているロジスティクス・ツールである配送計画システムの基幹を成すモデルである． 本来ならば，配送だけでなく集荷にも使われるので運搬経路問題（vehicle routing problem）と よぶのが学術用語としては正しい使い方だが，「運搬」という言葉のイメージが悪いためか， 実務家および研究者の間でも「配送計画」とよばれることが多いので，ここでもそれにならうものとする．

一般に，古典的な配送計画モデルの基本形は以下の仮定をもつ．

• デポとよばれる特定の地点を出発した運搬車が，顧客を経由し再びデポに戻る．このとき運搬車による顧客の通過順をルートとよぶ．
• デポに待機している運搬車の種類および最大積載重量は既知である．
• 顧客の位置は既知であり，各顧客の需要量も事前に与えられている．
• 地点間の移動時間，移動距離，移動費用は既知である．
• 1つのルートに含まれる顧客の需要量の合計は運搬車の最大積載重量を超えない．
• 運搬車の台数は，決められた上限を超えない．（超過した運搬車に対するレンタル料を考える場合や，ルートに含めない顧客に対するペナルティを与える場合もある．）
• 運搬車の稼働時間が与えられた上限を超えない．（超過時間を残業費用として考える場合もある．）

配送計画の応用としては，小売店への配送計画，スクールバスの巡回路決定，郵便や新聞の配達，ゴミの収集，燃料の配送などがある． もちろん，これらの応用に適用する際には，上の基本条件に新たな条件を付加する必要がある．

ここで考えるのは，ほとんどの実際問題を解けるようにするために，以下の一般化をした配送計画モデルである．

• 複数時間枠制約
• 多次元容量非等質運搬車
• 配達・集荷
• 積み込み・積み降ろし
• 複数休憩条件
• スキル条件
• 優先度付き
• パス型許容
• 複数デポ（運搬車ごとの発地，着地）

基本データ

地点 node

地点は顧客，積み込み積み下ろし地点，運搬車の発着地を順に並べたものである．最適化に使うのは経度・緯度の情報を保持したlocation列だけである． 移動時間の計算に地図を使用する場合には，以下のデータフレームで保持しているので必要はない．

移動時間を地図で計算しない場合には，この地点の番号を参照し，移動時間を計算したデータ（移動時間データ）を参照する．

例題においては，地点データの番号は以下の順に保管されている．

• ジョブ job に対応する顧客
• 輸送 shipment の積み込み地点に対応する顧客
• 輸送 shipment の積み降ろし地点に対応する顧客
• 運搬車のデポ

したがって，地点の数は，「ジョブ数 \(+\) 輸送数 \(\times 2 +\) デポ数」となる．

node_df = pd.read_csv(folder +"node.csv", index_col=0)
node_df.head()

	name	zip	都道府県	市区町村	大字	location
0	合同会社藤本建設	2860114	千葉県	成田市	本城	[140.37645821,35.73859296]
1	有限会社西之園運輸	2850053	千葉県	佐倉市	下勝田	[140.26801893,35.69354415]
2	株式会社村山印刷	2620021	千葉県	千葉市花見川区	花園町	[140.07757664,35.654959999999996]
3	青田印刷合同会社	2991902	千葉県	安房郡鋸南町	保田	[139.85405777,35.14919189]
4	合同会社山田水産	2820021	千葉県	成田市	駒井野（成田国際空港内）	[140.36806495,35.77641112]

ジョブ job

ジョブは，荷物の集荷もしくは配達を希望している地点の総称であり，以下の列から構成される．

• name: 地点の名称；例題では仮想の名前を入れているが，重複している場合もあるので注意されたい．
• service: 作業時間（以下では時間の単位は全て秒であり，整数値をとるものとする．）
• pickup: 集荷量を表す整数値のリスト．荷量は複数の属性をもつ場合があるので，リストとして表現している．たとえば，重量，容積，パレット数にそれぞれ上限がある場合には，3次元のリスト（ベクトル）として入力する．
• delivery： 配達量を表す整数値のリスト
• time_windows： 時間枠（作業開始可能時刻，終了時刻の組）を表すリストのリスト．複数の時間枠を表すことができる． たとえば，午前中と午後に作業が可能で，昼の時間帯には作業不能である顧客に対しては， [[8:00,12:00],[13:00,17:00] ]の時刻を基準時刻からの秒に換算したものを入力する． すなわち8時を基準とした場合には，[[0,14400], [18000, 32400] ] と入力する．
• location: 経度と緯度（浮動小数点数）から構成されるリスト．地図データを用いる場合には，これらの値を用いて移動時間を計算する．
• location_index: 移動時間データを用いる場合の地点に対応する番号． 地図データを用いる場合には使用しない．
• skills: ジョブを遂行するために必要なスキルを表す整数のリスト．少なくとも1つのスキルを定義する必要がある． 運搬車がジョブを処理可能か否かを判定するときに用いられる． 運搬車はジョブが要求するすべてのスキルをもたないと処理できない． たとえば，4トン車と10トン車の2種類の運搬車があり，10トン車では入れない顧客がいる場合を考える． 10トン車では入庫不能な顧客（ジョブ）に対してはスキルを [0,1] と定義し， 入れる顧客に対しては [0] と定義する． 4トン車のスキルを [0,1] と，10トン車のスキルを [0] と定義すれば，10トン車はスキル1をもたないので，入庫不能な顧客を処理することができないことが表現できる．
• priority: ジョブの優先度を表す [0,100] の整数値．ジョブを処理しない（どの運搬車にも割り当てない）としたときに支払われるペナルティを表す．優先度が大きいジョブほど運搬車に割り当てられる（処理される）可能性が高くなる．

job_df = pd.read_csv(folder +"job.csv", index_col=0) 
job_df.head()

	name	service	pickup	delivery	time_windows	location	location_index	skills	priority
0	合同会社藤本建設	1068	[56]	[244]	[[10820, 12620], [33575, 35375]]	[140.37645821,35.73859296]	0	[0,1]	9
1	有限会社西之園運輸	852	[75]	[229]	[[8151, 9951], [21049, 22849]]	[140.26801893,35.69354415]	1	[0,1]	9
2	株式会社村山印刷	1090	[100]	[683]	[[753, 2553], [27719, 29519]]	[140.07757664,35.654959999999996]	2	[0]	7
3	青田印刷合同会社	998	[70]	[849]	[[11742, 13542], [19888, 21688]]	[139.85405777,35.14919189]	3	[0]	6
4	合同会社山田水産	1162	[87]	[608]	[[1110, 2910], [24285, 26085]]	[140.36806495,35.77641112]	4	[0]	9

輸送 shipment

輸送は，運搬車のデポ（出発地点もしくは最終到着地点）以外での荷物の積み込みと積み降ろしを表し，以下の列から構成される．

• amount: 積み込み地点で積み込み，積み降ろし地点で降ろす量（輸送量）．整数値のリスト
• pickup_point: 積み込み地点の名称
• pickup_service: 積み込みにかかる作業時間
• pickup_time_windows: 積み込みの時間枠を表すリストのリスト
• pickup_location: 積み込み地点の経度・緯度のリスト
• pickup_index: 移動時間データを用いる場合の積み込み地点に対応する番号． 地図データを用いる場合には使用しない．
• delivery_point: 積み降ろし地点の名称
• delivery_service: 積み降ろしにかかる作業時間
• delivery_time_windows: 積み降ろしの時間枠を表すリストのリスト
• delivery_location: 積み降ろし地点の経度・緯度のリスト
• delivery_index: 移動時間データを用いる場合の積み降ろし地点に対応する番号． 地図データを用いる場合には使用しない．
• skills: 輸送を行うために必要なスキル
• priority: 優先度

shipment_df = pd.read_csv(folder +"shipment.csv", index_col=0) 
shipment_df.head()

	amount	pickup_point	pickup_service	pickup_time_windows	pickup_location	pickup_index	delivery_point	delivery_service	delivery_time_windows	delivery_location	delivery_index	skills	priority
0	[38]	有限会社吉田食品	835	[[7935, 9735], [18905, 20705]]	[139.8874225,35.06991256]	5	有限会社青山鉱業	672	[[10863, 12663], [33913, 35713]]	[139.92525888,35.84571653]	6	[0]	0

運搬車 vehicle

運搬車（トラック，車両）は，輸送手段の総称であり， 以下の列をもつ．

• name: 運搬車を区別するための名称
• start: 運搬車の出発地点を表す経度・緯度のリスト．(start_indexで点の番号を参照させ，移動時間行列を与える方法も可能である．） 省略した場合には，最初の訪問地点から出発する．
• start_index: 移動時間データを用いる場合の運搬車の出発地点に対応する番号． 地図データを用いる場合には使用しない． このデータが空 (NaN) の場合には，出発地点を指定せず，最初に訪問した地点から運搬車の経路が開始される．
• end: 運搬車の最終到着地点を表す経度・緯度のリスト． 省略した場合には，最後の訪問地点で終了する． ただし，出発地点と最終到着地点の両者を省略することはできない． 出発地点と同じ座標にした場合には，出発地点であるデポに戻ることを表す．
• end_index: 移動時間データを用いる場合の運搬車の最終到着地点に対応する番号． 地図データを用いる場合には使用しない． このデータが空 (NaN) の場合には，最終到着地点を指定せず，最後に訪問した地点で運搬車の経路が終了する． もちろん出発地点と最終到着地点が異なっても良い．そのため，複数デポや最終地点が車庫であることも表現できる．
• capacity: 運搬車の積載量上限（容量）を表す整数値のリスト．ジョブデータの集荷量・配達量，輸送データの輸送量と同じ長さのリスト（ベクトル）である必要がある．
• time_window: 運搬車の時間枠（最早開始時刻と最遅到着時刻の組）を表すリスト
• skills: 運搬車のもつスキル． ジョブや輸送で要求するすべてのスキルをもたないと処理できない．
• breaks: 休憩の番号のリスト．既定値は「なし」を表す None． 例における休憩データの場合で，昼食だけの場合は[0]，昼食と夕食の場合は[0,1]と設定する．

vehicle_df = pd.read_csv(folder +"vehicle.csv", index_col=0) 
vehicle_df.head()

	name	start	start_index	end	end_index	capacity	time_window	skills	breaks
0	truck0	[139.92142527,35.67868735]	7	[]	NaN	[2209]	[0, 36000]	[0,1]	[]

休憩 break

• description: 休憩の説明
• time_windows: 休憩をとる時間枠（（最早時刻と最遅時刻の組(タプル)）のリスト
• service: 休憩時間

break_df = pd.DataFrame( {"description":["lunch", "supper"], "time_windows": [[10800,18000],[32400,39600]], "service": [3600,1800]} )
#break_df.to_csv(folder+"break.csv")
break_df

	description	time_windows	service
0	lunch	[10800, 18000]	3600
1	supper	[32400, 39600]	1800

#hide ## Remark

数値は全部整数

座標は (lon, lat)

costはduration（移動時間の合計）

#hide ### 最短路計算

./osrm-routed –max-table-size=10000 japan-latest.osrm

docker run -t -i -p 5000:5000 -v “${PWD}:/data” osrm/osrm-backend osrm-routed –max-table-size=10000 /data/japan-latest.osrm

ポートがすでに使われている場合の対処法

lsof -i:ポートNo

kill -9 PID

#hide ### ルートリクエストの例

リクエストで　Web APIをコールできる． 以下はOSRMを呼んでいる．

APIの詳細は以下を参照：

http://project-osrm.org/docs/v5.23.0/api/#

requests関数で距離と時間をOSRMから得る．

OSRMサーバーのURLの後に，ルート検索(route)，バージョン(v1)，車での移動の指定(driving)，発着地の経度・緯度を文字列で与えると，レスポンスが得られる．

#hide JSONとはJavaScript Object Notationの略で，Pythonの辞書（のリスト）のようなものである． データフレームを辞書に変換した後で，json.dumpsで文字列に変換すると，Webでやりとりできるようになる．

データ生成

移動時間行列の計算関数 compute_distance_table_for_vrp

地図アプリ OSRM を用いて移動時間と移動距離を計算する．

引数： - node_df: ノードデータフレーム（緯度経度情報を含む） - toll: 有料道路が使用可のときTrue（既定値 True) - host: ホスト名；既定値は “localhost”

返値： - durations: 地点間の移動時間の配列 - distances: 地点間の距離の配列

---

source

compute_distance_table_for_vrp

def compute_distance_table_for_vrp(
    node_df, toll:bool=True, host:str='localhost'
):

Call self as a function.

compute_distance_table_for_vrp関数の使用例

移動時間と移動距離を計算し，移動時間の度数分布表を描画する．

#node_df = pd.read_csv(folder +"node10.csv")
durations,  distances = compute_distance_table_for_vrp(node_df, toll=False, host=host)

#durations[-1] #デポから他の地点への移動時間
node_df["duration"] = durations[-1]
node_df["distance"] = distances[-1]
fig = px.histogram(node_df, x="duration",nbins=30, title ="デポからの移動時間の度数分布表", marginal="violin")
#plotly.offline.plot(fig);

地点間の距離と移動時間（高速道路利用の有無あり）のデータフレームを生成する関数 make_time_df_for_vrp

引数： - node_df: 点のデータフレーム

返値： - time_df: 発地，着地，移動時間（秒），道路距離（m）,高速なしの移動時間（秒），高速なしの道路距離（m)を入れたデータフレーム

def make_time_df_for_vrp(node_df):
    try:
        node_df.reset_index(inplace=True)
    except:
        pass
    durations,  distances = compute_distance_table_for_vrp(node_df, toll=True)
    durations2,  distances2 = compute_distance_table_for_vrp(node_df, toll=False)
    n = len(durations)
    name_dic = node_df.name.to_dict() #番号を顧客名に写像
    from_id, to_id, duration, distance, duration2, distance2 =[],[],[],[],[],[]
    from_name, to_name = [], [] 
    for i in range(n):
        for j in range(n):
            if durations[i][j] is not None and durations2[i][j] is not None:
                from_id.append(i)
                to_id.append(j)
                from_name.append(name_dic[i])
                to_name.append(name_dic[j])
                duration.append( int(durations[i][j]) )
                distance.append( int(distances[i][j]) )
                duration2.append( int(durations2[i][j]) )
                distance2.append( int(distances2[i][j]) )
    time_df = pd.DataFrame({"from_node": from_id, "from_name": from_name, "to_node":to_id,
                            "to_name":to_name, "time": duration, "distance": distance, "time(no toll)": duration2, "distance(no toll)": distance2 })
    return time_df

node_df = pd.read_csv(folder +"node10.csv")
time_df = make_time_df_for_vrp(node_df)
time_df.head()

	from_node	from_name	to_node	to_name	time	distance	time(no toll)	distance(no toll)
0	0	合同会社前田建設 第 18 支店	0	合同会社前田建設 第 18 支店	0	0	0	0
1	0	合同会社前田建設 第 18 支店	1	有限会社阿部運輸 第 73 支店	0	0	0	0
2	0	合同会社前田建設 第 18 支店	2	株式会社村上印刷 第 98 支店	0	0	0	0
3	0	合同会社前田建設 第 18 支店	3	佐藤印刷合同会社 第 9 支店	0	0	0	0
4	0	合同会社前田建設 第 18 支店	4	合同会社青木水産 第 33 支店	0	0	0	0

郵便番号データをもとに日本のノードデータをランダムに生成する関数 generate_node

引数： - df: 郵便番号データと緯度経度データを合わせたデータフレーム - n: 地点数 - random_seed=1：乱数の種 - prefecture=None: 県名 - matrix: 移動時間行列を生成するとき True

返値： - node_df: 顧客データフレーム - time_df: 移動時間データフレーム（matrix引数がTrueのとき；それ以外のときは，空の文字列”“を返す．）

---

source

generate_node

def generate_node(
    df, n, random_seed:int=1, prefecture:NoneType=None, matrix:bool=False
):

郵便番号データをもとに日本のノードデータをランダムに生成する関数

generate_node関数の使用例

zip_df = pd.read_csv("../data/zipcode.csv")  # 日本の郵便番号データの読み込み
node_df, time_df = generate_node(zip_df, n=10, random_seed=1, prefecture="千葉県", matrix=False)
node_df.head()

	name	zip	都道府県	市区町村	大字	location
0	合同会社前田建設 第 18 支店	2860114	千葉県	成田市	本城	[140.37645821,35.73859296]
1	有限会社阿部運輸 第 73 支店	2850053	千葉県	佐倉市	下勝田	[140.26801893,35.69354415]
2	株式会社村上印刷 第 98 支店	2620021	千葉県	千葉市花見川区	花園町	[140.07757664,35.65496]
3	佐藤印刷合同会社 第 9 支店	2991902	千葉県	安房郡鋸南町	保田	[139.85405777,35.14919189]
4	合同会社青木水産 第 33 支店	2820021	千葉県	成田市	駒井野（成田国際空港内）	[140.36806495,35.77641112]

ノードデータを正規分布にしたがってランダムに生成する関数 generate_node_normal

引数： - n: 地点数 - lat_center: 中心緯度 - lon_center: 中心経度 - std: 正規分布の標準偏差 - country_code: 国を表すコード（名称をランダムに生成するときに用いる．） 既定値は日本 ja_JP． その他の国コードについては https://faker.readthedocs.io/en/master/locales.html 参照． - random_seed=1：乱数の種 - matrix: 移動時間行列を生成するとき True

返値： - node_df: 顧客データフレーム - time_df: 移動時間データフレーム（matrix引数がTrueのとき；それ以外のときは，空の文字列”“を返す．）

---

source

generate_node_normal

def generate_node_normal(
    n, lat_center, lon_center, std:float=0.1, country_code:str='ja_JP', random_seed:int=1, matrix:bool=False
):

ノードデータを正規分布にしたがってランダムに生成する関数

generate_node_normal 関数の使用例

lat_center = 30.567201
lon_center = 120.112051
std = 0.1
country_code = 'zh_CN' #中国
random_seed = 1
node_df, time_df = generate_node_normal(n=10, lat_center=lat_center, lon_center=lon_center, std= std, country_code=country_code, random_seed=1, matrix=False)
node_df.head()

	name	location
0	精芯传媒有限公司	[120.25826179370449,30.729635536366324]
1	维旺明网络有限公司	[119.90603692905023,30.506025358634993]
2	太极科技有限公司	[120.07980927959865,30.514383824773656]
3	襄樊地球村网络有限公司	[120.07364556453315,30.459904137784385]
4	超艺网络有限公司	[120.22542794423354,30.65374176293247]

配送計画問題例の生成関数 generate_vrp

配送計画のランダムな問題例を生成する関数

引数： - df: ノードデータフレーム - num_depots = 1: デポ数 - open_flag = False: Trueだと，運搬車の最終地点がデポでなく，最後の訪問地点となる． - num_jobs=10: ジョブ数 - num_shipments=0: デポ以外での積み込み積み降ろしの輸送数 - num_time_windows =1: 時間枠の数 - time_window_bounds =(0,36000): 時間枠の下限と上限の組 - time_window_ratio = 0.9: 稼働時間に対する時間枠の比（小さいほど時間枠が狭くなる） - delivery_bounds = (0,0): 配達量の下限と上限の組 - pickup_bounds = (0,0): 集荷量の下限と上限の組 - service_bounds= (0,0): 作業時間の下限と上限の組 - amount_bounds = (0,0): デポ以外での積み込み積み下ろし量の下限と上限の組 - priority_bounds = (0,100): 優先度の下限と上限の組；0..100の間にする必要がある． 優先度は訪問しない場合のペナルティ量を表す（大きいほどルートに含まれる）． - load_factor = 0.9: 運搬車の積載率の目標値 - num_customers_per_route = 5： １ルートあたりの配達件数 - skill_flag = False: スキルを考慮した問題例とするときTrue - breaks = None: 休憩の番号のリスト．既定値は「なし」を表す None． 例における休憩データの場合で，昼食だけの場合は[0]，昼食と夕食の場合は[0,1]と設定する．

返値： - job_df: ジョブデータフレーム - shipment_df: 輸送データフレーム - vehicle_df: 運搬車データフレーム

---

source

generate_vrp

def generate_vrp(
    node_df, num_depots:int=1, open_flag:bool=False, num_jobs:int=10, num_shipments:int=0, num_time_windows:int=1,
    time_window_bounds:tuple=(0, 36000), time_window_ratio:float=0.9, delivery_bounds:tuple=(0, 0),
    pickup_bounds:tuple=(0, 0), service_bounds:tuple=(0, 0), amount_bounds:tuple=(0, 0),
    priority_bounds:tuple=(0, 100), load_factor:float=0.9, num_customers_per_route:int=5, skill_flag:bool=False,
    breaks:NoneType=None
):

郵便番号データをもとに配送計画問題のデータをランダムに生成する関数（ノード生成を分離）

generate_vrp関数の使用例

#パラメータの準備
matrix = True
delivery_bounds = 100, 1000
pickup_bounds  = 50, 100
service_bounds = 10*60, 20*60 #seconds 
amount_bounds = 1,100
priority_bounds = 0,100
load_factor = 0.5 #積載率
num_customers_per_route = 5 #1ルートに含まれる顧客数

num_depots = 1
num_jobs = 1000
num_shipments = 0
n= num_depots +num_jobs + num_shipments*2

#日本のノードデータ生成
zip_df = pd.read_csv("../data/zipcode.csv")  # 日本の郵便番号データの読み込み
node_df, time_df = generate_node(zip_df, n=n, random_seed=1, prefecture="埼玉県", matrix=matrix)

#中国のデータ生成
# lat_center = 30.567201
# lon_center = 120.112051
# std = 0.1
# country_code = 'zh_CN'
# random_seed = 1
# node_df, time_df = generate_node_normal(n=n, lat_center=lat_center, lon_center=lon_center, std= std, country_code=country_code, random_seed=1, matrix=matrix)

job_df, shipment_df, vehicle_df = generate_vrp(node_df, num_depots=num_depots, open_flag=False, num_jobs=num_jobs, num_shipments = num_shipments, num_time_windows =2, 
                                                        time_window_bounds =(0,36000), time_window_ratio =0.5,
                                  delivery_bounds= delivery_bounds, pickup_bounds=pickup_bounds, service_bounds = service_bounds, amount_bounds=amount_bounds, 
                                  priority_bounds =priority_bounds, load_factor=load_factor, num_customers_per_route=num_customers_per_route, skill_flag=False, breaks=[0])

job_df.head()

	name	service	pickup	delivery	time_windows	location	location_index	skills	priority
0	合同会社前田建設 第 18 支店	782	[65]	[137]	[[7244, 16244], [26360, 35360]]	[139.48372896,36.08020962]	0	[0]	20
1	有限会社阿部運輸 第 73 支店	698	[87]	[335]	[[2125, 11125], [19323, 28323]]	[139.3262383,35.96836517]	1	[0]	48
2	株式会社村上印刷 第 98 支店	635	[88]	[172]	[[6210, 15210], [18590, 27590]]	[139.19460618,36.05815305]	2	[0]	38
3	佐藤印刷合同会社 第 9 支店	714	[82]	[867]	[[1493, 10493], [20297, 29297]]	[139.66804321,36.09307749]	3	[0]	22
4	合同会社青木水産 第 33 支店	784	[86]	[815]	[[5098, 14098], [22005, 31005]]	[139.51107504,35.90863789]	4	[0]	64

node_df.head()

	name	zip	都道府県	市区町村	大字	location
0	合同会社前田建設 第 18 支店	3650063	埼玉県	鴻巣市	稲荷町	[139.48372896,36.08020962]
1	有限会社阿部運輸 第 73 支店	3500323	埼玉県	比企郡鳩山町	小用	[139.3262383,35.96836517]
2	株式会社村上印刷 第 98 支店	3550300	埼玉県	比企郡ときがわ町	以下に掲載がない場合	[139.19460618,36.05815305]
3	佐藤印刷合同会社 第 9 支店	3400217	埼玉県	久喜市	鷲宮	[139.66804321,36.09307749]
4	合同会社青木水産 第 33 支店	3500021	埼玉県	川越市	大中居	[139.51107504,35.90863789]

job_df.head()

	name	service	pickup	delivery	time_windows	location	location_index	skills	priority
0	合同会社前田建設 第 18 支店	782	[65]	[137]	[[7244, 16244], [26360, 35360]]	[139.48372896,36.08020962]	0	[0]	20
1	有限会社阿部運輸 第 73 支店	698	[87]	[335]	[[2125, 11125], [19323, 28323]]	[139.3262383,35.96836517]	1	[0]	48
2	株式会社村上印刷 第 98 支店	635	[88]	[172]	[[6210, 15210], [18590, 27590]]	[139.19460618,36.05815305]	2	[0]	38
3	佐藤印刷合同会社 第 9 支店	714	[82]	[867]	[[1493, 10493], [20297, 29297]]	[139.66804321,36.09307749]	3	[0]	22
4	合同会社青木水産 第 33 支店	784	[86]	[815]	[[5098, 14098], [22005, 31005]]	[139.51107504,35.90863789]	4	[0]	64

shipment_df.head()

	amount	pickup_point	pickup_service	pickup_time_windows	pickup_location	pickup_index	delivery_point	delivery_service	delivery_time_windows	delivery_location	delivery_index	skills	priority

vehicle_df.head()

	name	start	start_index	end	end_index	capacity	time_window	skills	breaks
0	truck0	[139.18710879,36.22963938]	1000	[139.18710879,36.22963938]	1000	[3150]	[0, 36000]	[0]	[0]
1	truck1	[139.18710879,36.22963938]	1000	[139.18710879,36.22963938]	1000	[3150]	[0, 36000]	[0]	[0]
2	truck2	[139.18710879,36.22963938]	1000	[139.18710879,36.22963938]	1000	[3150]	[0, 36000]	[0]	[0]
3	truck3	[139.18710879,36.22963938]	1000	[139.18710879,36.22963938]	1000	[3150]	[0, 36000]	[0]	[0]
4	truck4	[139.18710879,36.22963938]	1000	[139.18710879,36.22963938]	1000	[3150]	[0, 36000]	[0]	[0]

time_df.head()

	from_node	from_name	to_node	to_name	time	distance
0	0	合同会社前田建設 第 18 支店	0	合同会社前田建設 第 18 支店	0	0
1	0	合同会社前田建設 第 18 支店	1	有限会社阿部運輸 第 73 支店	0	0
2	0	合同会社前田建設 第 18 支店	2	株式会社村上印刷 第 98 支店	0	0
3	0	合同会社前田建設 第 18 支店	3	佐藤印刷合同会社 第 9 支店	0	0
4	0	合同会社前田建設 第 18 支店	4	合同会社青木水産 第 33 支店	0	0

break_df

	description	time_windows	service
0	lunch	[10800, 18000]	3600
1	supper	[32400, 39600]	1800

最適化のための準備

モデル構築関数 build_model_for_vrp

データフレームからモデル（JSONファイルの元になる辞書）を生成する関数．

引数： - job_df: ジョブデータフレーム - shipment_df: 輸送データフレーム - vehicle_df: 運搬車データフレーム - break_df: 休憩データフレーム - time_df: 移動時間データフレーム（既定値は「なし」を表すNone）

返値： - model: モデル（JSONファイルの元になる辞書）

---

source

build_model_for_vrp

def build_model_for_vrp(
    job_df, shipment_df, vehicle_df, break_df, time_df:NoneType=None
):

Call self as a function.

build_model_for_vrp関数の使用例

no = "01"
job_df = pd.read_csv(folder+"job"+no+".csv", index_col=0)
shipment_df = pd.read_csv(folder+"shipment"+no+".csv", index_col=0)
vehicle_df = pd.read_csv(folder+"vehicle"+no+".csv", index_col=0)
time_df = pd.read_csv(folder+"time"+no+".csv", index_col=0)
break_df = pd.read_csv(folder +"break.csv", index_col=0)
model = build_model_for_vrp(job_df, shipment_df, vehicle_df,  break_df, time_df)
pprint(model["jobs"][0])

{'delivery': [137],
 'description': '合同会社藤本建設',
 'id': 0,
 'location': [139.48372896, 36.08020962],
 'location_index': 0,
 'pickup': [57],
 'priority': 13,
 'service': 751,
 'skills': [0],
 'time_windows': [[0, 36000]]}

ルートデータフレーム生成関数 make_route_for_vrp

ルートのデータフレームを格納した辞書を生成する関数．

引数： - job_df: ジョブデータフレーム - shipment_df: 輸送データフレーム - vehicle_df: 運搬車データフレーム - break_df: 休憩データフレーム - output_dic: 最適化の結果を格納した辞書

返値： - route_df_dic: キーをルート番号とし，ルートの情報を格納したデータフレームを値とした辞書． ルートデータフレームの列は以下の通り．

• index: 訪問順序

• name: 地点名（開始地点はstart，終了地点はend，休憩はbreakと表示される．）

• pickup: 積み込み量を表すリスト

• delivery: 積み降ろし量を表すリスト

• load: その地点での積載量を表すリスト

• time_window(s): 時間枠のリスト（複数時間枠の場合にはリストのリスト）

• arrival: 到着時刻（単位は秒；以降全て）

• service: 作業時間

• waiting_time: 待ち時間

• duration: 累積移動時間

• skills: スキルのリスト

• priority: 優先度

• unassigned_job_df: 未割り当てのジョブのデータフレーム

• unassigned_shipment_df: 未割り当ての輸送のデータフレーム

---

source

make_route_for_vrp

def make_route_for_vrp(
    job_df, shipment_df, vehicle_df, break_df, output_dic
):

未割り当てとルートのデータフレーム（の辞書）を返す関数

make_route_for_vrp関数の使用例

#最適化の出力を読むこむ
# with open('output1.json', 'r') as example1_out:
#     output_dic = json.load(example1_out)

# route_df_dic, unassigned_job_df, unassigned_shipment_df = make_route_for_vrp(job_df, shipment_df, vehicle_df, break_df, output_dic)

# #ルートデータフレームの最初のルートを表示
# route_df_dic[0].head()

時間変換のユーテリティ関数 time_convert

引数： - sec: 秒数 - start: 開始時刻を表す文字列（年，月，日，時間，分，秒で，“2000-01-01 00:00:00”のような形式で入力する．）

返値： - 開始時刻startからsec秒経過した時刻

---

source

time_convert

def time_convert(
    sec, start
):

時間変換のユーテリティ関数

time_convert関数の使用例

time_convert(1000, "2000-01-01 00:00:00")

'2000-01-01 00:16'

ガントチャート生成関数

ルート情報をもとにガントチャートを生成する関数

引数： - route_df_dic: キーをルート番号とし，ルートの情報を格納したデータフレームを値とした辞書 - start: 開始時刻を表す文字列（年，月，日，時間，分，秒で，“2000-01-01 00:00:00”のような形式で入力する．）

返値： - fig: plotlyの図オブジェク

---

source

gannt_for_vrp

def gannt_for_vrp(
    route_df_dic, start:str='2000/01/01 00:00:00'
):

ルートのガントチャートを生成する関数

gannt_for_vrp関数の使用例

# 
# fig = gannt_for_vrp(route_df_dic, start= "2020/01/01 8:00" )
# plotly.offline.plot(fig);

時間枠の可視化関数 make_tw_fig_for_vrp

引数： - job_df: ジョブデータフレーム - shipment_df: 輸送データフレーム - start: 開始時刻を表す文字列（年，月，日，時間，分，秒で，“2000-01-01 00:00:00”のような形式で入力する．）

返値： - fig: plotlyの図オブジェクト

---

source

make_tw_fig_for_vrp

def make_tw_fig_for_vrp(
    job_df, shipment_df, start:str='2000/01/01 00:00:00'
):

時間枠を可視化する関数

make_tw_fig_for_vrp関数の使用例

# 
# job_df = pd.read_csv(folder+"job.csv", index_col=0)
# shipment_df = pd.read_csv(folder+"shipment.csv", index_col=0)
# fig = make_tw_fig_for_vrp(job_df, shipment_df, start= "2020/01/01 8:00")
# #plotly.offline.plot(fig);

地図描画

ルートを追加する関数 add_route_for_vrp

引数： - output_dic: 最適化の出力を保管した辞書 - map_style: 地図のスタイルを表す番号で 0,1,2のいずれかを入れる．これは，mapboxのスタイル “satellite-streets” , “open-street-map”, “dark” に対応している．

返値： - data: ルートの図オブジェクトのリスト

---

source

add_route_for_vrp

def add_route_for_vrp(
    output_dic, map_style:int=0
):

Call self as a function.

通過した道路を追加する関数 add_road_for_vrp

引数： - output_dic: 最適化の出力を保管した辞書 - map_style: 地図のスタイルを表す番号で 0,1,2のいずれかを入れる．これは，mapboxのスタイル “satellite-streets” , “open-street-map”, “dark” に対応している．

返値： - data: ルート（通過道路）の図オブジェクトのリスト

---

source

add_road_for_vrp

def add_road_for_vrp(
    output_dic, map_style:int=0
):

Call self as a function.

描画関数 make_fig_for_vrp

引数： - input_dic: 最適化への入力情報を保管した辞書 - output_dic: 最適化の出力を保管した辞書 - show_mode: 描画モードを表す文字列． ノードのみを表示させるとき “node”， ルートを直線で表示させるとき “route”， 道路情報を図に入れるとき “road” とする． - map_style: 地図のスタイルを表す番号で 0,1,2のいずれかを入れる．これは，mapboxのスタイル “satellite-streets” , “open-street-map”, “dark” に対応している．

返値： - fig: plotlyの地図オブジェクト

---

source

make_fig_for_vrp

def make_fig_for_vrp(
    input_dic, output_dic, show_mode:str='road', map_style:int=0
):

図の表示

make_fig_for_vrp関数の使用例

#
# with open('test1.json', 'r') as example1_in:
#     input_dic = json.load(example1_in)
# with open('output1.json', 'r') as f:
#     output_dic = json.load(f)        
# fig = make_fig_for_vrp(input_dic, output_dic, show_mode="route", map_style = 2 )
# plotly.offline.plot(fig);

詳細ルートを描画する関数 make_detailed_route

引数： - output_dic: 最適化の出力を保管した辞書 - route_df_dic: ルートのデータフレームを保持する辞書 - route_id: 表示したいルートの番号 - matrix: 移動時間行列を与えるときTrue（既定値はFalse） - map_style: 地図のスタイルを表す番号で 0,1,2のいずれかを入れる．これは，mapboxのスタイル “satellite-streets” , “open-street-map”, “dark” に対応している． - straight: Uターンを抑制するためのフラグ；Trueのとき直線を優先する．FalseのときはUターンを許す．既定値は Noneで，Uターンと移動時間の兼ね合いを考えて自動選択する． - host: ホスト名；既定値は “localhost”

返値： - fig: plotlyの地図オブジェクト

---

source

make_detailed_route

def make_detailed_route(
    input_dic, output_dic, route_df_dic, route_id:int=0, matrix:bool=False, map_style:int=0, straight:NoneType=None,
    host:str='localhost'
):

詳細ルートの図を描画する関数

make_detailed_route関数の使用例

#
# fig = make_detailed_route(input_dic, output_dic, route_df_dic, route_id=0, matrix=False, map_style=1, straight = False)
# plotly.offline.plot(fig);

最適化関数 optimize_vrp

引数： - model: 最適化モデルを入れた辞書 - matrix = False: 移動時間データを用いる場合True - thread: 最適化に使用するスレッド数 - explore: 探索の度合いを表すパラメータ； 0から5の整数で，大きいほど念入りに探索する． - cloud: 複数人が同時実行する可能性があるときTrue（既定値はFalse）; Trueのとき，ソルバー呼び出し時に生成されるファイルにタイムスタンプを追加し，計算終了後にファイルを消去する． - osrm: OSRMを外部のサーバーで呼び出しをしたいときTrue， localhostで呼び出すときFalse

返値： - input_dic: データ入力のためのJSONデータ - output_dic: 結果出力のためのJSONデータ - error: エラーメッセージを入れた文字列

---

source

optimize_vrp

def optimize_vrp(
    model, matrix:bool=False, threads:int=4, explore:int=5, cloud:bool=False, osrm:bool=False, host:str='localhost'
):

Call self as a function.

実行例

#問題例読み込み

matrix = False #時間行列を用いる場合 True
map_style = 1

no = "10"
node_df = pd.read_csv(folder+"node"+no+".csv", index_col=0)
job_df = pd.read_csv(folder+"job"+no+".csv", index_col=0)
shipment_df = pd.read_csv(folder+"shipment"+no+".csv", index_col=0)
vehicle_df = pd.read_csv(folder+"vehicle"+no+".csv", index_col=0)
time_df = pd.read_csv(folder+"time"+no+".csv", index_col=0)
break_df = pd.read_csv(folder + "break.csv", index_col=0)

#モデル生成
if matrix:
    model = build_model_for_vrp(job_df, shipment_df, vehicle_df, break_df, time_df)
else:
    model = build_model_for_vrp(job_df, shipment_df,vehicle_df, break_df)

#最適化
input_dic, output_dic, error = optimize_vrp(model,matrix=matrix, explore=5, cloud=False, osrm=True, host=host)

if error != "":
    print(error) 
else:
    pass
    if matrix:
        fig = make_fig_for_vrp(input_dic, output_dic, show_mode="route", map_style=map_style)
    else:
        fig = make_fig_for_vrp(input_dic, output_dic, show_mode="road", map_style=map_style)
    plotly.offline.plot(fig);

    route_df_dic, unassigned_job_df, unassigned_shipment_df = make_route_for_vrp(job_df, shipment_df, 
                                                                                 vehicle_df, break_df, output_dic)

    fig = gannt_for_vrp(route_df_dic, start= "2020/01/01 8:00" )
    plotly.offline.plot(fig);

    fig = make_tw_fig_for_vrp(job_df, shipment_df, start= "2020/01/01 8:00")
    plotly.offline.plot(fig);

print("cost=", output_dic["summary"]["cost"])

Now solving ...
Done
cost= 487560
CPU times: user 6.4 s, sys: 305 ms, total: 6.7 s
Wall time: 9.43 s

例題

Webシステムで現在使用している例題を以下に示す（Webシステムで番号を選択すると例題がロードされる）．

0. 容量制約
1. 広い時間枠
2. 狭い時間枠
3. 複数の時間枠
4. 複数のデポ（運搬車の発着地）
5. パス型のルート（始点か終点のいずれかがなし）
6. （デポ以外での）積み込み積み降ろし
7. 休憩（11時から2時の間に1時間昼食休憩を入れる．）
8. スキル（入庫不可条件など）
9. 優先度（顧客を訪問しない場合のペナルティ）
10. 大規模問題例

ExcelとStreamlitによる簡易配送計画インターフェイス

テンプレート生成関数のための準備関数群

---

source

make_job_excel

def make_job_excel(
    wb, n_job:int=100, num_dim:int=3, num_tw:int=3, num_skill:int=3, date_flag:bool=True
):

Call self as a function.

wb = Workbook()
ws = wb.active
wb.remove(ws)
wb = make_job_excel(wb, n_job=100, num_dim = 2, num_tw = 2, num_skill = 2, date_flag = False)
wb.save("metro-job.xlsx")

---

source

make_shipment_excel

def make_shipment_excel(
    wb, n_shipment:int=100, num_dim:int=3, num_tw:int=3, num_skill:int=3, date_flag:bool=True
):

Call self as a function.

wb = Workbook()
wb = make_shipment_excel(wb, n_shipment=100, num_dim = 1, num_tw = 1, num_skill = 1, date_flag = True)
wb.save("metro-shipment.xlsx")

---

source

make_vehicle_excel

def make_vehicle_excel(
    wb, n_vehicle:int=100, num_dim:int=3, num_skill:int=3, num_break:int=2, date_flag:bool=True
):

Call self as a function.

wb = Workbook()
wb = make_vehicle_excel(wb, n_vehicle=100, num_dim = 3, num_skill = 3, num_break = 2, date_flag = True)
wb.save("metro-vehicle.xlsx")

---

source

make_break_excel

def make_break_excel(
    wb, num_break:int=2, date_flag:bool=False
):

Call self as a function.

wb = Workbook()
ws = wb.active
wb.remove(ws)
wb = make_break_excel(wb, num_break = 1, date_flag = True)
wb.save("metro-break.xlsx")

Excelデータを生成する関数 create_excel_for_metro

引数： - n_job: ジョブ数； 既定値は \(100\) - n_shipment: 輸送数；　既定値は \(100\) - n_vehicle: 運搬車数； 既定値は \(100\) - num_dim: 積載重量の次元数; 既定値は \(1\) - num_tw: 時間枠の数; 既定値は \(1\) - num_skill: スキル数; 既定値は \(1\) - num_break: 休憩数; 既定値は \(1\) - date_flag: 時間入力を日付時刻型にする場合 True（既定値）， 時刻型にする場合 False（既定値はFalse)

返値：

• OpenPyXLのWorkbookオブジェクト；以下のシートをもつ．
  • ジョブ：列数は 4+num_tw * 2+num_dim * 2+num_skill+1 であり，既定値は \(10\)
  • 輸送: 列数は 8+num_tw*4+num_dim+num_skill+1 であり，既定値は \(15\)
  • 運搬車: 列数は 8+num_skill+num_break であり，既定値は \(10\)
  • 休憩: 列数は 4

---

source

create_excel_for_metro

def create_excel_for_metro(
    n_job:int=100, n_shipment:int=100, n_vehicle:int=100, num_dim:int=1, num_tw:int=1, num_skill:int=1,
    num_break:int=1, date_flag:bool=False
):

Call self as a function.

wb = create_excel_for_metro(n_job=100, n_shipment=100, n_vehicle=100, num_dim = 2, num_tw = 2, num_skill = 2, num_break=1, date_flag = False)
wb.save("metro.xlsx")

Excelブックからデータフレームを読み込む関数 read_dfs_from_excel

引数 - wb: Excel Workbook

返値： - job_df: ジョブデータフレーム - shipment_df: 輸送データフレーム - vehicle_df: 運搬車データフレーム - break_df: 休憩データフレーム

---

source

read_dfs_from_excel

def read_dfs_from_excel(
    wb
):

Call self as a function.

Excelブックから移動時間データフレームを読み込む関数 read_time_from_excel

引数 - wb: Excel Workbook

返値： - time_df: 移動時間データフレーム

---

source

read_time_from_excel

def read_time_from_excel(
    wb
):

Call self as a function.

make_table_for_metro関数の準備関数 compute_table_sub

移動時間の可視化でも用いる．

---

source

compute_table_sub

def compute_table_sub(
    job_df, shipment_df, vehicle_df, break_df, num_dim:int=1, num_tw:int=1, num_skill:int=1, num_break:int=1,
    toll:bool=True, host:str='localhost'
):

Call self as a function.

移動時間・距離のデータを生成する関数 make_table_for_metro

ジョブ，輸送，運搬車の経度・緯度情報をもとに，地点データを抽出し，ユニークなインデックスをもつ地点シートを追加する．

地点間の移動時間をOSRMで計算し， 移動時間データを生成し，移動時間シートに追加する．

さらに，ジョブ，輸送，運搬車に，対応する地点のインデックス情報を追加する．

引数 - wb: ExcelのWorkBook - num_dim: 積載重量の次元数; 既定値は \(1\) - num_tw: 時間枠の数; 既定値は \(1\) - num_skill: スキル数; 既定値は \(1\) - num_break: 休憩数; 既定値は \(1\) - toll: 高速道路を使う場合 True（既定値）

返値 - wb: データを更新したExcelのWorkBook - durations: 移動時間行列（単位は秒） - distances: 距離行列（単位はm）

---

source

make_table_for_metro

def make_table_for_metro(
    wb, num_dim:int=1, num_tw:int=1, num_skill:int=1, num_break:int=1, toll:bool=True, host:str='localhost'
):

Call self as a function.

make_table_for_metro関数の使用例

num_dim = 2
num_tw = 2
num_skill = 2
num_break=1
wb = load_workbook("metro-ex1.xlsx")
job_df, shipment_df, vehicle_df, break_df = read_dfs_from_excel(wb)
wb, durations, distances = make_table_for_metro(wb, num_dim, num_tw, num_skill, num_break, toll=False, host=host)
wb.save("metro-ex1-tbl.xlsx")

Excel用のデータフレームを用いた移動時間を可視化する関数 make_time_fig_for_excel

---

source

make_time_fig_for_excel

def make_time_fig_for_excel(
    job_df, shipment_df, vehicle_df, break_df, num_dim:int=1, num_tw:int=1, num_skill:int=1, num_break:int=1,
    toll:bool=True, host:str='localhost'
):

Call self as a function.

make_time_fig_for_excel関数の使用例

# num_dim = 2
# num_tw = 2
# num_skill = 2
# num_break=1
# toll = False
# wb = load_workbook("metro-ex1.xlsx")

# # num_dim = 2
# # num_tw = 1
# # num_skill = 8
# # num_break=1
# # toll = False
# # wb = load_workbook("metro3.xlsx")
# job_df, shipment_df, vehicle_df, break_df = read_dfs_from_excel(wb)

# fig, fig_hist =  make_time_fig_for_excel(job_df, shipment_df, vehicle_df, break_df, num_dim, 
#                                          num_tw, num_skill, num_break, toll, host=host)
# plotly.offline.plot(fig);
# #plotly.offline.plot(fig_hist);

Excel用のデータフレームを用いた時間枠を可視化する関数 make_tw_fig_for_excel

引数： - job_df: ジョブデータフレーム - shipment_df: 輸送データフレーム - vehicle_df: 運搬車データフレーム - num_dim: 積載重量の次元数; 既定値は \(1\) - num_tw: 時間枠の数; 既定値は \(1\)

返値： - fig: Plotlyの図オブジェクト

---

source

make_tw_fig_for_excel

def make_tw_fig_for_excel(
    job_df, shipment_df, vehicle_df, num_dim:int=1, num_tw:int=1
):

Excel用のデータフレームを用いた時間枠を可視化する関数

make_tw_fig_for_excel関数の適用例

wb = load_workbook("metro-ex2.xlsx")
job_df, shipment_df, vehicle_df, break_df = read_dfs_from_excel(wb)

fig = make_tw_fig_for_excel(job_df, shipment_df, vehicle_df, num_dim=1, num_tw = 1)
#plotly.offline.plot(fig);

荷量簡易分析関数 analyze_load

ジョブの荷量が運搬車の積載量上限でまかなえるかを，線形最適化を用いて簡易的に分析することを考える．

荷量は複数の属性をもつ場合があるので，多次元のベクトルとして扱う．その次元数と積み込み・積み降ろしの区別をするので，全体で「次元数$$2」の資源制約をもつと考える．

次元の添字を \(j\)，積み込み・積み降ろしの添字を \(k　(=0,1)\) とし， \(j,k\) の組を資源とよぶ．

ジョブ（顧客）を運搬車に割り当てる際には，スキルを考慮する必要がある．顧客のスキル集合が運搬車のスキル集合の部分集合になっている場合に割り当て可能になる．

以下のパラメータと変数を導入する．

パラメータ - \(d_{ijk}\): 顧客 \(i\) の資源 \(j,k\) の荷量 - \(C_{vj}\): 運搬車 \(v\) の次元 \(j\) の積載量上限 - \(M\): 大きな数（超過ペナルティを優先するために用いる．） - \(\epsilon\): 小さな数（不用意な超過・余裕量を \(0\) にするため．）

変数 - \(x_{iv}\): 顧客 \(i\) を運搬車 \(v\) に割り当てる割合； 顧客 \(i\) のスキルが運搬車 \(v\) のスキル集合の部分集合になっているときだけ定義する． - \(surplus_{vjk}\): 運搬車 \(v\) の資源 \(j,k\) の超過量の割合 - \(slack_{vjk}\): 運搬車 \(v\) の資源 \(j,k\) の余裕量の割合 - \(y\): 最大の超過割合 - \(z\): 最小の割合

定式化 \[ \begin{array}{lll} minimize & My-z +\epsilon \sum_{v,j,k} (surplus_{vjk}+slack_{vjk}) & \\ s.t. & \sum_{v} x_{iv} = 1 & \forall i \\ & \sum_{i} d_{ijk} x_{iv} = C_{vj}(1- slack_{vjk} +surplus_{vjk}) & \forall v,j,k \\ & 0 \leq slack_{vjk} \leq z & \forall v,j,k \\ & 0 \leq surplus_{vjk} \leq y & \forall v,j,k \\ & x_{iv} \geq 0 & \forall i,v \end{array} \]

引数： - job_df: ジョブデータフレーム - vehicle_df: 運搬車データフレーム - num_dim: 積載重量の次元数; 既定値は \(1\) - num_tw: 時間枠の数; 既定値は \(1\) - num_skill: スキル数; 既定値は \(1\)

返値： - fig_surplus: 超過のPlotly図オブジェクト - fig_slack: 不足量のPlotly図オブジェクト

---

source

analyze_load

def analyze_load(
    job_df, vehicle_df, num_dim:int=1, num_tw:int=1, num_skill:int=1
):

Call self as a function.

analyze_loadの使用例

#wb = load_workbook("metro-ex6.xlsx")
wb = load_workbook("metro-ex1.xlsx")
job_df, shipment_df, vehicle_df, break_df = read_dfs_from_excel(wb)

fig_surplus, fig_slack = analyze_load(job_df, vehicle_df, num_dim=2, num_tw = 2, num_skill = 1)

#plotly.offline.plot(fig_slack);
#plotly.offline.plot(fig_surplus);

Welcome to the CBC MILP Solver 
Version: 2.10.3 
Build Date: Dec 15 2019 

command line - /Users/mikiokubo/Library/Caches/pypoetry/virtualenvs/scmopt-KVX_UVCf-py3.8/lib/python3.8/site-packages/pulp/apis/../solverdir/cbc/osx/64/cbc /var/folders/69/5y96sdc94jxf6khgc8mlmxrr0000gn/T/68cc38c1b4754c91a26b698268590dac-pulp.mps branch printingOptions all solution /var/folders/69/5y96sdc94jxf6khgc8mlmxrr0000gn/T/68cc38c1b4754c91a26b698268590dac-pulp.sol (default strategy 1)
At line 2 NAME          MODEL
At line 3 ROWS
At line 65 COLUMNS
At line 331 RHS
At line 392 BOUNDS
At line 472 ENDATA
Problem MODEL has 60 rows, 79 columns and 231 elements
Coin0008I MODEL read with 0 errors
Presolve 44 (-16) rows, 63 (-16) columns and 199 (-32) elements
Perturbing problem by 0.001% of 598.13951 - largest nonzero change 0.00068043615 ( 9.9290948%) - largest zero change 0
0  Obj 0.16247847 Primal inf 8.0248717 (12) Dual inf 0.76082576 (46)
0  Obj 0.16 Primal inf 8.0248717 (12) Dual inf 4.5e+11 (46)
25  Obj -0.041144353
Optimal - objective value -0.041144353
After Postsolve, objective -0.041144353, infeasibilities - dual 0 (0), primal 0 (0)
Optimal objective -0.04114435258 - 25 iterations time 0.002, Presolve 0.00
Option for printingOptions changed from normal to all
Total time (CPU seconds):       0.00   (Wallclock seconds):       0.00

荷量のヒストグラムを作成する関数 show_load

---

source

show_load

def show_load(
    job_df, num_dim:int=1, num_tw:int=1
):

Call self as a function.

show_load関数の使用例

wb = load_workbook("metro-ex3.xlsx")
job_df, shipment_df, vehicle_df, break_df = read_dfs_from_excel(wb)
num_dim= 1
num_tw = 1
fig_bar, fig_hist = show_load(job_df, num_dim=num_dim, num_tw=num_tw)
#plotly.offline.plot(fig_hist);
#plotly.offline.plot(fig_bar);

Excelから読んだデータフレームを最適化用のデータフレームに変換する関数 create_dfs_from_excel

引数： - job_df: ジョブデータフレーム - shipment_df: 輸送データフレーム - vehicle_df: 運搬車データフレーム - break_df: 休憩データフレーム - num_dim: 積載重量の次元数; 既定値は \(3\) - num_tw: 時間枠の数; 既定値は \(3\) - num_skill: スキル数; 既定値は \(3\) - num_break: 休憩数; 既定値は \(3\) - date_flag: 時間入力を日付時刻型にする場合 True（既定値）， 時刻型にする場合 False （未使用）

返値： - job_df: （最適化用の）ジョブデータフレーム - shipment_df: （最適化用の）輸送データフレーム - vehicle_df: （最適化用の）運搬車データフレーム - break_df: （最適化用の）休憩データフレーム - start: 運搬車の最早開始時刻

---

source

create_dfs_from_excel

def create_dfs_from_excel(
    job_df, shipment_df, vehicle_df, break_df, num_dim:int=1, num_tw:int=1, num_skill:int=1, num_break:int=1,
    date_flag:bool=False
):

Call self as a function.

create_dfs_from_excel関数の実行例

num_dim = 2
num_tw = 2
num_skill = 2
num_break=1
wb = load_workbook("metro-ex1.xlsx")

# num_dim = 1
# num_tw = 1
# num_skill = 1
# num_break=1
# wb = load_workbook("metro-ex3.xlsx")
#wb = load_workbook("metro_example1.xlsx")
#wb = load_workbook("metro-ex1-tbl.xlsx")
#wb, durations, distances = make_table_for_metro(wb, num_dim, num_tw, num_skill, num_break, toll=True, host=host)
job_df, shipment_df, vehicle_df, break_df = read_dfs_from_excel(wb)
job_df, shipment_df, vehicle_df, break_df, start = create_dfs_from_excel(job_df, shipment_df, vehicle_df, break_df, 
                                                                    num_dim, num_tw, num_skill, num_break, date_flag = False)

#time_df = read_time_from_excel(wb)
#model = build_model_for_vrp(job_df, shipment_df, vehicle_df,  break_df, time_df)
model = build_model_for_vrp(job_df, shipment_df, vehicle_df,  break_df)
input_dic, output_dic, error = optimize_vrp(model, matrix=False, explore=5, cloud=False, osrm=True, host=host)
route_df_dic, unassigned_job_df, unassigned_shipment_df = make_route_for_vrp(job_df, shipment_df, vehicle_df, break_df, output_dic)
route_df_dic[0]

Now solving ...
Done

	index	name	pickup	delivery	load	time_window(s)	arrival	service	waiting_time	duration	skills	priority
0	0	start : 車１	[0]	[0]	[0, 0]	[0, 46800]	16487	0	0	0	[0, 1, 2]	0
1	1	星乃珈琲店 上野店	[100, 20]	[0, 0]	[100, 20]	[[14400, 28800]]	17004	600	0	517	[0]	1
2	2	星乃珈琲店 東京スカイツリータウン・ソラマチ店	[100, 20]	[0, 0]	[200, 40]	[[18000, 32400]]	18000	600	0	913	[0]	1
3	3	顧客B	[10, 1]	[0]	[210, 41]	[[10800, 21600], [32400, 39600]]	21431	600	0	3744	[0, 1]	1
4	4	顧客A	[100, 20]	[0, 0]	[310, 61]	[[7200, 14400], [21600, 32400]]	23036	600	0	4749	[0, 1, 2]	1
5	5	顧客C	[0]	[10, 1]	[300, 60]	[[21600, 28800], [32400, 43200]]	24036	1800	0	5149	[0, 1]	1
6	6	break	[0]	[0]	[300, 60]	[25200, 28800]	25836	3600	0	5149	None	None
7	7	星乃珈琲店 錦糸町駅前店	[100, 20]	[0, 0]	[400, 80]	[[28800, 43200]]	32408	600	0	8121	[0]	1
8	8	星乃珈琲店 数寄屋橋店	[100, 20]	[0, 0]	[500, 100]	[[25200, 39600]]	33452	600	0	8565	[0]	1
9	9	end : 車１	[0]	[0]	[500, 100]	[0, 46800]	34096	0	0	8609	[0, 1, 2]	0

# model = build_model_for_vrp(job_df, shipment_df, vehicle_df,  break_df)
# pprint(model["vehicles"][1])

#最適化
input_dic, output_dic, error = optimize_vrp(model, matrix=False, explore=5, cloud=False)

Now solving ...
Done

route_df_dic, unassigned_job_df, unassigned_shipment_df = make_route_for_vrp(job_df, shipment_df, vehicle_df, break_df, output_dic)

#ルートデータフレームの最初のルートを表示
route_df_dic[0]

	index	name	pickup	delivery	load	time_window(s)	arrival	service	waiting_time	duration	skills	priority
0	0	start	[0]	[0]	[0, 0]	[0, 46800]	9930	0	0	0	[0, 1, 2]	0
1	1	顧客B	[10, 1]	[0]	[10, 1]	[[10800, 21600], [32400, 39600]]	12795	600	0	2865	[0, 1]	1
2	2	顧客A	[100, 20]	[0, 0]	[110, 21]	[[7200, 14400], [21600, 32400]]	14400	600	0	3870	[0, 1, 2]	1
3	3	顧客C	[0]	[10, 1]	[100, 20]	[[21600, 28800], [32400, 43200]]	15400	1800	6200	4270	[0, 1]	1
4	4	東京スカイツリー店	[100, 20]	[0, 0]	[200, 40]	[[18000, 32400]]	26346	600	0	7216	[0]	1
5	5	上野店	[100, 20]	[0, 0]	[300, 60]	[[14400, 28800]]	27323	600	0	7593	[0]	1
6	6	break	[0]	[0]	[300, 60]	[25200, 28800]	27923	3600	0	7593	None	None
7	7	錦糸町駅前店	[100, 20]	[0, 0]	[400, 80]	[[28800, 43200]]	31988	600	0	8058	[0]	1
8	8	数寄屋橋店	[100, 20]	[0, 0]	[500, 100]	[[25200, 39600]]	33031	600	0	8501	[0]	1
9	9	end	[0]	[0]	[500, 100]	[0, 46800]	33675	0	0	8545	[0, 1, 2]	0

unassigned_shipment_df

	amount	pickup_point	pickup_service	pickup_time_windows	pickup_location	delivery_point	delivery_service	delivery_time_windows	delivery_location	skills	priority	pickup_index	delivery_index

fig = make_fig_for_vrp(input_dic, output_dic, show_mode="route", map_style = 0 )
plotly.offline.plot(fig);

#fig = gannt_for_vrp(route_df_dic, start= "2020/01/01 8:00" )
fig = gannt_for_vrp(route_df_dic, start= "08:00" )
plotly.offline.plot(fig);

未割り当てのExcelデータを得る関数 unassigned_for_excel

引数： - job_df: ジョブデータフレーム - shipment_df: 輸送データフレーム - vehicle_df: 運搬車データフレーム - output_dic: 最適化の出力を保管した辞書

返値： - unassigned_job_df: 未割り当てのジョブデータフレーム - unassigned_shipment_df: 未割り当ての輸送データフレーム - unassigned_vehicle_df : 未割り当ての運搬車データフレーム

---

source

unassigned_for_excel

def unassigned_for_excel(
    job_df, shipment_df, vehicle_df, output_dic
):

Excel用の未割り当てを返す関数

#
wb = load_workbook("metro-ex1.xlsx")
#wb = load_workbook("metro-ex5.xlsx")
job_df, shipment_df, vehicle_df, break_df = read_dfs_from_excel(wb)
job_df0 = job_df.copy()
shipment_df0 = shipment_df.copy()
vehicle_df0 = vehicle_df.copy()
            
job_df, shipment_df, vehicle_df, break_df, start = create_dfs_from_excel(job_df, shipment_df, vehicle_df, break_df, 
                                                                    num_dim = 2, num_tw = 2, num_skill = 2, num_break=1, date_flag = False)
model = build_model_for_vrp(job_df, shipment_df, vehicle_df,  break_df)
input_dic, output_dic, error = optimize_vrp(model, matrix=False, explore=5, cloud=False)
route_df_dic, unassigned_job_df, unassigned_shipment_df = make_route_for_vrp(job_df, shipment_df, vehicle_df, break_df, output_dic)
unassigned_job_df, unassigned_shipment_df, unassigned_vehicle_df = unassigned_for_excel(job_df0, shipment_df0, vehicle_df0, output_dic)
unassigned_vehicle_df

結果をExcelシートに書き込む関数 write_result_excel

引数： - start: 運搬車の最早開始時刻 - output_dic: 最適化で出力されたJSONデータ - unassigned_job_df: 未割り当てのジョブのデータフレーム - unassigned_shipment_df: 未割り当ての輸送のデータフレーム - output_dic: 最適化出力のJSONnum_tw

返値： - wb: 結果を書き込んだExcel Worksheet

---

source

write_result_excel

def write_result_excel(
    start, route_df_dic, unassigned_job_df, unassigned_shipment_df, unassigned_vehicle_df, output_dic, num_tw
):

Call self as a function.

write_result_excel関数の使用例

unassigned_job_df, unassigned_shipment_df, unassigned_vehicle_df = unassigned_for_excel(job_df, shipment_df, vehicle_df, output_dic)
wb = write_result_excel(start, route_df_dic, unassigned_job_df, unassigned_shipment_df, unassigned_vehicle_df, 
                        output_dic, num_tw=1)
wb.save("result.xlsx")

#hide ### PyVRPのテスト

#hide ### 実験

#hide delivery_bounds = 100, 1000 pickup_bounds = 50, 100 service_bounds = 1060, 2060 #seconds amount_bounds = 1,100 load_factor = 0.7 #積載率 num_customers_per_route = 5 #1ルートに含まれる顧客数 node_df, job_df, shipment_df, vehicle_df = generate_vrp(zip_df, num_depots=1, open_flag=False, num_jobs=1, num_shipments = 1000, num_time_windows =1, time_window_bounds =(0,36000),

n=1000 EXPLORE = 0 cost= 1381758 CPU times: user 2.88 s, sys: 98.2 ms, total: 2.97 s Wall time: 14.8 s —– EXPLORE = 1 cost= 1398022 (worse!) CPU times: user 777 ms, sys: 43.5 ms, total: 821 ms Wall time: 35.9 s —– EXPLORE = 5 cost= 1522317 (worse!!) CPU times: user 2.81 s, sys: 113 ms, total: 2.93 s Wall time: 4min 7s

======= n=1500 EXPLORE = 0 cost= 3386775 CPU times: user 1.33 s, sys: 50.3 ms, total: 1.38 s Wall time: 26.2 s

EXPLORE = 1 cost= 3323622 (better) CPU times: user 1.31 s, sys: 44.9 ms, total: 1.36 s Wall time: 55.2 s

#hide

delivery_bounds = 100, 1000 pickup_bounds = 50, 100 service_bounds = 1060, 2060 #seconds amount_bounds = 1,100 load_factor = 0.99 #積載率 num_customers_per_route = 5 #1ルートに含まれる顧客数 node_df, job_df, shipment_df, vehicle_df = generate_vrp(zip_df, num_depots=1, open_flag=False, num_jobs=20, num_shipments = 1, num_time_windows =1, time_window_bounds =(0,36000), time_window_ratio =0.5, delivery_bounds= delivery_bounds, pickup_bounds=pickup_bounds, service_bounds = service_bounds, amount_bounds=amount_bounds, priority_bounds = (0,100), load_factor=load_factor, num_customers_per_route=num_customers_per_route, skill_flag=False, random_seed=1, prefecture=“千葉県”)

ーーーーー THREADS = 4 EXPLORE = 0 (fast mode)

n=1000 cost= 1312465 CPU times: user 646 ms, sys: 34.1 ms, total: 680 ms Wall time: 5.18 s

n=2000 cost= 3221695 CPU times: user 1.42 s, sys: 50.4 ms, total: 1.47 s Wall time: 19.2 s

n=3000 cost= 3201265 CPU times: user 2.09 s, sys: 52.6 ms, total: 2.14 s Wall time: 46 s

THREADS = 4 EXPLORE = 1 (これが推奨値？もちろん問題による．実験が必要！！！）
THREADS = 4 EXPLORE = 2
n=1000 cost= 1291625 (worse????) CPU times: user 652 ms, sys: 36.7 ms, total: 689 ms Wall time: 43.3 s
n=2000 cost= 3165255 (worse???) CPU times: user 1.27 s, sys: 42.3 ms, total: 1.31 s Wall time: 4min 29s
n=3000 cost= 3137744 (worse ????) CPU times: user 2.09 s, sys: 59.2 ms, total: 2.15 s Wall time: 15min 30

THREADS = 4 EXPLORE = 3

n=1000 (worse!!) cost = ???? CPU times: user 653 ms, sys: 36.5 ms, total: 690 ms Wall time: 1min 27s

n=2000 cost= 3198741 (worse???) CPU times: user 1.41 s, sys: 51.5 ms, total: 1.46 s Wall time: 9min 5s

n=3000

THREADS = 4 EXPLORE = 4

n=1000 cost= 1325962 (much worse?)

CPU times: user 797 ms, sys: 43.4 ms, total: 840 ms Wall time: 3min 25s

n=2000

n=3000

THREADS = 4 EXPLORE = 5 n = 1000

cost= 1327968 ???? IIt’s bad!!! CPU times: user 660 ms, sys: 42.9 ms, total: 703 ms Wall time: 6min 26s

n=2000 cost= 3282467 bad! CPU times: user 1.47 s, sys: 76.4 ms, total: 1.55 s Wall time: 42min 1s

n=3000 ?

#hide ## OSRMを用いた道路距離・時間の計算 ランダムデータで実験

県ごとに迂回係数と平均時速を計算しておき，デポとの間は道路距離（時間），それ以外は近似とすることも考えられる．

#hide

METRO V

https://github.com/VROOM-Project/vroom/blob/master/docs/API.md

https://github.com/VROOM-Project/pyvroom

https://github.com/scmopt/metroV

GCP

https://medium.com/@calroughan/a-beginners-guide-to-installing-osrm-and-vroom-on-gcp-28fbcf1f7857

Inputクラス

class Input
    - amount_size: int | None = None,
    - servers: Dict[str, str | Any] | None = None,
    - router: Any = _vroom.ROUTER.OSRM

• Args:

  • amount_size: The size of the job to be transported. Used to verify all jobs have the same size limit.

  • servers: Assuming no custom duration matrix is provided (from set_durations_matrix), use coordinates and a map server to calculate durations matrix. Keys should be identifed by add_routing_wrapper. If string, values should be on the format {host}:{port}.

  • router: “orsm” に設定 If servers is used, define what kind of server is provided. See vroom.ROUTER enum for options.

problem_instance = vroom.Input()

set_durations_matrixメソッド

set_durations_matrix(
    profile: str,
    matrix_input: _DualArrayLike[dtype, bool | int | float | complex | str | bytes]
) -> None

Set durations matrix.

• Args:
  • profile: Name of the transportation category profile in question. Typically “car”, “truck”, etc.
  • matrix_input: A square matrix consisting of duration between each location of interest. Diagonal is canonically set to 0.

problem_instance.set_durations_matrix(
    profile="car",
    matrix_input=[[0, 2104, 197, 1299],
         [2103, 0, 2255, 3152],
         [197, 2256, 0, 1102],
         [1299, 3153, 1102, 0]],
)

vroomだと行列を以下のように移動時間と費用に分けて入力できる．

"matrices": {
    "car": {
        "durations": [[0, 14], [21, 0]]
    },
    "bike": {
        "durations": [[0, 57], [43, 0]]
    }
}

#hide

add_vehicleメソッド

problem_instance.add_vehicle([vroom.Vehicle(47, start=0, end=0),
                              vroom.Vehicle(48, start=2, end=2)])

Add vehicle.

• Args:
  • vehicle: Vehicles to use to solve the vehicle problem. Vehicle type must have a recognized profile, and all added vehicle must have the same capacity.

Vehicleクラス

運搬車クラス

id: ‘int’, start: ‘Union[None, Location, int, Sequence[float]]’ = None, end: ‘Union[None, Location, int, Sequence[float]]’ = None, profile: ‘str’ = ‘car’, capacity: ‘Union[Amount, Sequence[int]]’ = (), skills: ‘Optional[Set[int]]’ = None, time_window: ‘Optional[TimeWindow]’ = None, breaks: ‘Sequence[Break]’ = (), description: ‘str’ = ’‘, costs: ’VehicleCosts’ = VehicleCosts(), speed_factor: ‘float’ = 1.0, max_tasks: ‘int’ = 18446744073709551615, max_travel_time: ‘Optional[int]’ = None, steps: ‘Sequence[VehicleStep]’ = (),

• Args:
  • id: Vehicle idenfifier number. Two vehicle can not have the same identifier.
  • start: The location where the vehicle starts at before any jobs are done. If omitted, the vehicle will start at the first task it will be assigned. If interger, value interpreted as an the column in duration matrix. If pair of numbers, value interpreted as longitude and latitude coordinates respectively.
  • end: The location where the vehicle should end up after all jobs are completed. If omitted, the vehicle will end at the last task it will be assigned. If interger, value interpreted as an the column in duration matrix. If pair of numbers, value interpreted as longitude and latitude coordinates respectively.
  • profile: 運搬車の種類（プロファイル）を表す．既定値は “car” だが， “bicycle”, “walk” などを指定すると， 該当する移動時間や費用を使う．
  • costs: 運搬車の費用（以下に定義するVehicleCosts）
  • capacity: Array of intergers representing the capacity to carry different goods.
  • skills: Skills provided by this vehilcle needed to perform various tasks.
  • time_window: The time window for when this vehicle is available for usage.
  • breaks: Breaks this vehicle should take.
  • description: Optional string descriping the vehicle.
  • speed_factor: 既定値の速度の何倍かを表すパラメータ．既定値は \(1\) で， \((0, 5]\) の実数値を設定する．
  • max_tasks: 最大タスク数．タスクはジョブもしくは輸送の積み込み，積み降ろしを表す．
  • max_travel_time: 最大移動時間
  • steps: 運搬車のステップ（以下に定義するVehicleStep）の配列．これによって，運搬車のルートを固定することができる．

VehicleCostsクラス

• fixed: 固定費用；既定値は \(0\)
• per_hour: \(1\) 時間あたりの費用；既定値は \(3600\)

VehicleStepクラス

運搬車のルートを固定するためのステップ； 計画モードで求解するときには，逸脱量を求める．最適化モードで求解するときには，初期解として用いる．

• Args:
  • step_type: ステップの種類； 開始（start）, 終了（end）, 休憩（break）, 通常のジョブ（single；job）, 積み込み（pickup）, 積み降ろし（delivery）から選択する．
  • id: Reference to the job/break the step is associated with. Not used for step_type == “start” and step_type == “end”.
  • service_at: サービスを開始する時刻
  • service_after: サービスを開始する時刻の下限
  • service_before: サービスを開始する時刻の上限

#hide

add_jobメソッド

（複数の）ジョブ（輸送）を追加する．

• Args:
  • job: One or more (single) job and/or shipments that the vehicles needs to carry out.

使用例：

problem_instance.add_job([vroom.Job(1414, location=0, setup=200, service=20),
                     vroom.Job(1515, location=1, setup=100, service=10),
                      vroom.Job(1616, location=2),
                       vroom.Job(1717, location=3),
                       vroom.Job(1818, location=1, setup=100, service=10)])

Jobクラス

ジョブクラス

A regular one-stop job with both a deliver and pickup that has to be performed.

• Args:

  • id: Job identifier number. Two jobs can not have the same identifier.

  • location: Location of the job. If interger, value interpreted as an the column in duration matrix. If pair of numbers, value interpreted as longitude and latitude coordinates respectively.

  • setup: 段取り時間； その地点で最初にタスクを開始するときにかかる時間

  • service: 作業時間； １つの作業を行うときの時間は，「段取り時間 \(+\) 作業時間」になる． 2つ以上の作業を同じ地点で行う場合には，

  • delivery: An interger representation of how much is being carried to customer.

  • pickup: An interger representation of how much is being carried back from customer.

  • skills: Skills required to perform job. Only vehicles which satisfies all required skills (i.e. has at minimum all skills values required) are allowed to perform this job.

  • priority: The job priority level, where 0 is the most important and 100 is the least important.

  • time_windows: Windows for where service is allowed to begin. Defaults to have not restraints.

  • description: Optional string descriping the job.

Locationクラス

• index: Location index referring to column in the duration matrix.
• coords: Longitude and latitude coordinate.

Shipmentクラス

• Args:

  • pickup: Description of the pickup part of the shipment. (以下のShipmentStepのインスタンス）

  • delivery: Description of the delivery part of the shipment. (以下のShipmentStepのインスタンス）

  • amount: An interger representation of how much is being carried back from customer.

  • skills: Skills required to perform job. Only vehicles which satisfies all required skills (i.e. has at minimum all skills values required) are allowed to perform this job.

  • priority: The job priority level, where 0 is the most important and 100 is the least important.

ShipmentStepクラス

• Args:
  • id: Job identifier number. Two jobs can not have the same identifier.
  • location: Location of the job. If interger, value interpreted as an the column in duration matrix. If pair of numbers, value interpreted as longitude and latitude coordinates respectively.
  • setup: The cost of preparing the vehicle before actually going out for a job.
  • service: The time (in secondes) it takes to pick up/deliver shipment when at customer.
  • time_windows: Windows for where service is allowed to begin. Defaults to have not restraints.
  • description: Optional string descriping the job.

#hide

Breakクラス

Break
(id: Break | int, time_windows: Sequence[TimeWindow] = (), service: int = 0, description: str = "") -> None

A break allocated to the vehicle’s driver.

• Args:

  • id: Job identifier number. Two jobs can not have the same identifier.

  • time_windows: Time windows for where breaks is allowed to begin. Defaults to have not restraints.

  • service: The time duration (in secondes) of the break.

  • description: A string describing this break.

  • max_load: （vroomのみ） 休憩する際の荷物の最大積載量

#hide

solveメソッド

時間制限なども付けられない！ (JSONで呼び出しが必要！）

• Args:
  • exploration_level: int,
  • nb_threads: int

solution = problem_instance.solve(exploration_level=5, nb_threads=4)

solutionオブジェクト

print(solution.summary.cost)
print(solution.routes)

solution.to_dict()の例

{"code":0,
"summary":{"cost":6411,"routes":2,"unassigned":0,"setup":300,"service":40,"duration":6411,"waiting_time":0,"priority":0,"violations":[],"computing_times":{"loading":0,"solving":3}},
"unassigned":[],
"routes":[{"vehicle":47,"cost":4207,"setup":300,"service":40,"duration":4207,"waiting_time":0,"priority":0,"steps":[{"type":"start","location_index":0,"setup":0,"service":0,"waiting_time":0,"arrival":0,"duration":0,"violations":[]},{"type":"job","location_index":1,"id":1818,"setup":100,"service":10,"waiting_time":0,"job":1818,"arrival":2104,"duration":2104,"violations":[]},{"type":"job","location_index":1,"id":1515,"setup":0,"service":10,"waiting_time":0,"job":1515,"arrival":2214,"duration":2104,"violations":[]},{"type":"job","location_index":0,"id":1414,"setup":200,"service":20,"waiting_time":0,"job":1414,"arrival":4327,"duration":4207,"violations":[]},{"type":"end","location_index":0,"setup":0,"service":0,"waiting_time":0,"arrival":4547,"duration":4207,"violations":[]}],"violations":[]},{"vehicle":48,"cost":2204,"setup":0,"service":0,"duration":2204,"waiting_time":0,"priority":0,"steps":[{"type":"start","location_index":2,"setup":0,"service":0,"waiting_time":0,"arrival":0,"duration":0,"violations":[]},{"type":"job","location_index":3,"id":1717,"setup":0,"service":0,"waiting_time":0,"job":1717,"arrival":1102,"duration":1102,"violations":[]},{"type":"job","location_index":2,"id":1616,"setup":0,"service":0,"waiting_time":0,"job":1616,"arrival":2204,"duration":2204,"violations":[]},{"type":"end","location_index":2,"setup":0,"service":0,"waiting_time":0,"arrival":2204,"duration":2204,"violations":[]}],"violations":[]}]}

#hide

Solving options:

  -a, --host arg     host for the routing profile (default: car:0.0.0.0)
  -c, --choose-eta   choose ETA for custom routes and report violations
  -g, --geometry     add detailed route geometry and distance
  -h, --help         display this help and exit
  -i, --input arg    read input from a file rather than from stdin
  -l, --limit arg    stop solving process after 'limit' seconds
  -o, --output arg   write output to a file rather than stdout
  -p, --port arg     host port for the routing profile (default: car:5000)
  -r, --router arg   osrm, libosrm, ors or valhalla (default: osrm)
  -t, --threads arg  number of available threads (default: 4)
  -v, --version      output version information and exit
  -x, --explore arg  exploration level to use (0..5) (default: 5)

route_df_dic

{0:     index              name pickup delivery    load time_window(s) arrival  \
 0       0     start : トラック1    [0]      [0]     [0]     [0, 32400]       0   
 1       1      川崎市高津区久地1121   [50]      [0]    [50]   [[0, 25200]]    1190   
 2       2  川崎市多摩区宿河原5-30-11   [50]      [0]   [100]   [[0, 25200]]    2072   
 3       3      川崎市多摩区登戸3816   [50]      [0]   [150]   [[0, 25200]]    2980   
 4       4    川崎市麻生区細山3-17-2  [320]      [0]   [470]   [[0, 14400]]    4240   
 5       5   川崎市宮前区菅生3-41-14  [250]      [0]   [720]   [[0, 25200]]    5554   
 6       6      川崎市宮前区馬絹1451   [50]      [0]   [770]   [[0, 25200]]    6666   
 7       7       横浜市都筑区大棚町64   [50]      [0]   [820]   [[0, 25200]]    7869   
 8       8   横浜市都筑区川向町922-40  [150]      [0]   [970]   [[0, 25200]]    8892   
 9       9        横浜市戸塚区柏尾町1  [400]      [0]  [1370]   [[0, 14400]]   10876   
 10     10      横浜市戸塚区柏尾町380  [400]      [0]  [1770]   [[0, 25200]]   11476   
 11     11     横浜市戸塚区舞岡町3543  [150]      [0]  [1920]   [[0, 25200]]   12189   
 12     12       逗子市逗子7-2-38  [250]      [0]  [2170]   [[0, 25200]]   14326   
 13     13      横須賀市船越町1-201  [200]      [0]  [2370]   [[0, 25200]]   15530   
 14     14       川崎市幸区小倉1682  [150]      [0]  [2520]   [[0, 25200]]   18808   
 15     15   横浜市港北区日吉7-15-35  [165]      [0]  [2685]   [[0, 25200]]   19735   
 16     16    川崎市中原区井田中ﾉ町402   [50]      [0]  [2735]   [[0, 25200]]   20775   
 17     17   川崎市中原区宮内1-23-10   [50]      [0]  [2785]   [[0, 25200]]   21893   
 18     18   川崎市中原区宮内2-25-16  [150]      [0]  [2935]   [[0, 25200]]   22578   
 19     19    川崎市中原区上小田中1263   [50]      [0]  [2985]   [[0, 25200]]   23357   
 20     20       end : トラック1    [0]      [0]  [2985]     [0, 32400]   25478   
 
    service waiting_time duration  skills priority  
 0        0            0        0  [0, 1]        0  
 1      600            0     1190     [0]        1  
 2      600            0     1472     [0]        1  
 3      600            0     1780     [0]        1  
 4      600            0     2440     [0]        1  
 5      600            0     3154     [0]        1  
 6      600            0     3666     [0]        1  
 7      600            0     4269     [0]        1  
 8      600            0     4692     [0]        1  
 9      600            0     6076     [0]        1  
 10     600            0     6076     [0]        1  
 11     600            0     6189     [0]        1  
 12     600            0     7726     [0]        1  
 13     600            0     8330     [0]        1  
 14     600            0    11008     [0]        1  
 15     600            0    11335     [0]        1  
 16     600            0    11775     [0]        1  
 17     600            0    12293     [0]        1  
 18     600            0    12378     [0]        1  
 19     600            0    12557     [0]        1  
 20       0            0    14078  [0, 1]        0  ,
 1:    index                               name  pickup delivery    load  \
 0      0                      start : トラック2     [0]      [0]   [100]   
 1      1                     東京都台東区台東4-33-2   [400]      [0]   [500]   
 2      2                     東京都台東区小島2-8-14   [200]      [0]   [700]   
 3      3                     東京都台東区松が谷1-1-1  [1000]      [0]  [1700]   
 4      4                      東京都墨田区業平1-5-3   [150]      [0]  [1850]   
 5      5                  東京都江戸川区中葛西5-40-15   [165]    [100]  [1915]   
 6      6  千葉県千葉市美浜区真砂4-1-10ショッピングセンターPIA ２Ｆ   [165]      [0]  [2080]   
 7      7              千葉県千葉市花見川区幕張本郷2-22-15   [150]      [0]  [2230]   
 8      8                        end : トラック2     [0]      [0]  [2230]   
 
      time_window(s) arrival service waiting_time duration  skills priority  
 0        [0, 32400]   13684       0            0        0  [0, 1]        0  
 1  [[14400, 25200]]   14400     600            0      716  [0, 1]        1  
 2  [[14400, 25200]]   15116     600            0      832     [0]        1  
 3      [[0, 25200]]   15866     600            0      982     [0]        1  
 4      [[0, 25200]]   16752     600            0     1268     [0]        1  
 5  [[14400, 25200]]   18134     600            0     2050     [0]        1  
 6      [[0, 25200]]   20340     600            0     3656  [0, 1]        1  
 7      [[0, 25200]]   21254     600            0     3970     [0]        1  
 8        [0, 32400]   24262       0            0     6378  [0, 1]        0  ,
 2:     index                 name  pickup delivery    load    time_window(s)  \
 0       0        start : トラック3     [0]      [0]     [0]        [0, 32400]   
 1       1      横浜市瀬谷区五貫目町25-16    [50]      [0]    [50]      [[0, 14400]]   
 2       2      横浜市瀬谷区五貫目町25-16    [50]      [0]   [100]      [[0, 14400]]   
 3       3         大和市深見東2-1-12   [165]      [0]   [265]      [[0, 25200]]   
 4       4          大和市深見東1-3-6    [50]      [0]   [315]      [[0, 25200]]   
 5       5         大和市深見西1-1-37   [165]      [0]   [480]      [[0, 25200]]   
 6       6           大和市上和田2674   [400]      [0]   [880]      [[0, 25200]]   
 7       7              藤沢市桐原町8    [50]      [0]   [930]      [[0, 25200]]   
 8       8         藤沢市善行2-24-39    [50]      [0]   [980]      [[0, 14400]]   
 9       9        藤沢市湘南台1-32-10   [165]      [0]  [1145]      [[0, 25200]]   
 10     10                break     [0]      [0]  [1145]    [14400, 18000]   
 11     11       神奈川県藤沢市高倉947-4   [320]      [0]  [1465]  [[18000, 25200]]   
 12     12          藤沢市遠藤2002-4    [50]      [0]  [1515]      [[0, 25200]]   
 13     13         藤沢市遠藤2021-11    [50]      [0]  [1565]      [[0, 25200]]   
 14     14     神奈川県綾瀬市寺尾中1-1394  [1000]      [0]  [2565]  [[18000, 25200]]   
 15     15         大和市桜森3-16-17    [50]      [0]  [2615]      [[0, 25200]]   
 16     16         大和市鶴間2-12-15   [165]      [0]  [2780]      [[0, 25200]]   
 17     17  神奈川県横浜市緑区長津田5801-11   [200]      [0]  [2980]  [[18000, 25200]]   
 18     18          end : トラック3     [0]      [0]  [2980]        [0, 32400]   
 
    arrival service waiting_time duration  skills priority  
 0     5115       0            0        0  [0, 1]        0  
 1     7716     600            0     2601     [0]        1  
 2     8316     600            0     2601     [0]        1  
 3     9301     600            0     2986     [0]        1  
 4     9971     600            0     3056     [0]        1  
 5    10711     600            0     3196     [0]        1  
 6    11964     600            0     3849     [0]        1  
 7    13274     600            0     4559     [0]        1  
 8    14260     600            0     4945     [0]        1  
 9    15234     600            0     5319     [0]        1  
 10   15834    1860            0     5319    None     None  
 11   18000     600            0     5625     [0]        1  
 12   19244     600            0     6269     [0]        1  
 13   19844     600            0     6269     [0]        1  
 14   21257     600            0     7082     [0]        1  
 15   22246     600            0     7471  [0, 1]        1  
 16   23269     600            0     7894     [0]        1  
 17   24584     600            0     8609  [0, 1]        1  
 18   27284       0            0    10709  [0, 1]        0  ,
 3:    index              name  pickup delivery    load    time_window(s) arrival  \
 0      0     start : トラック4     [0]      [0]   [100]        [0, 32400]    3808   
 1      1   埼玉県浦和市内谷2-10-14   [200]      [0]   [300]      [[0, 25200]]    4906   
 2      2  埼玉県上尾市日の出1-10-22   [165]      [0]   [465]      [[0, 25200]]    6329   
 3      3        埼玉県上尾市上304   [400]      [0]   [865]      [[0, 25200]]    7190   
 4      4    埼玉県鶴ヶ島市脚折5-4-6   [580]    [100]  [1345]      [[0, 25200]]    9433   
 5      5     埼玉県日高市下大谷沢546    [50]      [0]  [1395]      [[0, 25200]]   10496   
 6      6  埼玉県入間郡大井町苗間226-1   [250]      [0]  [1645]      [[0, 25200]]   12268   
 7      7  東京都練馬区下石神井4-6-16  [1000]      [0]  [2645]  [[14400, 25200]]   14400   
 8      8       end : トラック4     [0]      [0]  [2645]        [0, 32400]   16106   
 
   service waiting_time duration  skills priority  
 0       0            0        0  [0, 1]        0  
 1     600            0     1098     [0]        1  
 2     600            0     1921     [0]        1  
 3     600            0     2182     [0]        1  
 4     600            0     3825     [0]        1  
 5     600            0     4288     [0]        1  
 6     600            0     5460     [0]        1  
 7     600            0     6992     [0]        1  
 8       0            0     8098  [0, 1]        0  ,
 4:    index               name  pickup delivery    load    time_window(s)  \
 0      0      start : トラック5     [0]      [0]     [0]        [0, 32400]   
 1      1  東京都東村山市美住町2-18-41   [150]      [0]   [150]  [[18000, 25200]]   
 2      2   東京都立川市高松町1-24-36  [1000]      [0]  [1150]  [[14400, 25200]]   
 3      3     東京都八王子市片倉町1781  [1000]      [0]  [2150]  [[14400, 25200]]   
 4      4     東京都八王子市高倉町54-6    [50]      [0]  [2200]  [[14400, 25200]]   
 5      5    東京都八王子市高倉町55-10   [500]      [0]  [2700]  [[14400, 25200]]   
 6      6      東京都府中市緑町2-6-3   [250]      [0]  [2950]  [[14400, 25200]]   
 7      7        end : トラック5     [0]      [0]  [2950]        [0, 32400]   
 
   arrival service waiting_time duration  skills priority  
 0   15974       0            0        0  [0, 1]        0  
 1   18000     600            0     2026     [0]        1  
 2   19234     600            0     2660     [0]        1  
 3   21035     600            0     3861  [0, 1]        1  
 4   22083     600            0     4309     [0]        1  
 5   22683     600            0     4309     [0]        1  
 6   24294     600            0     5320     [0]        1  
 7   26815       0            0     7241  [0, 1]        0  ,
 5:    index              name  pickup delivery    load    time_window(s) arrival  \
 0      0     start : トラック6     [0]      [0]     [0]        [0, 32400]   13032   
 1      1     東京都目黒区鷹番1-1-4  [1000]      [0]  [1000]      [[0, 25200]]   13173   
 2      2             break     [0]      [0]  [1000]    [14400, 18000]   14400   
 3      3  東京都渋谷区神宮前4-32-16   [320]      [0]  [1320]  [[14400, 25200]]   16260   
 4      4    東京都世田谷区北沢5-6-3  [1000]      [0]  [2320]  [[14400, 25200]]   17244   
 5      5       end : トラック6     [0]      [0]  [2320]        [0, 32400]   18468   
 
   service waiting_time duration  skills priority  
 0       0            0        0  [0, 1]        0  
 1     600            0      141     [0]        1  
 2    1860            0      768    None     None  
 3     600            0      768     [0]        1  
 4     600            0     1152     [0]        1  
 5       0            0     1776  [0, 1]        0  ,
 6:     index               name pickup delivery    load    time_window(s)  \
 0       0      start : トラック7    [0]      [0]   [100]        [0, 32400]   
 1       1       横浜市青葉区榎が丘6-2   [50]      [0]   [150]      [[0, 14400]]   
 2       2   神奈川県座間市広野台2-5000    [0]      [0]   [150]      [[0, 25200]]   
 3       3          厚木市三田3000  [200]      [0]   [350]      [[0, 14400]]   
 4       4       愛甲郡愛川町中津4056  [165]      [0]   [515]      [[0, 14400]]   
 5       5       相模原市田名3357-1  [165]      [0]   [680]      [[0, 25200]]   
 6       6       相模原市田名2696-1  [400]      [0]  [1080]      [[0, 25200]]   
 7       7     津久井郡藤野町小渕321-1   [50]      [0]  [1130]      [[0, 25200]]   
 8       8      相模原市宮下3-15-15  [165]      [0]  [1295]      [[0, 14400]]   
 9       9       相模原市宮下3-2-21   [50]      [0]  [1345]      [[0, 25200]]   
 10     10      相模原市南橋本3-2-25  [200]      [0]  [1545]      [[0, 25200]]   
 11     11        相模原市下九沢1082  [400]      [0]  [1945]      [[0, 25200]]   
 12     12      相模原市清新8-18-10   [50]      [0]  [1995]      [[0, 25200]]   
 13     13   神奈川県相模原市大野台6-3-5   [50]      [0]  [2045]  [[18000, 25200]]   
 14     14     東京都町田市原町田3-2-8  [580]    [100]  [2525]  [[14400, 25200]]   
 15     15       川崎市高津区宇奈根777  [150]      [0]  [2675]      [[0, 25200]]   
 16     16     川崎市高津区宇奈根728-2  [150]      [0]  [2825]      [[0, 25200]]   
 17     17  神奈川県横浜市緑区霧ヶ丘2-9-8  [165]      [0]  [2990]  [[18000, 25200]]   
 18     18        end : トラック7    [0]      [0]  [2990]        [0, 32400]   
 
    arrival service waiting_time duration  skills priority  
 0      488       0            0        0  [0, 1]        0  
 1     2470     600            0     1982     [0]        1  
 2     4283     600            0     3195     [0]        1  
 3     5800     600            0     4112     [0]        1  
 4     6939     600            0     4651     [0]        1  
 5     8267     600            0     5379     [0]        1  
 6     8867     600            0     5379  [0, 1]        1  
 7    11201     600            0     7113     [0]        1  
 8    13641     600            0     8953     [0]        1  
 9    14241     600            0     8953     [0]        1  
 10   15232     600            0     9344     [0]        1  
 11   15999     600            0     9511     [0]        1  
 12   16759     600            0     9671  [0, 1]        1  
 13   18000     600            0    10312     [0]        1  
 14   19167     600            0    10879     [0]        1  
 15   21441     600            0    12553     [0]        1  
 16   22041     600            0    12553     [0]        1  
 17   23632     600            0    13544     [0]        1  
 18   25117       0            0    14429  [0, 1]        0  ,
 7:     index               name pickup delivery    load    time_window(s)  \
 0       0      start : トラック8    [0]      [0]     [0]        [0, 32400]   
 1       1       横浜市泉区和泉町3321   [50]      [0]    [50]      [[0, 14400]]   
 2       2             積み込み地点   [11]      [0]    [61]   [[7200, 14400]]   
 3       3          海老名市本郷520   [50]      [0]   [111]      [[0, 14400]]   
 4       4     高座郡寒川町倉見1790-3   [50]      [0]   [161]      [[0, 14400]]   
 5       5      神奈川県伊勢原市鈴川5-6  [400]      [0]   [561]      [[0, 14400]]   
 6       6            伊勢原市鈴川5   [50]      [0]   [611]      [[0, 14400]]   
 7       7            伊勢原市鈴川5  [400]      [0]  [1011]      [[0, 14400]]   
 8       8           秦野市曽屋400  [150]      [0]  [1161]      [[0, 25200]]   
 9       9         小田原市成田1060   [50]      [0]  [1211]      [[0, 25200]]   
 10     10  神奈川県小田原市寿町2-10-10  [500]      [0]  [1711]  [[18000, 25200]]   
 11     11         平塚市代官町29-3   [50]      [0]  [1761]      [[0, 25200]]   
 12     12         平塚市代官町29-3  [400]      [0]  [2161]      [[0, 25200]]   
 13     13         平塚市代官町29-3  [400]      [0]  [2561]      [[0, 25200]]   
 14     14         平塚市浅間町12-8  [150]      [0]  [2711]      [[0, 25200]]   
 15     15          平塚市田村6770   [50]      [0]  [2761]      [[0, 25200]]   
 16     16       海老名市河原口577-3  [150]      [0]  [2911]      [[0, 25200]]   
 17     17            積み降ろし地点    [0]     [11]  [2900]  [[25200, 39600]]   
 18     18        end : トラック8    [0]      [0]  [2900]        [0, 32400]   
 
    arrival service waiting_time duration  skills priority  
 0     2959       0            0        0  [0, 1]        0  
 1     6569     600            0     3610     [0]        1  
 2     7531    1200            0     3972     [0]        1  
 3     9633     600            0     4874     [0]        1  
 4    10455     600            0     5096     [0]        1  
 5    12268     600            0     6309     [0]        1  
 6    12868     600            0     6309     [0]        1  
 7    13468     600            0     6309     [0]        1  
 8    14899     600            0     7140     [0]        1  
 9    16945     600            0     8586     [0]        1  
 10   18000     600            0     9041     [0]        1  
 11   20224     600            0    10665     [0]        1  
 12   20824     600            0    10665     [0]        1  
 13   21424     600            0    10665     [0]        1  
 14   22229     600            0    10870     [0]        1  
 15   23452     600            0    11493     [0]        1  
 16   25007     600            0    12448     [0]        1  
 17   26496    1200            0    13337     [0]        1  
 18   30775       0            0    16416  [0, 1]        0  }