配送計画システム METRO とその使用法
はじめに
配送計画モデルは，我が国では最も普及しているロジスティクス・ツールである配送計画システムの基幹を成すモデルである． 本来ならば，配送だけでなく集荷にも使われるので運搬経路問題（vehicle routing problem）と よぶのが学術用語としては正しい使い方だが，「運搬」という言葉のイメージが悪いためか， 実務家および研究者の間でも「配送計画」とよばれることが多いので，ここでもそれにならうものとする．
一般に，古典的な配送計画モデルの基本形は以下の仮定をもつ．
- デポとよばれる特定の地点を出発した運搬車が，顧客を経由し再びデポに戻る．このとき運搬車による顧客の通過順をルートとよぶ．
- デポに待機している運搬車の種類および最大積載重量は既知である．
- 顧客の位置は既知であり，各顧客の需要量も事前に与えられている．
- 地点間の移動時間，移動距離，移動費用は既知である．
- 1つのルートに含まれる顧客の需要量の合計は運搬車の最大積載重量を超えない．
- 運搬車の台数は，決められた上限を超えない．（超過した運搬車に対するレンタル料を考える場合や，ルートに含めない顧客に対するペナルティを与える場合もある．）
- 運搬車の稼働時間が与えられた上限を超えない．（超過時間を残業費用として考える場合もある．）
配送計画の応用としては，小売店への配送計画，スクールバスの巡回路決定，郵便や新聞の配達，ゴミの収集，燃料の配送などがある． もちろん，これらの応用に適用する際には，上の基本条件に新たな条件を付加する必要がある．
ここで考えるのは，ほとんどの実際問題を解けるようにするために，以下の一般化をした配送計画モデルである．
- 複数時間枠制約付き
- 多次元容量非等質運搬車
- 配達・集荷
- 積み込み・積み降ろし
- 複数休憩条件付き
- スキル条件付き
- 優先度付き
- パス型許容
- 複数デポ
# # 度単位10進数形式
# # 緯度： 33 + ( 51 * 60 + 10.59 ) /3600 = 33.852942
# # 経度： 130 + ( 45 * 60 + 17.86 ) / 3600 = 130.75496
# longitude, latitude =[],[]
# for i in cust_df["経度"]:
# row = i[1:].split(".")
# degree = list(map(float, [row[0],row[1],row[2]+"."+row[3]]))
# longitude.append(degree[0]+(degree[1]*60+ degree[2])/3600.)
# for i in cust_df["緯度"]:
# row = i[1:].split(".")
# degree = list(map(float, [row[0],row[1],row[2]+"."+row[3]]))
# latitude.append(degree[0]+(degree[1]*60+ degree[2])/3600.)
# cust_df["経度"] = longitude
# cust_df["緯度"] = latitude
# #cust_df.to_csv("metro-sample2000.csv")
#plotly.offline.plot(fig);
地点 node
地点は顧客，積み込み積み下ろし地点，運搬車の発着地を順に並べたものである．最適化に使うのは経度・緯度の情報を保持したlocation列だけである． 移動時間の計算に地図を使用する場合には，以下のデータフレームで保持しているので必要はない．
移動時間を地図で計算しない場合には，この地点の番号を参照し，移動時間を計算したデータ（移動時間データ）を参照する．
例題においては，地点データの番号は以下の順に保管されている．
- ジョブ job に対応する顧客
- 輸送 shipment の積み込み地点に対応する顧客
- 輸送 shipment の積み降ろし地点に対応する顧客
- 運搬車のデポ
したがって，地点の数は，「ジョブ数 $+$ 輸送数 $\times 2 +$ デポ数」となる．
node_df = pd.read_csv(folder +"node.csv", index_col=0)
node_df.head()
ジョブ 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()
輸送 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()
運搬車 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()
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
durations, distances = compute_distance_table_for_vrp(node_df, toll=False, host=host)
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);
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()
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()
ノードデータを正規分布にしたがってランダムに生成する関数 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のとき；それ以外のときは，空の文字列""を返す．）
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()
配送計画問題例の生成関数 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: 運搬車データフレーム
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()
node_df.head()
job_df.head()
shipment_df.head()
vehicle_df.head()
time_df.head()
break_df
# pprint(model["jobs"][0])
ルートデータフレーム生成関数 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: 未割り当ての輸送のデータフレーム
# 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(1000, "2000-01-01 00:00:00")
#plotly.offline.plot(fig);
# 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);
描画関数 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の地図オブジェクト
# 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の地図オブジェクト
# plotly.offline.plot(fig);