〈一般研究課題〉 効率的な共同輸送経路構築アルゴリズムの開発
助 成 研 究 者

中京大学

藤田実沙

効率的な共同輸送経路構築アルゴリズムの開発
藤田 実沙（中京大学）Development of an efficient algorithm
for constructing the joint transport route
Misa Fujita(Chukyo University)

Abstract：
The shortage of truck drivers is a serious problem around the world. One of the reasons for theshortage of truck drivers is the poor working environment. For sustainable logistics, the working
environment of truck drivers must be improved.
This study deals with the problem of constructing a joint transport path combining milk-run
transportation and relay transportation. Milk-run transportation can reduce the number of truck
drivers needed. Relay transportation can reduce truck drivers’working hours. The formulation of
the milk-run transport section and the results of a performance comparison between the piston andmilk-run transport paths using the saving method are reported here.
1．はじめに物流業界は人手不足が深刻化しており，特にトラックドライバーの不足は日本だけでなく世界各国で問題となっている[1]．人手不足の原因の一つとして，長距離トラックドライバーの労働環境の劣悪さが挙げられる．持続可能な物流のためには，労働環境のホワイト化が急務である．
長距離トラックドライバーの労働環境のホワイト化を実現する方法の一つとして，共同輸送[2]がある．共同輸送にも様々な種類があるが，本研究ではミルクラン輸送と中継輸送に注目する．ミルクラン輸送は産地を巡回して集荷する輸送方式，中継輸送は長距離輸送を中継地点で分割する輸送方式である．前者は必要なトラックドライバー人数の削減に，後者はトラックドライバーの労働－ 231 －環境の改善に効果的であることが知られている．これらの輸送方式を組み合わせることにより効率的で持続可能な物流を実現することが期待されるが，その輸送経路を構築するアルゴリズムは現在のところ存在しない．本稿ではミルクラン輸送と中継輸送を組み合わせた共同輸送経路構築アルゴ
リズムの開発に向け，ミルクラン輸送部分の定式化およびセービング法[3]を用いたピストン輸送
経路とミルクラン輸送経路の性能比較の結果を報告する．
2．共同輸送経路構築問題の定式化
本研究では，共同輸送経路構築問題を容量制約付き配送計画問題として定式化する．配送計画問
題は種々の制約を満たしつつ，トラックの総移動距離が最小となるような，各トラックへの顧客の割り当ておよびその巡回順を決定する問題である．トラックの使用可能台数，最大積載量，集積所および各顧客の位置は既知とする．各トラックは集積所から出発し，担当する顧客を順番に巡回して需要を回収し，集積所へ戻る．各顧客の需要量は過去のデータから平均と変動幅が求められた一様分布に従うと仮定する．実際の需要量は顧客に到着したときに判明し，需要量の合計がトラックの最大積載量を超過してしまう場合には，トラックは一度集積所に戻って積荷を下ろし，再びその顧客を巡回することとする．つまり，求める配送計画は，(1) 使用するトラック台数の最小化，(2)トラックの総移動距離の最小化，(3) 積載量上限の超過により発生する顧客と集積所の往復にかかる距離の最小化を同時に達成するものである．本問題の目的関数を式 (1) に示す．
(1)

ここで，Sは配送計画，m(S)はSにおけるトラックの使用台数，nは顧客数，dij (=dij )は顧客i，j間の距離，xkij (S)はSにおける決定変数で，トラックkが顧客iの次に顧客jを訪問するとき1，そうでないとき0とする．また，P(S)はSにおいて積載量上限を超える顧客の集合，α，β，γはそれぞれ各項のバランスを調整するパラメータである．本研究では，顧客の需要の変動に対してロバストな配送計画を作成することを目指す.
3．セービング法
共同輸送の有効性を確認するため，集積所と各顧客間を往復するピストン輸送経路と，集積所からいくつかの顧客を巡回して集積所に戻るミルクラン経路で総移動距離を比較する．ミルクラン経路の構築にはセービング法[3]を使用する．
セービング法は集積所と各顧客を往復するピストン輸送経路を元に，各経路を併合する操作を繰り返すことにより巡回路を構築する手法である．
セービング法の概念図を図1に示す．集積所を顧客0とすると，図1左は顧客を0→i→0の順に訪問する巡回路と0→j→0の順に訪問する巡回路からなる配送計画である．これらの巡回路を結合し，顧客を0→i→j→0の順に訪問する図1右の巡回路を考える．このとき，巡回路長の合計は式(2)の－ 232 －

図1 セービング法

