Abstract: In urban road network, more physical differences should be considered to measure the comprehensive traffic impedance, such as number and width of lanes in each road and crossing light working rule in each intersections. On this basis, this paper gives a scheduling mathematical model with multiple types of vehicles. A two-stage algorithm is put forward to solve the model. At first stage, an improving A-star search algorithm is designed to calculate the exact time passed matrix. At second stage, a hybrid simulated annealing algorithm is designed to find scheduling scheme. Selecting one of Dalian distribution centers as actual case, the experimental results are used to verify performance of algorithm and analyze scheduling scheme changes in different network situations. Analysis result shows improving A-star search algorithm has faster speed than the Dijkstra signature improving algorithm which ever use. The comprehensive cost of scheduling scheme founded by simulated annealing algorithm has an 13.1% reduction than actual operation scheme. Three changes in urban road network conditions such as the increase of road network flow, the congestion of some areas and the ban of some roads passing, can disturb five parts in distribution scheme, which are vehicle configuration plan, route selection plan, customer service sequence, vehicle operation time and default cost from unpunctuality. The numerical result proposes that the changes in urban road network conditions should be considered in details before planning a scheduling scheme.

Key words: Urban network, Vehicle scheduling, Time-distance Matrix, Improved A-star algorithm, Hybrid simulated annealing algorithm

摘要： 在实际路网情境下结合车道数、车道宽度、路口信号灯设置等路网物理特性,构建了考虑综合交通阻抗的多车型车辆调度模型,提出了两阶段求解策略:第1阶段设计了改进A-star精确解算法用于计算客户时间距离矩阵;第2阶段针对实际路网的特征设计了混合模拟退火算法求解调度方案。以大连市某配送中心运营实例进行路网情境仿真试验,结果表明:改进A-star算法较改进Dijkstra算法具有更短的路径搜索时间;混合模拟退火算法求解结果较实际调度方案优化了13.1% 的综合成本;路网增流、区域拥堵和路段禁行三类路网情境均能对配送方案的车辆配置、路径选择、客户服务次序、作业时间和违约费用等5方面内容产生干扰,调度计划的制定需要详细考虑这些因素的变化。

关键词: 实际路网, 车辆调度, 时间距离矩阵, 改进A-star算法, 混合模拟退火算法