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

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

项目编号： No.71461006

项目类型： 地区科学基金项目

立项/批准年度： 2015

项目学科： 管理科学

项目作者： 熊浩

作者单位： 海南大学

项目金额： 36万元

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

中文关键词： 车辆路径问题；优化模型；启发式算法；智能优化算法

英文摘要： 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.

英文关键词： vehicle routing problem;optimization model;heuristic algorithm;intelligent optimization algorithm