“安定マッチングに基づく貨客混載車両のキャリア間提携経路最適化”
8
0
0
全文
(2) の定式化を行い, これに基づく旅客の移動経路探索問題 について述べる. そして, 安定マッチングに基づく同乗 者決定手法を含む一連の車両経路決定アルゴリズムを 提案する. 4 章では提案手法の有効性をシミュレーショ ンにより検証する. 5 章では, 本稿のまとめと今後の研 究方針について述べる.. 2 2.1. 問題設定 キャリア間提携配送車両ルーティング問題. ここではまず, 貨物輸送に関して複数の運送事業者に サービスを求める顧客が存在する場合の車両ルーティン グ問題 (The Shared Customer Collaboration Vehicle Routing Problem 以下, SCC-VRP12) ) について考え る. 同じ時間帯に共通の顧客にサービスを提供しなけれ ばならないキャリア間のコラボレーションは, 共通のエ リアへの度重なる往復を削減し, 使用車両数と走行距離 の両方の面での節約を達成することができると考えら れ, こうしたキャリア間の提携から得られる潜在的な利 益をルーティングに焦点を当てて最適化することを試 みたのが SCC-VRP である. 本稿では SCC-VRP を解 く方法論として 2 つの代替的な混合整数線形計画問題 の定式化の提案をする. 各定式化はそれぞれ異なる特徴 をもっており, 一方は車両台数を複数台に分散させた輸 送を想定し, もう一方は一度に全ての貨物を輸送するこ とを想定した積載量をベースとした定式化がなされて いる. なお, ここでの積載量とは, 貨物の重量として扱う ことに注意する. Table 1 に, 最適化問題を設定する際 に用いる主な記号の定義をまとめる.. Table 1: Definition of Symbols Symbol C N m = |C| n = |N | or Q V E Er cij dri Nr Ci. Parameter Set of carriers operating in a given area Set of customers Number of carriers Number of customers Depot of carrier r ∈ C Carriers’ vehicle capacity Set of customers and depots Set of edges Set of edges associated with carrier r ∈ C Routing cost of each edge (i, j) ∈ E Demand of customer i with respect to carrier r Set of customers for carrier r ∈ C Set of carriers for customer i. あるエリアにおいて, 物流コストを削減するために協 力し合う事業者の集合が存在すると考える. 顧客の中に は複数の運送事業者に需要があり, 異なる運送事業者が 共有している顧客がいると仮定する. また, キャリア間 のコラボレーションとは, 各キャリアが需要の一部を他 のキャリアに譲渡することを意味する. C をあるエリ ア内におけるキャリアの集合とし, N を同エリア内の顧 客の集合とする. 各キャリア r ∈ C は自身の発着点 or を有し, 容量 Q(全てのキャリアで同一) の同質な車両群 を持つとする. G = (V, E) は, 各顧客とキャリアの発着 点を示すノードの集合 V と, それらを結ぶエッジの集 合 E から成る有向グラフを表す. さらに, Nr をキャリ ア r ∈ C の顧客の集合とするとき, キャリア r に関連す. るエッジを E r と表すと, E r = {(i, j) ∈ E : i, j ∈ Nr , or(i = or and j ∈ Nr ), or(i ∈ Nr and j = or )} であ る. また, 各エッジ (i, j) ∈ E は経路コスト cij ≥ 0 をも つ. このとき, キャリア r に対する顧客 i の需要 dri ≥ 0 は, dri > 0 のときに i はキャリア r の顧客であること を示す. Ci ⊆ C を顧客として i を受け持つキャリアの 集合とする. これを用いると, |Ci | > 1 のとき, 顧客 i の キャリア s ∈ Ci に対する需要 dsi は, これをキャリア r が提供することが可能となる. さらに, 顧客 i のキャ リア r, キャリア s に対するそれぞれの需要 dri , dsi は キャリア間で互いに交換して提供することを可能とす る. SCC-VRP の概念図を示す Fig. 1 では, 各エッジ に経路コストが設けられ, 2 つのキャリア発着点ノード B oA , oB と, 各キャリアに需要 dA x , dx を持つ 3 つの顧 客ノード i, j, k ∈ N から成るネットワークを示す.. Fig. 1: Concept of SCC-VRP SCC-VRP の最大の目的は, 顧客に需要を提供する キャリアの総経路コストを最小化することであり, この とき各キャリアは発着点 or を始点とし, 同一の発着点 or を終点とする一連の経路を走行し, 各経路が提供す る全体の需要は容量 Q を超えてはならないものとする. 2.2. 逐次的旅客移動最短経路問題. ここでは, 定められた貨物輸送経路に基づき, ある時 刻における出発地, 目的地が近い者同士の利用を想定し たライドシェアリングの同乗者ペアを決定するマッチ ングと, 旅客移動を含めた各サービス提供車両の経路を 決定する流れを説明する. ここで, 以下の仮定をおく. 仮定 1. 1. 全利用者の出発地, 目的地の情報は所与とする. 2. 想定する道路網は貨物輸送経路の決定に基づくこと から, ノードとエッジからなるネットワークとして表現 する. 旅客の移動に関して述べる. まず基準となる貨物輸送 経路を決定した後, ライドシェアリング利用客の出発地 ノード座標, 目的地ノード座標が新規デマンドとして 発生する. この情報に基づき, ドライバーを除く車両の 定員数を q = 2 名として利用客同士のペアを組むマッ チングを行い, 貨物輸送を担ういずれかのキャリアの 車両に割り当てられるとする. 利用客は目的地に到達 するまで, 異なる貨物輸送キャリアの車両を乗り継いで 目的地へ向かうものとする. これは, キャリア間の連携.
(3) によって全体経路コストを削減することを目的とした SCC-VRP の考えに基づく. このとき, 各キャリアが貨 物輸送を担うエリアは定められていることから, ライド シェア利用客の車両乗り換えが発生する場合にのみ, 車 両はエリア間を往来するものと考える.. 車両ベース定式化 (VF). 3.1.1. 各キャリア r ∈ C について, Kr を同種車両の集合とす る. ここでは２つの決定変数を使用し, 一方はキャリアに よって走行されるエッジを示すルーティング変数 x であ り, もう一方はキャリアへの顧客需要の配分を示す変数 z である. このとき各キャリア r ∈ C, k ∈ Kr , (i, j) ∈ E r について, 車両ベース定式化におけるバイナリルーティ ング変数として xkij を導入する. これは, エッジ (i, j) が 車両 k によって利用されるときに 1 をとり, そうでな いときは 0 となる変数を示す. さらに, キャリア r ∈ C k に対する顧客の需要割り当てに関しての変数 zirs を導 入する. これは, 顧客 i ∈ Nr のキャリア r に対する需要 dri が, キャリア s ∈ Ci によって車両 k ∈ Ks で提供さ れる場合にのみ正の値をとり, そうでないときは 0 とな る変数である. 以上を踏まえ, 車両台数をベースとした 最適化問題を次のように設定する.. Fig. 2: Sequential insertion algorithm このとき, 貨物輸送経路を既存経路として旅客輸送を 組み込んだ新経路を決定する本研究の経路探索アルゴ リズムは, 逐次挿入法の考えに基づく. 逐次挿入法とは, 既に決定した経由順序の間に, 新デマンド i の乗車地点 oi と降車地点 di を挿入する手法 13) である. 新デマンド が割り当てられる際の経路探索は, 経由地点の経由順の 列挙と, 各経由地点間の経路探索に分けられる. このと き, ライドシェアサービスに求められるのはリアルタイ ムにデマンドの割り当てが可能な手法であり, 文献 13) では実際に逐次挿入法を利用した経路探索の有効性が 示されている. Fig. 2 では, 黒い点を顧客ノード, 黒い 実線を既存経路となる貨物輸送経路として考え, このエ リアに新規デマンドとしてライドシェア利用客の出発 地, 目的地の情報が与えられた際に, 赤色の新経路を更 新する逐次挿入法の適用例を示している. このときラ イドシェアを利用する旅客の立場となって考えると, 貨 物の輸送を伴う場合, 旅客は点線の最短移動経路に対し て, 赤色の経路が示すように顧客ノードを経由して目的 地へ向かっていくことがわかる. 貨客混載を導入した際 の旅客の迂回率に関する評価については後の章で扱う.. 3 3.1. 同乗者マッチングを含む経路最適化問題 最適貨物輸送経路の決定. 以下では, SCC-VRP を解く 2 つの MILP 定式化を 行う. 1 つ目は車両台数をベースとした定式化であり, キャリアの各車両が通過するエッジに関連付けられた 決定変数を使用する. 2 つ目の定式化は積載量をベー スとしたものであり, キャリアが訪問した頂点 (=顧客) における車両の荷重に基づいたものとなっている. 各定式化にあたり, Table 1 で示した記号に加え, 次 のような追加表記を使用する. S ⊂ V のとき, δ + (S) = {(i, j) ∈ E|i ∈ S, j ∈ V \S} は出次数を示す. 反対に, δ − (S) = {(i, j) ∈ E|i ∈ V \S, j ∈ S} は入次数であ ることを示す. また, S ⊂ V かつキャリア r ∈ C の場 合, δ + (S) と δ − (S) の E r のエッジの集合はそれぞれ, δr+ (S) = δ + (S) ∩ E r と δr− (S) = δ − (S) ∩ E r のように 表記される.. ∑ ∑. min xk ij. s.t.. ∑ ∑. ∑. cij xkij. (1). r∈C k∈Kr (i,j)∈E r. k zirs = 1, i ∈ N, r ∈ Ci. (2). s∈Ci k∈Ks. xk (δr+ (or )) ≤ 1, r ∈ C, k ∈ Kr x. k. (δr− (i)). −x. k. (δr+ (i)). = 0,. r ∈ C, k ∈ Kr , i ∈ Nr x. k. (δr+ (W )). ≥. (3) (4). k zisr ,. r, s ∈ C, k ∈ Kr , W ⊂ Nr \{or }, i ∈ W ∩ Ns (5) ∑ ∑ k dsi zisr ≤ Q, r ∈ C, k ∈ Kr (6) i∈Nr s∈Ci. ∑ ∑. i∈Nr s∈Ci. k−1 zisr ≥. ∑ ∑. k zisr ,. i∈Nr s∈Ci. r ∈ C, k ∈ Kr \{min Kr }. (7). xkij ∈ {0, 1}, r ∈ C, (i, j) ∈ E r , k ∈ Kr. (8). 0≤. (9). k. k zirs ,. i ∈ N, r, s ∈ Ci , k ∈ Ks. 式 (1) は, 通過するエッジの総コストを表す目的関数 とその最小化を示す. 制約条件に関して, 式 (2) は異な るキャリアに対する各顧客の需要が, 必ずあるキャリア によって提供されることを示す等式制約である. 式 (3), 式 (4) は経路のフローバランスを示したものである. 式 (5) は r に関する顧客ノードの集合 W について, 集合 W 内のある顧客需要がキャリア r の車両 k によって提 供される場合, その経路は集合 W から出ている少なく とも 1 つのエッジを使用しなければならないことを課 すことで, 顧客 i に需要が提供されたときの経路と発着 点との接続性を示している. 式 (6) は, 提供する需要が 車両の容量 Q を超えないことを保証するための不等式 制約である. 式 (7) は, キャリア r の k − 1 台目の車両 が使用されない限り, k 台目の車両は使用されないこ とを課すものである. 最後に, 各変数の領域は式 (8), 式.
(4) (9) で定義される. 式 (1) から式 (9) において, ルーティ ∑ ング変数 x は r∈C |E r ||Kr |, 需要割り当て変数 z は ∑ 2 i∈N,s∈Ci |Ci | |Ks | のサイズを有する. 3.1.2. 積載量ベース定式化 (LF). 以下では, 決定変数に車両を区別する k を関連させ ることなく, キャリアの総積載量に注目した定式化を示 す. キャリアは顧客の需要を複数の車両に分割して運ぶ という概念がなく, 十分な容量をもつ一台の配送車をも つと考える. ここでは次のような決定変数を導入する. まず, 車両ルーティング変数 xrij は, キャリア r ∈ C の 経路においてエッジ (i, j) ∈ E r が利用される場合に 1 をとり, そうでない場合は 0 をとるバイナリ変数を示 す. また, 需要割り当てに関しての変数 zirs を導入す る. zirs は, i ∈ Nr , r, s ∈ Ci のときに, 顧客 i のキャリ ア r に対する需要 dri がキャリア s によって提供される 場合に正の値をとり, そうでない場合は 0 をとる. 車両 k ベースの需要割り当て変数 zirs と比較して, 車両 k に 依存しなくなったという点のみが異なっている. 最後 rs rs に, 積載量に関する変数 lij を新たに定義する. lij は, r r ∈ C, h ∈ Nr , (i, j) ∈ E のときにキャリア r がエッ ジ (i, j) を通って顧客 h に需要を提供するときの積載 量を示す. 以上の決定変数を用いて, 積載量をベースと した最適化問題を次のように設定する. ∑ ∑ min cij xrij (10) r xij. s.t.. ∑. r∈C (i,j)∈E r. (11). s∈Ci. xr (δr+ (i)) − xr (δr− (i)) = 0, i ∈ N, r ∈ Ci (12) xs (δs+ (i)) ≥ zirs , i ∈ N, r, s ∈ Ci (13) ∑ rh + s l (δr (or )) = dh zhsr , r ∈ C, h ∈ Nr s∈Ch. (14) lrh (δr+ (i)) − lrh (δr− (i)) { 0, if h ̸= i ∑ = − s∈Ci dsi zisr , if h = i ∑ rh lij ≤ Qxrij , r ∈ C, (i, j) ∈ E r. (15) (16). h∈Nr. xrij ∈ {0, 1}, r ∈ C, (i, j) ∈ E r. (17). 0 ≤ zirs , i ∈ N, r, s ∈ Ci 0≤. r ∈ C, s ∈ Nr , (i, j) ∈ E. 3.2. 安定マッチングに基づく同乗者決定アルゴリズム. ここでは, ライドシェアの移動車両を共にするペアを 決定するための, 利用客同士の同乗者マッチングアル ゴリズムを示す. 本稿では, 全ての利用客が必ず同乗者 ペアを組むものとし, ライドシェアを利用する偶数人の グループに対して, ドライバーを除く車両の定員数を q = 2 とし, これを「一対一マッチング問題」として考 えることで GS アルゴリズムによりマッチング解を求 める. マッチング理論について議論するにあたり, 選好 を以下のように定義する. 定義 1. 集合 X 上の個人 i の選好 ⪰i とは, 以下の条件 を満たす X 上の二項関係である.. 1. x ⪰i x, ∀x ∈ X. zirs = 1, i ∈ N, r ∈ Ci. rs lij ,. ことを保証するものである. 続いて, 式 (14) から式 (16) rs は積載量に関する変数 lij のフローバランス制約であ り, 提供された需要に応じてエッジを介して積載量を更 新していくことを示す. ルーティング変数と積載量に関 する変数間の関係は式 (16) で示され, キャリア r が通 る各道筋において積載量が常に容量 Q 以下になること を課すものである. 各変数の領域は式 (17) から式 (19) に示す通りである. 式 (10) から式 (19) において, バイ ∑ ナリルーティング変数 x は r∈C |E r |, 需要割り当て変 ∑ 数 z は i∈N |Ci |2 のサイズを有することから, キャリ アの所有する車両に依存しない積載量ベースの定式化 では, 決定変数のサイズが小さくなることがわかる.. (18) r. (19). 車両ベースの場合と同様, 式 (10) は総経路コストを 目的関数とし, その最小化を意味する. 式 (11) は顧客 i の需要が必ずあるキャリアに割り当てられることを保 証するものである. また式 (12) はあるキャリアの全ての 経路を集約して考えた場合について, ある顧客ノードを 訪れたらそのノードを出るという経路上での流れを示 したものである. 式 (13) は, 変数 x と z を関連付け, 顧 客 i のキャリア r に対する需要がキャリア s によって提 供された場合, ルーティング変数 xs (δs+ (i)) が 1 となる. 2. [x ⪰i y and y ⪰i z] ⇒ x ⪰i z, ∀x, y, z ∈ X 3. x ⪰i y or y ⪰i x, ∀x, y ∈ X x ⪰i y とは, 個人 i の選好のもとで, y より x を同程度 以上に好むことを表す. すなわち同乗者を決める際には, 各利用客の選好を決 め, マッチングを実行するというステップを踏む. ここ で, GS アルゴリズムで得られるマッチング µ は安定で あり, リクエストを送る側の希望を最も反映するという 意味で, リクエストを送る側にとって最適となる. 文献 14) によるマッチング手法では, 同乗者がドライバーに 対してリクエストを送っているが, 今回は同乗者とドラ イバーといった立場の異なる相手同士のマッチングで はなく, 利用客同士のマッチングを行う. したがって本 稿では, リクエストの申し込み側と受け付け側を区別す る際, 出発地から目的地までの移動距離が長く, サービ スを提供する側にとって得られる利益が高いことが想 定される利用客の上位半数を申し込み側とし, 残り半数 の利用客をリクエストを受け付ける側として区別する.. 3.2.1. 利用客選好決定. ここではまず, 各利用客の同乗者選好を決定する最適 化問題を設定する. 利用客はライドシェアをすることに よって単独でタクシーを利用する場合と比較して, 同乗 者となる相手の出発地点と目的地点を経由する必要が 生じる. これを各利用客の迂回路として考え, この迂回 路が小さい順に並べたものを各利用客の同乗者の選好.
(5) リストとする. リクエストを申し込む側の利用客を i, 受け入れる側の利用客を j とし, i と j がペアとなった u 場合, 利用客同士のペア u に関する迂回路の距離 Dij を 以下の様に定義する. u Dij = d{oi , oj } + d{di , dj } √ d{oi , oj } = (oi,x − oj,x )2 + (oi,y − oj,y )2 √ d{di , dj } = (di,x − dj,x )2 + (di,y − dj,y )2. (20) (21) (22). oi = (oi,x , oi,y ), di = (di,x , di,y ) はそれぞれ, 利用客 i の 出発地および目的地の座標を示す. このとき, U を同じ エリアを移動する偶数人のライドシェア全利用客の集 合として表すと, リクエストを申し込む側となる利用客 は全利用客数の半数となることから, {oi }i∈{1,··· ,|U |/2} , {di }i∈{1,··· ,|U |/2} であり, 受け入れる側の oj , dj に関し ても同様の関係が成り立つ. さらに, 以下のバイナリ変数 xuij を導入する. { xuij =. 1, if user i is assigned to user j 0, otherwise. (23). 式 (20)∼式 (23) より, 以下の最適化問題を設定する. ∑ u u min Dij xij (24) u xij. j∈U. u s.t. Dij = d{oi , oj } + d{di , dj } ∑ xuij = 1. (25) (26). j∈U. xuij ∈ {0, 1}. (27). この最適化問題において式 (24) が最小となるとき, す u なわち xuij = 1 のときの最小の Dij となる利用客 j が, 利用客 i にとって最も好ましい同乗者となる. しかしこ れを一度解くだけでは, 利用客 i にとっては最も好まし い同乗者を 1 人しか選ぶことができない. このとき, リ クエストを申し込む側である利用客 i は上記の最適化 問題を |U |/2 回繰り返し解くことによって, 各利用客の 選好を求めることができる. イテレーション回数を tu (1∼|U |/2) と表し, 利用客 ∗ i が tu 回目に求められた最適解を xuij,t として, この u u∗ xij,tu を求めるたびに ∗ =0 xuij,t u. (28). と制約を追加し, 現段階で最適となった同乗者候補以外 で繰り返し最適化問題を解いていくことにより, 利用客 ∗ ∗ ∗ ∗ , · · · , xuij,|U , · · · , xuij,t , xuij,2 i の選好 Pi = (xuij,1 |/2 ) を u 求めることができる. また, リクエストを受け入れる側 の利用客 j の選好 Pj もこれと同様にして決定すること ができる.. 3.2.2. 同乗者決定マッチング. 続いて, 求められた各利用客の選好から, GS アルゴリ ズムを用いてマッチングの解を求める. このときの GS アルゴリズムのフローチャートを Fig. 3 に示す.. Fig. 3: Passenger matching algorithm まず, 利用客全員が同乗者候補がいない状態から開始 する. Fig. 3 中では, 利用客 u を申し込み側, 利用客 r を受け入れ側として扱っている.「unmatched」の利用 客 u は, 自身の選好の先頭の同乗者候補である利用客 r に対してリクエストを送り, もし r が「unmatched」の 状態であれば利用客 u のリクエストを受け入れ, u と r のマッチングが成立し,「matched」の状態となる. し かし, 利用客 u が r に対してリクエストを送った際に 「matched」の状態であるならば, その時点での同乗者候 補の利用客 u∗ と u のうち, 利用客 r の選好順位が高い 方が「matched」の状態となる. このとき「unmatched」 の状態となった利用客は, 自身の選好リストから利用客 r を削除し, 再度選好リストの先頭の利用客に対してリ クエストを送る. これを繰り返し, 最終的に得られたマッ チングの解が, ライドシェアリング同乗者となる.. 3.3. 貨客混載車両の経路最適化. ここでは, 貨物, 旅客輸送経路を統合することによっ て, 最終的に各キャリアが走行する経路を決定すること を考える. 本稿では, 目的地までの到達コストを推定し, 推定値が小さいノードを優先して経路を探索する A∗ ア ルゴリズムに基づく最短経路探索を行っていく. ここで, A∗ では, あるノード n から目的地までの推定最小コス ト h∗ (n) をヒューリスティック関数と呼ぶが, 本稿では この推定最小コストとして, 貨物輸送の際に決定された 各顧客座標から, 移動車両を共にする各ペアの目的地を 結ぶユークリッド距離を用いる. ここで, ペアとなった ライドシェア利用客 1, 利用客 2 の目的地ノード座標を それぞれ (xd1 , yd1 ), (xd2 , yd2 ) とし, 貨物輸送の対象で ある各顧客ノード座標を (xnr , ynr ) とすると, 各目的地 までの推定コスト R1 (nr ), R2 (nr ) は,. R1 (nr ) = R2 (nr ) =. √ √. (xnr − xd1 )2 + (ynr − yd1 )2 , ∀nr ∈ Nr (29) (xnr − xd2 )2 + (ynr − yd2 )2 , ∀nr ∈ Nr (30).
(6) として求められる. また, 貨物輸送の対象となっている 顧客ノードを次の経由ノード候補とすると, 現在地ノー ドからの距離は各顧客ノード間の経路コストに相当す る. これは, 貨物輸送経路を決定する過程で既に算出さ れている値であり, n 番目に経由するノードから n + 1 番目ノードへの経路コストという意味でこれを cn→n+1 と表す. したがって, n 番目の現在地ノードから利用客 1, 2 のいずれかの目的地 d1 , d2 までの推定コストを考 慮した次式を最小とする顧客ノード nr ∈ Nr を, 次の 経由ノードとして選ぶことでノード更新を行う.. C(n, d1 ) = cn→n+1 + R1 (nr ), ∀nr ∈ Nr. (31). C(n, d2 ) = cn→n+1 + R2 (nr ), ∀nr ∈ Nr. (32). 以上の推定コストを用いた経由ノードの選択を目的地 に到達するまで繰り返すことで, ライドシェア利用客の 移動経路として最短となる経由ノードを求め, 列挙され たノードを接続することで最短経路を求めることがで きると考えられる. しかしこの操作のみでは, 本来は貨 物輸送の経路として含まれていた顧客ノードが孤立し てしまう状態が発生し得る. 孤立顧客ノードが生じた場 合, 再度同じ経路を通って貨物を輸送する必要が生じる.. 場合 xrbc = 1) と最適解が得られていた部分に対し, XR true で xac = 1 となる部分を比較する. このような 経路が最適解として得られた場合には, xab = 1, xbc = 1 としてノード vb を経由ノードとして NRt rue に挿入し, XR true の経路を更新する. Fig. 4 では, 孤立顧客ノー ド 3 を経由ノードとして含んだ経路に更新する例を示 している. この操作によって 3.1 で得られた貨物輸送経 路の最適解を利用し, 重複経路を最小限に抑えることで, 貨客を混載した全体としての経路コストを削減するこ とができる. 貨物輸送とライドシェアリングによる旅 客輸送を組み合わせた, 車両経路を決定する一連の提案 アルゴリズムを以下にまとめる. 同乗者マッチングを含む経路最適化アルゴリズム. Step 1 : Determination of Cargo Transport Routes XC true ⇐ ∅, 顧客ノード座標 (xnr , ynr ), 需要量 dri を既知として, 式 (1)∼式 (9)(VF) または式 (10) ∼式 (19)(LF) を解くことで, 顧客の需要割り当て を行い, 最適貨物輸送経路を決定する. 最適解とし て得られたエッジを XC true に格納する. Step 2 : GS Alg. User’s Preference Determination 出発地ノード座標, 目的地ノード座標の情報から, 制約式 (25)∼式 (27), および式 (28) のもと式 (24) を tu (1∼|U |/2) 回解くことによって, リクエスト を申し込む側と受け入れる側の同乗者候補の選好 を決定する. Step 3 : GS Alg. Passenger Pair Decision Matching Fig. 3 に示した手順に従って, 利用客同士のマッチ ングを行うことで, 全ての利用客に関して移動車両 を共にする同乗者を決定する.. Fig. 4: Route update algorithm そこで, 貨物輸送経路の最適解である xkij = 1(VF の 場合) または xrij = 1(LF の場合) が格納されたエッジ の集合を XC true とする. すなわち, { (VF) xkij = 1 ∈ XC true ∀(i, j) ∈ E r , ∀k ∈ Kr (LF) xrij = 1 ∈ XC true ∀(i, j) ∈ E r , ∀r ∈ C (33) と表せる. また, ライドシェア利用客の最適経由ノードと して, 利用客の出発地, 目的地ノードを含む経由順に列挙 されたノードの集合を NR true と表し, NR true の各要 素を接続することで得られるエッジの集合を XR true と する. このとき, NR true の要素である経由ノード vi か ら vj の有向エッジを xij = vi → vj とすると, NR true の要素と XR true に関して,. xij (= vi → vj ) ∈ XR true. (34). という関係が成り立つ. これらを用いると, XC true の要 素である, xkab = 1(LF の場合 xrab = 1), xkbc = 1(LF の. Step 4 : Update Nodes on Passenger Travel Routes NR true ⇐ ∅, XR true ⇐ ∅, ライドシェア利用客 の移動エリアにおいて, 貨物輸送の対象となってい る顧客ノード座標に加えて, 各利用客の出発地, 目 的地ノード座標を経由候補ノード座標とする. Step 5 : Determination of Passenger Travel Routes 出発地から最も近い貨物顧客ノードから, 同乗者 2 人の出発地ノードを順に NR true に格納. ここから いずれかの目的地ノードに到達するまで, 式 (31), 式 (32) を最小とするノードを順次 NR true に格納. 一方の目的地に到達したら, もう一方の目的地ノー ドを NR true に格納. 全ての同乗者ペアの経由ノー ド NR true が決定されるまで繰り返す. Step 6 : Determination of Optimal Vehicle Routes NR true の各要素である経由ノードを接続するこ とで得られるエッジを XR true に格納. XC true と 比較して孤立貨物顧客ノードが生じた場合, 新たに 経路を挿入. NR true の目的地に到達する一つ前の ノードの最短隣接ノードへの経路を XR true に挿 入することで貨物輸送経路と接続する..
(7) シミュレーション検証. 4 4.1. 4.2. シミュレーション条件. シミュレーション対象エリアとして, Fig. 5 に示す 5 km×9 km のエリア範囲を設定した. Fig. 5 には各キャ リアの発着点の座標 (m 単位) が示してある. また, 黒い 四角で囲まれた数字は, 2.5 km×4.5 km の範囲で区切 られたエリア 1 からエリア 4 を表しており, 貨物輸送で は各エリアに配置されている 2 つのキャリアが, エリア 内に存在する顧客のみを共有顧客の対象として考える.. シミュレーション結果. まず, 貨客を混載した場合と, 混載せずに貨物と旅客 の輸送を分けた場合の総経路コストの比較を Fig. 6 に 示す. 青色が混載無し, 緑色が混載した場合の総経路コ ストを示しており, 削減率を赤色の点で示す. また, 総経 路コストを燃料費に換算することでの比較を行ったも のが Fig. 7 である. 燃料費は, 車両ベースと積載量ベー スで用いる車両の燃費が文献 15) よりそれぞれおよそ 16km/L, 9km/L であると想定し, ガソリン代の平均価 格を 125 円/L として 1km あたりに要する価格を求め, これを Fig. 6 に示す青色, 緑色の総経路コストと積を とることで燃料費として算出した.. Fig. 5: Simulation area and location of each carrier このとき, 平均顧客数を λ = 40 としてポアソン分布 に従って顧客ノード数を決定し, このノード数分だけ一 様分布した乱数を割り当てて各顧客ノード座標を決定 した. 車両容量 Q については, 各キャリアが Q = 1200 の車両 1 台を所有する場合 (積載量ベース定式化) と, Q = 350 の車両 3 台を所有する場合 (車両ベース定式 化) の 2 つのパターンを想定した. Table 2 では, Fig. 5 に示した各エリアの赤色, 青 色のキャリアに対する顧客の需要をそれぞれ d(Nred ), d(Nblue ), 顧客数を |Nred |, |Nblue | として表している.. Fig. 6: Route cost reduction ratio. Table 2: Demand volume and number of customers area. λ. Q. 1 2 3 4. 40 40 40 40. 1200, 1200, 1200, 1200,. 350 350 350 350. d(Nred ). d(Nblue ). |Nred |. |Nblue |. 949 1000 930 1049. 963 1035 900 995. 36 35 34 40. 35 35 34 40. ライドシェアを利用する旅客の移動方向は, Fig. 5 に 示すエリア 1 から 2 へ移動するグループと, エリア 4 か ら 3 へ移動するグループについて, 各グループ 4 名の移 動を考えた. このとき, ライドシェアリングでは, 出発, 目的地点が類似した客同士の移動を考えるため, 出発地 と目的地の分布が二変数正規分布に従うものとして各 利用客の出発, 目的地を決定した. Table 3 が各利用客 の出発地, 目的地座標を示す.. Table 3: Coordinates of origin and destination user 1 2 3 4. area1→2 o d (2250, 4250) (8000, 3250) (2000, 4500) (7250, 3500) (2750, 4750) (8000, 3750) (2750, 4000) (7750, 3000). area4→3 o d (5750, 1250) (1000, 1750) (5750, 750) (750, 1250) (6250, 1250) (1250, 1500) (6250, 1000) (1250, 2250). Fig. 7: Comparison by fuel cost Fig. 6 より, 貨客混載による経路コストの削減が確認 できるが, 車両を複数台に分けるより, 一度に輸送を完 了することを想定した Q = 1200 の場合の方が, その経 路コスト削減率が高くなることがわかる. しかし, Fig. 7 より燃料費という観点で見ると, Q = 350 とした場合 の方がコストが低く抑えられていることがわかる. さらに, ライドシェア利用客の経路の迂回率に関して 比較を行ったものを Fig. 8 に示す. 迂回率は, 各ペア の出発, 目的地点間を直線で結んだ場合と, 貨客を混載 した場合の旅客移動経路との差をとり, 最短走行距離で 除することで求めた. 横軸の項目は, Q1200 − 12 であれ ば,「Q = 1200 としたときのエリア 1 から 2 を移動す るグループ」を示している. 青いグラフが貨物輸送のみ を行った場合の経路コストを示しており, 赤い折れ線が 各エリアにおけるライドシェア利用客の迂回率を示す..
(8) 今後の課題としては, 動的な需要予測を取り入れるこ とに加え, パレート効率性を考慮した利益配分の検討を 行うことが考えられる. 謝辞 本研究の一部は, (株) デンソー先進エネルギシステ ム開発部, 株式会社 J-QuAD DYNAMICS 車両運動技 術部との共同研究により実施されたものである．. 参考文献 Fig. 8: Comparison by detour rate この結果より, 同じ移動エリアでの迂回率を比較する と, Q = 350 としたときの迂回率が低く抑えられるこ とがわかる. Fig. 9, Fig. 10 に貨物輸送のみを対象とし た車両経路を示すが, これはキャリアの車両台数の増加 に伴って, 目的地に到達するまでの経路の選択肢が多く なったことによるものと考えられる.. Fig. 9: Q350 cargo transport routes. Fig. 10: Q1200 cargo transport routes 以上の結果より, 貨客混載タクシーの運行による有効 性が検証された. また, 貨物輸送のみを対象とする場合 とは異なり, 旅客輸送を伴う場合には目的に適った車両 の選択が必要であると考えられる.. 5. おわりに. 本稿では, 貨物輸送と同時にライドシェアリングを旅 客輸送として組み込んだ貨客混載型タクシーの運行に 関して, 安定マッチングに基づく同乗者決定手法を含む 一連の経路最適化アルゴリズムを提案した. シミュレー ションによって, 貨物と旅客の輸送を分離して行う場合 と比較し, キャリアの提携による貨客混載車両の運行に よって全体経路コストが削減されることを示した.. 1) “ 宅配・郵便業界における人手不足について ”, 財 務 省, https://www.mof.go.jp/public_relations/ finance/201810/201810l.pdf, 2020/12/2 閲覧 2) “ 過疎地域における地域公共交通の現状と課題 ”, 国 土交通省, https://www.soumu.go.jp/main_content/ 000569916.pdf, 2020/12/2 閲覧 3) 国 土 交 通 省, https://www.mlit.go.jp/report/ press/jidosha04_hh_000134.html, 2020/12/2 閲覧 4) Ming Zhu, Xiao-Yang Liu, Xiaodong Wang,“ An Online Ride-Sharing Path-Planning Strategy for Public Vehicle Systems ”, IEEE Transactions on Intelligent Transportation Systems, vol. 20, no. 2, pp. 616-627, 2019. 5) G. B. Dantzig, J. H. Ramser, “ The Truck Dispatching Problem ”, Management Science, vol. 6, no. 1, pp. 80–91, 1959. 6) Shaoqing Zheng, “ Solving Vehicle Routing Problem: A Big Data Analytic Approach ”, IEEE Access, vol. 7, pp. 169565-169570, 2019. 7) Ruey-Maw Chen, Po-Jen Fang, “ Solving Vehicle Routing Problem with Simultaneous Pickups and Deliveries Based on A Two-Layer Particle Swarm Optimization ”, Proc. of IEEE/ACIS Internatinal Conference on Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing (SNPD), pp. 212-216, 2019. 8) Hagai Nuansa Ginting, Andrew Brian Osmond, Annisa Aditsania, “ Item Delivery Simulation Using Dijkstra Algorithm for solving Traveling Salesman Problem ”, Journal of Physics: Conference Series, vol. 1201, pp. 1-9, 2019. 9) Cordeau, J.-F., Laporte, G., “ The dial-a-ride problem: models and algorithms ”, Annals of Operations Research, vol. 153, no. 1, pp. 29-46, 2007. 10) Xian Yu, Siqian Shen,“ An Integrated Decomposition and Approximate Dynamic Programming Approach for On-Demand Ride Pooling ”, IEEE Transactions on Intelligent Transportation Systems, vol. 21, no. 9, pp. 3811-3820, 2020. 11) 谷本圭志, 小澤陽,“ タクシーを活用した貨客混載システ ムの導入可能性の評価 ”, 都市計画論文集, vol. 54, no. 3, pp. 665-671, 2019. 12) Elena Fernandez, Mireia Roca-Riu, M.Grazia Speranza, “ The Shared Customer Collaboration Vehicle Routing Probrem ”, European Journal of Operational Research, vol. 265, no. 3, pp. 1078-1093, 2018. 13) 吉塚裕生, 内田英明, 藤井秀樹, 吉村忍, “ ライドシェア サービス向け経路探索アルゴリズムの性能評価 ”, The 32nd Annual Conference of the Japanese Society for Artificial Intelligence, pp. 1-4, 2018. 14) 田村祐貴, TRONCOSO PARADY Giancarlos, 高見淳 史, 原田昇,“ 地方都市におけるライドシェアのマッチン グ成立可能性と効果に関する研究-群馬県パーソントリッ プ調査データを用いた分析- ”, 交通工学論文集, 第 5 巻, 第 2 号, pp. A 108-A 117, 2019. 15) “ 日産 NV350 キャラバン ”, カーセンサー, https: //www.carsensor.net/catalog/nissan/nv350\ _caravan/F001/M001G021/, 2020/12/2 閲覧.
(9)
図
+3
関連したドキュメント
By constructing a suitable Lyapunov functional and using almost periodic functional hull theory, we study the almost periodic dynamic behavior of a discrete Leslie-Gower
Proof of Theorem 2: The Push-and-Pull algorithm consists of the Initialization phase to generate an initial tableau that contains some basic variables, followed by the Push and
Proof of Theorem 2: The Push-and-Pull algorithm consists of the Initialization phase to generate an initial tableau that contains some basic variables, followed by the Push and
Comparing the Gauss-Jordan-based algorithm and the algorithm presented in [5], which is based on the LU factorization of the Laplacian matrix, we note that despite the fact that
The (GA) performed just the random search ((GA)’s initial population giving the best solution), but even in this case it generated satisfactory results (the gap between the
By an inverse problem we mean the problem of parameter identification, that means we try to determine some of the unknown values of the model parameters according to measurements in
Massoudi and Phuoc 44 proposed that for granular materials the slip velocity is proportional to the stress vector at the wall, that is, u s gT s n x , T s n y , where T s is the
The aim of this work is to prove the uniform boundedness and the existence of global solutions for Gierer-Meinhardt model of three substance described by reaction-diffusion
