カープーリング最適化問題に対する局所探索法を用いたグループ決定法による解法の検討

摘要

一台の車を共有し，他者と通勤等を行うことをカープールと呼ぶ．近年，効率的なカープールサービスを実現するために，UberやLyftなど，数多くのマッチングアプリケーションが提供されている．このようなアプリケーションでは参加者同士の素早いマッチングが求められているが，参加者数が増加するとマッチングの組合せ数が増加し，参加者同士のマッチングに時間がかかる恐れがある．このような背景からカープールをモデル化した，カープーリング最適化問題が既に提案されている．カープーリング最適化問題は運転手と乗客が同一の目的地を持つ問題（Many-Source Single-Destination以下，MSSD）と運転手と乗客が異なる目的地を持つ問題（Many-Source Many-Destination以下，MSMD）の二つに大別される．また，我々は既にMSMD問題に対して，乗客グループを予め決定することで車の総移動距離が短くなる経路を短時間で探索する手法を提案しているが，MSSD問題に対しては手法の有効性を示していない．そこで本稿では，MSSD問題に対する提案手法の有効性について調査した．また，MSSD問題とMSMD問題に対する提案手法の性能を調査した．数値実験より，提案手法はカープーリング最適化問題のいずれの問題に対しても短時間で総移動距離の短い経路を探索可能であることを確認した．