（管理科学与工程专业论文）具有同时配送和收集需求的车辆路径问题研究.pdf

摘要 随着物流业在我国的不断发展以及物流专业化水平的不断提高，我国物流 配送业近年来也得到了迅速的发展。在物流配送活动中，配送车辆的路线问题是 配送合理化的核心问题，对于企业提高服务水平、降低物流成本、增加经济效益 的影响也最大。为实现成本最小化和效益最大化的根本目的，在进行配送的同时 收集货物将是现代物流配送的发展方向，因此对具有同时配送和收集货物需求的 车辆路线问题进行研究是具有一定的理论价值和现实意义的。 本文对具有同时配送和收集需求的车辆路径问题进行了研究。本文首先对 经典的车辆路径问题及其求解方法的研究进展进行了阐述，并提出了具有同时配 送和收集需求的车辆路径问题的数学模型，然后对该模型的算法复杂度进行了分 析，针对问题的复杂性，设计了适合求解该问题的遗传算法。采用改进节约法构 造和随机产生相结合的方法为遗传算法产生初始解群体，针对该问题的特点设计 了适合于求解该模型的交叉算子以及适应性变异概率，这些对算法快速有效地搜 索到满意解都起着重要作用，最后用计算机编程实现了该算法，通过与有关文献 中的实例进行比较，所求解的质量提高了4 6 ，说明本文设计算法对该问题具 有比较好的适应性。 关键词 配送，集货，车辆路径问题，遗传算法 a b s t r a c t w 胁t h ec o n t i n u o u sd e v e l o p m e n to fl o g i s t i c si n d u s t r ya n dt h ec o n s t a n t l y i m p r o v e m e n to ft h es p e c i a l i z a t i o nl e v e lo fl o g i s t i c si no u rc o u n t r y , l o g i s t i c s d i s t r i b u t i o ni n d u s t r yh a sa l s ob e e nd e v e l o p e dq u i c k l y o fa l lt h ea c t i v i t i e si n d i s t r i b u t i o n ，t h ev e h i c l er o u t i n gp r o b l e mi st h ek e yp r o b l e m i na d d i t i o n ，i th a s g r e a tm u c he f f e c to ne n t e r p r i s et ou p g r a d et h el e v e lo fs e r v i c e ，t or e d u c et h e l o g i s t i c sc o s ta n dt oi n c r e a s ee c o n o m i cb e n e f i t s t oa c h i e v et h eb a s i ca i mo f m j n i m u mc o s ta n dm a x i m u mb e n e f i t s u n i t i z i n gt h ea c t i v i t i e so fd e l i v e r ya n d p i c k u pw i l lb et h et r e n d s o ，i ti so ft h e o r e t i c a la n dp r a c t i c a ls e n s e st os o m e e x t e n t st os t u d yt h ev e h i c l er o u t i n gp r o b l e mw i t hs i m u l t a n e o u sp i c k - u p sa n d d e l i v e r i e sf o rt h i sp a p e r t h eo b j e c to ft h i sp a p e ri st h ev e h i c l er o u t i n gp r o b l e mw i t hs i m u l t a n e o u s p i c k - u p sa n dd e l i v e n e s f i r s t l y , t h ep a p e rr e v i e w so nv e h i c l er o u t i n gp r o b l e m a n di t ss o l u t i o nm e t h o d s ，t h e na n a l y s e st h ec o m p l i c a t i o no fs o l v i n gt h e m a t h e m a t i cm o d e la n dd e s i g n sag e n e t i ca l g o r i t h ma c c o r d i n gt ot h ep e c u l i a r n y t h i sp r o b l e mt os o l v i n gi t c o m b i n et h et w om e t h o d so fs t r u c t u r i n gb yi m p r o v e d c wa l g o r i t h ma n dp r o d u c i n gr a n d o m l yt op r o d u c es t a r t i n gg r o u pf o rg e n e t i c a l g o r i t h m t h ec o m p u t i n gr e s u l ti s2 1 b e t t e rc o m p a r ew i t ht h er e l a t e d l i t e r a t u r e ，w h i c hs h o wt h es u i t a b i l 时o fd e s i g n e da l g o r i t h m z h o n gz h l y u a n ( m a n a g e m e n ts c i e n c ea n de n g i n e e r i n g ) ，directedb yp r o f e s s o ru uh a i l a n k e y w o r d s ：d e l i v e r y , p i c k - u p ，v e h i c l er o u t i n gp r o b l e m ，g e n e t i ca l g o r i t h m 论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。 论文中除了特别加以标注和致谢的地方外，不包含其他人或者其他机构 已经发表或撰写过的研究成果。其他同志对本研究的启发和所做的贡献 均已在论文中作了明确的声明并表示了感谢。 作者签名：二匪垄s 妇期：三垫缦万 论文使用授权声明 本人同意上海海事大学有关保留、使用学位论文的规定，即：学校 有权保留送交论文复印件，允许论文被查阅和借阅；学校可以上网公布 论文的全部和部分内容，可以采用影印、缩印或者其它复制手段保存论 文。保密的论文在解密后遵守此规定。 具有同时配送和收集需求的车辆路径问题研究 1 1 问题的提出 第一章引言 运输、储存、包装、装卸搬运、流通加工、配送和信息组成了物流的七个功能要 素，两其中运输和配送起着尤为重要的作用。在物流过程中，运输是实现物质实体由 供应方向需求方的移动，也就是创造空间价值的过程。根据一般综合分析计算社会物 流费用，运输费占6 0 的比例，有些产品运输费用甚至高于产品的生产费用。可见， 运输成本是影响物流成本的重要因素，物流总成本的大小和运输成本的大小直接相 关。据测算，我国物流成本占g d p 的比重高达2 0 ( 超过2 万亿元) ，发达国家一般只 有1 0 左右，物流成本降低l 到2 个百分点，将产生社会效益1 0 0 0 到2 0 0 0 亿元阳3 ， 因此，控制物流总成本、降低运输成本对我国的经济建设有着十分重要的意义。另外， 配送制可以使库存相对集中，有条件也有可能按照统一计划合理分配和使用资源，做 到物尽其用；实施配送也有利于建立起合理的库存结构和运输结构，进而能够提高物 流设施的利用率和物流设备的工作效率。在库存结构和运输结构分散的状态下，汽车 的货物实载率一般比较低，有的只有2 5 ，而在结构合理、运力集中的状态下，车辆 的货物实载率可提高到7 0 8 0 9 6 。 在长期的经营实践中，企业的经营者逐渐认识到：如果物流活动缺乏系统管理， 不仅会影响企业各项业务的正常运行，而且还会导致经营成本不断上升。因而，物流 工作不是企业一种派生的经营职能，也不是种经营的辅助手段，而是经营过程中的 一个重要的组成部分，物流部门工作的好坏直接决定着企业的发展、经营的效益、服 务的质量和竞争的成败。提高物流效率、降低物流成本、提高物流服务水平对于提高 企业的竞争力有着至关重要的作用。由于物流行业本身不生产产品，靠的是节约的思 想来提高利润，所以必须在各个环节中尽可能地节约成本，特别是在货物的流通环节， 如配送。配送对于各个企业来说都具有十分重要的作用。首先在生产企业中，要贯彻 j i t 思想，建立高效的生产供应链管理系统，准时配送是一个必不可少的方面，无论 是原材料的供应，还是产品的配送，都涉及到货物的配送。其次在服务行业中，要提 具有同时配送和收集需求的车辆路径问题研究 升企业品牌，服务水平就是一个很重要的方面，企业追求的目标是在保证服务水平的 条件下，尽可能的降低物流成本。以货运公司为例，为了提高企业竞争力，专业服务 公司己逐步采用收货、送货服务到家的经营方式。然而，传统经验表明，提高服务水 平将导致成本增加而使利润降低，要在保证服务水平的条件下降低成本，这就对配送 运输提出了更高的要求。所以，研究在企业物流系统中如何降低车辆空驶率、为车辆 安排合理的运输路线具有很强的理论价值和现实意义。 有关满载车辆的最短路径和关于非满载车辆的经典车辆路线问题( v e h i c l e r o u t i n gp r o b l e m v r p ) 或是带时间窗的车辆路线问题( v e h i c l er o u t i n gp r o b l e m w i t ht i m e - w i n d o w s ，v r p t w ) 的研究无论是国外还是国内都比较多，很难再有大突 破，那么从其它角度来降低成本就成为对配送提出的新要求。在一般的车辆路线问题 中，通常由站点( d e p o t ) 派出一组车辆来服务一组顾客，顾客的需求只有单纯的收集 货物( p i c k u p s ) 或是配送( d e l i v e r i e s ) 时，很明显，采用这种运输方式在回程或去程 中车辆就为空载。而如果用集成的观点同时考虑配送客户和集货客户，则能避免或减 少车辆的空载里程，提高车辆的实载率，于是利用回程车辆的空闲容量来降低成本、 增加收入就成为人们新的追求目标。提倡配送和集货一体化能为企业进一步降低成 本、提高利润，为社会节约资源，成为物流配送的又一发展目标。 1 2 问题概述 1 2 1 问题描述 具有同时配送和收集的车辆路线问题( v e h i c l er o u t i n gp r o b l e mw i t h s i m u l t a n e o u sd e l i v e r i e sa n dp i c k u p s ，简称v r p s d p ) 是指在为车辆指定路线的过程 中，用相同的态度对待配送客户( 需要货物的客户) 和集货客户( 供应货物的客户) ，而 不是把这两者分开考虑，分别派车，是经典车辆路线问题( v r p ) 当车辆不仅要为客户 送货，还要从客户处把货物带回站点( d e p o t ) 时豹情形。很显然，这样傲可以提高车 辆的实载率，因为如果车辆进行单纯配送( 或单纯集货) 那么车辆路线中的装载量就越 来越少( 或越来越多) ，在回程( 或去程) 时就是空载，而如果同时进行配送和收集货物 则能够在很大程度上提高车辆实载率，节约运输成本。 2 具有同时配送和收集需求的车辆路径闫题研究 1 2 2 应用范围 同时配送和收集的车辆路径问题的应用范围很广，如提供服务的第三方物流企业， 如果提倡在配送的同时收集货物，利用先进的信息平台就能够更进一步地节约成本， 提高服务水平。又如制造企业，需要把原材料从供应商处运到仓库，同时又需要把生 产出来的产品配送到客户处；又如啤酒厂，需要把啤酒产品送到客户处，同时又需要 把客户喝完的空瓶回收到工厂；还有如纯净水厂，既要把纯净水送到客户处，又要从 客户处带回用完的空桶等。在上述这些情形中，采用同时配送和收集的思想就能起到 很大的节约成本的作用。另外，在邮政系统中，如果能把取信送信、取包裹和送包裹 看成一体、集成操作，不仅能提高服务水平，而且能够降低运营成本。 配送和集货一体化的思想在国外己有一定的应用，有关研究也正在深入的进行， 在实际中的应用也正在扩展中。在该问题的一些初步尝试应用中，已经取得了明显的 效果，这对促进有关该问题的进一步深入研究起到了很大的作用。美国州际商业委员 会新闻报( 1 9 8 0 ) 估算通过使用回程集货每年可节约的燃料为4 2 0 0 万仑；k e a r n e y 0 9 8 4 ) 总结了企业在1 9 7 8 年到1 9 8 3 年间为了提高物流的多样性而执行的项目，第一个项目就 是协调开出的车和返回的车从而提供自有车辆的回程集货，已被8 3 的支持者采用“。 y a n o 等“7 1 描述了以密歇根为中心的铁路链，近4 0 家商店和一个在托利多附近的配送中 心的情形，商店自有或租用了l l 辆货车，其载重量和容量是确定的，这些车是用来配 送货物到商店并从附近的供应商处收集货物，最后，所有配送中心的司机要在路线结 束后回到配送中心。在1 9 8 6 年用同时配送和收集的思想为车辆分配路线，发现使用自 有车辆从供应商处收集货物比另外派车节约了4 5 0 ，0 0 0 美元。 物流业务的整合意味着物流技术的整合，在技术上实现各项业务的整合才能真正 的为社会、为企业节约资源，降低成本、提高利润，因此现代物流提倡同时配送和收 集有着很大的应用空间和前景。 1 3 国内外研究动态 1 3 1 国外有关v r p s p d 的研究 相对于众多研究v r p 及v r p t w 问题的文献，研究v r p s p d 问题的文献较少。此外，在 许多文献中提至s j v r p b ( v e h i c l er o u t i n gp r o b l e mw i t hb a c k h a u l s ) 问题，其特点是 3 具有同时配送和收集需求的车辆路径问题研究 回程收货的作业方式强调必须在所有需要配送的货物配送完毕之后才可以开始集货， 但当某个客户点同时有配送、集货需求时，将会造成对同客户点需要访问两次的现 象，造成车辆资源的浪费；另外限制集货作业只能在配送作业完成之后才能开始会导 致车辆的路线规划缺乏弹性，可能会因为要满足这一约束，增加运输的距离和成本。 v r p m ( v e h i c l er o u t i n gp r o b l e mw i t hm i x e d l o a d ) 是一种取消对先配送后集货的限 制，但是在每一个客户点只进行单纯的集货或单纯的配送作业，这一类型的问题最早 # h g o l d e n “”等人( 1 9 8 5 ) 提出，在他们的假设中允许有集货作业需求的客户点在有配 送作业需求的客户点之前被访问，使用基于在收货客户( d e l i v e r y ) 的路线中插入送货 客户( p i c k u p ) 的方法来求解该问题；另外c a s c o 嘲等( 1 9 8 8 ) 利用c l a r k e 和w r i g h t ( 1 9 6 4 ) m 1 所提出的节约法来构造有配送需求客户的初始路径，有集货需求客户则是使 用修改后的g o l d e n 等人( 1 9 8 5 ) 的插入法，其思路是当剩余的配送量足够少时，才允许 集货点插到配送点之前。 m i n ( 1 9 8 9 ) 1 首次求解了v r p s p d 的问题，这类问题不仅取消对先配送后集货的限 制，而且允许同一客户点同时有集货和配送，即当客户既是集货客户又是配送客户时 的情形，解决了如一个站点、两辆车和2 2 个客户的公众图书面临的实际问题。其解法 思路是首先把客户分组，接着求解每组的旅行商问题( t r a v e l i n gs a l e s m a np r o b l e m ， t s p ) ，惩罚不可行弧( 把它们的长度设为无限大) ，然后再求解t s p s 。h a l s e ( 1 9 9 2 ) 用先分组后分配路线的方法求解了该问题，首先把客户分配给车辆，接着在安排路 线的过程使用3 一o p t 方法优化。g e n d r e a u 等( 1 9 9 9 ) 汹1 研究了带取货和送货的旅行商问 题( t s p p d ) ，首先在不考虑取货和送货的情况下求解t s p 问题，然后再在t s p 的路线中 确定取货和送货的次序。 1 3 2 国内有关v r p s p d 的研究 国内研究该问题的文献也十分有限，只有少数几位学者对该类问题进行了研 究。郎茂祥分别用模拟退火和禁忌搜索算法求解配送和集货一体化车辆路线问题以 及带时间窗的配送和集货一体化车辆路线问题，并给出了含有2 0 个客户点的实例及其 计算结果。但是在其求解的问题中，同一客户的配送和集货的时间是不一样的，这样 每个客户必须要访闯两次，相当于每个客户只有单纯的集或配的需求，于是归为v r p m 。 叶志坚等”3 提出求解配送和集货一体化车辆路线问题的索套启发式解法，该方法对一 4 具有同时配送和收集需求的车辆路径问题研究 些集货量和配送量都很大的客户在路线开始阶段和结束阶段共访问两次，显然，当集 货量和配送量都很大的客户位于离站点较远的位置，用该方法求解将导致车辆行驶路 线迂回过多，其求解结果的质量就不高。 1 4 本文主要研究内容 本文的研究对象是经典车辆路线问题的一个扩展，考虑路线中的客户既需要货物 又供应货物的情形，并且建立该问题的模型及其求解方法。在实际应用中，对于单纯 送货或单纯取货的客户，只需把模型中客户的取货量或送货量设为零，就能使用本文 提出的方法求解。 本文的第一章阐述了提高物流服务水平、降低物流成本的必要性和重要性，由此 引出了研究车辆路线问题的重要性及迫切性，并分析了在目前物流发展状况下，提倡 同时进行配送和收集物流运作模式的重要意义；介绍了国内外v r p s p d 的研究现状，尤 其是国内学者的研究成果，并指出其不足之处。 本文的第二章对车辆路径问题( v e h i c l er o u t i n gp r o b l e m ，v r p ) 领域的研究进行 了综述，根据目前的研究状况对该问题进行了分类；分析了该问题的图模型和数学模 型两大类模型各自的优缺点；分四大类讨论了求解该问题的算法：精确算法( e x a c t a l g o r i t h m ) ，构造启发式算法( c o n s t r u c t i v eh e u r i s t i ca l g o r i t h m ) ，改进启发式算 法( i m p r o v i n gh e u r i s t i ca l g o r i t h m ) ，和亚启发式算法( m e t a - - h e u r i s t i c a l g o r i t h m ) 。评述各类算法适用的问题求解阶段以及各自的优缺点；并且探讨了国内 在v r p 领域的研究成果。 论文的第三章简述了配送和集货的相关概念；建立了具有同时配送和送货需求的 车辆路径问题的数学模型，并进行了模型的算法复杂度分析。 论文的第四章求解v r p s p d 的遗传算法，确定了算法中的各算子及参数，用c 语言 编程实现所设计的算法并给出算例与前人的研究结果进行比较，从丽证明本文设计算 法的可行性和有效性。 论文的第五章总结本文的主要工作和研究结论，并对需要进一步研究的问题进行 简要说明。 5 具有同时配送和收集需求的车辆路径问题研究 第二章车辆路径规划问题及其求解方法研究进展 车辆路径规划问题( v e h i c l er o u t i n gp r o b l e m ，v r p ) 最早是由d a n t z i g 和r a m s e r ”“ 于1 9 5 9 年首次提出的。由于该问题是一个n p 难题，随着节点数目的不断增多，问题的 求解过程将会极大地消耗系统的运行时间和存储空间，因此它的提出很快引起了运筹 学、应用数学、组合数学、图论与网络分析、物流科学、计算机应用等学科的专家与 运输计划制订者和管理者的极大重视，随着近年来电子商务以及物流供应链系统的高 速发展，v r p 也成为上述领域的研究热点。 2 1 车辆路径规划问题及其分类 车辆路径规划问题一般指的是：对一系列发货点和收货点，调用一定的车辆，组 织适当的行车路线，使车辆有序地通过它们，在满足指定的约束条件下( 例如：货物 的需求量与发货量，交发货时间，车辆可载量限制，行驶里程限制，行驶时问限制等) ， 力争实现一定的目标( 如车辆空驶里程最短，运输总费用最低，车辆按一定时间到达， 使用的车辆数最小等) 。 表2 - 1 车辆路径问题的分类属性及其取值 分类属性属性的取值 车辆载货状况满载，非满载 单车场( 货场、配送中心) ，多车场( 货 车场( 或货场、配送中心) 数目 场、配送中心) 车型数目 单车型，多车型 时问要求无时问窗，硬时间窗，软时闻窗 确定需求，随机需求；确定服务时间， 信息的确定性随机服务时间；确定车辆行驶时间，随 机车辆行驶时间 6 具有同时配送和收集需求的车辆路径问题研究 ：二：三二：二 二二：二三：二：二： 在实际应用过程中，v r p 可以按照不同的分类原则细分为许多子问题，不同的分类 属性的不同取值( 见表2 - 1 ) 的组合形成了各种类型的问题。例如：当车辆装载状况取 值为：非满载：配送中心数目取值为：多配送中心；车型数目取值为：单车型；时间 限制取值为：硬时间窗；而需求信息取值为需求不确定；那么该问题就是一个载重量 限制下的多配送中心、单车型、硬时间窗的随机需求的v r p 问题。考虑的属性越多问 题越复杂，求解越困难。目前研究的较为复杂的问题类型一般最多考虑3 4 个属性。 多数的研究都是只针对考虑了l 2 个属性的问题展开。比如：d r o r 等研究的满载问 题。李军等泓1 研究的非满载问题，c o r d e a u 等汹3 研究的带有时间窗的问题，g e n d r e a u 等m 3 研究的多车型的问题等等都是针对1 2 个属性进行研究。近年来随着计算机科 学，通讯科技的发展v r p 问题的研究领域逐渐拓宽，最近几年研究的较多的问题类 型有： 多供货点问题( m u l t i p l ed e p o tw p m d v r p ) ：多个供货点可以同时对客户进 行供货，该类问题的研究涉及到供货点如何选择； 带有时间窗的问题( v r pw i t ht i m ew i n d o w s v r p t w ) ：每个客户对车辆的最 早到达时间( e a r l i e s tt i m e ) 、最迟到达时间( 1 a t e s tt i m e ) 及服务时间( s e r v i c et i m e ) 均有一定的要求； 随机问题( s t o c h a s t i cv r p ，s v r p ) ：问题涉及的某类元素具有随机性，比如 需求的到达，服务时间等等，也有研究者将该类问题定义为动态车辆路径问题 ( d y n a m i cv r p ，d v r p ) 。谢秉磊等嘲对d v r p 特征进行总结，延伸了该问题的定义，对 近些年该问题模型、渐进结果和算法的研究成果做了较为详细的回顾。 分批交货闯题( s p l i td e l i v e r yv r p s d v r p ) ：相当于满载问题一个客户的 需求需要多个车来满足。 回程时集货的问题( v r pw i t hb a c k h a u l s ，v r p b ) ：该类型的问题是指当所有 的货物都送完之后车辆还要到一些客户处取货的问题。 同时配送和收集货物的问题( v r pw i t hs i m u l t a n e o u sp i c k - u p sa n d d e l i v e r i e s ，v r p s p d ) ：即车辆在送货同时要取货的问题。 混合配送和牧集货物的闯题( v r pw i t hm i x e d - l o a d ，v r 跏) ，是指不需要等所 有的货物都送完才可以收货，收货和配送可以任何顺序进行，但与同时配送和收集货 7 具有同时配送和收集需求的车辆路径问题研究 物的问题不同的是，这类问题不允许车辆在同一个客户处同时进行配送和收货作业。 也就是说如果某个客户既有配送需求也有收集需求的话，车辆必须访问两次。 国内的研究一般分为对传统确定性v r p 的研究和对动态v r p 的研究两大类。近几年 的研究多集中在对动态v r p 的研究上。 2 2 车辆路径规划模型形式及其特点 目前研究的车辆路径规划模型有两类一类为网络图模型另一类为数学模型。 2 2 1 网络图模型 经典v r p 定义在图g ：( y ，e ) i - ，其中v = v o ，v l ，v 。) ，e = ( v i ，v j ) ，v ；，v j y 。 表示供货点该供货点拥有m 辆载重量为q 的同型车辆( m 可以是已知的，也可以是决策 变量) 。v l , - - - , 匕代表n 个需求量分别为吼( j = i ，由的待访问的客户点。o 是弧或者 说路段p 。，v ) e 的费用或者距离。经典v r p 在以下的约束条件下求解m 条路径的总行 驶成本最小： 每条路径的起点和终点都是供货点； 每个客户只应该被车辆访问一次； 每条路径中的所有客户需求的总和不能超过车辆的载重量q 。 该经典v r p 模型定义的前提条件是所有的需求都是收货或者都是配送，而非配送 收集一体化。 网络图模型的优点是直观性强，容易理解；缺点是对参数的容纳能力有限，能够 使用的求解方法不多，因此该种模型缺乏表达复杂问题的能力。 2 ，2 2 数学模型 ， 随着v r p 研究的深入，其数学模型针对不同问题条件，呈现出不同的模型形式， 以车流或物流为基础的数学模型就是其中的代表。式( 1 ) 删与式( 2 ) 分别给出了两类 模型的一个例子，其中式( 1 ) 是针对单车型、带有硬时闻窗、且有装载能力约束的v r p 编制的基于三下标车流变量的数学模型，式( 2 ) 则针对多车型、有最长行驶距离限制、 3 具有同时配送和收集需求的车辆路径问题研究 集货送货一体化的v r p 给出了双下标物流变量组成的数学模型。 m i n z = 勺目标函数 ， s j g i y a q ，k = 1 ，m 车辆载重约束 i = 1 y 。= 1 ，k y 碡= m k = l= f ，j 基二左务约束 j o = 0 z 独21 s j + t i + t f 。s ， i ，j = 0 ，z ；i 歹+ a j sj 冬bj ，j = 1 ，l t j = m a x 和。一0 ) 2 0 或1 ，y 往= o 或1 ，l 变量 i ，j = o ，l ；k = l ，m i 9 时间窗约束 ( 2 - 1 ) 柬约路道 m m = “ 江 七 仉 u “ 卜 江 ，枷。脚 具有同时配送和收集需求的车辆路径问题研究 z = 轰( 弘n 汕峨巾咖g z 一毛l 荟汕“。咖g t ) j j = l ，2 ，n t 一1 h 。sq 。 车辆载重约束 薹堙n 。 道路约束 荟d n + d i ，i 。s f g ng t ) d t 道路约束 0 i l l f n 。= 工 t = i r 。= k l l ，工 f - 1 ，n 。 r inr k ：= 彩，v 乏l t2 任务约束 s ；鲫( n 。) = ，n 其k 他 1 变量 ( 2 屯) 数学模型的特点是：容量大。该种模型对参数的容纳能力很大。能够表达任 何大规模的问题；灵活性高。随着实际应用需求的出现数学模型的表达形式会 随着问题条件的变化而发生一些改变，但是无论数学模型采用何种形式，基于v r p 问 题的基本含义，它们都可归结为式( 2 3 ) 所示的模型基本结构； m l no r 蝴x z = f ( x ) 与车辆能力相关的约束 与时间窗相关的约束 与任务相关的约束 与道路网络流量相关的约束 其他约束 变量设定 ( 2 3 ) 在该结构中要增加、减少或者改变一些约束只需要对相应约束内容对应的式子 进行操作：通用性强。一旦将路径规划问题抽象成上述的数学模型，从模型本身就 很难看出原问题所属的领域，任何可以抽象成该类型模型的其他管理决策问题都可以 q v l h ，口 纵，一 v i + - 吼 “ h， 具有同时配送和收集需求的车辆路径问题研究 用这类模型表示。这一特点也使得v r p 在抽象成上述数学模型的过程中失去了本身的 问题特征，其求解过程单纯是对数据的操作，因此求解的结果将是不带任何领域知识 和信息的数据要将这些数据包含的意思还原成用户能够理解的形式需要寻找建模 之初对这些变量做的假定含义，这个过程往往需要专家来实现，这样就造成了模型使 用过程的复杂化。 2 3 车辆路径规划问题求解算法概述 由于v r p 包含了旅行商问题( t r a v e l i n gs a l e s m a np r o b l e m ，t s p ) ，而t s p 本身就是 n p 难题，所以v r p 也是一个n p 组合优化难题1 。自该问题被提出之日起。国内外学者 力求构造高效的算法来解决这一难题。这些求解算法大体可分为两类：一类为精确算 法( e x a c ta l g o r i t h m ) ，另一类为近似算法( a p p r o x i m a t i o na l g o r i t h m ) 。其中的近似 算法又可以大致分为三类：构造启发式( c o n s t r u c t i v eh e u r i s t i c s ) 算法、改进启发 式( i m p r o v i n gh e u r i s t i c s ) 算法、亚启发式( 埘e t a h e u r i s t i e s ) 算法。下文就这四类算 法近些年的研究成果做简要评述。 2 3 1 精确算法 基于v r p 的传统数学模型的精确型求解算法代表性的研究成果主要有：f i s h e r 眦1 提出的k 一树法、p a d b e r g 等m 1 的分技剪枝法、g o h l 和m a d s e n m l 用拉格朗曰松弛算法求 解带有时问窗的v r p 、f u m e r o 等“”的修正拉格朗日松弛及子梯度优化方法、l o r e n a l u i z 等“”对列生成方法的改进等。 精确算法主要适用于解决闯题结构比较清晰、所含各元素之间的关系明确、边界 清楚的良性结构问题。这些问题有判定解的可行性和最优性( 或满意性) 的明确准则， 得出的解能反映解决问题的可行方案，求解工作所需的计算量不大，所需费用不多。 另外还有许多实际的v r p 不具有良性结构，并且有些问题不存在严格最优解( 例如， 目标之间相互矛盾的多目标决策问题) ，或者有些问题要得到最优解需花费过大的代 价当采用精确算法求解这种类型的问题时难以得到理想的效果，它们的解决就需依 赖于近似算法。 具有同时配送和收集需求的车辆路径问题研究 2 3 2 构造启发式算法 构造启发式算法是将尚未指定路线的客户按照某些标准插入到现有的已部分形 成的路线中去，以最终形成解。该算法是秉解v r p 问题最早使用的近似算法。c l a r k e 和w r i g h t 提出的c - w 节约算法1 ，g i l l e t t 和m i l l e r 提出的扫描算法“”，以及s o l o m o n 提出的最近邻启发式算法都是构造启发式算法中最为经典的算法。其后虽有很多学 者将这些经典算法加以改进，但这些改进大都以缩短计算时间和减少内存的占用为目 标，对于当代如此发达的计算机而言，这些改进都是微不足道的。 虽然构造启发式算法简单易懂，但有时找到的解离最优解差的较远，因此该算法 现已不单独用来求解v r p 问题，而是与改进算法相结合，用在构造初始解阶段。 2 3 3 改进启发式算法 改进启发式算法可以将构造启发式算法得到的比较差的解通过邻域的搜索反复 改进，得到较好的解。改进启发式算法大概可以分为路线内部改进和路线闻改进两种。 路线内部改进是将某条路线内部的某些边和结点互换位置，而路线间改进是在相邻路 线之间交换一些边和结点来改进当前的解。 具有代表性的求解v r p 的改进启发式算法有k o p t 以及2 一i n t e r c h a n g e 算法。o p t 算法来自于l i n m 提出一种旅行商问题( t r a v e l i n gs a l e s m a np r o b l e m ，t s p ) 的路径优 化思想其思想是对给定的初始回路，通过每次交换k 条边来改进当前解。后续的研 究者对该算法加以扩展，延伸应用到v r p 领域，出现了3 - o p t 算法和4 一o p t 算法等一系 y i j o p t 算删。该算法在求解v r pj b 题时，k 条边可以是路线内部的，也可以是路线之 间的。丑一i n t e r c h a n g e 算法由o s m a n 发起。它的思想是在几条线路之问相互交换一 些客户来改进路线。该算法在后续的研究中也被应用解决多类v r p 闯题，如有时间窗 的v r p 删。 该类算法的优点是得到最优解的概率较高；缺点是随着k 和a 值的增大，运算时 间会成倍增长，不利于实时系统的处理。 2 3 4 亚启发式算法 构造启发式算法和改迸启发式算法都不允许劣质中阉解的产生，而只允许解的优 化结果朝好的方向单向递增，因此这两种算法都较容易陷入局部最优，为了克服这一 具有同时配送和收集需求的车辆路径问题研究 缺点，多种亚启发式算法相继出现亚启发式算法在优化问题的过程中允许劣质的中间 解出现能够跳出局部最优而在全局内寻优。 用于求解v r p 问题的亚启发式算法有禁忌搜索、模拟退火、遗传算法、蚁群算法 等。 ( 1 ) 禁忌搜索 禁忌搜索是对局部邻域搜索扩展后的一种全局逐步寻优算法。该算法d 目g l o v e r 陶 在1 9 8 6 年首次提出，由于该算法的搜索速度快、效率高，适用于大规模的优化计算， 因此随着v r p 复杂性的提高和问题领域的延伸，该算法在近些年来更是备受研究者的 亲睐，很多复杂的问题都用该算法解决。例如：c h a o l 嘲1 、s c h e u e r e r 5 7 1 用该算法解决 了带拖车的货车v r p ；b r a n d a o 脚3 用该算法解决了开放的v r p ；h e 和h a u g l a n d 陆9 1 解决了 带时间窗的分批交货的v r p ；m o n t a n e 和g a l v a o t ”1 用该算法解决了具有同时配送和收集 货物的v r p 。但禁忌搜索算法具有对初始解有较强的依赖性和搜索过程中只能对一个 解操作的缺陷，所以往往需要使用别的启发式方法先获得一个较好的初始解。 ( 2 ) 模拟退火算法 模拟退火算法( s i m u l a t e da n n e a l i n ga l g o r i t h m ) 是a h k i r k p a t r i c k 等3 提出的一 种求解组合最优化闯题的算法。该方法适用的领域较多，具有较强的实用性，并可人 为地控制迭代次数，反复求解。然而该方法所得解的好坏与初始状态、温度函数等都 有一定的联系，降温较快的效果不一定很好，效果好的，其降温过程又极其缓慢。该 法创立之初对于解决单目标路径规划问题可以褥到非常满意的解，虽然后经过一些学 者如u l u n g u 和t e g h e m 池1 ( 1 9 9 4 ) 的研究改进，可以解决多目标问题。但是就其运算过程 和得到的解来说不如遗传算法的效果好。 ( 3 ) 遗传算法 遗传算法通过多个个体间的选择、交叉等的遗传操作，相互协力地进行解的探索， 与以前的算法中对单纯的并列的解的探索相比，容易发现更好的解。遗传算法运用到 v r p 上，对于解诸如带有时阀窗的v r p 鲥，先分组后安排路径的路径规划问题等等一 些具有多目标的路径规划问题，取得了很好的效果。然而在运用该方法的过程中，问 题的遗传因子型的表现依赖于设计者的能力。并且该算法所得结果的好坏，主要依赖 于遗传代数和解组规模，在实际应用中只能根据具体要求，在合理的时间内对问题进 行求解，若所得解不能令人满意，就要增大解组规模或遗传代数，从而有希望得到问 具有同时配送和收集需求的车辆路径问题研究 题的全局最优解，当然，这是以延长计算时间为代价的。 ( 4 ) 蚁群算法 蚁群算法是近十几年来新兴起的一种摹仿蚂蚁觅食行为的算法。可以查到的最早 将该算法应用到路径规划问题上的文献的年代始于1 9 9 5 年。此后，g a m b a r d e l l a 和 d o r i g o ”。州，s t u t z l e 和h o o s ，b u l l n h e i m e r ，h a r t l 和s t r a u s s 渊以及m a z z e o 和 l o i s e a u 协3 都有将该算法应用到路径规划问题中并获得成功。蚁群算法具有群体合作、 正反馈选择、并行计算等三大特点，并且可以根据需要为人工蚁加入前瞻、回溯等自 然蚁所没有的特点。因此，该算法具有很强的发现较好解的能力。但是这种算法也存 在一些缺陷，如搜索时间较长，容易出现停滞现象( s t a g n a t i o nb e h a v i o r ) ，即搜索 进行到一定程度后，所有个体所发现的解完全一致，不能对解空间进一步进行搜索， 不利于发现更好的解。现在对该算法的研究大多数都集中在对这些缺陷进行改进上。 综合上文分析可以发现，每一种算法单独工作都会存在一些比较大的缺陷，而且 ： 随着社会的发展，问题规模不断扩大化，结构不断复杂化，单一的算法很难解决现实 中复杂化的问题。如果将几类算法融合贯通，取长补短，就可以克服很多缺点，构造 出比较好的算法。近十几年对算法的研究开始侧重于融合多种算法，构造混合算法上。 2 4 国内在y r p 领域的研究成果与进展 国内对v r p 问题的研究是随着近几年电子商务物流配送业的发展两发展起来的。 根据研究的问题类型的不同，可以将国内的研究工作大体分为两个阶段：第一个阶段 是对确定性v r p 的研究，第二个阶段是对动态v r p 的研究。 在第一个阶段的研究中，国内学者的研究多集中于对已有v r p 算法的改进，其中 较多的是对c - - w 节约算法、遗传算法两类算法的改进。较有代表性的成果有：李军等 人用h v 节约算法实现了有时间窗的车辆路径安排哺1 ；设计了基于自然数编码的遗传 算法并将其用于求解非满载车辆调度问题，在实验分析中获得了较好的结果1 ；采 用先分组、后组内安排路线的启发式方法解决多车场情况的非满载的小货运量运输问 题，提高了车辆的使用效率；另有文献 7 1 0 3 的研究都是对c 邗节约算法、遗 传算法两类算法的改进应用到求解各种不同类型的确定性v r p 闯题中。 动态车辆路径问题是近年来v r p 研究领域的一个新发展，它比传统的确定性车辆 具有同时配送和收集需求的车辆路径问题研究 路径问题更符合实际，更有理论和应用价值。最近几年，国内对该问题的关注与研究 逐渐增多，其中有代表性的研究成果之一是出自于西南交通大学郭耀煌教授带领下的 团队n 3 “”；另外还有刘浩等人将快速扫描算法与模拟退火算法相结合，首先用快 速扫描算法求一个初始可行解，然后用模拟退火思想求近似最优解，用该混合算法实 现了求解单类型车辆随机需求问题的一个例子“；张涛等将遗传算法和禁忌搜索算法 的结合混合算法引入到求解v r p 中0 1 ，实现了不确定车辆数的车辆路径问题的求解。 由于国内对v r p 问题的研究起步较晚，有国外研究学者的研究成果作基础因此 国内第一个阶段的研究中，基础性的工作较少，都是直接对已有的算法进行改进以使 其能够运用到较复杂的问题中：或者直接利用已有的算法构造混合算法，以弥补单一 算法求解过程的不足或者单一算法不能够求解多目标约束的v r p 的不足；第二个阶段 的研究则涉及到对模型的建立与分析，算法的建立与评价等各个方面。 具有同时配送和收集需求的车辆路径问题研究 3 1 概念 第三章具有同时配送和收集需求的车辆路径问题 3 1 i 配送 配送是物流中一种特殊的、综合的活动形式，是商流与物流紧密结合，包含了商 流活动和物流活动，也包含了物流中若干功能要素的一种形式：它是指在经济合理区 域范围内，根据用户要求，对物品进行拣选、加工、包装、分割、组配等作业，并按 时送达指定地点的物流活动。 从物流角度看，配送几乎包括了所有的物流功能要素，是物流的一个缩影或在某 小范围中物流全部活动的体现。一般的配送集装卸、包装、保管、运输于一身，通过 这一系列活动完成将货物送达的目的；特殊的配送则还要以加工活动为支撑，所以包 括的方面更广。但是，配送的主体活动与一般物流却有不同，一般物流是运输及保管， 而配送则是运输及分拣配货，分拣配货是配送的独特要求，也是配送中有特点的活动， 以送货为目的