Genetic algorithm for very large traveling salesman problems and its applications to practical applications

超大型旅行商问题的遗传算法及其在实际应用中的应用

• 批准号: 19700134
• 负责人: NAGATA Yuichi
• 金额: $ 1.83万
• 依托单位: Tokyo Institute of Technology (2009)Japan Advanced Institute of Science and Technology (2007-2008)
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2007
• 资助国家: 日本
• 起止时间: 2007 至 2009
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-19700134/
• 关键词: 遺伝的アルゴリズム; 巡回セールスマン問題; 車両配送問題; メメティックアルゴリズム; memetic algorithm; 組合せ最適化; メタヒューリスティクス

We have developed an genetic algorithm (GA) for the traveling salesman problem (TSP). The GA uses edge assembly crossover (EAX), which is known to be efficient and effective for solving TSPs. We first propose a modified EAX algorithm that can be executed more efficiently than the original, which is 2-7 times faster. We then propose a selection model that can efficiently maintain population diversity at negligible computational cost. The edge entropy measure is used as an indicator of population diversity. We further improved the performance of the GA with EAX, especially for large instances of more than 10,000 cities. Our method is highly competitive with existing approaches. Moreover, we have developed very efficient MAs for several vehicle routing problems by extending the GA developed for the TSP.

我们已经开发了一种遗传算法（GA）的旅行商问题（TSP）。GA使用边缘组装交叉（EAX），这是已知的是高效和有效的解决TSP。首先，我们提出了一个修改的EAX算法，可以更有效地执行比原来的，这是2-7倍的速度。然后，我们提出了一个选择模型，可以有效地保持人口的多样性在可以忽略不计的计算成本。边缘熵测度被用作种群多样性的指标。我们使用EAX进一步提高了GA的性能，特别是对于超过10，000个城市的大型实例。我们的方法与现有的方法具有很强的竞争力。此外，我们已经开发了非常有效的MA几个车辆路径问题，通过扩展的遗传算法开发的TSP。

项目成果

Edge Assembly Crossover for the Capacitated Vehicle Routing Problem

• DOI: 10.1007/978-3-540-71615-0_13
• 发表时间: 2007-04
• 作者: Y. Nagata

Guided Ejection Searchによる車両配送問題の車両数最小化

使用引导弹射搜索最大限度地减少车辆交付问题的车辆数量

• 发表时间: 2009
• 作者: 永田裕一;小林重信
• 通讯作者: 小林重信

A powerful route minimization heuristic for the vehicle routing problem with time windows

• DOI: 10.1016/j.orl.2009.04.006
• 发表时间: 2009-09
• 期刊: Oper. Res. Lett.
• 作者: Y. Nagata;Olli Bräysy

局所的な交叉EAXを用いたGAの高速化とTSPへの適用

使用本地交叉 EAX 加速 GA 并应用于 TSP

• 发表时间: 2007
• 期刊: 人工知能学会論文誌 vol.22,no.5
• 作者: Yuichi Nagata;Olli Brasys;永田裕一
• 通讯作者: 永田裕一

Effective Crossover Operator for the traveling Salesman Problems: Edge Assembly Crossover

解决旅行推销员问题的有效交叉算子：边组装交叉

• 发表时间: 2009
• 作者: Takadama;K.;Kawai;T.;and Koyama;Y.;Yuichi Nagata
• 通讯作者: Yuichi Nagata