サービスネットワーク設計 SENDO (SErvice Network Design Optimizer)

簡易システムの紹介ビデオ

サービスネットワーク設計最適化システム SENDO

はじめに

ロジスティクス・ネットワークが供給地点から需要地点への,一方向的な「もの」の流れを扱うのに対して, サービス・ネットワークでは,発地と着地の間に輸送される,多対多の「もの」の流れを扱う. ロジスティクス・ネットワークにおいては,顧客需要の不確実性やサービス・レベルの要求などの条件を満たすために, ネットワーク内の地点で在庫を適切に管理することが重要になる. それに対して,サービス・ネットワークにおいては,基本的には途中で在庫することなく, 発地から着地へ「もの」が流れていく. (ただし,輸送のタイミングをとるために,一時保管することは許される.)

サービス・ネットワーク設計問題(consolidation transportation network design problem)は, しばしば混載ネットワーク設計問題ともよばれる. しかし,我が国における実務家の間では,「混載」という用語が「異なる種類の製品の積み合わせ」という意味で用いられ,本モデルでは,同じ種類の製品の積み合わせが主な応用であるため, 混乱を避ける意味でサービス・ネットワーク設計問題とよぶことにする. ここで考えるモデルでは, 主に(郵便物や宅配便のように)発地・着地が異なる同じ種類の製品の積み合わせを対象とする 場合が多いが,異なる種類の製品の積み合わせ(いわゆる業界用語での混載)への適用も可能である.

配送計画は,比較的短距離の輸送を計画するためのモデルであるが, サービス・ネットワーク設計では比較的長距離の輸送を対象とする. そのため,途中での積み替えを考慮する必要が出てくる. これが,ここで考えるサービス・ネットワーク設計が, 配送計画と異なったアプローチを必要とする理由である. 配送計画においては,積み替えを考慮する必要がなかったので,運搬車の移動経路を求めれば, 荷(品目)の移動は自動的に定まった.一方,サービス・ネットワーク設計においては, 積み替えを考慮する必要があるので,運搬車の流れのみならず,荷の流れが意思決定項目となり, これによって問題の難しさが増大する.

ここで考えるモデルは,実務から生まれたものであり,以下の仮定に基づく.

  • (load)とは,地点間を移動させる「モノ」の総称である.ネットワーク理論では品種(commodity) とよばれるが,ここでは現実問題を想定していることを強調するために荷とよぶことにする. 荷は,その移動によって利益を生む資源の総称である. 荷が最初に出発する(最後に到着する)地点を荷の発地(着地)とよび,あらかじめ決められている. ネットワーク理論では,発地(source)は始点もしくは発生点,着地(sink, terminal)は終点もしくは集中点とよばれるが,以下では,発地,着地とよぶものとする.

  • 荷は途中で分岐してはならない.言い換えれば,荷の発地から着地までの移動経路は,1本のパスでなければならない.

  • 宅配便や郵便事業などへの応用では,さらに荷の移動に入木条件とよばれる制約が付加される. 入木条件とは,着地が同じ荷のパスが合流したら,その後のパスは同じ経路にならなければならないことを規定する. これは,集荷した荷物を積み替え(ソーティング)する際に,現場でのオペレーションの簡便性のため, 着地の情報だけを利用するためである. 実際に,東京行きの荷物という荷の集まりは,様々な発地からの荷が集約されたものであり,これを発地別に分けて 異なる方面行きの運搬車に積み替えることは (たとえそれによって費用が減少する可能性があっても)現実には行われないのである.

  • 運搬車(トラック)の積載容量は既知であり,積載される荷量の合計は積載容量を超えない.

  • 地点間の運搬車の移動費用は既知である.

  • 中継地点での積替え費用は荷量によって定まり,既知である.

  • 運搬車は出発地点に戻ってくる必要はない.(この仮定を緩めるのは比較的容易である.)

