带时窗回程取货的车辆路径问题的算法-JournalofNortheastern.PDF

第2 7 卷第5 期 东 北 大 学 学 报 ( 自 然 科 学 版 ) Vol 27 ,No . 5 2 0 0 6 年 5 月 Journal of Nort heastern U niver sity (N at ural Science) May 2 0 0 6 文章编号 : (2006) 带时窗回程取货的车辆路径问题的算法 郭 　伏 , 隆　颖 ( 东北大学 工商管理学院 , 辽宁 沈阳　110004) 摘 　　　要 : 车辆路径问题如果考虑回程取货过程就可以在送货的过程中先后完成取货任务 , 比 传统不考虑回程过程的问题更有实用性 ,基于此对传统问题进行了改进 ,不限制车辆的取送货顺 序 ,而是设计了相应参数 ,避免了货物的重新排列 在确定 目标时 ,综合考虑车辆运行成本 、人员等 · 待成本及服务成本等因素 ,实现 目标解的真正可行 最后 ,根据此问题的特点 ,设计了先通过分枝 · 定界法及遗传算法确定可行路线 ,再运用整数规划方法求解的算法 ,并以实例说明了算法的有效 性 · 关 　键 　词 : 车辆路径问题 ;时窗 ;分枝定界法 ;遗传算法 ;整数规划 ;可回程取货的车辆路径问题 中图分类号 : F 253 　　　文献标识码 : A ( ) 带时窗回程取货的车辆路径问题 VRPB TW 精确式算法虽然鲁棒性好 ,但是对于解决大规模 ( ) 是带时窗的车辆路径问题 VRP TW 以及可回程取 复杂问题有很大的局限性 本文根据两类算法的 · ( ) [4 ,5 ] 货的车 辆 路 径 问题 VRPB 的发 展 传 统 的 特点 ,先通过启发式算法 得到尽可能多的可 · V RPB TW 问题只考虑先服务送货节点再服务取 行路线 ,再通过整数规划方法求解 ,最后通过解决 货节点 ,这样就必然造成运行路线迂回 ,而且这种 经典实例证明其有效性 · 方法也很难解决有些地点既有送货又有取货任务 的情况[ 1 ] 近年来 , 由于车辆设计的改进 ,很多研 1 　V R PB TW 问题数学模型 · 究 V RPB 以及 V RPB TW 的文献已经不考虑货物 1. 1 　VRPB TW 问题描述 的重新排列 ,只是将车辆的实际能力作为问题的 V RPB TW 问题可以描述为 ,车队车辆从初始 限制[ 1 ] 可是在现实情况下 , 即使车辆已经改进 , 点出发 ,完成节点的取货送货任务 ,并回到初始点 · 如果不考虑货物重新排列 ,送货与取货过程也难 的过程 为了将现实的取送货问题抽象为数学模 · 免会发生冲突 因此在本研究中 ,对于以上两种情 型 ,建立如下假设 : 只有一个初始点 ,每辆车都从 · 况进行改进 ,设计了相应参数 ,即在送货没有完成