著者

吉田 岳人 矢野 正基 堀川 健一郎 佐藤 啓太 南 翔太 繁野 麻衣子

雑誌

研究報告数理モデル化と問題解決(MPS) (ISSN:21888833)

巻号頁・発行日

vol.2018-MPS-117, no.3, pp.1-6, 2018-02-22

---

近年,ライドシェアリングは広く注目を集めているが,その中でもタクシー相乗りは効果が高いことが期待されている.本研究では,イベントへの参加などで共通の目的地のある乗客のタクシー相乗りの可能性を探る.タクシー相乗り問題では通常移動コストの最小化を扱うが,ここでは,タクシーの総走行距離が長くならない中で,乗客の総移動距離を最小化することを目的とする.この問題を混合整数線形計画問題として定式化するとともに,乗車人数に制限がある場合に対する厳密アルゴリズムと制限がない場合に対するヒューリスティックアルゴリズムを提案する.そして,数値実験により,ヒューリスティックアルゴリズムの解が適切であることを検証し,さらに,得られた解の相乗り方法と支払料金から評価して妥当性を示す.