配送計画システム 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
0 truck0 [139.92142527,35.67868735] 7 [] NaN [2209] [0, 36000] [0,1]

休憩 break

  • description: 休憩の説明
  • time_window: 休憩をとる時間枠((最早時刻と最遅時刻の組(タプル))のリスト
  • 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

データ生成

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

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

引数:

  • node_df: ノードデータフレーム(緯度経度情報を含む)

返値:

  • durations: 地点間の移動時間の配列
  • distances: 地点間の距離の配列

compute_distance_table_for_vrp[source]

compute_distance_table_for_vrp(node_df)

compute_distance_table_for_vrp関数の使用例

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

durations,  distances = compute_distance_table_for_vrp(node_df)
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);

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

引数:

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

返値:

  • node_df: 顧客データフレーム
  • time_df: 移動時間データフレーム(matrix引数がTrueのとき;それ以外のときは,空の文字列""を返す.)

generate_node[source]

generate_node(df, n, random_seed=1, prefecture=None, matrix=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のとき;それ以外のときは,空の文字列""を返す.)

generate_node_normal[source]

generate_node_normal(n, lat_center, lon_center, std=0.1, country_code='ja_JP', random_seed=1, matrix=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: 1ルートあたりの配達件数
  • skill_flag = False: スキルを考慮した問題例とするときTrue
  • breaks = None: 休憩の番号のリスト.既定値は「なし」を表す None. 例における休憩データの場合で,昼食だけの場合は[0],昼食と夕食の場合は[0,1]と設定する.

返値:

  • job_df: ジョブデータフレーム
  • shipment_df: 輸送データフレーム
  • vehicle_df: 運搬車データフレーム

generate_vrp[source]

generate_vrp(node_df, num_depots=1, open_flag=False, 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), load_factor=0.9, num_customers_per_route=5, skill_flag=False, breaks=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 = 14
num_shipments = 1
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])
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 支店 913 [100] [683] [[7108, 16108], [26689, 35689]] [139.48372896,36.08020962] 0 [0] 23
1 有限会社阿部運輸 第 73 支店 1113 [54] [849] [[1612, 10612], [21098, 30098]] [139.3262383,35.96836517] 1 [0] 55
2 株式会社村上印刷 第 98 支店 916 [73] [608] [[1844, 10844], [20669, 29669]] [139.19460618,36.05815305] 2 [0] 65
3 佐藤印刷合同会社 第 9 支店 809 [73] [490] [[15, 9015], [20244, 29244]] [139.66804321,36.09307749] 3 [0] 77
4 合同会社青木水産 第 33 支店 864 [91] [381] [[7906, 16906], [19306, 28306]] [139.51107504,35.90863789] 4 [0] 3
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] 株式会社小川印刷 第 63 支店 835 [[905, 9905], [20763, 29763]] [139.46293794,35.82373752] 14 有限会社橋本情報 第 4 支店 672 [[7395, 16395], [22644, 31644]] [139.51471034,36.05771354] 15 [0] 1
vehicle_df.head()
name start start_index end end_index capacity time_window skills breaks
0 truck0 [139.74548574,36.01159379] 16 [139.74548574,36.01159379] 16 [2785] [0, 36000] [0] [0]
1 truck1 [139.74548574,36.01159379] 16 [139.74548574,36.01159379] 16 [2785] [0, 36000] [0] [0]
2 truck2 [139.74548574,36.01159379] 16 [139.74548574,36.01159379] 16 [2785] [0, 36000] [0] [0]
3 truck3 [139.74548574,36.01159379] 16 [139.74548574,36.01159379] 16 [2785] [0, 36000] [0] [0]
4 truck4 [139.74548574,36.01159379] 16 [139.74548574,36.01159379] 16 [2785] [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 支店 2463 27425
2 0 合同会社前田建設 第 18 支店 2 株式会社村上印刷 第 98 支店 1975 34842
3 0 合同会社前田建設 第 18 支店 3 佐藤印刷合同会社 第 9 支店 1501 22322
4 0 合同会社前田建設 第 18 支店 4 合同会社青木水産 第 33 支店 1381 22666
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ファイルの元になる辞書)

build_model_for_vrp[source]

build_model_for_vrp(job_df, shipment_df, vehicle_df, break_df, time_df=None)

build_model_for_vrp関数の使用例

model = build_model_for_vrp(job_df, shipment_df, vehicle_df,  break_df, time_df)
pprint(model["jobs"][0])
{'delivery': [683],
 'description': '合同会社前田建設 第 18 支店',
 'id': 0,
 'location': [139.48372896, 36.08020962],
 'location_index': 0,
 'pickup': [100],
 'priority': 23,
 'service': 913,
 'skills': [0],
 'time_windows': [[7108, 16108], [26689, 35689]]}

ルートデータフレーム生成関数 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: 未割り当ての輸送のデータフレーム

