Heuristic Algorithms for the Vehicle Routing Problems
Heuristic Algorithms for the Vehicle Routing Problems
复制标题
车辆路径问题的启发式算法
DOI：
10.11509/isciesci.64.6_218
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
胡 艶楠
中科院分区：
文献类型：
--
作者：
橋本 英樹;胡 艶楠
配送計画問題は, さまざまな制約条件のもとで, 複数の車両を用いてすべての客をちょうど 1 回ずつ訪問するような経路の中で, コストが最小のものを求める問題である [22]. この問題は代表的な組合せ最適化問題の一つで, 理論および実務の両面から多くの研究が報告されている. Braekers ら [2] は, 配送計画問題についての 2009 年から 2015 年の文献に対して取り扱われているモデルの特徴として 「容量制約」,「異なる種類の車両」,「時間枠制約」,「多期間」,「時刻依存の移動時間」 などの 16 個を挙げており, 文献ごとにさまざまなモデルが提案されていることがわかる.制約条件として各車両に容量制約があるものを容量制約付き配送計画問題 (capacitated vehicle routing problem, CVRP) とよぶ. 容量制約とは, 客の要求量の総和が車両の容量を超えてはいけないというものである. また, 容量制約に加えて, 時間枠制約があるものをとくに時間枠付き配送計画問題 (vehicle routing problem with time windows, VRPTW) とよぶ. 時間枠制約とは, 客が指定する時間枠内にサービスを開始しなければならないというものである. いずれの制約も, 容量制約のみを課した問題は分割問題を, 時間枠制約のみを課した問題はスケジューリング問題を特殊な場合として含むことから, 一方の制約のみを課した問題に対する実行可能解の存在の判定がすでに NP 完全である. この点を克服する方法の一つとして, これらの制約を考慮制約として扱い, 制約の違反量に応じたコストを付加した目的関数を最小化するという方針がとられている [8, 11, 16]. 一般に, このように違反することを許容する制約をソフト制約とよび, 必ず満たす必要がある制約をハード制約とよぶ. VRPTW において, 時間枠制約をソフト制約とした問題は VRPSTW とよばれる. 本稿では, まず, 2. 節で配送計画問題の代表的なモデルである時間枠付き配送計画問題を紹介する. 3. 節では, 配送計画問題に対してこれまでに提案されている発見的解法を概観する. 4. 節では, さまざまなタイプに適応可