Hybrid genetic algorithm for multi-depot vehicle routing problem with capacity and route duration constraints

カテゴリ: 部門大会

論文No: GS1-4

グループ名: 【C】平成23年電気学会電子・情報・システム部門大会講演論文集

発行日: 2011/09/07

タイトル(英語): Hybrid genetic algorithm for multi-depot vehicle routing problem with capacity and route duration constraints

著者名: 趙 成晤(早稲田大学),藤村 茂(早稲田大学)

著者名(英語): Sungoh Cho(Waseda University),Shigeru Fujimura(Waseda University)

キーワード: 遺伝的アルゴリズム|運搬経路問題|genetic algorithm|multi depot vehicle routing problem

要約(日本語): This paper describes a hybrid genetic algorithm for the multi-depot vehicle routing problem (MDVRP) with capacity and route duration constraints. The MDVRP is well-known NP-hard problem which means that an efficient algorithm to solve the problem to optimality is unavailable. To solve with the problem efficiently, previous researchers preferred heuristic algorithms such as tabu search (TS) or simulated annealing (SA). To compete with them classic genetic algorithm must be hybridized with some kind of improvement methods. For the MDVRP, we developed simple and powerful improvement methods by local search algorithm. The algorithm is tested on a set of 33 classic MDVRP benchmark problems and evaluated by comparing with existing GAs and non-GA approaches.

PDFファイルサイズ: 6,631 Kバイト