時間ウィンドウを考慮した車両経路問題のためのGRASP

本論文は、時間ウィンドウ制約に従って一連のノードを訪問するために必要な車両の最小数を見つける問題を扱います。副目的は、移動距離の合計を最小化することです。各ノードは、ピックアップおよび配送の形で予め定められたサービス量を必要とします。艦隊は均質で、共通のデポに位置しています。車両の容量は有限で、分割サービスは許可されていません。実行可能な解を得るために貪欲でランダム化された適応探索手法（GRASP）が使用されます。結果は、標準の100ノードデータセットと、最大417人の顧客を持ついくつかの実世界の問題について報告されています。結果は、一般に、提案された手法が現在の技術より優れており、正確な方法でかかる時間のわずかな部分しか必要としないことを示しています。解の質を評価するために、3つの異なる下限推定ヒューリスティックが開発されました。最初は、車両の容量に関する問題の「ビンパッキング」側面を考慮し、2番目は顧客の不適合グラフに関連する最大クリークに基づいており、3番目は時間ウィンドウ制約を独立して活用します。これらのヒューリスティックを使用して、バランスの取れたサービスと厳しい容量制約を含むほぼすべてのケースで最適解が見つかることが実証され、残りの相当な割合でも成り立ちます。INFORMS Computing誌、ISSN 1091-9856は、1989年から1995年までISSN 0899-1499の下でORSA Computing誌として発行されました。