考虑油耗的车辆调度问题模型与算法

Model and Algorithm for Fuel Consumption Vehicle Routing Problem with Time Windows

针对目前运输行业中能源消耗已经成为影响社会环境和运行成本的重要因素这一实际,在分析汽车行驶油耗规律和定量描述的基础上,引入考虑能源消耗的车辆调度问题,考虑了车辆运行能耗目标以及客户的需求时间窗等约束,建立问题的精确数学模型。由于问题具有NP-hard性质,为了求解实际大规模此类问题而设计了一种新型禁忌搜索算法。该算法引入大规模邻域搜索思想,并提出基于虚拟车辆的新型搜索邻域。通过算例试验验证了算法的有效性。

Aiming at the fact that energy consumption has become an important factor of social environment and operating cost in transportation industry, the fuel consumption vehicle routing problem with time windows is discussed. Based on fuel consumption rules analysis and quantitative description, an accurate mathematical model is built by considering the fuel consumption objective and constraints such as time windows. For the NP-hard character of vehicle routing problem, a modified tabu search algorithm is designed to solve large scale such problem. The new algorithm introduces the large neighborhood theory and proposes a new kind neighborhood based on virtual vehicle. The validity of the new algorithm has been verified by computational study.