2020年春季学期视觉计算实验室第四周论文研读预告

时间 : 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)计算实验表明,单纯基于在近距离路线间重新定位客户的搜索能够获得高质量的解决方案。

图1 路径间邻域搜索示意图
[2]文章提出了一个使用强化学习来解决车辆路径问题(VRP)的端到端框架。在这种方法中,作者训练单个模型,该模型仅通过观察奖励信号和遵循可行性规则,便能从给定分布采样的问题实例找到近似最优解。模型通过应用策略梯度算法来优化其参数,训练模型实时地生成解决方案作为连续动作的序列,而不需要针对每个新问题实例重新训练。在具有容量限制的车辆路径问题(VRP)上,文章提出的方法在解决方案质量方面优于经典启发式算法和谷歌的OR-Tools。本文提出的框架可以应用于车辆路径问题(VRP)的其他变体,例如随机车辆路径问题,并且有可能更普遍地应用于组合优化问题。
图2 模型示意图
123