Solving Generalized Vehicle Routing Problem With Occasional Drivers via Evolutionary Multitasking
Solving Generalized Vehicle Routing Problem With Occasional Drivers via Evolutionary Multitasking
复制标题
DOI：
10.1109/tcyb.2019.2955599
复制
发表时间：
2019-12
影响因子：
11.8
通讯作者：
Liang Feng;Lei Zhou;Abhishek Gupta;J. Zhong;Zexuan Zhu;K. Tan;Kai Qin
中科院分区：
文献类型：
--
作者：
Liang Feng;Lei Zhou;Abhishek Gupta;J. Zhong;Zexuan Zhu;K. Tan;Kai Qin
随着众包和共享经济的出现，最近提出了临时司机的车辆路径问题（VRPOD），该问题涉及临时司机使用私家车运送货物。在本文中，我们考虑了车辆的容量异质性和时间窗，提出了 VRPOD 的广义变体，即具有异构容量、时间窗和偶然驾驶员的车辆路径问题（VRPHTO）。此外，为了满足当今云计算服务中可能需要同时解决多个优化任务的要求，我们提出了一种新颖的进化多任务算法（EMA），可以在单个群体中同时优化多个 VRPHTO。最后，基于现有的通用车辆路径基准生成了 56 个新的 VRPHTO 实例。我们进行了全面的实证研究，以说明新 VRPHTO 的优势，并验证所提出的 EMA 对于多任务处理相对于最先进的单任务进化求解器的有效性。获得的结果表明，使用临时驱动程序可以显着降低路由成本，并且所提出的 EMA 不仅能够同时解决多个 VRPHTO，而且还可以通过进化搜索过程中任务之间的知识传递来实现增强的优化性能。
With the emergence of crowdshipping and sharing economy, vehicle routing problem with occasional drivers (VRPOD) has been recently proposed to involve occasional drivers with private vehicles for the delivery of goods. In this article, we present a generalized variant of VRPOD, namely, the vehicle routing problem with heterogeneous capacity, time window, and occasional driver (VRPHTO), by taking the capacity heterogeneity and time window of vehicles into consideration. Furthermore, to meet the requirement in today’s cloud computing service, wherein multiple optimization tasks may need to be solved at the same time, we propose a novel evolutionary multitasking algorithm (EMA) to optimize multiple VRPHTOs simultaneously with a single population. Finally, 56 new VRPHTO instances are generated based on the existing common vehicle routing benchmarks. Comprehensive empirical studies are conducted to illustrate the benefits of the new VRPHTOs and to verify the efficacy of the proposed EMA for multitasking against a state-of-art single task evolutionary solver. The obtained results showed that the employment of occasional drivers could significantly reduce the routing cost, and the proposed EMA is not only able to solve multiple VRPHTOs simultaneously but also can achieve enhanced optimization performance via the knowledge transfer between tasks along the evolutionary search process.