DEIM Forum 2019 H6-4

中継可能な協調型輸送の提案とアルゴリズムの効率化
藤井 貴彬†

浅野 泰仁†† 京都大学情報学研究科〒 606–8501 京都府京都市左京区吉田本町 36-1
E-mail: †lab5fujii@gmail.com, ††asano@i.kyoto-u.ac.jp
あらまし 近年, 宅配サービスによる荷物の輸送は急速に増加しているが, 宅配業者の数は十分には対応出来ておらず,
個々の負担が増加している. そこで我々は一般の人でもより気軽に参加できるように, 複数の輸送者が一つの荷物を中継を挟んで輸送することを可能とした “中継可能な協調型輸送モデル” を提案した. 本研究でこの輸送モデル定式化を行い, 厳密解法を考案しを求めた. その結果, 問題の性質として有向非巡回グラフ (DAG) が重要であること, 時間計算量が問題になることを特定した. さらに, 時間計算量を軽減するため効率的に探索木を枝刈をする手法を新たに考案し,より時間計算量を軽減することも可能になった. これらより, 我々のモデル及びアルゴリズムは宅配業者の負担を軽減する取組みの一つとして期待される.
キーワード グラフ， 配送， 協調型輸送， 厳密解， 最適化， 最適経路， シェアリングエコノミー
ニエンスストア) から学校に近い施設 B に少し迂回して持って1 はじめにスマートフォンやパソコンの普及により, インターネットがより身近なものとなり, それに伴い Amazon.com 1 などのオンラインショッピングの需要も増加している. 結果として, オンラ
インショッピングで注文された商品を配送するために輸送形態も変化した. Jiang ら [1] や Mallapragada ら [2],Xu ら [3] もオ
ンラインショッピングが我々の生活に影響を与え, 利便性や値段を変化させていると述べている. しかし, サービスなどが充実すればするほど配送する荷物も増加し, 運送業者の負担も増加している. 実際に日本の運送業者であるヤマト運送は輸送サービスの負担が大きすぎると発表している 2 .
運送業者の負担の増加は解決すべき問題としてすでに認識されており, 負担を軽減しようと様々な試みが行われている. その一つの例として, 協調型輸送がある. これは運送業者のみが輸送を行うのではなく, 様々な人が参加する輸送を行うものである. その例として,Amazon は既存の配達業者ではなく一般の人が荷物を配送する新しいオンデマンドのサービス,Amazon