make_route_for_vrp[source]

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]
---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
~/Library/Caches/pypoetry/virtualenvs/scmopt-HY5JLThu-py3.8/lib/python3.8/site-packages/pandas/core/indexes/base.py in get_loc(self, key, method, tolerance)
   3079             try:
-> 3080                 return self._engine.get_loc(casted_key)
   3081             except KeyError as err:

pandas/_libs/index.pyx in pandas._libs.index.IndexEngine.get_loc()

pandas/_libs/index.pyx in pandas._libs.index.IndexEngine.get_loc()

pandas/_libs/hashtable_class_helper.pxi in pandas._libs.hashtable.PyObjectHashTable.get_item()

pandas/_libs/hashtable_class_helper.pxi in pandas._libs.hashtable.PyObjectHashTable.get_item()

KeyError: 'time_window'

The above exception was the direct cause of the following exception:

KeyError                                  Traceback (most recent call last)
<ipython-input-74-8b65876cd818> in <module>
      3     output_dic = json.load(example1_out)
      4 
----> 5 route_df_dic, unassigned_job_df, unassigned_shipment_df = make_route_for_vrp(job_df, shipment_df, vehicle_df, break_df, output_dic)
      6 
      7 #ルートデータフレームの最初のルートを表示

<ipython-input-58-a5399211947f> in make_route_for_vrp(job_df, shipment_df, vehicle_df, break_df, output_dic)
     47                 name = "break"
     48                 pickup = delivery =[0]
---> 49                 tw = break_df.iloc[d["id"]]["time_window"]
     50                 skills = None
     51                 priority = None

~/Library/Caches/pypoetry/virtualenvs/scmopt-HY5JLThu-py3.8/lib/python3.8/site-packages/pandas/core/series.py in __getitem__(self, key)
    822 
    823         elif key_is_scalar:
--> 824             return self._get_value(key)
    825 
    826         if is_hashable(key):

~/Library/Caches/pypoetry/virtualenvs/scmopt-HY5JLThu-py3.8/lib/python3.8/site-packages/pandas/core/series.py in _get_value(self, label, takeable)
    930 
    931         # Similar to Index.get_value, but we do not fall back to positional
--> 932         loc = self.index.get_loc(label)
    933         return self.index._get_values_for_loc(self, loc, label)
    934 

~/Library/Caches/pypoetry/virtualenvs/scmopt-HY5JLThu-py3.8/lib/python3.8/site-packages/pandas/core/indexes/base.py in get_loc(self, key, method, tolerance)
   3080                 return self._engine.get_loc(casted_key)
   3081             except KeyError as err:
-> 3082                 raise KeyError(key) from err
   3083 
   3084         if tolerance is not None:

KeyError: 'time_window'

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

引数:

  • sec: 秒数
  • start: 開始時刻を表す文字列(年,月,日,時間,分,秒で,"2000-01-01 00:00:00"のような形式で入力する.)

返値:

  • 開始時刻startからsec秒経過した時刻

time_convert[source]

time_convert(sec, start)

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

time_convert関数の使用例

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

ガントチャート生成関数

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

引数:

  • route_df_dic: キーをルート番号とし,ルートの情報を格納したデータフレームを値とした辞書
  • start: 開始時刻を表す文字列(年,月,日,時間,分,秒で,"2000-01-01 00:00:00"のような形式で入力する.)

返値:

  • fig: plotlyの図オブジェク

gannt_for_vrp[source]

gannt_for_vrp(route_df_dic, start='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の図オブジェクト

make_tw_fig_for_vrp[source]

make_tw_fig_for_vrp(job_df, shipment_df, start='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: ルートの図オブジェクトのリスト

add_route_for_vrp[source]

add_route_for_vrp(output_dic, map_style=0)

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

引数:

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

返値:

  • data: ルート(通過道路)の図オブジェクトのリスト

add_road_for_vrp[source]

add_road_for_vrp(output_dic, map_style=0)

描画関数 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の地図オブジェクト

make_fig_for_vrp[source]

make_fig_for_vrp(input_dic, output_dic, show_mode='node', map_style=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="road", map_style = 0 )
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ターンと移動時間の兼ね合いを考えて自動選択する.

返値:

  • fig: plotlyの地図オブジェクト

make_detailed_route[source]

make_detailed_route(input_dic, output_dic, route_df_dic, route_id=0, matrix=False, map_style=0, straight=None)

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

make_detailed_route関数の使用例

fig = make_detailed_route(input_dic, output_dic, route_df_dic, route_id=3, 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のとき,ソルバー呼び出し時に生成されるファイルにタイムスタンプを追加し,計算終了後にファイルを消去する.

返値:

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

optimize_vrp[source]

optimize_vrp(model, matrix=False, threads=4, explore=1, cloud=False)

実行例

%%time
#問題例読み込み

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

no = "07"
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,cloud=True)

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= 35459
CPU times: user 18.1 ms, sys: 10.5 ms, total: 28.5 ms
Wall time: 67.8 ms
unassigned_job_df

例題

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

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