Abstract: According to the heavy traffic congestion during the development of city construction，this paper presents two types of vehicle routing and scheduling problems and gives the solving frameworks．A dynamic vehicle routing and scheduling model with variable time is presented，which includes three types of cost：fixed vehicle costs，vehicle operating costs that are proportional to the time traveled and spent waiting at customers，and early arrival or delay penalties for designated pickup／delivery times at customers．The problem is NP-hard．，This study adopts genetic algorithms for identifying the optimal solutions． The model was applied to a test road network with different congested conditions．Results indicated that the total cost decreased by implanting the dynamic vehicle routing and scheduling model with real time travel time compared with that of the forecast model．

Key words: dynamic vehicle routing and scheduling, genetic algorithm, variable travel time, simulation

摘要： 针对城市建设发展中道路交通阻塞问题，研究了两种类型的车辆路径与调度问题，给出了相应的求解框架，并构建了一个具有可变行驶时间的动态车辆路径与调度模型，涉及了车辆的固定费用、运营成本和早到或者延期的惩罚费用等多种费用。该问题是一个NP-hard问题，采用遗传算法确定最优解，并给出了车辆路径与调度方案的表示方式。最后设计了一个交通网络，通过动态交通仿真更新行驶时间，研究了多个不同时间段道路阻塞情况下算法的性能。结果显示比不考虑实时行驶时间信息的模型，该模型能够得到更低的总成本。

关键词: 动态车辆路径与调度, 遗传算法, 可变行驶时间, 仿真