Flex 3 を開始した. また, 様々な配送・輸送サービスを提供している Uber が Uber Freight 4 という協調型輸送サービスを開始
した. Uber Freight は有資格の運送業者や個人トラック運転手が輸送する貨物を手軽に探して受注できるようにしたオンデマ
ンドのサービスである.
このような協調型輸送サービスは一人の人が一つの荷物をサービスセンターやショップから目的地まで運ぶものである.
その結果, 比較的長い時間と長距離の配送に従事できる人しかこの輸送に参加できない. そこで我々は複数の輸送者が一つの荷物を配送するサービスについて考えた. 例えば, ある人が学校へ通学するとき, 荷物を自分の家に近い施設 A(例えばコンビ
1：https://www.amazon.co.jp

いく. そして, 施設 B 近くに住んでいるもう一人がそこから荷物を引き継いで, 通勤するついでに仕事場近くの施設 C へ運ぶ.
結果的に, 施設 A から施設 C まで運んだ二人は日頃の通学や通勤から少し多く移動するだけ済むはずであるため, それほど負担はないはずである. この中継可能な協調型輸送によって, 荷物を最終目的地まで輸送者の個々の負担をかけることなく運ぶことが可能になる. しかし, 我々の知る限り, 荷物を輸送するときに中継を許した協調型輸送の理論モデルは提案されていない.
したがって, 我々の論文の一つ目の貢献点としては, 中継可能な協調型輸送の提案と定式化を行ったことである.
図 1 は中継可能な協調型輸送が有用である具体的なグラフの例である. (a) のようなグラフについて考え, 各円はグラフの節点を表している. 節点にある記号は, 二人の輸送者 x と yと一つの荷物 n の出発地点を表す xs , ys , ns と目的地点を表す

xd , yd , nd である. また各辺の値は節点間の距離を示している.
このグラフにおいて, 輸送者 x と y は両者共にただ目的地点に到達するだけならば距離 4 だけで移動できる. 次に (b) のように輸送者 x が一人で荷物を輸送するならば合計距離が 16 となり,12 増加することとなる. 一方 (c) のように輸送者 y が一人で荷物を輸送するならば合計距離が 18 となり,14 増加することとなる. しかし,(d) のように二人で輸送した場合ならば, 輸送
者 x の合計距離は 10, 輸送者 y の合計距離は 12 となり, それぞれの増加した距離は 6 と 8 になる. このように, 中継可能な協調型輸送により二人で輸送すれば, 一人一人の迂回する負担は一人で輸送するより小さくすることができる.
我々の研究の二つ目の貢献点は提案した輸送モデルの厳密解
アルゴリズムである. 我々は厳密解アルゴリズムの考案にあたり, そのアルゴリズムが正しいことを証明した. この証明にはモデルの興味深い理論的性質も含まれていた. 性質を大まか言えば, 各輸送者に割り当てられた荷物の輸送経路の辺の関係を2：https://mainichi.jp/articles/20170407/k00/00e/020/198000c

表したグラフを作成し (このグラフを “輸送順序関係グラフ” と3：https://flex.amazon.com

言う), このグラフが有向非巡回グラフ (DAG) でなければ割当

4：https://freight.uber.com

xs

4
3

ns

4

xd

3

xs

5

3
nd

4
6

4

4
3

ns

4

xd

3

ys

4

6

4
ys

4
3

nd

ns

4

4

xd

3

であるという点で異なっている. また, 時間制約については荷物
nd

4
ys

4

だけではなく輸送する側にも存在している点でも異なっている.

4

また, 合流を考慮した経路最適化問題の研究に Zhang らの研

yd

究 [14] や Takise らの研究 [15] がある. 合流を考慮した経路最

5
4

6

yd

(c) 輸送者 y のみでの輸送
図1

3し, 本研究では輸送者と荷物の目的地点が全ての地点でも可能
5
4

xs

4

4

xd

(b) 輸送者 x のみでの輸送

5
4

6

4

yd

(a) グラフの例
xs

ns

4

4
ys

4

適化問題とは, 複数のユーザが各々の出発地点から目的地点へ向かうとき経路の途中で合流して移動することに利益があると考え, その合流の利益も考慮した最短経路を決定する問題であnd

る. さらに, 合流を考慮した問題を派生させたライドシェアリン

4グの研究として Cao らの研究 [16] や Drews らの研究 [17] があyd

る. 合流を考慮した問題と異なる点は, 合流を考慮した問題は(d) 二人による輸送

協調型輸送が有用である例

どちらも移動可能であることに対し, ライドシェアリングでは輸送を行う一方のみが移動可能であるという点である.
本研究も合流を考慮した経路最適化問題やライドシェアリンてが実行可能ではないというものである. 我々が扱う問題は多項式時間内に正確には解くことができないと予想され, 実際に提案した手法も多項式時間では解けなかった. しかし, 我々は上記の性質も利用して冗長な割当ての候補を枝刈りする方法も提案した.

2 関連研究
複数人が合流するときにそれぞれ最短距離の合計が最小となる地点を求める研究に,Yan らの研究 [4] がある. 更にこの研究を発展させたものとして, 複数人が好きな経路を持ち, それぞれの経路からの迂回した最短距離の合計が最小となる地点を求める研究に,Ahmadi と Nascimento の研究 [5] がある.
本研究でも, 一つの荷物を複数の輸送者によって輸送される
場合には荷物を引き継ぐ中継地点が存在するため, 輸送者と輸送者がどこで合流するべきかを決定しなければならない. しかし, [4] [5] の研究と異なり, 合流地点と輸送者の位置だけではな
く荷物の出発地点及び目的地点も考慮しなければならない. また, 本研究では輸送者及び荷物に出発時刻と到着時刻が存在す
る. そのため, 輸送者の移動距離の合計を最小にするだけでは出発時刻及び到着時刻を満たさない場合が存在する. よって, それら時間制約も考慮して移動距離の合計を最小にする必要がある.

グの問題の一種と捉えることができる. 例えば, 本研究における荷物を客, 輸送者をタクシーに変換すればライドシェアリングのように扱うことができる. しかし, 一般的なライドシェアリ
ングでは一台のタクシーが客を目的地点まで運びきることに対し, 本研究では複数の輸送者が中継して輸送することも可能としている点で異なっており, [14] [15] [16] [17] よりも計算量が大きくなると予想される.

3 中継可能な協調型輸送モデル
本研究では，前持って準備された荷物及び輸送者のデータに対して，全ての荷物を輸送することのできる計画を求めるバッ
チ処理を対象としている．なお，輸送者は必ず決定した計画には従うと仮定している．3. 1 節では, 我々が新しく提案した中継可能な協調型輸送モデルにおける問題の入力となる道路情報・荷物・輸送者と，問題の出力となる輸送計画の定義を行い，その後輸送計画の最適性を議論するために，システム側 (配送サービス会社など) の利益の定義をしている. 3. 2 節では，以上に基づく問題の定式化のまとめを行っている．

3. 1 問題の定式化のための定義及び制約
まず，問題の入力となる道路情報，荷物とその時刻制約，輸送者とその時刻制約の定義を与える．

次に Dantzig と Ramserfor により提唱された配送問題がある [6]. この問題は特定の施設にある輸送車が顧客の荷物を輸定義 1. [道路情報 (グラフ)] 道路情報は有向グラフ G(V, E) と送・回収する問題である. 配送計画問題には条件設定によって表す. 各辺 e ∈ E の始点を vs (e) ∈ V と表し, 終点を vd (e) ∈ V

様々な問題に分類される. Nagy と Salhi の研究 [7],Ho らの研と表す. ただし, 全ての輸送者は同じ速度で移動し, その速度を究 [8],Yu らの研究 [9] では特定の施設が一つではなく複数の場維持し続けるとする. よって, ある辺を通過する時間をその距離合に拡張した配送問題を扱っている. また,Salhi らの研究 [10]に比例した値とみなすことできる. このことより, 各辺 e の時と Lahyani らの研究 [11] では輸送車が１種類ではなく, 異なる

間を w(e) > 0 と表す. 節点 v から v ′ にその節点間の最短経路

積載量の輸送車で配送する場合の配送問題を扱っている. さで移動するために要する時間を W (v, v ′ ) > 0 と表す.

らに,Garcia-Najera と Bullinaria の研究 [12] や Vidal らの研
究 [13] では顧客の荷物の回収に時間制約を与えた配送問題を扱っている. 特に, [13] では複数の施設かつ荷物の回収に時間制約を与えた場合でも対応できることが言及されている.
本研究は配送計画問題を大幅に拡張したものと考えられる.

定義 2. [荷物と時刻制約] 荷物の集合を B と表す. 荷物 bi ∈ Bの出発地点を s(bi ) ∈ V , 目的地点を d(bi ) ∈ V , 荷物が輸送可能となる時刻を ts (bi ), 目的地点に到着しなければない上限時刻
を td (bi ) とする.

配送計画問題では特定の施設に全ての荷物を回収する問題であ定義 3. [輸送者と時刻制約] 輸送者の集合を U とする. 各輸送るため輸送車と荷物の目的地点は特定の施設に絞られる. しか者 uj ∈ U の 出発地点を d(uj ) ∈ V , 目的地点を d(uj ) ∈ V , 輸

送者が移動可能となる時刻を ts (uj ), 目的地点に到着しなければない上限時刻を td (uj ), 同時に輸送可能な荷物の数を m(uj ) >=1

3. 2 最適化問題

とする.

入力

次に，問題の出力は，以下で定義される，全ての荷物を運ぶ

前節より, この研究で考えた問題は次のように定式化される.
道路情報 G(V, E), 荷物集合 B と各荷物 bi ∈ B の出発・目的地点 s(bi ), d(bi ) およびそれらにおける時刻制約 ts (bi ),td (bi ), 輸送者集合 U と各輸送者 uj ∈ U の出発・目的地点

ことのできる輸送計画となる．
定義 4. [輸送計画] 各荷物 b ∈ B の輸送計画とは，s(b) から t(b) までの輸送経路 pb と，各辺の移動時刻および担当輸送者の情報からなる. この計画の経路長を len(pb ) で表す．各
輸送者 u ∈ U の輸送計画とは，s(u) から t(u) までの輸送経
路 pu と，各辺の移動時刻，および各辺で運ぶ荷物の情報からなる. この計画の経路長を len(pu ) で表す．荷物の輸送経路の集合を PB = {pb | b ∈ B}, 輸送者の輸送経路の集合を

PU = {pu | u ∈ U } と表す.

s(uj ), d(uj ) およびそれらにおける時刻制約 ts (uj ), td (uj ).
出力

各荷物及び各輸送者の輸送計画

目的関数

最大化 Rwd(PB , PU )問題を簡単にするため, 本論文では次の二つを条件設定として加えた.

I 荷物の輸送経路は出発地点と目的地点を結ぶ最短経路(複数ある場合は予め定めた最短経路) に限定する
II 中継が出来る場所を限定し, 各荷物の輸送経路を等分割した節点のみにする.

この輸送計画が時刻制約を満たすならば，それはこの問題の解となる．この解が最適であるかどうかを議論するには，このIII 各輸送者 u が一度に輸送できる積載荷物数 m(u) はm(u) = 1 に限定する輸送計画に対してシステムが得られる利益を定める必要がある．

我々は条件設定 I は合理的だと考えている. 条件設定 II につ本研究では一つの荷物を複数人で運ぶ中継を可能とした輸送

いても, どこでも荷物が中継できるよりいくつか限定された場モデルを考えている. そのため, ある荷物の輸送計画の担当輸送

所 (例えばコンビニエンスストアなど) で中継する方が自然で者が二人以上になっても良い.(中継を許さない輸送モデルでああり合理的だと考えている. また, 条件設定 III がない問題にアるならば, ある荷物の輸送計画の担当輸送者は一人に限られる.)

ルゴリズムが拡張できるとも考えている.

システム側の利益を決定する利益関数を定義するために, まず収入関数と支出関数を定義する. 収入関数 Rmdin は各荷物

4 厳密解アルゴリズムの大きさと最短経路における輸送距離に応じた金額に設定される. つまり収入関数は, 荷物の大きさを x, 定数を α とすると収入関数は Rwdin (b, pb ) = α · x · len(pb ) (b ∈ B) となる. 一方,

4. 1 利益関数の性質
利益関数の性質を利用して次節からの議論で用いる目的関数

支出関数 Rwdout は 2 種類の方法が考えられる. 一つ目の方法

を簡単化する. 問題設定で与えられた荷物は全て輸送するため,は, 輸送者が荷物を輸送するために要した移動距離のみに応じ次の命題が成り立つ.

て金額を設定する方法で, 各輸送者は輸送計画で移動する距離に比例したものが報酬となる. このときの支出関数は, 定数を βとすると支出関数は Rwdout (u, pu ) = β · len(pu ) (u ∈ U ) とな

命題 6. 荷物と輸送者の輸送経路が決定すれば, 目的関数の値は各経路の辺の輸送時刻割当てに依らず変化しない.

る. もう一つの方法は, 輸送者が荷物を輸送するため要した移動

Proof. 与えられた荷物は全て輸送するため収入関数の値が固距離だけでなく輸送者の元々の移動距離も考慮して金額を設定定される. したがって, 目的関数が以下のように表せる.

する方法で, 各輸送者の報酬は輸送計画で移動した距離から出発
地点から目的地点までの移動距離を引いた距離に比例するものになる. つまり, このときの支出関数は, 定数を β ′ とすると支出関数は Rwd′out (u, pu ) = β ′ (len(pu ) − w(s(u), d(u))) (u ∈ U )となる.
この二つの関数にはどちらにもメリット・デメリットが存在する. 前者は元々の移動距離が長い輸送者が報酬を得やすくなっており, 後者は元々の移動距離が短い輸送者が報酬を得やすく∑ˆmin Rwd(RU ) = minPU

PU

Rwdout (u, pu )

(2)

u∈U

支出関数は輸送者の輸送経路のみに依存し値が決まる. そのため, もし荷物と輸送者の輸送経路が決定していれば, 輸送時刻割
当てに関わらず目的関数の値は決定される. これは定義 5 で述べた支出関数 Rwd′out の場合でも成立する.

ˆ の最小化として議論を進めていく.
以降, 目的関数を Rwdなっている. 後ほど命題 6 で説明するが, 最適化は前者・後者どちらの場合でも成立している. 本研究では前者を支出関数とし

本研究の問題を解く, つまり荷物及び輸送者の輸送計画を決て利益関数を定義する.
以上より, システム側にとっての利益関数 Rwd は次のように定するにはそれぞれ通る経路とその時刻とそれらの担当を決定する必要がある. まず, 経路の決定であるが, 荷物の経路は場合定義される.

は条件設定 I により固定されている. したがって輸送者の経路

定義 5. [利益関数]

Rwd(PB , PU ) =4. 2 考えられる輸送経路の列挙∑
b∈B

Rwdin (b, pb ) −∑が問題となるが, 各輸送者にどの荷物のどの辺が割り当てられRwdout (u, pu )u∈Uwhere PB = {pb |b ∈ B}, PU = {pu |u ∈ U }るか決定しただけでは，経路は一意に定まらない．各輸送者が,どういう順序で, どの荷物のどの辺を運ぶかを決定すれば経路(1)が決定される. これを表すのが後に定義する “辺順序割当て” でs(b1)

eb
11

v1

eb
12

eu
11

s(b1)

d(b1)

eb
11

経路が決定され, 赤色と青色の経路はこの図における u1 と u2

eu
22

v1

eb
12

d(b1)

各々の輸送経路を示している.

s(u1)

d(u1)

s(u1)

d(u1)

ここで注意するべきことは, 輸送組合せが全て決まったとき,

s(u2)

d(u2)

s(u2)

d(u2)

その輸送組合せについて複数の輸送者の輸送順序が存在しえる

s(b2)

eb
21

v2

eb
22

s(b2)

d(b2)

eb
21

v2

eu
21

(a)

eb
22

d(b2)

eu
12

(a)
eu
12

s(b1)

eb
11

eu
22

v1

e12

s(u2)
s(b2)

eb
21

v2

eu
21

eb
22

である. しかし, 輸送者 u1 の輸送経路に注目すると,(b) では e1d(u1)序で輸送している. つまり,(b) において eu
11 は e1 であるが,(c)d(u2)

においては e4 となっており,(b) での輸送者の輸送順序と (c) で

d(b2)

eu
11

(c)
図2

(c) の輸送組合せは共に (u1 , eb11 ), (u1 , eb22 ), (u2 , eb12 ), (u2 , eb21 )から e4 の順序で輸送しているのに対し,(c) では e4 から e1 の順

d(b1)
b

s(u1)

ことである. そのことの例を図 2 の (b) と (c) で挙げる. (b) と輸送組合せと輸送順序ある. 本節では辺順序割当てを定義するために “輸送順序” と“輸送組合せ” の二つについて述べる.

の輸送者の輸送順序が異なっている. したがって, 輸送者の輸送経路を決定するためには, 考えられる全ての輸送組合せを列挙
したあと, さらに各輸送組合せで考えられる全ての輸送者の輸送順序合を列挙する必要がある.
以下, 輸送組合せと輸送順序の列挙方法についてまとめる. まず, 輸送組合せを全列挙する. ただし, 全ての荷物の輸送順序は最短経路に固定されている注意して欲しい. そのため, 荷物の輸送順序の各辺において, 各輸送者を割り当てていくことがで

定義 7. [荷物の輸送順序] 荷物の輸送経路の辺の順番を “荷物きる. したがって, 輸送者の数を |U | とし全ての荷物の輸送順序の輸送順序” と呼ぶ. 荷物 bi の輸送順序が k 番目の辺を ebik との辺の数を |E ′ | としたとき, 輸送組合せ集合は |U ||E | 通り考

する.

えられる.

′

次に, 輸送者の輸送順序を全列挙する. 決定した輸送組合せ
ただし, 各荷物の輸送順序は条件設定 I により固定されていることの注意されたい.

における各輸送者が担当する辺の順序の順列を考えることで全列挙することができる. この順列は各輸送者ごとに考える必要

定義 8. [輸送組合せ] 輸送者が荷物の輸送経路のある辺を割りがあるため,uj が担当する辺の数を |Euj | とすると, 輸送者の輸当てられたとき, その輸送者と辺との組を “輸送組合せ” と呼ぶ.

送順序は合計で |Eu1 |! ∗ |Eu2 |! ∗ · · · |Eu|U | |! 通り考えられることになる.

図 2 の (a) でグラフ G における輸送組合せの例を挙げる. こ
れらの図おいて, グラフ G は実線で示した eb11 , eb12 , eb21 ,eb22 の4. 3 輸送順序関係グラフ

4 つ辺しか存在しないが,G には他に多くの辺があるものとして上記で説明したようにすることで輸送組合せと輸送順序を全いる. また, 赤色の辺の eb11 と eb22 は輸送者 u1 が割り当てられた辺とし, 青色の辺の eb12 と eb21 は u2 が割り当てられた辺とすて列挙することが可能となった. 輸送組合せと輸送順序が決定る. このときの輸送組合せを考えると,u1 については (u1 , eb11 )と (u1 , eb22 ) の輸送組合せがある. 同様に u2 について考える

時刻割当てを考えると実行不可能な場合がある. そのような組と,(u2 , eb21 ) と (u2 , eb12 ) の輸送組合せがある.

まず, そのグラフの節点として “辺順序割当て” を定義する. こ

荷物の輸送経路の辺と輸送者との輸送組合せが全て決定すれば, 各輸送者が割り当てられた辺をどの順序で輸送するか決める必要がある. この順序を “輸送者の輸送順序” と呼ぶ.
定義 9. [輸送者の輸送順序] 輸送者 uj が ej1 , ej2 , . . . の順序に沿って輸送を行うとき, これを輸送者 uj の輸送順序と呼ぶ. 輸
送者 uj の輸送順序が ℓ 番目の辺を eu
jℓ とする.
図 2 の (b) で輸送者の輸送順序の例を示している. ただし, 点
線は節点間の最短経路を示している. ここで,u1 は赤色の経路にb
沿って s(u1 ) から d(u1 ) に進む. ただし,eu
11 = e11 = e1 であるが, 荷物 b1 の輸送順序と輸送者 u1 の輸送順序を区別するため

e1 に 2 つの線で表している. 同様に,e2 ,e3 ,e4 でも 2 つの線で表している. したがって,u1 は e1 で最初に輸送を行い,2 番目に

e4 で行う. そのため,eu11 = e1 , eu12 = e4 となる. 一方,u2 は青色
uの経路に沿って s(u2 ) から d(u2 ) に進むため,eu
21 = e3 ,e22 = e2である. このように輸送順序が決定されることで輸送者の輸送すれば, 時刻割当てを除いて PB と PU を決定できる. しかし,を見つけるために, 我々は “輸送順序関係グラフ” を定義する.
れは輸送組合せと輸送順序を詳細に説明したものである.
定義 10. [辺順序割当て] 辺 ebik が eu
jℓ である, つまり uj の輸
送順序において ℓ 番目の辺が ebik であるとき, その辺の関係を“辺順序割当て” と呼び,a(i, k, j, ℓ) と表す. この辺順序割当て ab
おいて,eik= eujl を ea で表す. さらに全ての辺順序割当ての集合を A とする.
辺順序割当ての例として, 図 2 の (b) を挙げる. 辺 e1 は荷物の輸送順序においては eb11 であり, 輸送者の輸送順序においては eu11 である. したがって, 辺順序割当ては a1 (1, 1, 1, 1)となり, 図 2 の (a) で ea1 = e1 と表される. 他の辺でも同様にして,a2 (1, 2, 2, 2) は ea2 = e2 と表わされ,a3 (2, 1, 2, 1) は

ea3 = e3 と表わされ,a4 (2, 2, 1, 2) は ea4 = e4 と表わされる.
辺順序割当てが定義したので, 辺順序割当てと辺順序割当て同士の関係を表す “輸送順序関係グラフ” を定義する.
定義 11. [輸送順序関係グラフ] 与えられた全ての辺順序割

ea 1

u1

ea 2

d(b1)

v1

s(b1)

!"#!"$%&'()*
d(b1)

v1

s(b1)

!"#$1%&
v2

s(b2)

d(b2)

ea 3

v2

s(b2)

ea 4

d(b2)

u2

(a) グラフの例!"#$2%&!"#$3%&(b) 輸送が可能な例
!"b1#
$%&'

!"#!#$%&'()*
u2

s(b1)

v1

d(b1)

s(b2)

v2

d(b2)

!"#$1%&!"#$2%&

!"b2#
$%&'

u1

図 4 探索木の例(c) 輸送が不可能な例
図 3 輸送が可能/不可能な例のため輸送が輸送が開始されず輸送不可能である.
本論文では輸送順序関係グラフに CTA が存在しないとき, 輸

当ての集合を A とすると, 有向グラフ H(A) を A の “輸送順

送順序関係グラフが “矛盾している” と呼んでいる. これはコ序関係グラフ” と呼ぶ. ただし, 有向辺は二つの辺順序割当て

ンピュータ科学におけるデットロックの状態に相当する. 我々a(i, k, j, ℓ) と a′ (i′ , k′ , j ′ , ℓ′ ) が次の [A],[B] のいずれかの条件満は輸送順序関係グラフが有向非巡回グラフ (DAG) ではなけれ

たした場合に a → a′ の向きで接続する.

ば矛盾していることを証明した. ただし, 照明については [18] のA ea と ea′ で輸送される荷物が同じであり, その荷物の輸送

論文を参照されたい.

順序において ea で輸送されたあと ea′ で輸送される場合. すな
わち i = i′ and k + 1 = k ′B ea と ea′ で輸送する輸送者が同じであり, その輸送者の輸送順序において ea で輸送したあと ea′ 輸送する場合. すなわち

j = j ′ and ℓ + 1 = ℓ′

補題 13. H(A) を辺順序割当て集合 A とそれに対応する輸送
前後関係集合 R の輸送順序関係グラフとする. もし H が DAGでないならば, そのとき H は矛盾している.
補題 13 より輸送が不可能な A を取り除くことが可能となる.

ここで,A が決定したとするとそのとき輸送順序関係グラフ

ここから貪欲アルゴリズムを使うことで輸送時刻割当てを判定も決定される. さらに, 輸送計画のうち輸送時刻を除いた輸送し決定し, 最適解となる A を見つけることができる. この貪欲経路と各辺の担当荷物・輸送者が決定される. つまり, ゆえに,アルゴリズムの詳細については [18] の論文を参照されたい.

輸送順序関係グラフの与えられた輸送時刻が整合性の取れたも

4. 4 輸送経路の列挙の効率化のか確認するため,“整合した輸送時刻割当て” を定義する.

前節で提案した手法により中継可能な協調型輸送における厳定 義 12. [整 合 し た 輸 送 時 刻 割 当 て] 輸 送 順 序 関 係 グ ラ フ

密解は求めることが可能になった. しかし, この手法では非常H = (A) が決定されたとする. 定義 11 の条件 [A],[B] のいに小さい規模でしか動かすことができず, また小規模であって′ずれかを満たした a, a ∈ A において, 次の式が成立した場合,も計算量が大きくなりすぎてしまう. この問題を改善する方法

辺順序割当て集合 A の輸送時刻割当てを “整合した輸送時刻割として, 探索木を作成し枝刈することで全ての辺順序割当て集

当て (CTA と略記)” とする.

td (ea ) <= ts (ea′ )合を列挙する手法を考案した. その探索木の例として, 図 4 に(3)

その一部を挙げる. 点線の各枠組みはどの輸送者の辺順序割当てを決定しているか表し, 図のように輸送者 u1 , u2 · · · の順に

上記で述べたように, 与えられた輸送順序関係グラフに CTA決定し, 各ノードは輸送者がどの辺を担当するかを表している.

が存在しない場合がある. そのような例を図 3 の (a) から (c)また, 点線の枠内での高さが各輸送者の輸送順序を表している.

で例に挙げる. (a) は荷物 b1 と b2 の出発地点と目的地点及び以上のこと組み合わせることにより各ノードで辺順序割当てを輸送経路が表している. (b) と (c) の赤矢印と青矢印は輸送者決定することができる. 例えば図 4 の太枠のノードように, 輸送

u1 ,u2 の輸送経路を表している. ただし, 実線は節点間の辺を表者 u2 の枠内で輸送順序 1 番目の部分に eb31 のノードある場合,

し, 点線は節点間の最短経路を表している.

そのノードでは辺順序割当て a(1, 3, 2, 1) が決定されたことを(b) と (c) では輸送組合せが同じであるが, 輸送順序が異なる意味する. この探索木での根から葉まで道それぞれが一つの辺ため輸送経路が異なる場合を表している. このとき,(b) では 2

順序割当て集合, つまり輸送者の輸送経路に対応している. ここ

人の輸送者が二つの荷物それぞれの出発地点から輸送が始まっ

で, 図では点線の枠組み内での高さが異なっている場合があるている. そのため両者が中間地点まで輸送して中継し輸送するが, これは各輸送者が担当する辺の数は定まっていないためでことが可能である. 一方,(c) の場合は両者の輸送が中間地点かある. そのため, 図の左側のような輸送者 u1 がどれも担当せず,

ら始まってる. そのため輸送が開始されるには荷物が中間地点

根の子ノードが輸送者 u2 の辺順序割当てとなる場合もある.

に荷物が届く必要がある. しかし, 両者が荷物を待っている状態

次に探索木の作成方法について説明する. 探索木の各ノード

Algorithm 1 探索木の作成

s(uj) *+:ts(uj),-:ts(uj)+ Δt d(uj)

1: Â = ϕ
2: make tree(Eb , Â, 0, 1)
3: procedure make tree(Eb , Â, j, ℓ)4:

uj%&'#$(&'():Δt)

