基于群体智能的动态需求车辆路径规划

RESEARCH ON VEHICLE ROUTING PROBLEM WITH DYNAMIC DEMANDS BASED ON SWARM INTELLIGENCE

刘明德

11849245

硕士

计算机科学与技术

史玉回

2020-05-30

2020-07-08

哈尔滨工业大学

深圳

得益于移动互联网带来的快捷便利的通信方式，客户和物流配送方之间的交流更加频繁，客户可以随时提交或者取消自己的配送需求。面对这种动态变化的客户需求，如何提高车辆路径规划效率，及时响应客户需求，对路径再优化以服务新增的客户需求，尽可能多地服务客户以提升客户满意度同时减少车辆配送花销，这些是物流配送中急需解决的问题。此外，传统的车辆路径规划方面的研究较少关注实际的道路交通网络，导致规划得到的车辆路径对车辆行驶缺乏指导意义。为了解决以上问题，本文考虑了道路交通网络以贴近实际的物流配送场景。本文对带道路网的车辆路径规划问题特点进行分析，构建了带道路网络的车辆路径规划问题模型，并通过抽象化深圳市南山区道路网络构建了贴近实际的测试数据集。为了更好地处理带道路网络的车辆路径规划问题，本文提出了基于群体智能的混合算法。该算法通过头脑风暴优化算法中的聚类操作使得蚁群系统算法学习解的共性特征，进而加快搜索速度；通过局部搜索来搜索不同范围内的解以提升解的质量。本文通过在实际的道路网络测试数据集上将基于群体智能的混合算法与其他算法对比，验证了基于群体智能的混合算法具有良好的求解能力。本文在带道路网络车辆路径规划问题的基础上考虑动态需求场景下的车辆路径规划问题。为了处理该问题，本文研究了动态车辆路径规划问题中的动态处理策略，提出了滚动周期处理策略来确定合适的问题求解时间点，以将动态问题及时地转化为静态问题（即带道路网络的车辆路径规划问题）求解。此外，为了在尽可能多地服务客户的同时降低物流配送成本，本文提出了重复插入算法以解决传统插入算法因未充分利用原有路径信息而无法服务客户的问题。最后，本文通过仿真实验验证了所提出的滚动周期处理策略和重复插入算法的有效性。

Thanks to the convenient communication brought by the mobile Internet, customers can submit or cancel their delivery demands at any time. In the case of dynamically changing customer demands, how to plan routes to respond to customer demands in time and serve customers as many as possible, thereby increasing customer satisfaction and reducing logistics cost become an open issue. Besides, the research on the traditional vehicle routing problem pays less attention to real-world road networks in the city, which limits its applicability on practical vehicle routing problems.To solve the above problems, this dissertation analyzes the vehicle routing problem with the road network, constructs a mathematical model of this problem, and establishes a test data set based on the road network in Nanshan district, Shenzhen. In this dissertation, a hybrid algorithm based on swarm intelligence is proposed to handle the vehicle routing problem with the road network. In the proposed algorithm, the clustering operation in the brain storm optimization algorithm helps the ant colony system algorithm learn similar features in the same category to speed up the convergence. A local search algorithm is used to search more space to maintain the diversity of solutions. The efficacy of the hybrid algorithm is verified through the comparison experiment on the real-world road network.This dissertation considers the vehicle routing problem in a dynamic demand scenario based on the vehicle routing problem with the road network. To deal with the problem, this dissertation studies the dynamic processing strategy in dynamic vehicle routing problems and proposes a rolling periodic processing strategy to determine the appropriate time to transform the dynamic problem into a static problem (i.e., the vehicle routing problem with the road network). To reduce the distribution cost and serve customers as many as possible, this dissertation further proposes a repeated insertion algorithm to solve the problem of traditional insertion algorithms failing to serve customers due to the underutilization of original path information. Finally, simulation experiments verify the efficacy of the proposed rolling cycle processing strategy and repeated insertion algorithm.

群体智能 车辆路径规划 动态需求 滚动周期 道路网络 重复插入算法

swarm intelligence vehicle routing problem dynamic demand rolling cycle strategy road network repeated insertion algorithm

中文

联合培养

南方科技大学

刘明德. 基于群体智能的动态需求车辆路径规划[D]. 深圳. 哈尔滨工业大学,2020.