带时间窗车辆路径问题的启发式遗传算法.pdf

收藏

编号:20181111062306186344    类型:共享资源    大小:335.97KB    格式:PDF    上传时间:2019-02-16
  
3
金币
关 键 词:
启发式遗传算法 时间窗的车辆路径问题 车辆路径问题 时间窗 车辆路径问题的 遗传算法 时间窗车辆路径问题的遗传算法 带时间窗的车辆路径问题 时间窗车辆路径问题 问题的启发式 时间窗车辆路径问题的 带时间窗
资源描述:
第8卷第1期 2008年2月 交通运输工程学 Journal of Traffic and Transportatio 报 n Engineering VoL 8 Feb. N0.1 2008 文章编号:1671—1637(2008)01—0113—05 0 带时间窗车辆路径问题的启发式遗传算法 赵建有1,吴利清2,刘大学 (1.长安大学汽车学院,陕西西安 710064;2.集美大学航海学院,福建厦门 361021; 3.浙江交通职业技术学院汽车系,浙江杭州 311i12) 摘 要:为了在运输生产中按时间要求合理安排车辆路径,建立了带时间窗车辆路径问题数学模 型,用启发式遗传算法进行求解。先构造染色体,产生初始群,再对其进行优化,根据个体生存能力 的体现进行性能估计,并计算优化值。运用Visual Basic编写相应计算程序,设定迭代代数为100, 运算次数为10次,对有时间窗限制的有1个中心仓库与8个分仓库的实际问题进行求解。模拟结 果显示需要3辆车按照3条运输线路进行物流配送服务,总运行距离为483 km,总运行时间为 15.55 h,车辆未出现闲置时阎,且全部仓库得到及时服务。可见启发式遗传算法有效、可行。 关键词:交通运输;车辆路径问题;数学模型;时间窗;启发式遗传算法 中图分类号:U492.22 文献标识码:A Heuristic genetic algorithm of vehicle routing problem with time windows ‘Zhao Jian-youl,Wu Li—qin92,Liu Da-xue3 (1.School of Automobile,Chang’an University,Xi’an 710064,Shaanxi,China;2.School of Navigation,Jimei University,Xiamen 361021,Fujian,China;3.Department of Automobile, Zhejiang Institute of Communications,Hangzhou 311112,Zhejiang,China) Abstract:In order to reasonably arrange vehicle routes according to time request in transportation production.a mathematical model for vehicle routing problem with time windows(VRPTW)was constructed,and a heuristic genetic algorithm was put forward to solve it.In the algorithm, chromosomes were constructed,initial groups were produced and optimized,their capability was estimated by the existent ability of individual,and the optimized value was computed.The number of evolving offspring is 100,operating time is 10,VRPTW with one center depot and eight branch depots was solved by correspond program.The result indicates that goods are distributed with three trucks in three routes,total distance iS 483 km,total time iS 15.55 h, there is no idle time for truck,and a11 warehouses are served on time.Obviously,the algorithm is effective and feasible.1 tab,3 figs,1 1 refs. Key words:traffic transportation;vehicle routing problem;mathematical model;time windows; heuristic genetic algorithm Author resume:Zhao Jian-you(1963一),male,professor,+86—29—82334069,jyzhao@chd.edu.ca. 引 车辆路径问题(vehicle routing problem,简称 VRP)由Danting和Rasmer在20世纪50年代末首 先提出,在实际运输生产中,往往对货物的送达时 间、卸货时间会有具体的要求,这样就引出了有时间 收稿日期:2007—08-15 基金项目:江苏省交通科学研究计划项目(06R22) 作者简介:赵建有(1963一),男,河南西峡人,长安大学教授,从事交通运输规划与管理研究。 言目 万方数据 114 交通运输工程学报 2008篮 窗车辆路径问题(vehicle routing problem with time windows,简称VRPTW)。求解有时间窗车辆路径 问题的常用算法有神经网络算法、蚁群算法、禁忌算 法、免疫算法和节约算法等[1-11],这些算法为求解 VRPTW提供了方便,但也存在一些问题。例如节 约算法的优点是通过列出各点间的节约量,按节约 量的大小构造路线,其运算速度快,但存在未组合点 零乱,边缘点难于组合等缺点[1{]。本文针对 VRPTW的特点,对遗传算法加以研究,构造出运算 简便、性能优良的启发式算法。 1 VRPTW数学模型 VRPTw描述为:中心仓库有车队集合V,分仓 库集合C和有向图G 7;有向图有Jfl+2个顶点,顶 点l、…、,z表示分仓库,顶点,l+1表示返回中心仓 库,顶点o、1、…、竹+1记为集合N;分仓库之间及 分仓库与中心仓库之间的弧记为集合A,且没有弧 开始于,2+1顶点,没有弧终止于0顶点,每条弧牙 对应一个运输成本值%和一个时间值t。;每辆车有 一个容量g,每个分仓库i有一个需求d。和一个时 间窗口[n;,b;],时间窗口说明车辆须在b,之前到达 分仓库i,在a;前车辆虽可到达分仓库i,但车辆须 等待到a;才能卸货;中心仓库的时间窗口为[n0, 60],表示车辆在a。前不能离开中心仓库,且须在b。 或b。之前返回中心仓库;本文规定口、a;、b;、d;和f。 是非负整数,t。是正整数。 对于弧巧(i≠歹,拇!n+1,歹≠o)和车辆是,定义 变量z潞为 f0(车辆曼没有从节点i到达节点歹) ~‘ 11(车辆忌从节点i到达节点.『) 对每个分仓库i和车辆愚定义变量s砖,表示车 辆矗在S。开始对分仓库i进行访问,如果车辆愚不 访问分仓库i,则&不表示任何意义。假设a。为0, 这样对所有的车辆愚,跏为0。对于每辆车,设计一 条费用最小的路径,此路径开始于顶点0,终止于顶 点咒+1,同时还要保证每个分仓库被访问一次,且 不能违反时间窗口和车辆的容量约束。VRPTW的 数学模型为 2一min∑∑∑f。z社 (1) ^∈yiEN j∈” s.t.∑∑z驰一1 (i∈c) (2) ^∈y J∈N ∑d;∑z驰≤q (惫∈V) (3) iEC J∈/g ≥:z。砖=1 (志∈V) (4) ∑z舭一∑z可^=0 (^∈C,忌∈y) (5) iEN 』∈Ⅳ ≥:zi‘井m一1 (惫∈V) (6) f∈N s*+‘o—K(1一z肼)≤趴(f,』∈N,忌∈V) (7) nf≤≤s&≤≤6f (i∈N,志∈V) (8) z触∈{0,1) (i,J∈N,忌∈V) (9) 式中:z为配送总运输成本;z。施为车辆矗从中心仓 库0出发到达下一仓库J的O一1变量;z湘+1)。为车 辆矗从仓库i返回到中心仓库0的。一l变量;乩、跏 分别为车辆愚对仓库i、歹进行访问的最早时间;a;、 b;分别为仓库i时间限制窗口的最小、最大时间; z访。为车辆惫从仓库i到下一仓库^的0—1变量; z掀为车辆是从仓库^到下一仓库J的0-1变量;K “为常数系数。 式(1)为目标函数,其余为约束条件;式(2)表示 每个分仓库只能被访问一次;式(3)表示车辆都能满 足约束条件;式(4)~(6)保证了每辆车从中心仓库出 发,访问分仓库后,最终回到中心仓库;式(7)表示车 辆尼在从i分仓库向.f分仓库行驶的过程中,在缸+ t。之前不能到达分仓库.『;式(8)表示在车辆行驶过程 中,满足时间窗的约束;式(9)是整数化的约束。 2 VRPTW的启发式遗传算法 2.1构造染色体。产生初始群 首先定义染色体编码形式,直观的方法就是基 于车辆行驶路径的顺序编码[1’6],因此,本文采用自 然数编码方式,用{s,娩,…,如)表示染色体G,其中 元素(基因)s』为[1,咒]之间的一个不重复的自然数, 随机产生一组互异染色体G^(^=1,2,…,m),优为 种群中的个体数,它为第1代种群。 2.2优化过程 本文采用从左向右的顺序进行分组,可将其编 码为线路结构,例如,染色体{1,2,3,4,5,6,7,8)可 编码成如下线路结构:{(1,2),(3,4,5),(6,7,8)}、 {(1,2,3),(4,5),(6,7,8)}、{(1,2,3),(4,5,6),(7, 8))、{(1,2,3,4),(5,6),(7,8))等。每一组表示一 条路径,不同分组的染色体表示不同的解。显然,这 些解可行,但不一定是最优解。为了找到每个染色 体的最佳分组,方便计算,可把分组信息和每个解联 系起来,染色体表示为 {(1,2),(3,4,5,),(6,7,8))净(1,2,3,4,5,6,7,8,[2 3 3]} {(1,2,3),(4,5),(6,7,8)}净{1,2,3,4,5,6,7,8,[3 2 3]} {(1,2,3),(4,5,6),(7,8)}净{1,2,3,4,5,6,7,8,[3 3 2]} {(1,2,3,4),(5,6),(7,8))净{1,2,3,4,5,6,7,8,[4 2 2]} 万方数据 第1期 赵建有,等:带时间窗车辆路径问题的启发式遗传算法 115 在右侧新的分组结构中,括弧内部分是分组信 息,[2 3 3]表示前2个客户在第1条线路,接下来的 3个客户在第2条线路,最后3个客户在第3条线 路。然后使用知交换局部搜索方法在路径之间交换 客户,以改善可行解。该方法是由Osman等在 1994年提出的一种有效局部搜索方法[4]。本文将 交换法中交换算子的个数A设为1,即路径间至多 交换1个客户。A的取值决定了可执行3种交换操 作,即(0,1)、(1,0)、(1,1)操作。对一个线路对 (RP,RQ)执行(1,1)操作,含义是1个客户从路线R 上的P点迁移到Q点,同时1个客户从路线R上的 Q点迁移到P点。其他操作类似定义,操作时应沿 路径逐一考虑所有客户在每种交换情况下的成本, 目的是寻找导致总成本下降的交换。如果初始分组 信息是[2 3 3],就可检查[3 2 3]、[3 3 23等,这样容 易定义搜索顺序和操作。每个新分组将首先进行可 行性检查,检查是否满足车辆容量约束,再继续检查 是否满足各个用户的时间窗口约束,若满足,则该染 色体是对应问题的一个可行解,否则,该染色体对应 不可行解,只有可行的分组才会被考虑。搜索策略 有局部最优法(图1)和全局最优法(图2)。前者当 找到第1个导致成本下降的分组时停止搜索,如果 搜索时间结束,还没有找到新的分组时,则分组信息 不变;后者则寻找导致成本下降的最大解。. 初始分组 lN I 厂———————.1銮垫!全查2卜一 lY . 1Y巫圈螽萄游丝 坚 输出新分组 图1局郡最优法 Fig.1 Partial optimal method 2。3性能估计与优化值计算 对种群中每个染色体G^,将上面得到的改善解 代入式(1),求出对应的目标函数值z;若某染色体 对应不可行解,则赋予其目标函数z一个很大的整 数仇;令G^的适应值函数f一=1/z,^是G。个体生 存能力的表现,,^越大表明其性能越好,即其对应 的解越接近最优解。 2.4判断停止优化过程 判断迭代的代数是否为要求的代数H,若是, 停止进化,选性能最好的染色体G^所对应的路径 初始分组 秽II襻I|辫I...1襻 客户l 1个客户l 1个客户l … 1个客户 南兮端6秽 成本降低l I成本降低l l成本降低 值为0 l l值为6。I l值为d: 塾剜丫Y庄 I I停I L一翻 值为6。I 比较成本下降值 输出成本下降值最大 相对应的分组 图2全局最优法 Fig.2 Overall optimal method 集合,作为原VRPTW问题的优化解输出;反之,继 续执行染色体复制。 2.5染色体复制 采用比例选择和精华模型相结合的选择策略, 将每代种群中适应值^最大的染色体复制后直接 进入下一代种群;剩下的咒一1个染色体从前代种群 染色体中用轮盘旋转法产生。这样既可保证最优个 体可以生存至下一代,又可避免个体间因适应值不 同而使被选择进入下一代的机会相差悬殊。 2.6染色体交叉重组 交叉算子是把2个父代个体的部分结构加以替 换重组,而生成新个体。对染色体复制产生的新种 群,按染色体交叉概率进行n/2次交叉重组,交叉规 则采用PMX法[7]。设父代的2个染色体G。、G2分 别为{1,2,3,4,5,6,7,8,[2 3 33)、{8,7,6,5,4,3, 2,1,[2 3 3]),按PMX法,交叉重组过程如下 G1={1,2,3,4,5,6,7,8,[2 3 3]}净∥l={1,2,6,5,4,3,7,8,[2 3 3]} G2={8,7,6,5,4,3,2,1,[2 3 3])净∥。={8,7,3,4,5,1,2,6,[2 3 3]} 当2个父代染色体相同时,交叉重组将无法继 续迭代进化,只能寻找到问题的局部最优解。为 了继续寻找问题的优化解,可将2个相同的父代 染色体进行迭代进化,随机产生2个交叉点,将每 一个染色体的交叉段移到对方染色体的首部,再 消去相同项,就能产生不同于父体的新个体,交叉 重组过程如下 G,=/1,2,3,4,5,6,7,8,[2 3 3]}辛∥l=t3,4,5,1,2,6,7,8,[3 2 3]) 国=/8,7,6,5,4,3,2,1,[2 3 3]toa'2=13,4,5,1,2,6,7,8,[3 2 3]} 其中交叉交换点是随机选取的。对交叉成功得到的 子代应用2.2、2.3节求得其对应的适应值,并与其 父代进行比较,选择性能优者进入种群。 万方数据 116 交通运输工程学报 2008皋 2.7染色体变异 变异算子是对染色体的某些基因座上的基因值 做变动,作用是维持群体的多样性。在每代种群中 以变异概率进行染色体变异,采用随机交换选中染 色体内2个基因值的变异策略,对变异成功的染色 体应用2.2、2.3节求其适应值,并与父代染色体比 较,选择性能优者进入种群。 3 实验分析 设有1个中心仓库0和8个分仓库,各分仓库 的需求量为d;(z=l,2,…,8),卸货时间为L,要求 的服务时间窗为[口;,b;],中心仓库与各分仓库的距 离由表1给出,其单位为km。车队是由载质量为8 t 的车辆组成,车辆的行驶速度为60 km·h~,车辆 行驶费用与行驶距离成正比。如何安排车辆的行 驶路线,使所有车辆的行驶成本之和达到最小,并 满足每个仓库都在规定时间内被访问到是本文求 解的问题。 裹I仓库参数 Tab.1 Parameters of warehouses 仓库 0 1 2 3 4 5 6 7 8 0 0 54 36 96 24 120 48 45 60 1 0 60 45 60 60 60 60 45 2 0 45 39 60 45 45 45 3 O 66 54 66 54 42 4 0 30 60 24 45 5 0 45 30 42 6 O 90 60 7 O 54 8 0 需求量dr/t 2.0 1.0 2.0 1.5 1.0 2.0 3.5 3.0 卸货时问瓦/h 1.5 1.0 1.5 O.5 1.0 0.5 0.5 1.0 [2.0, [2.5, [2.5, [o.5, [1.5, [o.5, [0.5, [1.0, 服务时间窗 4.5] 5.03 4.O] 2.o] 2.5] 2.03 I.O] 2.5] 根据上述算法原理,本文运用Visual Basic编 写相应计算程序,计算流程见图3,设定迭代代数为 100,运算次数为10次。 实验结果表明,此中心仓库需要3辆车,每辆车 行走的路径、运行距离和运行时间分别为:第1条路 线为0-6-5—1—0,运行距离为207 km,运行时间为 6.45 h;第2条路线为0-8-3—2-0,运行距离为 183 km,运行时间为6.55 h;第3条路线为0-7-4-0, 运行距离为93 km,运行时间为2.55 h;总运行距离 为483 km,总运行时间为15.55 h,车辆未出现闲置 产生初始群 优化过程 二工二 计算优化值 输出路径集 图3计算流程 Fig.3 Computation process 时间,且所有分仓库均得到及时服务。按照以上结 果安排的车辆行驶路线,能使所有车辆的行驶成本 之和达到最小,并满足每个仓库都在规定时间内被 访问到等约束条件。 4 结 语 在实际运输生产中,根据时间要求,合理安排 车辆路线是提高服务质量与经济效益的重要手 段,因此,研究VRPTW具有重要的现实意义和实 用价值。但VRPTW是一个NP疑难问题,精确求 解很困难,采用启发式算法是一种有效的方法。 为了求解有时间窗车辆路径问题,本文建立了数 学模型,提出了染色体编码和可行化过程,建立了 基于启发式遗传算法的有时间窗的车辆路径数学 算法,经过实例计算验证,本文算法可以较快找到 问题的优化解或近似优化解,能有效地实现对路 径自动寻优。 参考文献: References: Tan K,Lee T.A messy genetic algorithm for the vehicle routing problem with time window constraints[C]}}IEEE. Proceedings of the IEEE Congress on Evolutionary Computa’ tion.New Yorkl IEEE,2001:679—686. Ozdemir H,Mohan C.Evolving schedule graphs for the vehi— cle routing problem with time windows[C]//IEEE.Proceed— ings of the IEEE Congress on Evolutionary Computation. New York:IEEE,2000:888-895. ‘ Hwang H.An improved model for vehicle routing problem with time constraint based on genetic algorithm[J].Comput— ers&Industrial Engineering。2002,42(2/4)l 361-369. Osman H,Christofides N.Capaqitated clustering problem by hybrid simulated annealing and tabusearch[J].International Transaction in Operation Research,1994,1(3)I 317—336. 卜雷,尹传忠,蒲云.优化普零货物拼箱装配的遗传 算法[J].交通运输工程学报,2004,4(4);84—87. 万方数据 第1期 赵建有,等:带时间窗车辆路径问题的启发式遗传算法 117 Bu Lei,Yin Chuan-zhong,Pu Yu几Genetic algorithm for op— timal arrangement of general piece goods[J].Journal of Traf— fie and Transportation Engineering,2004.4(4):84—87.(in Chinese) [6]樊小红,荆便顺.基于遗传算法的交通事件控制[刀.长安大学 学报:自然科学版,2005,25(4):70-72. Fan Xiao-hong,Jing Bian—shun.Freeway automatic incident detection with genetic algorithm[J].Journal of Chang’an University:Natural Science Edition,2005,25(4)l 70—72. (in Chinese) [7]王来军,胡大伟,史忠科.容量受限型设施定位模型及遗传 算法[刀.长安大学学报:自然科学版,2006,26(6):65—68. Wang Lai-iun,Hu Da—wei,Shi Zhong-ke.Model and genetic algorithms applying to a type of constrained facility location problem[J].Journal of Chang’an Universityl Natural Science Edition,2006。26(6)l 65-68.(in Chinese) [8]姜大立,杨西龙,杜 文,等.车辆路径问题的遗传算法 研究[刀.系统工程理论与实践,1999,19(6)t40—45. Jiang Da—li,Yang Xi—long,Du Wen,et a1.A study on the genetic algorithm for vehicle routing problemFJl.Systems Engineering--Theory and Practice,1999,19(6):40’45.(in Chinese) [9]牛永亮,王金妹.物流配送车辆路线求解算法[J].交通运输工 程学报,2006,6(2):83-87. Niu Yong-liang.Wang Jin-md.The algorithm for vehicle routing problem of logistics[J].Journal of namc and Transportation Engineering,2006,6(2):83—87.(in Chinese) [10]胡大伟,朱志强,胡勇.车辆路径问题的模拟退火算法[J]. 中国公路学报:2006,19(4):123—126. Hu Da-wei,Zhu Zhi-qiang,Hu Yong.Simulated annealing algorithm for vehicle routing problem[J].China Journal of Highway and Transport,2006,19(4):123—126.(in Chinese) [11] 樊涛.基于遗传算法的路基土石方数量估算方法[J].中国 公路学报,2006。19(6)145—48. Fan Tao.Evaluation method of subgrade earthwork volumes based on genetic algorithm[J].China Journal of Highway and Transport,2006。19(6)l 45—48.(in Chinese) (上接第105页) 城市道路级配的问题作了进一步的探讨与补充。最 appropriate grade proportion of urban road network[J]. 后通过实例分析给出了上虞市合理的道路级配,说 UrbanTm5p。n ofChina,2005,3‘1’l 37—42·‘inchine3。’ 明小城市道路级配模型科学合理,有一定推广价值。 罱C‰JJ 3k7-J9。二.城嚣:竺冀‰fra。。ru咖…apa血,: 参考文献:theory,data structures and analytics[J].Computers,Environ。 References: mant and Urban Systems,1990,14(4):283—297·(in Chinese) [1]王波,赵枫.中小城市交通策略及规划模式研究[J].ills ‘9 3挈竺震’城市道路交通供需平衡理论研究‘D1西安:长安 交通与始2005.5(5)118-21. [10]婵Chio冀:删ici哪。。哪tionalgofi。hmfo……raf- Wang Bo,Zhao Fang.A study on the urban transportation 。 。 ‘ ’ strategies and planning m。des。f medium and small cities口]. fi。∞“’。。l probl。“”i‘h li“k。pacity。1p8“8i。“5口]·Applied Road Traffic and Safety,2005,5(5)l 18-21.(in Ch№e) Ma2h。“8‘i。?8nd Comp“‘8‘i。“,2007'188(2):1 094—1102· [2]GB 50220.95,城市道路交通规划设计规范[s].(in。m”8。) [3]石飞.城市道路等级级配及布局方法研究[D].南京:东南 [11]陆建,王炜·城市道路网规划指标体系[J]·交通运输工程 大学,2006. 学报,2004,4(4):62—67· [4]李旭宏,田锋,顾政华.城市道路网供求分析技术[J].交通Lu Jian,Wang Wei·P1anning indices 8Y8‘8“of urban road 运输工程学报,2002,2(2)188—90. network[J].Journal of Traffic and Transportation Enginee‘一 Li Xu.hong,Tian Feng,Gu Zheng-hoa.Analytical techniqu婚 ing'2004,4(4):62—67·(in Chinese) aboutthe supply and demand of urban road network口].Journal [12]赵志宏,吕连恩,王元庆.城市快速路布局方法[J]·长安大学 ofTraffic andTransportation Engineering,2002,2(2):88-90. 学报:自然科学版,2006,26(4),87—91. (iIl CKne蹄) Zhao Zhi—hong,Lu Lian-en,Wang Yuan-qing.Layout plan‘ [5]魏连雨,马永锋.城市道路交通系统供需协调发展[J].交通 ning method of urban expressway[J].Journal of Chang’an 运输工程学报,2004,4(4):58.60. University:Natural Science Edition,2006,26(4):87_91. Wei Lian-yu,Ma Yong-feng.Supplrdemand coordination devd一(in Chinese) opment of urban road traffic system[J-].Journal of Traffic and [13] 李 娟.相关系数法在通道交通需求预测中的应用[J].中国 Transportation Engineering,2004,4(4):58-60.(in Chinese) 公路学报,2006,19(5):98-101. [6]王建军,王吉平,彭志群.城市道路网络合理等级级配Li Juan.Application of correlation coefficientmethodfor cor- 探讨[J].城市交通,2005,3(1)137—42. ridor traffic demand forecast[J].China Journal of Highway Wang Jian-jun,Wang Ji-ping,Pang Zhi-qun.Discussion on and Transport。2006,19(5):98—101.(in Chinese) 万方数据
展开阅读全文
  皮皮文库所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:带时间窗车辆路径问题的启发式遗传算法.pdf
链接地址:http://www.ppdoc.com/p-10930916.html
关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服客服 - 联系我们

copyright@ 2008-2018 皮皮文库网站版权所有
经营许可证编号:京ICP备12026657号-3 

收起
展开