时间 ： 2020年03月26日 09: 00
地点 ： 四川大学视觉计算实验室钉钉群
研读成员 ： 杨啸
研读内容 ：
[1]D. Bustos Coral, M. Oliveira Santos, C. Toledo and L. Fernando Niño, "Clustering-Based Search in a Memetic Algorithm for the Vehicle Routing Problem with Time Windows," 2018 IEEE Congress on Evolutionary Computation (CEC), Rio de Janeiro, 2018, pp. 1-8.
[2]NAZARI, Mohammadreza, et al. Reinforcement learning for solving the vehicle routing problem. In: Advances in Neural Information Processing Systems. 2018. p. 9839-9849.
论文简介
[1]以旅行费用最小为目标的带时间窗的车辆路径问题(VRPTW)是已知的NP-hard组合优化问题。由于其复杂性，现已提出多种启发式搜索算法来解决这一问题。本文提出了一种简单模因算法(MA)。在搜索开始时，对客户的空间信息应用一个聚类程序。搜索过程包括在近距离线路之间进行顾客搬迁，寻求最小化与搬迁相关的绕道成本。聚类过程所收集的信息用于识别哪条路线彼此接近。实验表明了所提方法的有效性。
本文的主要贡献在于：(1)引入了一种利用客户集群来指导搜索空间探索的本地搜索程序，(2)计算实验表明，单纯基于在近距离路线间重新定位客户的搜索能够获得高质量的解决方案。
