时变条件下道路网的车辆路径优化  

Time-dependent Vehicle Routing Optimization Problem Under Road Network

作　　者：张晓楠[1] 王陆宇 谭昕妮 姜帅 ZHANG Xiaonan;WANG Luyu;TAN Xinni;JIANG Shuai(College of Mechanical and Electrical Engineering,Shaanxi University of Science and Technology,Xi'an 710021,China)

机构地区：[1]陕西科技大学机电工程学院,西安710021

出　　处：《机械科学与技术》2023年第11期1919-1928,共10页Mechanical Science and Technology for Aerospace Engineering

基　　金：国家自然科学基金项目(71802120);陕西省社会科学基金项目(2022R002);陕西省创新能力支撑计划项目(2020KRM024);教育部人文社会科学研究项目(2023XJCZH0019)。

摘　　要：针对车辆路径优化问题在现实中涉及的时变旅行时间特征和道路网络因素,研究时变条件下基于道路网的车辆路径优化问题。首先,考虑车辆旅行速度的时变特征,构建旅行速度的分段函数,采用跨时域的方法利用离散速度计算动态旅行时间;其次,基于关键节点的概念简化道路网络,克服车辆路径问题在考虑道路网时存在的维度灾问题。基于以上,结合时变旅行时间和基于关键点构建的道路网路,建立以总旅行时间最小为目标的优化模型;根据问题特征,设计蚁群算法求解;以西安市未央区桶装水配送区域实例进行测试,验证模型和算法的有效性,分析不同速度-时间变化模式和车辆出发时间的敏感性。Aiming at the time-dependent feature and road network in vehicle routing problem,this paper studies time-dependent vehicle routing optimization under road network.First,considering the time-dependent travel speed,we construct the piecewise function on vehicle travel speed,and based on that,we could calculate dynamically the travel time by using cross time-domain method;Second,using the concept of key road nodes,we simplify the road network to overcome the curse of dimensionality of the vehicle routing optimization problem under road network.Based on the above two,we consider both time-dependent travel time and the simplified road network with key nodes,and establish an optimization model with the objective of minimizing the total travel time.Then,we design ant colony algorithm to solve the model.Finally,we test an example of barreled water delivery service in Weiyang District of Xi′an to verify the effectiveness of the model and algorithm.Additionally,the sensitivity on vehicle speed and departure time is analyzed.

关 键 词：车辆路径优化问题 道路网络 时变路网 蚁群算法 

分 类 号：TP399[自动化与计算机技术—计算机应用技术]