Evolutionary algorithm for the k-interconnected multi-depot multi-traveling salesmen problem
Evolutionary algorithm for the k-interconnected multi-depot multi-traveling salesmen problem
复制标题
k互连多车场多旅行推销员问题的进化算法
DOI：
10.1145/2463372.2463434
复制
发表时间：
2013
期刊：
影响因子：
2.3
通讯作者：
M. G. Resende
中科院分区：
文献类型：
--
作者：
Carlos Eduardo de Andrade;F. Miyazawa;M. G. Resende
我们引入了 $k$ 互连多仓库多旅行推销员问题，这是一个类似于某些网络设计和位置路由问题的新问题，但具有没有一组固定的仓库或终端的固有困难。我们提出了一种基于有偏随机密钥遗传算法的启发式算法来解决这个问题。这种启发式方法使用本地搜索过程来最好地选择终端顶点并改进给定解决方案的游览。我们将我们的启发式方法与使用相同局部改进的多启动程序进行比较，并表明所提出的算法具有竞争力。
We introduce the $k$-Interconnected Multi-Depot Multi-Traveling Salesmen Problem, a new problem that resembles some network design and location routing problems but carries the inherent difficulty of not having a fixed set of depots or terminals. We propose a heuristic based on a biased random-key genetic algorithm to solve it. This heuristic uses local search procedures to best choose the terminal vertices and improve the tours of a given solution. We compare our heuristic with a multi-start procedure using the same local improvements and we show that the proposed algorithm is competitive.