セービング値sijだけ短くなる．
(2)あらかじめ全ての顧客の組合せのセービング値を求めておき，セービング値が大きい順に巡回路への挿入を試みる．挿入の対象を集積所と直接繋がる顧客に限定することにより，閉路の生成を回避することができる．
4．数値実験
本研究ではピストン輸送経路とミルクラン輸送経路の性能を文献[4]で使用されている顧客数50
および75のベンチマーク問題を用いて実験的に比較した．ピストン輸送経路は集積所と各顧客を往復する経路とし，ミルクラン輸送経路はセービング法により構築した.
4.1 需要が既知の場合
ベンチマーク問題[4]では，各顧客の需要が静的に与えられている．そこで，需要が既知の場合のピストン輸送経路とミルクラン輸送経路の総移動距離を比較した．結果を表1に示す．
表 1 需要が既知の場合

表1から，ピストン輸送経路よりもミルクラン経路のほうがトラックの総移動距離を大いに短縮できることが分かる．また，ミルクラン輸送経路の例をそれぞれ図2，図3に示す．図2，図3ともに集積所を■，顧客を◯で表す．

図2 顧客数50の経路例

図3 顧客数75の経路例－ 233 －

4.2 需要が未知の場合
ベンチマーク問題[4]で与えられる各顧客の需要量を確率的に定まる各顧客の需要量の平均値とし，需要が一様に変動する場合を考える．この問題設定はピストン輸送経路に対しては影響を及ぼさないが，ミルクラン輸送経路に対しては積載量上限の超過による顧客と集積所との往復の発生に影響を及ぼす．そこで，需要の変動が各顧客の需要量の10∼50%のときの総移動距離を調査した．
ミルクラン経路の構築に需要の平均値を用いた場合を平均値モデル，需要の最大値を用いた場合を最大値モデルと呼ぶこととする．結果を表2および表3に示す.
表 2 需要が変動する場合（顧客数 50）

表 3 需要が変動する場合（顧客数 75）

表2および表3から，需要の変動割合が高くなるほど総移動距離が増えていることが分かる．これらは，積載量に余裕をもった巡回路を構築することにより，積載量上限の超過による顧客と集積所との往復距離の増加を回避しようとしているためであると考えることができる．また，需要の変図 4 需要変動割合と距離の関係（顧客数 50）

図 5 需要変動割合と距離の関係（顧客数 75）－ 234 －

動割合と総移動距離の関係を図4および図5に示す．図4および図5から，需要の変動割合が異なる多くのシナリオにおいて平均値モデルよりも最大値モデルのほうが総移動距離の小さい解を構築していることが分かる．
5．まとめ
本研究ではホワイト物流の実現に貢献する効率的な共同輸送経路構築アルゴリズムを開発することを目指し，本問題の容量制約付き配送計画問題としての定式化を行い，セービング法により構築したピストン輸送経路とミルクラン輸送経路の性能について実験的に検討した．数値実験の結果，需要が既知の場合も未知の場合もピストン輸送経路よりミルクラン経路のほうが少ないトラック台数かつ短い総移動距離で配送できることが分かった．また，需要が未知の場合のミルクラン経路の性能を平均値モデルおよび最大値モデルで評価し，多くのシナリオにおいて最大値モデルのほうが積載量上限の超過によるペナルティが少ない良い解を構築することが分かった．
今後は，ミルクラン輸送と中継輸送を組み合わせた共同輸送問題を定式化し，その問題に対する効率的なアルゴリズムの開発に取り組む予定である．また，各トラックの稼働時間枠や各顧客の訪問時間枠を設定した問題に発展させる予定である.
参考文献
［1］ 国
 土 交 通 省 物 流 政 策 課，“物 流 を 取 り 巻 く 現 状 に つ い て ,”https://www.mlit.go.jp/common/001258392.pdf (最終アクセス：2023年5月28日).
［2］ 国
 土 交 通 省 物 流 政 策 課 ,“物 流 政 策 の 主 な 取 組 に つ い て ,”https://www.mlit.go.jp/seisakutokatsu/freight/content/001354698.pdf (最終アクセス：2023 年 5 月 28 日) .
［3］ G
 . Clarke and J. W. Wright,“Scheduling of Vehicles from a Central Depot to a Number ofDelivery Points,”Oper. Res., vol.12, no. 4, pp.568–581, Aug. 1964.
［4］ N
 . Christofides and S. Elilon,“An algorithm for the vehicle dispatching problem,”J. Oper.
Res. Soc., vol. 20, No. 3, pp. 309–318, 1979.

－ 235 －