if j < |U | then5:

make tree(Eb , Â, j + 1, 1)

6:for ∀ebik ∈ Eb doeif 枝刈基準を満たさない then7:

make tree(E \ {e}, Â ∩ {a(i, j, k, ℓ)}, j, ℓ + 1)(同

8:

10:
11:
12:

15:

図 5 最も早い輸送の例

end ifend forに出発地点 s(uj ) から最短経路で ebik の始点へ向かい, 輸送しelse
if Eb = ϕ then
最適解となり得る辺順序割当て集合として A を出力

13:
14:

!"#$%&!'("

ts(uj)+ Δt > td(uj)

じ輸送者の場合)
9:!"#$▷ 新しい輸送者の場合

end ifend if

16: end procedure

た後に最短経路で目的地 d(uj ) へ移動する場合である. この場
合は輸送が不可能であるため最適解となり得ないことがわかり,枝刈をすることができる. 上記のことを簡単に表した図が図 5である. また, この輸送者と辺の組み合わせは探索きを作成する前に予め作ることができるため, この枝刈を行うために時間計算量が大きく増えることはないと考えられる.

にはまだ担当が決まっていない荷物の輸送経路の辺集合を Eb

4. 5. 2 コストに関する枝刈と現時点で決まっている辺順序割当て集合 Â を状態として持コストに関する枝刈は辺順序割当てが決定する度に現状でのち, これらを基に考えれる子ノードを全て作成していく. 子ノー

