基于排队模型的动态车辆路径问题实时优化策略及算法研究

In recent years, as the development of the Internet of Things, the Intelligent Logistics and the Intelligent Transportation have also witnessed rapid growth. Based on these new technology applications, the Dynamic Vehicle Routing Problem (DVRP), which needs to be optimized at the real-time, becomes one of the new research trends of the vehicle routing problem. But, the optimization method with the objective of shortest routing plan of the traditional vehicle routing problem, which optimized only once at the beginning, can not match the continue optimizing at the real-time of the DVRP. A new method includes both the optimization strategy and the optimization algorithm should be explored urgently, which also should focus on the objective of the responding time of the customer. So, this project intends to constructed a series new real-time optimization strategies for three typical DVRPs, including the fully dynamic DVRP, the DVRP with time windows and the multi-stage DVRP. First, the multi-agent theory will be used to establish the structure of the real-time optimization strategy. Then, the construction method of the real-time optimization strategy based on queuing model of vehicle routing problem. Furthermore, the strategy competitive analysis model will be constrcucted according to the queuing theory, geometric distribution probability theory and the length estimation model of TSP. Finally, in order to do the simulation analysis and empirical research, the multiple scenario-based heuristic algorithm will be designed according to the rules of the real-time optimization strategy. This project will give the method of constructing the real-time optimization strategy and designing the algorithm of the dynamic vehicle routing problem. The result of this project can provide a theoretical basis for real-time response to dynamic vehicle scheduling needs,and can be widely used urban distribution system, emergency service system, express delivery system and so on.

动态车辆路径问题是随着物联网、智能物流和智能交通等技术应用而产生的新兴车辆路径问题。该类问题需要为不断出现的需求实时安排车辆。传统车辆路径问题中以路径最短为目标、以单次优化算法为手段的求解方法不再适合动态车辆路径问题。亟需一套既侧重策略又侧重算法、以响应时间最短为主要目标的求解方法来解决动态车辆路径问题。本项目拟对完全动态的、带时间窗的和多阶段的动态车辆路径问题进行实时优化策略及算法研究。利用多Agent模型分析实时优化策略的一般结构；以车辆路径问题排队模型为基础探索实时优化策略的构建方法；结合排队模型、几何概率分布理论、TSP区域里程估计理论等建立基于排队论的策略有效性分析模型；以实时优化策略规则为基础设计基于场景的启发式算法，并进行仿真研究。拟解决动态车辆路径问题的实时优化策略构建和算法设计问题，为实时响应动态需求的车辆调度提供理论依据，可广泛应用于城市配送、应急服务、快递服务等领域。

动态车辆路径问题（Dynamic vehicle routing problem，DVRP）是一种专门针对需要实时响应的随机动态需求而产生的车辆路径问题。随着“互联网+”的发展以及科技的进步，智能交通和智能物流的发展为动态车辆路径问题实时优化策略研究的发展提供了广阔的应用空间。比如：快递配送、仓库补货、出租车调度、应急物流等。.研究针对动态车辆路径问题提出了实时优化策略的多Agent结构：车辆Agent、调度中心Agent和顾客Agent。利用多Agent结合一些重要的策略规则构建实时优化策略：实时优化策略=形成规则+计划期规则+执行规则+计算规则。实时优化策略将动态出现的顾客需求转化为静态子问题的“规则”主要包括静态子问题的形成规则、计划期规则、执行规则和计算规则。其中，形成规则有分格、分区、定时、定量、贪婪、空间填充曲线等共6种，并且形成规则之间还能进行组合（空间策略可以和分批策略进行组合），总共可以构成9种形成规则；计划期规则包括长期和短期策略；执行规则包括跳转和非跳转策略；计算规则包括局域搜索和全局搜索策略。.研究发现：策略组合可分为前瞻性组合和非前瞻性组合。可行的前瞻性实时优化策略组合为：贪婪策略+长期优化目标+跳转+局部搜索；非前瞻性实时优化策略组合有：分格或分区+分批策略或灵活分批+短期优化目标+非跳转+全局搜索。.研究分析了三种典型的DVRP问题的实时优化策略：完全动态 DVRP 问题、带时间窗的DVRP问题和多阶段的DVRP问题。完全动态 DVRP 问题的实时优化策略主要分析策略对顾客平均系统时间的影响，对应的策略有：分区灵活分批TSP策略和隐分区灵活分批TSP策略；带时间窗的DVRP问题应以平均路径最短、平均车辆等待时间最少以及拒绝的顾客数最小为目标，对应的策略有：贪婪TSP策略和隐分区灵活分批TSP策略；多阶段的 DVRP 问题分为单决策多阶段问题和多决策多阶段问题，其目标函数包括拒绝顾客数量、车辆路径、车辆闲置时间等，对应的策略有：平均距离策略和分割-批量TSP策略。