上のサービス・ネットワーク設計モデルに対して,数理最適化(ならびに制約最適化)ソルバーを利用した専用解法を構築する.

データの読み込み

  • dc_df : 倉庫(拠点)データフレーム
  • od_df : OD需要データフレーム
od_df = pd.read_csv(folder +"od.csv", index_col=0)
Demand = od_df.values
#Demand
dc_df = pd.read_csv(folder+"DC.csv", index_col=0)
n = len(dc_df)
dc_df.head()
name lb ub fc vc lat lon
0 札幌市 0.0 5732551.52 10037 0.432510 43.06417 141.34694
1 青森市 0.0 5732551.52 10235 0.414573 40.82444 140.74000
2 盛岡市 0.0 5732551.52 10908 0.414802 39.70361 141.15250
3 仙台市 0.0 5732551.52 10072 0.136525 38.26889 140.87194
4 秋田市 0.0 5732551.52 10767 0.029622 39.71861 140.10250
trace1 = go.Histogram(
    x= [ Demand[i,j] for i in range(n) for j in range(n) ], 
    opacity=0.5,
    name="OD間需要"
)

data = [trace1]
layout = go.Layout(
    title='OD間需要量',
    xaxis=dict(
        title="需要量"
    ),
    yaxis=dict(
        title='件数'
    )
)
fig = go.Figure(data=data, layout=layout)
plotly.offline.plot(fig);

第k最短路を解くための関数

引数:

  • G : NetworkXのグラフ
  • source : 始点
  • sink : 終点
  • k : 第k最短路(単純パス)を求める。
  • weight : 移動距離を評価するための枝の属性名

返値:

  • cost_list : k本のパスの費用を入れたリスト
  • path_list : k本のパス(点列のタプル)を入れたリスト

k_th_sp[source]

k_th_sp(G, source, sink, k, weight='weight')

Find k-th shortest paths and returns path and its cost

サービスネットワーク設計モデル sndp

サービスネットワーク設計問題に対するパス型のモデル

引数:

  • K : 発生点と到着点の対を入れたリスト
  • all_paths = set of all paths
  • paths[o,d] = set of all paths from o to d
  • path_od[p] = dictionary that maps a path (tuple) to its origin-destination pair (tuple)
  • path_id[p] = dictionary that maps a path to its ID
  • paths_through[v,w] = set of paths through edge (v,w)

返値:

  • model: 最適化された後のモデルファイル.model.__data に解(x,y,total_transfer_cost, total_vehicle_cost)が保管されている. 最適化の状態は, model.Statusで確認できる.Statusの値はGurobiに準じており,以下の通り.

  • OPTIMAL = 1

  • INFEASIBLE = 3
  • INF_OR_UNBD = 4
  • UNBOUNDED = 5
  • UNDEFINED = None

sndp[source]

sndp(K, all_paths, paths, path_id, path_od, paths_through, Demand, Distance, transfer_cost, capacity, relax=False, cpu=10.0)

サービスネットワーク設計問題に対するパス型のモデル

add_shortest_paths[source]

add_shortest_paths(G, K, all_paths, paths, path_id, path_od, paths_through, k=1)

各地点間の第k最短路を計算し、追加する関数

結果のデータフレーム生成関数 make_result

make_result[source]

make_result(Demand, cust_df, K, paths, path_id, path_od, paths_through, x, y)

サービスネットワーク設計問題の可視化関数 draw_snd_all

draw_snd_all[source]

draw_snd_all(dc_df, x, y, pos, paths, path_id)

可視化関数

サービスネットワーク設計問題を解くための関数 solve_sndp