最低限のコスト (下限コスト) を計算し, 最適解であれば必ず越ドの作成には大きく 2 種類ある. それは子ノードの輸送者と基えないコスト (上限コスト) と比較し枝刈を行っている. ただし,のノードの輸送者が同じであるかである. 図 4 で考えると, こ

コストとは目的関数の値のことである.

のことは点線の枠組み内で子ノードを作るか枠組みを超えて子上限コストの初期値は, 中継を許さない輸送モデルでの最適ノード作るかの場合分けとなる. 同じ輸送者, つまり同じ枠組

解のコストとしている. これは, 本研究のモデルである中継をみ内であれば輸送順序を 1 増やして辺順序割当てを決定し, 異許した輸送モデルは中継を許さない輸送モデルよりもコストがなる輸送者, つまり枠組みを超える場合は輸送順序を 1 番目に大きくなることはないからである. もし, 中継を許さない輸送

して辺順序割当てを決定する. このようにして辺順序割当てがモデルで輸送ができない場合は上限コストの初期値を +∞ と決まれば, 基のノードの Eb から担当を決めた辺を除き,Â に新した. また, 探索中に辺順序割当て集合 A から成る輸送経路のしく決定された辺順序割当てを加えた状態を子ノードの状態とコストが現状の上限コストよりも良い値であった場合は上限コ

