ライドハイリングへの応用を伴うQUBOにおける経路問題のモデリング

要旨 多くの新興商業サービスは、コスト削減を目的とした共通利用のためのリソースの共有またはプールに基づいています。配達、モビリティ、あるいは輸送サービスとしてのビジネスは、世界の多くの地域で一般的になり、リアルタイムでの顧客からのオンデマンドリクエストに応えています。しかし、これらの問題の多くがNP困難であることが知られており、したがってそれらを正確にモデリングし解決することは課題です。ここでは、複数の顧客がフリート内の共有車両からのオンデマンドのピックアップおよびドロップオフをリクエストできるライドプーリング問題（RPP）という経路問題に焦点を当てます。この組合せ最適化タスクは、限られた車両セットを使用して顧客リクエストを最適にプーリングすることであり、小規模な柔軟バスルートに似ています。本研究では、2次元非制約バイナリ最適化（QUBO）プログラムを提案し、メタヒューリスティクス、特に新興の量子最適化アルゴリズムを使用して解決するためのRPPの効率的な定式化手法を紹介します。