交通运输系统工程与信息

交通运输系统工程与信息 ›› 2006, Vol. 6 ›› Issue (5): 70-73 .

• 系统工程理论与方法 • 上一篇    下一篇

基于遗传算法的带时间约束的车辆路径问题优化

张良智1 ，何民爱1 ，张志海2   

  1. 1．山东交通学院交通与物流工程系，济南250023；2．中航济南特种结构研究所，济南250023
  • 收稿日期:2006-04-04 修回日期:1900-01-01 出版日期:2006-10-20 发布日期:2006-10-20

Optimizing Vehicle Routing Problem with Time Constrains Based on Genetic Algorithm

ZHANG Liang-zhi1 ，HE Min-ai1 ，ZHANG Zhi-hai2   

  1. 1．Traffic And Logistics Engineering Department，Shandong Jiaotong University，Jinan 250023，China；
    2．Research Institute For Speical Structures Of Aeronautical Composites，Jinan 250023，China
  • Received:2006-04-04 Revised:1900-01-01 Online:2006-10-20 Published:2006-10-20

PDF

被引次数

11

摘要： 基于遗传算法的车辆路径优化问题，虽然已经被提出过多种思想方法，但仍有较大的改进余地．而且具体的车辆路径优化问题，往往在时间和路程两方面都有限制和要求，而在这方面的研究相对较少．针对这种问题，在传统遗传计算基础上，加入了时间约束算法，对算法的实时实现作出保证；同时根据客户点的位置改进初始群，提高了变异率，减少低效计算，极大提高了寻优速度，为多计算点的遗传操作提供有力的支持．计算机仿真实现的结果和物流公司的实际运作都证明了算法的有效性．

关键词: 遗传算法, 车辆路径问题, 时间约束

Abstract: Although many thoughts about vehicle routing problem bases on genetic algorithm ，there is still large space for its improvement．Faced to concrete routing problem，time and routs are both restricted and required and researches in this field are not enough．This paper，based on traditional genetic algorithm，added time restriction algorithm to guarantee the algorithm is achieved in real time．It improved the initial population in view of client distribution position，raised variation rate，reduced low eficiency calculation and improved optimistic speed greatly．It also provided strong support to multi-clients genetic computing．The eficiency of this algorithm was proved by the results of computer simulation and practical operation by logistic companies．

Key words: genetic algorithm, vehicle routing problem, time constrains