する. これらの操作を Eb が空集合となるまで繰り返すことでストを更新し, より効率的に枝刈をするようにしている.

全ての辺順序割当て集合を列挙する. また, 各辺順序割当てが次に下限コストについて説明する. 下限コストは探索木の各決定されたときに, それが最適解となり得るのかを判定し枝刈ノードで, 既に決まった輸送順序割当て集合 Â とまだ担当が決をしている. この枝刈については 4. 5 節にて説明する. 本研究

まっていない辺集合 Eb の二つ状態から計算している. 本研究の探索木は深さ優先で作成している. これは 4. 5. 2 節で説明しでは二つの下限コスト関数 Cost1 (Â, Eb ), Cost2 (Â) を使い, 各ている上限コストを計算するには全ての辺の担当を決めきらな

ノードにおいて値が大きい方をそのノードでの下限コストとしければ計算が不可能であるためである. 以上で説明した手法のている.

詳細について Algorithm1 で示す.

4. 5 探索木の枝刈
本研究の探索木は枝刈を複数種類行っている. 枝刈は各ノードで辺順序割当て a が決定するときに時刻・コスト・輸送順序のそれぞれ観点から最適解とならないか判定している. 以降それぞれの枝刈条件について説明する.

4. 5. 1 時刻に関する枝刈時刻による枝刈は担当することが不可能な輸送者と辺のペアを考える方法である. 例えば, ある辺 ebik を輸送者 uj が担当することになったとする. 各輸送者には目的地 d(uj ) に辿り着かなければならない時刻があり,uj の場合は td (uj ) となる. そのため,uj と ebik の位置関係ため, 最も早く輸送しても td (uj ) に間に合わない場合がある. すなわち, 移動可能となる時刻 ts (uj )Cost1 (Â, Eb ) はまだ担当が決まっていない辺を考慮したものである. これは, 既に決まった辺順序割当て集合 Â の部分を各輸送者が輸送したときにかかるコストとまだ決まっていない辺
集合 Eb の重みの和を合わせたものである. 輸送者 uj が辺順序
割当て a(i, k, j, ℓ) の輸送をするときにかかるコスト c(a) は,aの一つ前の辺順序割当て a′ (i′ , k ′ , j, ℓ − 1) の辺 ea′ の終点から

