Computer Engineering and Applications ›› 2008, Vol. 44 ›› Issue (22): 210-212.DOI: 10.3778/j.issn.1002-8331.2008.22.063

• 工程与应用 • Previous Articles     Next Articles

Research on time dependent vehicle routing problem based on GA

YU Qing1,2,ZHAO Hui3   

  1. 1.School of Computer Science and Technology,Tianjin University,Tianjin 300072,China
    2.School of Computer Science and Technology,Tianjin University of Technology,Tianjin 300191,China
    3.School of Economic and Management,CAUC,Tianjin 300300,China
  • Received:2007-12-07 Revised:2008-03-03 Online:2008-07-11 Published:2008-07-11
  • Contact: YU Qing

基于GA的时变路网中车辆动态派遣的研究

于 青1,2,赵 辉3   

  1. 1.天津大学 计算机科学与技术学院,天津 300072
    2.天津理工大学 计算机科学与技术学院,天津 300191
    3.中国民航大学 经济管理学院,天津 300300
  • 通讯作者: 于 青

Abstract: In order to accord with the actual traffic status in road networks,vehicle routing problem with time dependent travel time is researched.The authors modify the traditional vehicle scheduling model,total vehicle expense,total delay penalty,total vehicle use expenses are considered in the objective,so as to improve the applicability and universality of model.Since vehicle scheduling problem is NP-hard,parallel genetic algorithm is proposed to solve this problem.In order to verify the effectiveness of the parallel genetic algorithm,stand VRP problems are used.The simulation results show that the algorithm is very easy and feasible and compared with BC-Saving algorithm,it has rapid convergence ability and searching ability.

Key words: vehicle routing problem, time dependent, dynamic, genetic algorithm

摘要: 为了使网络中的车辆调度问题更加符合实际交通状况,针对时变网络中的车辆调度问题进行了研究。将传统车辆调度模型进行了修改,目标函数中考虑了车辆的总行驶费用、总迟到惩罚、车辆总启用费用3种因素,以提高模型的适应性和通用性。由于车辆调度问题属于NP难问题,提出了采用遗传算法对问题进行求解。采用标准的VRP问题进行测试,仿真结果表明该算法简单可行,较BC-Saving启发式算法有更好的求解性能。

关键词: 车辆派遣, 时变, 动态, 遗传算法