バッテリー電気自動車のための制約付き最短経路アルゴリズムのモデリングとエンジニアリング

私たちは、バッテリー電気自動車のための制約付き最短経路を計算する問題について研究します。バッテリー容量が限られているため、最速のルートはしばしば実現不可能です。代わりに、ユーザーはエネルギー消費がバッテリー容量を超えない速いルートに関心があります。そのために、ドライバーはエネルギーを節約するために意図的に速度を落とすことができます。したがって、ルート計画は経路と速度の推奨を提供すべきです。この結果として生じる最適化問題に取り組むために、以前の研究では実行時間の現実性のために基盤となるモデルの正確性を妥協しています。私たちは、速度適応を考慮しながら、より現実的な物理モデルを使用して、充電停止なしで電気自動車の最適な制約付き最短経路を計算する新しいフレームワークを提示します。慎重なアルゴリズムエンジニアリングにより、このアプローチは、大規模で現実的な道路ネットワークでも実用的になります：私たちは、典型的なバッテリー容量のために1秒未満で最適解を計算し、以前の不正確な手法の性能と一致します。さらに速いクエリ時間のために、このアプローチはミリ秒以内に高品質の解を提供するヒューリスティックで簡単に拡張できます。