ea の始点まで移動距離と荷物を輸送する距離の合計であるため, 次のような式となる. ただし,ℓ = 1 ときは輸送者は初期値の出発地点から向かうため vd (ea′ = s(uj )) とする.

c(a) = W (vd (ea′ ), vs (ea )) + w(ea )(4)

式 (4) これを使い,Cost1 (Â, Eb ) を表すと式 (5) のようになる.

Cost1 (Â, Eb ) =∑a∈Â

c(a) +

∑
e∈Eb

w(e)

(5)

表 1 中継の有用さの実験

一方 Cost2 (Â) は担当が決まっている辺のみを考慮したものである. これは, 現状で決まっている辺順序割当て集合 Â で全ての荷物の輸送が終わったと仮定して, そのときの全ての輸送
経路のコストを考える. Â より定まった輸送経路集合を PˆU とすると,Cost2 (Â) は式 (5) のようになる.

Cost2 (Â) =∑len(pu )

荷物数

4

3

2

輸送者数

4

4

4

中継点の限定数234

中継をしたサンプル数

6

5

2

中継のみ

3

2

1

中継なしの平均移動距離14,074.3 11,136.7

9,221

中継をした平均移動距離13,126 9,733.3 8,567

減少率

(6)

pu ∈PˆU

6.7

