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

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

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

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

はじめに

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

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

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

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

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

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

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

  • 運搬車（トラック）の積載容量は既知であり，積載される荷量の合計は積載容量を超えない．

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

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

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

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

#hide ## モデルの定式化 サービスネットワーク設計問題の定式化を示す. ターミナル間の需要量の予測値をもとに，各ターミナルに対して，他のターミナル行きの荷物を，どのターミナルに輸送すれば良いのかを指示する． 以下に,定式化を行うために必要な記号と集合を説明した後に,定式化を示す.

集合:

  • \(G=(N,A)\): 有向グラフ:；点集合はターミナルの集合，枝集合は移動可能な点対の集合．

  • \(K\): 発ターミナル・着ターミナルの組（これを品種と呼ぶ）の集合．

  • \(P_k\): 品種 \(k \in K\) に対するパスの集合． すべてのパスの集合を \(P\) とする．

  • \(A_{pk}\): 品種 \(k\) に対するパス \(p\) （これをパス \(p,k\) と呼ぶ）が使用する枝の集合．

パラメータ:

  • \(o_k, d_k\): 品種 \(k\) の発ターミナルと着ターミナル

  • \(D_{k}\): 品種 \(k\) の需要量（発ターミナルから着ターミナルまでの荷量)

  • \(c_{ij}\): 枝 \((i,j)\) の固定費用（トラック1台あたりの移動費用）． 簡単のため最も多い10トントラックのみと仮定する．

  • \(C_{pk}\): 品種 \(k\) に対するパス \(p\) の変動費用（需要量 \(1\) 単位あたりの費用）

  • \(M_{ij}\): トラック1台あたりの容量

  • \(Succ_{pk}\): 品種 \(k\) に対するパス \(p\) の最初の枝を除去したパス（後続パス）

変数:

  • \(x_{pk}\): 品種 \(k\) に対してパス \(p\) が使われるとき \(1\)，それ以外のとき \(0\)
  • \(y_{ij}\): 枝 \((i,j)\) 上を移動するトラックの台数（整数変数）

定式化:

\[ \begin{array}{l l l } minimize & \sum_{(i,j) \in A} c_{ij} y_{ij} + \sum_{k \in K} \sum_{p \in P_k} C_{pk} D_{k} x_{pk} & \\ s.t. & \sum_{p \in P_k} x_{pk} = 1 & \forall k \in K \\ & \sum_{p,k:(i,j) \in A_{pk}} D_{k} x_{pk} \leq M_{ij} y_{ij} & \forall (i,j) \in A\\ & x_{pk} \leq x_{p',k'} & \forall (p',k') = Succ_{pk}\\ &\lceil D_k/M_{ij} \rceil x_{pk} \leq y_{ij} & \forall (i,j) \in A_{pk}, p \in P_k, k \in K\\ & \sum_{(i,j) \in (S,N \setminus S)} y_{ij} \geq \lceil \sum_{k: o_k \in S, d_k \in N \setminus S } D_k/M \rceil & \forall S \subset N, S \neq \emptyset \end{array} \]

制約の意味は以下の通り。

  1. パス選択制約：各品種はいずれかのパスによって流さなければならない.

  2. 容量制約: 各枝上を流れる品種の量の合計は，その枝上を移動したトラックの容量の合計を超えてはいけない．

  3. 入木制約: パス \(p,k\) \(=(n_1,n_2,\ldots, n_m)\) が選ばれたときには，その後続パス \(p', k'\) \(=(n_2,\ldots, n_m)\)も選択されなければならない． つまり、同じ着地をもつ品種が一度合流したら，同じパス上を移動しなければならない．

  4. 強化制約： 品種 \(k \in K\) に対するパスの集合は，ちょうど1つ選択する必要があるが，それらのパスが通過する枝 \((i,j)\) に対して需要 \(D_k\) を満たす分のトラックが移動しなければならない．

  5. カットセット制約： 点の部分集合 \(S\) とそれ以外の点集合 \(N \setminus S\) へ移動する需要量を満たすだけのトラックが，\(S\) から \(N \setminus S\) へ移動しなければならない．これは，すべてのトラック容量 \(M_{ij}\) が同一量 \(M\) であるときに使われ，カットセット制約とよばれる．