引数:

  • dc_df: 倉庫データフレーム(緯度・経度情報,容量,変動費用(積替え費用)を利用)
  • od_df: 発地・着地間の需要量を保管したデータフレーム
  • cost_per_dis: 1kmあたりの運搬車の変動費用(人件費を含まず)
  • cost_per_time: 1時間あたりの運搬車の変動費用
  • capacity: 運搬車の積載容量
  • max_cpu: 最大CPU時間
  • scaling: 勾配スケーリング法を用いるとき True
  • k: 最短路の本数
  • alpha: 勾配スケーリング法のパラメータ
  • max_iter: 勾配スケーリング法の最大反復回数
  • osrm: 地図 (OSRM) を利用するとき True

返値:

  • path_df: 解のパス情報を保管したデータフレーム
  • vehicle_df: 解の運搬車情報を保管したデータフレーム
  • cost_df: 費用の内訳を表すデータフレーム
  • fig: 図オブジェクト

solve_sndp[source]

solve_sndp(dc_df, od_df, cost_per_dis, cost_per_time, capacity, max_cpu=10, scaling=True, k=10, alpha=0.5, max_iter=100, osrm=False)

サービスネットワーク設計問題を解くための関数

solve_sndp関数の使用例

dc_df = pd.read_csv(folder + "DC.csv", index_col=0) #ub =base capacity, vc = transfer cost
od_df = pd.read_csv(folder + "od.csv", index_col=0)

# 問題のサイズの縮小
n= 10
dc_df = dc_df.iloc[:n,:]
od_df = od_df.iloc[:n,:n]

try:
# just MIP
    #path_df, vehicle_df, cost_df, fig = solve_sndp(dc_df, od_df, cost_per_dis=20, cost_per_time=8000, capacity=1000., max_cpu = 10, scaling=False, k=10, alpha=0.9, max_iter = 10, osrm = False)
# slope scaling + column generation
    path_df, vehicle_df, cost_df, fig = solve_sndp(dc_df, od_df, cost_per_dis=20, cost_per_time=8000, capacity=1000., max_cpu = 10, scaling=True, k=10, alpha=0.5, max_iter = 10, osrm = False)
except SolverError as e:
    print(e)
Demand = od_df.values
od_df
札幌市 青森市 盛岡市 仙台市 秋田市 山形市 福島市 水戸市 宇都宮市 前橋市
name
札幌市 0.000000 748.604013 503.880787 479.530853 434.728978 325.400616 387.515654 380.707553 320.950984 306.975814
青森市 366.911870 0.000000 349.739599 216.591680 300.250555 146.736232 161.797705 137.690614 117.949336 110.061161
盛岡市 244.733739 346.578201 0.000000 374.849054 440.904081 236.165870 241.756337 178.105294 151.641357 135.078213
仙台市 316.873079 292.012168 509.987066 0.000000 420.427689 1732.062426 1488.646715 574.094165 492.841131 390.859150
秋田市 188.101580 265.062360 392.782315 275.293764 0.000000 199.309319 195.354280 142.173921 125.495887 115.713660
山形市 148.099418 136.258227 221.302373 1192.970578 209.647039 0.000000 864.339836 280.457384 255.262338 206.987265
福島市 230.485306 196.343595 296.050510 1339.913763 268.536343 1129.545011 0.000000 646.117267 588.446899 425.126180
水戸市 280.695094 207.127638 270.367267 640.556839 242.264298 454.333986 800.941289 0.000000 2276.291965 1030.798300
宇都宮市 194.660712 145.957188 189.361294 452.353290 175.911907 340.166357 600.057519 1872.510381 0.000000 1138.705559
前橋市 186.327252 136.300264 168.807399 359.024193 162.324098 276.045623 433.846478 848.599135 1139.578020 0.000000
vehicle_df.head()
from_id to_id from to flow number
0 0 1 札幌市 青森市 2721.081032 3.0
1 0 3 札幌市 仙台市 1167.214220 2.0
2 1 0 青森市 札幌市 2156.888050 3.0
3 1 2 青森市 盛岡市 991.311000 1.0
4 1 4 青森市 秋田市 1061.632374 2.0
cost_df
cost value
0 transfer 95017.015
1 vehicle 2161830.800