12.6

7.1

表 2 輸送順序の枝刈の実験

本研究で二つの下限コストの使用した理由は探索木作成におサンプル 1 サンプル 2 サンプル 3
荷物数

3

2

3

輸送者数

3

3

4

中継点の限定数242荷物の輸送経路の総辺数

9

10

9

枝刈なし (sec)

464.9

5,636.8

2,015.0

枝刈あり (sec)

121.6

355.2

640.1

いて根に近いノードと葉に近いノード両方において効率的に枝刈をするためである. 根に近いノードではまだ担当が決まっていない辺が多くあるため,Cost1 (Â, Eb ) の値が大きくなりや
すい. 一方, 葉に近いノードではほとんどの辺の担当が決まっているため, 輸送が行う輸送者の目的地点までの帰路を考えた

Cost2 (Â) の方が値が大きくなりやすい. このようにできる限者が移動する距離を比較した. その実験結果を表 1 に示す. たり下限コストの値を大きくなるようにし, 枝刈がより多く行わだし,“中継のみ” というのは中継可能な輸送モデルの場合のみれるようにしている.

で輸送が行えたサンプルの数である.

4. 5. 3 輸送順序に関する枝刈

表 1 より, 中継可能な輸送モデルでしか輸送が行えないサン

輸送順序に関する枝刈は補題 13 を利用した枝刈である. 新プルが存在していることがわかった. また, 中継可能な輸送モデ

しく辺順序割当てが決定したとき, その辺順序割当てを含めたルの方が中継を許さない輸送モデルに比べて輸送者の平均移動

現段階での辺順序割当て集合 Â から輸送順序関係グラフを作距離が短いこともわかった. これらのことから, 我々の提案した成し, そのグラフが矛盾しているかどうかを判定する. 矛盾しモデルが有用であると言える.

ていれば補題 13 より輸送不可能であるため枝刈を行う.

5. 2 枝刈の効率に関する実験

5 実

験

この章では, 次の二つの目的で実験を行なった. 一つ目の目
的は中継可能な輸送モデルが中継を許さない輸送モデルに比べ有用であるかであり, この実験結果は 5. 1 節で詳細を述べている. 二つ目は探索木の枝刈を利用した手法が我々のアルゴリズ
ムで時間計算量を軽減することに有用であるかであり,5. 2 節で実験結果について詳細を述べている.
これらの実験には OS が Mac OS High Sierra,CPU が Intel

Core i5 1867MHz, メモリが 8GB であるコンピュータを使用
し,C++ (gcc 4.2.1) を用いて行なった.

5. 1 中継の有用さの実験中継可能な輸送モデルの方が中継を許さない輸送モデルに比べ有用であることを確認するため実験を行った. 実験で使用した道路ネットワークは京都市の道路ネットワークを使用し, それはおよそ北大路通り・川端通り・丸太町通り・白川通りの四つの通りに囲まれたものである. サンプルは次のデータセット
より作成した.

•V = 8556,E = 10168 の道路情報グラフ.

•

s(u) と d(u) はランダム,ts (u) と td (u) は 0〜10,000 の範囲でランダム. ただし,ts (u) と td (u) で最低でも 3,000 の間
隔を空けている•s(b) と d(b) はランダム,ts (b) は 0〜3,000 の範囲でランダム,td (b) は 7,000〜10,000 の範囲でランダム.

•利益関数の定数 β は β = 1 に設定.

実験には, それぞれの荷物数・輸送者・中継点の限定数の場合
で 10 個のサンプルを作成し, その 10 個の各サンプルで全輸送

探索木を枝刈する手法によって時間計算量を軽減することを確認するため, 枝刈をする条件を変えて最適解を導くまでの時間を計測した. 各サンプルは 5. 1 節と同じデータセットを使用
した.
まず, 輸送順序の枝刈に関する実験を行った. 実験方法は同
じサンプルに対し輸送順序の枝刈を行う手法と行わない手法とで最適解を求め, 実行時間を計測した. その結果を表 2 に示す.
これを見ると, 輸送順序の枝刈により大きく実行時間が抑えることが可能となっている. これから, 輸送順序の枝刈の要と成っている DAG は本研究のモデルにおいて重要な性質であることがわかった.
次に時刻とコストの枝刈の実験を行った. この実験では輸送
順序の枝刈のみする手法, 輸送順序と時刻の枝刈をする手法, 輸
送順序とコストの枝刈をする手法,3 つ全ての枝刈をする手法の計 4 つの手法での実行時間を比較した. 全ての手法で輸送順序の枝刈が含まれているは, 節で示した通り, 最低でも輸送順序の枝刈を行わなければ極めて小さい規模でしか現実的な実行時間
では実験を行うことができないためである. この実験結果の結果が表 3 である. 結果より,3 種類全ての枝刈をした手法が大きく実行時間を抑えることができ, また時刻に比べコストの枝刈の方が効果が大きいことがわかった. 一方, サンプル 3 とサンプ
ル 4 とを見比べると, 輸送者数・荷物数・限定数の条件は同じだが全ての枝刈を使用したときの実行時間が 3 秒と 63 秒とで大きく異なっている. これを調べてみると 4. 5. 2 節で説明した
上限コストの初期値の有無が原因であることがわかった. 実際に表 3 よりも大きな規模で上限コストの初期値の有無がどれほど影響するか実験すると表 4 のようになった. このように上限

表3

時刻・コストの枝刈の実験
サンプル 1