適切なパスを生成するための勾配スケーリング法

ある枝 \((i,j)\) に対して説明するので，以下の記号では添字の \(ij\) を省略する．

\(y\) は整数変数であるが，緩和して求解する．その解を \(\bar{y}\) とする． 本来の費用は \(c \lceil \bar{y} \rceil\) であるので， \(\bar{y}\) のときに　\(c \lceil \bar{y} \rceil\) になるように勾配を調整する． 新しい勾配は， \(c \lceil \bar{y} \rceil/\bar{y}\) となる．

実際には，現在の費用 \(c'\) と新しい勾配をパラメータ \(0 < \alpha < 1\) で調整し． \[ c' := \alpha c \lceil \bar{y} \rceil/\bar{y} + (1-\alpha) c' \] と設定する． \(\alpha\) が \(0\) に近いほどほどあまり解を変えないように勾配を調整し， \(1\) に近いほど大胆に勾配を調整するようになる．

#hide ## 階層的アプローチ

  • サービスネットワーク設計 (SND): OD間のパスを求める．
  • 時空間ネットワーク上でのフロー最適化： 運搬車の中継地点とスケジュールを求める．
  • 積み込み・積み下ろし型配送計画： 運搬車の移動経路を求める．

データの読み込み

  • 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 501136.2 10037 0.432510 43.06417 141.34694
1 青森市 0.0 501136.2 10235 0.414573 40.82444 140.74000
2 盛岡市 0.0 501136.2 10908 0.414802 39.70361 141.15250
3 仙台市 0.0 501136.2 10072 0.136525 38.26889 140.87194
4 秋田市 0.0 501136.2 10767 0.029622 39.71861 140.10250 
# OD需要のヒストグラムの描画
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本のパス（点列のタプル）を入れたリスト

source

k_th_sp

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

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

#hide ## サービスネットワーク設計モデル 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

source

sndp

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

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

source

add_shortest_paths

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

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

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

source

make_result

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

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

source

draw_snd_all

 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: 図オブジェクト

source

solve_sndp

 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

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

着地点が destination の場合の描画

#hide ### AGV への応用

#hide ## 混合整数計画問題の定式化

集合:

  • \(G=(N,A)\): 有向グラフ:；点集合はターミナルの集合，枝集合は移動可能な点対の集合．

  • \(K\): 発ターミナル・着ターミナルの組（これを品種と呼ぶ）の集合．

  • \(P_k\): 品種 \(k \in K\) に対するパスの集合． すべてのパスの集合を \(P\) とする．

パラメータ:

  • \(o_k, d_k\): 品種 \(k\) の発ターミナルと着ターミナル
  • \(C_{p}\): パス \(p\) の移動費用
  • \(c_{pq}\): パス \(p,q\) の干渉費用

変数:

  • \(x_{p}\): パス \(p\) が使われるとき \(1\)，それ以外のとき \(0\)
  • \(y_{pq}\): パス \(p,q\) が干渉するとき1，それ以外のとき \(0\)

定式化:

\[ \begin{array}{l l l } minimize & \sum_{p,q} c_{pq} y_{pq} + \sum_{k \in K} \sum_{p \in P_k} C_{p} x_{p} & \\ s.t. & \sum_{p \in P_k} x_{p} = 1 & \forall k \in K \\ & x_{p} + x_{q} \leq 1 + y_{pq} & \forall p,q \\ \end{array} \]

#hide ## 制約最適化での定式化

変数： - \(X[k]\): 品種 \(k\) に対するパスの集合を領域とした変数

値変数:

  • \(x_{kp}\): 品種 \(k\) に対してパス \(p\) が使われるとき \(1\)，それ以外のとき \(0\)

定式化:

\[ \begin{array}{l l l } minimize & \sum_{k,k'} \sum_{p,q} c_{pq} x_{kp} x_{k'q} + \sum_{k \in K} \sum_{p \in P_k} C_{p} x_{kp} & \end{array} \]