基于遗传算法的集送一体化的车辆路径问题  

Research on Vehicle Routing Problem with Pickup and Delivery Based on Genetic Algorithm

作　　者：王兆赓[1] 李建更[1] 程世东[2] 

机构地区：[1]北京工业大学电子信息与控制工程学院,北京100022 [2]北京工业大学交通研究中心,北京100022

出　　处：《计算机工程与应用》2006年第1期208-211,共4页Computer Engineering and Applications

基　　金：北京市科委资助项目(编号:H020620340290)

摘　　要：有时间窗的集送货一体化的车辆路径问题(VRPPDTW)是对经典的车辆路径问题(VRP)的扩展,是一类重要的组合优化问题,但是目前对该问题的研究非常有限。论文采用了新的染色体编码方法,设计了遗传算法对该问题进行求解。在求解过程中,对集送一体化、多种配送车辆类型的问题进行了有效处理,同时考虑了车辆载重量和时间窗等约束。最后的实验结果表明,该算法可以求得这类车辆路径问题的最优解或次优解。Vehicle routing problem with pickup and delivery with time windows（VRPPDTW） as an extension for vehicle routing problem is an important problem in combinational optimization.While the research on VRPPDTW is rather scare. In this paper,while constrains of pickup and delivery,heterogeneous fleet are dealt with effectively,an improved genetic algorithm on novel decimal coding is deslgned.At the same time,vehicle capacity and time windows restraints are considered.The experiment result shows that this algorithm can obtain the optimal or nearly optimal solution to the VRPPDTW.

关 键 词：车辆路径问题 集送一体化 遗传算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]