サンプル 2 サンプル 3 サンプル 4

荷物数

3

2

3

3

輸送者数

4

4

5

5

中継点の限定数

2

4

2

2

荷物の輸送経路の総辺数

9

10

9

9

輸送順序のみ (sec)679.3

2,242.6

2,549.8

2,581.9

輸送順序と時刻 (sec)

556.8

900.4

1,423.080.2

輸送順序とコスト (sec)

8.0

16.1

1.9

129.5

枝刈全て (sec)

11.2

12.5

3.0

63.0

表4

上限コストの初期値の実験
サンプル 1

サンプル 2 サンプル 3 サンプル 4

荷物数

3

3

3

3

輸送者数

8

8

5

5

中継点の限定数

2

2

3

3

荷物の輸送経路の総辺数

9

9

12

12

上限コストの初期値

あり

なし

あり

なし

枝刈全て (sec)

1.2

1,144.8

11.2

32,732.0

コストの初期の有無により実行時間が大きく異なっている. そのため, これよりも大きな規模での実験を可能にするためには上限コストの初期値の問題を解決するか, 更に良い枝刈手法を考える必要がある.

6 おわりに
本研究では宅配業者の負担軽減に繋がる新しい輸送モデルとして, 一つの荷物を複数人によって中継して輸送するということも考慮した中継可能な協調型輸送モデルを提案し, このモデルの最適化問題の厳密解アルゴリズムを考案した. さらに, この問題には DAG が密接に関係していることも発見し, 計算量をより小さくすることができた.
本研究では, 荷物という物を輸送することについて取り組ん
だが, ヒッチハイク等の人を輸送する場合にも応用できると考えており, その場合には人の待ち時間も考慮する必要がある. また, 将来的に予想されるロボットによる無人輸送にも, ロボット間が連携して輸送するという点で貢献できると考えている.
しかし, 現状いくつかの現実的ではない条件設定下における手法となってしまっている. これら条件設定がない場合にも拡張できる手法についても検討する必要がある. また, 実験結果でも述べたようにこれよりも大きな規模でも動かすには上限コストの初期値の設定や更に効率的の良い列挙方法の考案が求められる. 今後としては, これらの問題解決のためヒューリスティッ
クな手法も検討に入れつつ取り組んでいきたい.

謝辞本研究は JSPS 科研費基盤研究 (S) No. 17H06099, (A) No.

18H04093, (C) No. 18K11314 の助成を受けたものです．
文

献[1] Y. Jiang, J. Shang, Y. Liu, J. May, “Redesigning promotion strategy for e-commerce competitiveness through pricing and recommendation,” International Journal of Production Economics , 167(3), 257-270, September 2015[2] G. Mallapragada, S.R. Chandukala, Q. Liu, “Exploring theeﬀects of what (product) and where (website) characteristics on online shopping behavior,” Journal of Marketing, 80(2) , 21-38, March 2016

[3] X. Xu, C.L. Munson, S. Zeng, “The impact of e-service offerings on the demand of online customers,” International
Journal of Production Economics, 184(2), 231-244, February 2017.
[4] D. Yan, Z. Zhao, W. Ng, “Eﬃcient Algorithms for Finding
Optimal Meeting Point on Road Networks,” Proceedings of
the VLDB, 4(11), 968-979, 2011.
[5] E. Ahadi, M.A. Nascimento, “k-Optimal Meeting Points
Based on Preferred Paths,” ACM SIGSPATIAL, Poster Pater, October 31 - November 3, 2016[6] G.B. Dantzig, J.H. Ramser, “The truck dispatching problem,” Management Science, 6(1), 80-91, 1959
[7] G. Nagy, S. Salhi, “Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries,” European journal of operational research, 162, 126141, 2005
[8] W. Ho, G.T.S. Ho, P. Ji, H.C.W. Lau, “A hybrid genetic
algorithm for the multi-depot vehicle routing problem,” Engineering Applications of Artificial Intelligence, 21, 548-557,
June, 2008
[9] B Yu, Z.Z. Yang, J.X. Xie, “A parallel improved ant
colony optimization for multi-depot vehicle routing problem,” Journal of the Operational Research Society, 62(1),183-188, January 2011[10] S. Salhi, A. Imran, N.A. Wassan, “The Multi-Depot Vehicle
Routing Problem with Heterogeneous Vehicle Fleet: Formulation and A Variable Neighborhood Search Implementation,” Computers & Operations Research, 52, 315-325,
December 2014[11] R. Lahyani, L.C. Coelho, J. Renaud, “Alternative formulations and improved bounds for the multi-depot fleet size
and mix vehicle routing problem,” OR Spectrum, 40(1),125-157, 2018[12] A. Garcia-Najera, J.A. Bullinaria, “An improved multiobjective evolutionary algorithm for the vehicle routing
problem with time windows,” Computers & Operations Research 38(1), 287-300, January 2011[13] T. Vidal, T.G. Crainic, M. Gendreau, C. Prins, “A Hybrid Genetic Algorithm with Adaptive Diversity Management for a Large Class of Vehicle Routing Problems withTime Windows,” Computers & Operations Research 40(1),475-489, January 2013[14] X. Zhang, Y. Asano, M. Yoshikawa, “Mutually beneficial
Confluent Routing,” IEEE Transactions on Knowledge andData Engineering, 28(10), 2681-2696, 2016.
[15] K. Takise, Y. Asano, M. Yoshikawa, “Multi-user Routing toSingle Destination with Confluence,” ACM SIGSPATIAL.
Poster Pater, October 31 - November 3, 2016[16] B. Cao, L. Alarabi, M.F. Mokbel, A. Basalamah, “A scalable dynamic ride sharing system,” Proceedings of the 16th
IEEE International Conference on Mobile Data Management (MDM), 2015.
[17] F. Drews, D. Luxen, “Multi-hop ride sharing,” Proceedings of the Sixth International Symposium on Combinatorial Search, 71-79, 2013.
[18] 藤井貴彬, 瀧瀬和樹, 浅野泰仁, 吉川正敏, “中継可能な輸送モデ
ルの提案,” DEIM, 2017.