（交通运输规划与管理专业论文）带回程取货的逆向物流车辆路径问题研究.pdf

e 立交适厶堂亟堂位迨塞主塞垣鍪 中文摘要 摘要：随着世界经济的发展和科技的进步，物流产业正在世界范围内迅速发展， 即使是长期受到学术界和企业界忽视的逆向物流也随着可持续发展理念的深入人 心而成为社会同益关注的话题。然而在我国逆向物流的研究还处于初级阶段，尤 其是关于带回程取货的逆向物流车辆路径问题( v e h i c l er o u t i n gp r o b l e m sw i t h b a c k h a u l s ，v r p b ) 的研究远未成熟。 v r p b 问题是车辆路径问题( v e h i c l er o u t i n gp r o b l e m s ，v r p ) 的延伸。v r p b 问 题不像v r p 问题那样只考虑车辆运行中的单纯送货或者单纯取货过程，而是将送 货与取货过程结合起来，同时实现送货和取货，更加节省运输成本。如何在逆向 物流中经济合适地安排车辆的配送路径成为物流管理者面临的一个重要的问题决 策。 本文首先介绍了逆向物流的内涵，通过对逆向物流和正向物流车辆路径问题 进行比较，指出了逆向物流车辆路径问题的特点。在此基础上，通过对比，指出 本文研究的取送交叉v r p b 问题和取送无交叉v r p b 问题的区别在于放松了取货 客户必须在送货客户之后的约束，然后建立无时问窗v r p b 问题模型及相关约束。 通过对不同算法的比较，最终选择改进遗传算法并进行具体的算法设计，最后以 算例进行了验证。 本文还针对物流行业的现状，在v r p b 问题上增加了节点的服务时间窗限制， 建立了带时间窗v r p b 问题( v e h i c l er o u t i n gp r o b l e m sw i t hb a c k h a u l sa n dt i m e w i n d o w s ，v r p b t w ) 模型及相关约束并使用最大一最小蚁群算法进行了具体的算法 设计。最后通过对示例求得的结果比较， 结果，从而在实际中更加节省运输成本， 采用本文设计的算法所求结果优于文献 实现了v r p b t w 问题的优化。 关键词：逆向物流；带回程取货车辆路径问题；时间窗；最大最小蚁群算法 分类号：0 2 3 2 e 塞窑垣厶堂亟堂位监塞旦s 卫坠! a b s t r a c t a b s t r a c t ：w i t ht h e r a p i dd e v e l o p m e n to ft h ew o r l de c o n o m ya n dm o d e m t e c h n o l o g y , l o g i s t i c si n d u s t r yi sg r o w i n gq u i c k l ya l l o v e rt h ew o r l d t h er e v e r s e l o g i s t i c sw h i c hh a sb e e ni g n o r e db ya c a d e m i aa n db u s i n e s sc i r c l ef o ral o n gt i m ei s g r a d u a l l yb e i n gp a i da t t e n t i o nt ob e c a u s eo ft h ei m p l e m e n t i n gg r a d u a l l yt h o r o u g h l yo f s u s t a i n a b l ed e v e l o p m e n ts t r a t e g y i no u rc o u n t r yt h er e s e a r c h e so ft h er e v e r s el o g i s t i c s ， p a r t i c u l a ri nt h ev e h i c l er o u t i n gp r o b l e m sw i t hb a c k h a u l s ( v r p b ) i sa tt h et h r e s h o l d c o m p a r e dw i t hf o r e i g nr e s e a r c hr e s u l t s v r p bi st h ee x t e n s i o no f t h ev e h i c l er o u t i n gp r o b l e m s ( v r p ) w h i c hs e l v e so n l y e i t h e rl i n e h a u lc u s t o m e r so rb a c k h a u lc u s t o m e r s v r p bc a ns e r v eb o t hl i n e h a u l c u s t o m e r sa n db a c k h a u lc u s t o m e r sb yaf l e e to fv e h i c l e ss ot h a ti tc a nr e d u c et h ec o s to f t h et r a n s p o r t a t i o n h o wt oa r r a n g ep r o p e rr o u t et oc u tt h ec o s to fl o g i s t i c so p e r a t i o n si s ak e yp r o b l e mt h a te v e r y1 0 9 i s t i c sm a n a g e rh a st of a c e f i r s t l y ，t h ep a p e ri n t r o d u c e st h ed e f i n i t i o no ft h er e v e r s e1 0 9 i s t i c s ，p o i n t st h e c h a r a c t e r i s t i co ft h ev r pi nt h er e v e r s el o g i s t i c st h r o u g ht h ec o m p a r i s o no ft h ev r pi n t h el o g i s t i c sa n dt h er e v e r s el o g i s t i c s o nt h eb a s i so ft h i s ，p o i n t st h a tt h ev r p bw h i c h i su s e di n t h i sp a p e rd o e s n th a v et h er e s t r i c t i o nt h a ta l lb a c k h a u l sh a v et ob ev i s i t e d a f t e ra 1 1l i n e h a u l sa st h ev i 冲bw h i c ha l ll i n e h a u l sa n db a c k h a u l sa r e n tm i x e d t h e n t h ev r p bm a t h e m a t i c a lm o d e la n ds p e c i a lc o n s t r a i n t sa r ea n a l y z e d t h ev r p bi s s o l v e db yt h ei m p r o v eg e n e t i ca l g o r i t h m s ( g a ) w h i c hi sc h o s eb yt h ec o m p a r i s o no f t h ed i f f e r e n ta l g o r i t h m s f i n a l l y ，i l l u s t r a t i o ni sg i v e nt h r o u g hac a s es t u d y t h ep a p e ra d d sar e s t r i c t i o no ft i m ew i n d o w so nt h ev r p bo nt h eb a s i so ft h e r e a l i t yo fl o g i s t i c si n d u s t r y , a n dt h e nt h ev e h i c l er o u t i n gp r o b l e m sw i t hb a c k h a u l sa n d t i m ew i n d o w s ( 、，r p b t w ) m a t h e m a t i c a lm o d e la n ds p e c i a lc o n s t r a i n t sa r ea n a l y z e d a n ds o l v e db yt h em a x - m i na n tc o l o n ya l g o r i t h m s ( m m a c a ) f i n a l l y , t h er e s u l t s w h i c ha r es o l v e db yt h em m a c aa r eb e t t e rt h a nt h et r a d i t i o n a la l g o r i t h m so nt h e e x a m p l e t h e r e f o r e ，t h em m a c a c a nr e d u c et h ec o s to ft h et r a n s p o r t a t i o ni nr e a l i t ys o a st or e a l i z et h eo p t i m i z a t i o no f t h ev r p b t w k e y w o r d s ：r e v e r s el o g i s t i c ；v r p b ；t i m ew i n d o w s ；m a x - m i na n tc o l o n y a l g o r i t h m s c l a s s n o ：0 2 3 2 e 峦銮道厶堂亟堂位：l 金塞幽酲苤 图目录 图2 1 逆向物流流程图一7 图2 2v r p b 问题示意图1 2 图2 3 正向物流与逆向物流车辆路径问题比较1 3 图3 1 取送无交叉v r p b 问题与无时间窗取送交叉v r p b 问题比较1 7 图3 2 赌盘示意图2 7 图4 - 1 模拟蚂蚁寻食过程3 9 图4 2 最大最小蚁群算法流程图4 5 图4 3 不同取货比例的运输总距离( 2 5 个节点) 5 0 图4 - 4 不同取货比例的平均运输距离( 2 5 个节点) 5 0 图4 5 不同耿货比例的平均使用车辆数( 2 5 个节点) 5 1 | e 立窑迪厶堂亟堂位论塞塞目苤 表目录 表2 1 逆向物流的分类 表3 - 1 精确算法、传统启发式算法和现代启发式算法的比较分析 表3 - 2 各种常用的遗传算子 表3 3 自然遗传学和遗传算法中的基本用语对照表 表3 - 4 各节点的取货、送货需求量 表3 5 车辆间的可行性调整 表3 - 6 车辆内部可行性调整 表3 7 客户节点的送货、取货需求量 表3 8 客户节点间距离 表3 - 9 算例的改进遗传算法结果 表3 1 0 基本遗传算法和改进遗传算法性能比较一 表4 1 示例的基本数据 表4 2 示例的平均时f 日j 窗宽度 表4 3 最大一最小蚁群算法计算结果与其他算法对比表( 2 5 个节点) 表4 - 4 最大一最小蚁群算法计算结果与其他算法对比表( 5 0 个节点) 一 9 2 1 2 3 2 4 2 9 3 0 3 0 3 l 3 l 3 2 3 3 ，4 6 4 8 4 8 4 9 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数掘库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 铷泛斟 签字同期：加9 年f 2 月醐 导师签名：胡关晕 签字同期：一俨l z 月，。同 j e 基窑煎叁堂亟土堂位论塞 独剑世主明 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究一 作和取得的研 究成果，除了文中特别加以杯注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者签名：寺善& 槲 签字同期：7 。7 年偿月，口同 致谢 在我的论文完成之际，首先感谢我的导师胡天军副教授。导师从论文的选题、 结构、写作、修改以及最终的定稿都给我悉心指导和莫大帮助，使论文得以顺利 的完成。回首近三年的硕士生活中，导师严谨的治学态度，渊博的学识、丰富的 实践经验、精益求精的工作作风更是我学习的典范，众多优点无一不在潜移默化 的影响着我，使我受益终生。 在攻读学位期间，北京交通大学交通运输学院的老师和领导也给予了我帮助 和支持，在此谨向各位老师表示衷心的感谢。 在研究生期日j 我在各个方面得到了在研究生期间我在各个方面得到了许多同 学的热情支持和帮助，与他们结下了深厚的友谊，我特别要感谢同门的李蓉蓉、 朱军伟、张志峰和滕耘同学在日常生活及课题研究期间给了我很大的支持和帮助， 在此衷心的祝愿他们前程似锦。 最后感谢我的家人，虽不能在身边相互照顾，但他们对我生活和精神上的关 心始终无微不至，他们是我最孥强的后盾，我的每一分进步都离不开他们。 e 塞交道厶堂砸：兰垃途塞 鳌迨 1 1 研究背景及意义 1 绪论 逆向物流作为物流活动的重要组成部分，长期以来受到人们的相对忽视和冷 遇。然而随着自然资源获取的困难、可持续发展深入人心及环境保护意识的增强 而获得了物流研究学者和企业管理层的高度重视，进入了飞速发展的阶段。 随着在1 9 9 2 年由j a m e ss t o c k 在给美斟物流管理协会的一份研究报告中给出 了逆向物流的定义后，逆向物流的理念得到了学术界和企业界更加广泛的重视， 逆向物流的实践也锝到了进一步的发展，逆向物流的重要性也在逐渐体现出来。 逆向物流具有社会的和企业战略方面的重要意义，其中社会意义主要体现在 资源环境效益方面。实施逆向物流管理，不仅具有环境保护方面的效应，在保护 环境、节约资源、促进循环资源发展方面具有重要的作用，而且能为企业带来节 约资源、降低成本、提高客户满意度、进而增加利润的直接经济效益。因此，实 施逆向物流，对于整个国民经济的发展有着举足轻重的作用。 同j 下向物流一样，在逆向物流中，物流运输是其重要的环节。从物流的概念 上看，物流是“物”的物理性运动，这种运动改变了物的时间状态和窄嘲状态， 而运输承担了改变空问状态的主要任务。这就造成了在现代物流观念未诞生之前， 甚至在今天，仍有不少人将运输等同于物流，其原因是物流中很大一部分责任是 由运输担任的，可见物流运输在物流中的重要地位。物流运输是生产的直接组成 部分同时也是生产过程的继续，联结了生产与生产、生产与消费的环节。再者根 据一般综合分析来计算社会物流费用，物流运输费用占整个物流成本消耗的5 0 左右。以我国为例，2 0 0 6 年，运输费用为2 1 0 1 8 亿元，占社会物流总费用的5 4 7 1 ， 这充分体现了物流运输在物流中的重要地位。 运输合理化的发展对物流产业的快速发展有着重要的影响。而车辆路径问题 是运输合理化的关键一环，该问题以及其延伸问题一直受到了学术界广泛的关注。 带回程取货的车辆路径问题( 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 ，简称 v r p b ) 是车辆路径问题( v e h i c l er o u t i n gp r o b l e m ，简称v r p ) 的延伸。传统的v r p 问题只是关注车辆运行中的单纯的送货或者单纯的取货过程。而v r p b 问题包含 资料米源十国家发展改革委、国家统计局，中国物流。采购联合会2 0 0 7 年3 月1 5 i 联合发布的2 0 0 6 年拿国物流运行报告 i b 立銮道厶堂亟土= ! ；兰位论塞 绪逾 两部分，一部分是将货物由配送中心运送给客户节点；另一部分是从客户节点取 货运并运送回配送中心。它是送货和取货过程相结合，同时实现送货和取货，可 以降低运输车辆的空驶率以此来节约运输成本。 下面两种情况非常适合v r p b 问题的条件： ( 1 ) 流通行业：超市、连锁店、饮料销售商筹要求上游的批发商同时完成软 饮料产品送货及空瓶的返回；超市要求批发商送来一定量的货物，并取走托盘、 包装箱、缺陷产品或多余库存。 ( 2 ) 制造企业：现在制造企业为了提高客户的服务水平，增强竞争力，很多 企业实施了对产品生命周期负责的政策。为了更好地控制产品生命周期过程，便 于产品废弃后的价值恢复，很多企业采取了“运送新产品+ 取回旧产品”的双向运 输方式，例如汽车、电子产品的召回。典型的例子就是联想集团备件物流处采取 的“客户自行更换备件单元”，其过程就是企业把新的计算机配件送达终端客户手 中并进行上门服务，同时取回已损坏的计算机配件。这就是典型的v r p b 问题。 然而传统的v r p b 问题要求必须先服务所有的送货客户后再服务取货客户， 这样就可以避免装货卸货时需要重新整理货柜的麻烦与服务时间的浪费，但是造 成一个同时需要送货、取货的客户节点就会被拜访两次，增加了运输路线的迂回， 浪费了车辆资源。而当前由于车辆货柜设计的改进，很多车辆都有两个以上的货 物出入口，货物装卸时还要重新整理货柜的麻烦已经被解决，因此不需要再考虑 货物的取送顺序，本文研究的就是取送交叉的v r p b 问题。而在实际配送时，服 务客户的时效性也是服务质量的重要一部分，所有客户节点必须考虑到在有效时 间内完成客户服务，也就是所谓的时间窗限制。因此关于带时间窗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 a n dt i m ew i n d o w s 简称v r p b t w ) 是物流 运输理论一个新的关注点，如何在逆向物流中经济合适地安排车辆的配送路径成 为物流管理者面临的一个重要的决策问题。 1 2 国内外研究现状 v r p b 问题是为了充分利用车辆回程资源而发展而来的。对v r p b 问题的重 视是在2 0 世纪8 0 年代，由于在制造业中物流成本占总成本的比例达到2 0 以上， 为了进一步减少货物流通成本，人们开始考虑如何降低返程车辆的空驶率，降低 运输成本，由此诞生了v r p b 问题。因此本文针对v r p b 问题及采用的蚁群算法 进行了检索和总结。 2 e 峦銮适厶堂亟：堂位i 佥塞 缝论 1 2 1v r p b 问题国内外研究现状 1 2 1 1v r p b 问题国外研究现状 国外相关领域研究者关于v r p bi u j 题无论是在理论研究还是在实际应用方面 都取得了非常显著的成果。随着研究的深入发展，如何使研究的理论模型更贴切 现实中的运输规划问题开始成为研究者们关注的焦点。 由于v r p b 问题是v r p 问题的延伸，早在1 9 6 2 年，b a l i n s k i 等首先提出v r p 问题的集分割直接考虑可行解集合，在此基础上进行优化，建立了最简单的v r p 问题模型。d e i f 和b o d i n l 2 】在v r p 问题模型的基础上于1 9 8 4 年建立了v r p b 问题 模型，并通过延伸c l a r k e t 习所提出的节约法观点，将每一个节点建立一条独立路径， 即是车子从配送中心出发，服务一个客户节点之后就返回配送中心，接着再依照 节约法将各个路径合并，反复此步骤直到无法再节约为止，为了使混合路线延后 发生，在处理送货节点和收货节点问的节线连接时，对节约值的衡量指标做修改， 加入了一个惩罚值的概念，并得出惩罚项的系数介于o 0 5 到0 2 0 之间时，示例计 算有较好的结果。 g o e t s c h a l c k x 和j a c o b s b l e c h a 4 1 在1 9 8 9 年提出一个两阶段的启发式解法，在 第一个阶段中，起始解是利用空问填满曲线的转换机制，将节点从平面坐标转换 成曲线，并且形成k 个区域间隔，接着再利用贪心法和k m e d i a n 法将节点分成群 组，每一个群组代表一个路径，由一辆车服务；第二个阶段则是将此问题的数学 模式分解成子问题，然后利用2 一o p t 和3 一o p t 的方式对子问题做改善。t o t h 和v i g o ”、 m i n g o z z i 、g i o r g i 和b a l d a c c i l 6 j 都有对v r p b 问题作探讨。 对于当前取送货节点混排的研究问题，最早由g o l d e n 等【7 于1 9 8 5 年提出，假 设取货节点可以在送货节点静完成，所使用的方法是先建立送货节点路径，然后 将取货节点插入到已经建好的路径中。在插入时，由于车辆从初始点出发时为满 载，所以车辆不能首先服务取货节点，因此加入了避免取货节点开始太早的惩罚 值。c a s c o 等【8 】在1 9 8 8 年也利用c l a r k e 所提的节约法来获得送货点客户的起始路 径，然后修改g o l d e n 等的插入法，其基本思想是在剩余送货量很少时，取货点可 以插入到送货点之i j i 。 s a l h i 和n a g y 【引在1 9 9 9 年提出一个新的插入法，先考虑将两个以上的相邻节 点组成小群组，然后将整个群组插入到路径中去。也有很多人应用智能启发式算 法来解决这类问题，如a n n e 与s a i d i i o 在2 0 0 1 年考虑首先应有蚂蚁算法求解，然 后通过路径改善的方法对所得到的路径进行调整。 对于带时间窗v r p b 问题，t h a n g i a h 等在1 9 9 6 年利用k o n t o r a v d i s 和b a r d 1 2 】 在1 9 9 2 年发展的插入法得到起始解，然后再利用k - i n t e r c h a n g e 和2 - o p t 这两种区 j e 丞窑适厶堂亟堂位迨塞 绪论 域搜寻法做改善：p o t v i n 等【1 3 1 在1 9 9 6 年利用s o l o m o n 【1 4 】在1 9 8 7 年所提出的贪 心插入法来针对必须先送货以后再取货的v r p b t w 问题求仞始解，以决定每辆车 所需服务的节点，再利用遗传算法来重新针对每辆车所需服务的节点顺序做安排， 来求得更好的解；d u h a m e l 等i ”i 在1 9 9 7 年则利用禁忌搜索法柬求解v r p b t w 问 题，其主要目标为使用的车辆数量最小化，第二个目标为距离最小化，其中起始 解是利用s o l o m o n 所提的贪心插入法获得，在该禁忌搜索法罩，是先随机选取 2 o p t 、o r - o p t 、s w a p 三种交换改善法的其中一种来尝试改善原来的可行解，当原 先的可行解被另一个较好的可行解取代，或是其搜索可行解的反复次数超过预先 订定的最大反复次数时，搜索法则会再重新随机选取2 - o p t 、o r - o p t 、s w a p 三种交 换改善法的其中一种来继续做改善。 1 2 1 2v r p b 问题国内研究现状 目前我国关于v r p b 问题的研究还处于初级阶段，有一些专家和学者都开始 了关于v r p b 问题的研究。吴泰熙、陈正芳、徐俊诚【1 6 1 在2 0 0 3 年文章中也是首先 应用模拟退火算法来得到近似最优解，然后再对得到的路径进行改善。隆颖【 】在 2 0 0 5 年通过对v r p b 问题可以同时服务路径上的取货送货节点的研究，利用遗传 算法对其求解，并通过实例证明其有效性。董媛嫒、陶绪林、周晶【18 】在2 0 0 6 年 针对物流企业在定价时存在的问题，研究了带回程车辆的运输路径优化及定价模 型，采用改进的遗传算法求解，为物流企业提供科学的决策依掘。尹传忠等【”】在 2 0 0 6 年在分析具有回送运输和时间窗的车辆路径问题特点的基础上，建立了该问 题的优化数学模型，并通过设黄与发货点距离为零的虚拟集货点使问题简化。霍 佳震、张磊【2 0 j 在2 0 0 6 年指出配送、收集旅行商问题大多假定必须在完成所有的 配送需求后，才服务收集需求。放松这一约束条件，通过对模型的分析、分解和 过滤，结合实际情况，以修正的c w 节约启发式算法和最邻近算法为基础进行插 人式排序，以解决这类问题。王发鸿，达庆利【2 i 】在2 0 0 6 年结合逆向物流中回收产 品的不同形态，构造了t s p 问题基础上的插入启发式算法求解最短路径，然后运用 二维动态规划求解最优回载策略，表明了逆向物流单车辆的最优回载策略应是建 立在最短路径之上的有选择回载，算例结果证明了该策略的实用性和有效性。郭 伏等【2 2 】在2 0 0 6 年在其文中指出考虑回程取货过程可以在送货的过程中先后完成 取货任务，不限制车辆的取送货顺序，因此设计了相应参数，避免了货物的重新 排列。在确定目标时，综合考虑车辆运行成本、人员等待成本及服务成本等因素， 实现目标解的真j 下可行。最后，根据此问题的特点，设计了先通过分枝定界法及 遗传算法确定可行路线，再运用整数规划方法求解的算法，并以实例说明了算法 的有效性。 4 e 立交堑厶堂硒堂位途塞绪论 1 2 2 蚁群算法研究现状 蚁群算法( a n tc o l o n y a l g o r i t h m s ，简称a c a ) 是由意大利著名学者m d o r i g o ， vm a n i e z z o ，a c o l o r o n i 等1 ”】首先提出来的。最早被应用求解旅行商问题( 简称 t s p ) 、指派问题、车i 日j 作业调度问题等并取得了较好的结果。受此影响，蚁群算 法逐渐引起世界许多国家研究者的关注，其应用领域得到了迅速拓宽，取得了大 量有价值的研究成果。g a m b a r d e l l a 和d o r i g o i ”】于1 9 9 6 年又提出了一种修j 下的蚁 群算法，称之为“蚁群系统”。吴庆洪等f 2 1 在提出具有变异特征的蚁群算法，以克 服蚁群算法收敛速度较慢的问题。陈烨( 2 6 】在2 0 0 1 年提出的带杂交算子的蚁群算 法。通过引入遗传算法中用到的杂交算子来改善蚁群，使其对应的问题的解更加 优良，用改进算法求解t s p 问题的结果表明改进算法是有效的。 王颖等i ”】于2 0 0 2 年提出的自适应蚁群算法，通过自适应地改变算法的挥发度 等系数，在保证收敛速度的条件下提高解的全局性，通过对t s p 问题的仿真证明 本文中的算法相对与原始的蚁群算法收敛速度和解的性能都有一定的提高。 d c o s t a 等 2 8 1 在m d o r i g o 等研究成果的基础上，提出了一种求解指派问题的一般 模型，并用来研究图着色问题。gb i l c h e v , i c p a r m e e l 2 9 以及魏平等i3 0 j 研究了求解 连续空间优化问题的蚁群系统模型。 物流配送路径优化问题和t s p 问题一样属于求解最短路径的问题，因此将蚁 群算法应用于物流配送路径优化问题己经受到国内外越来越多研究者的重视，蚁 群算法凭借其在路径优化问题中天然的优势，目鲋在配送路径优化问题上有许多 成功应用的例子。 1 3 本文主要研究内容和创新点 1 3 1 本文主要研究内容 本文首先结合逆向物流自身的特点，在介绍了逆向物流内涵及v r p b 问题的 描述基础上，建立了无时间窗v r p b 问题和带时问窗v r p b 问题的模型及相应的 约束。然后介绍了遗传算法和蚁群算法的基本原理，分别使用改进遗传算法对 v r p b 问题和使用最大最小蚁群算法对v r p b t w 问题进行了具体的算法设计，然 后和相同假设背景的文献做实际的对比。 论文具体结构和内容如下： 第一章为绪论。主要是介绍了论文的选题背景及意义、v r p b 问题和蚁群算法 的国内外研究现状，最后介绍了论文的主要研究内容和创新点。 e 立至适厶堂亟堂位渔塞绪论 第二章为逆向物流车辆路径问题概述。主要是介绍了逆向物流综述以及v r p 问题和v r p b 问题的概述，并对正向物流和逆向物流车辆路径问题进行了一番比 较，指出逆向物流车辆路径问题的特点。 第三章为无时f b 】窗v r p b 问题模型及算法研究。进行了无时问窗v r p b 问题 的介绍，并用改进遗传算法进行了算法设计和算法实现，最后以算例进行了验证 并对改进遗传算法和基本遗传算法的性能比较。 第四章为带时间窗v r p b 问题模型及算法研究。进行了v r p b t w 问题的介绍， 使用最大一最小蚁群算法进行了算法设计和算法实现。最后以算例进行验证并对不 同算法进行了关于算例结果的比较。 第五章为总结与展望。对全文的研究内容进行了总结，指出了其中有待进一 步改进的地方，并对今后的研究内容进行了进一步的展望。 1 3 2 本文的创新点 本文主要的创新点在于： ( 1 ) 详细地分析了带回程取货的逆向物流车辆路径的特点及意义。建立无时间 窗v r p b 问题的模型，运用改进遗传算法进行算法设计并给出具体算例，最后分 析了关于无时1 日j 窗v r p b 问题的改进遗传算法和基本遗传算法的性能比较。 ( 2 ) 针对物流行业现实状况的需求，建立了带时间窗v r p b 问题模型，通过设 计的最大一最小蚁群算法对算例进行了求解，然后与相同背景文献所求结果进行了 比较，通过比较证明设计的最大最小蚁群算法的有效性和优良性。 6 e 立銮迪厶堂亟堂位途塞 逆囱塑适芏扫蹬径四壁拯述 2 逆向物流车辆路径问题概述 2 1 逆向物流综述 2 1 1 逆向物流的内涵 物流与供应链管理的重要性己得到学术界和企业界的普遍重视和关注。然而， 物流管理的重点和焦点一般都集中于“i f 向”的物流活动，即对从原材料的获取、 生产、包装、运输、分销直至在正确的时间、地点送达客户手中的物流过程的一 体化管理。当产品到达了客户手中以后，就基本上离开了企业的物流系统，某些 附属品如包装物也就完成了自己的使命而成为无用的废弃物。而产品在使用一段 时间以后被消费者丢弃、淘汰，这些产品本身及其附属品就会无序地流向自然环 境，造成资源的浪费和环境的污染，为了解决上述产生的问题，逆向物流也因此 而诞生。 从供应链的角度看，逆向物流是指产品、零部件和材料沿着与正向物流流通 渠道相反的方向，从产品的下游向上游回流的过程。它所关心的j 下是这些产品、 零部件和材料的价值修复，废旧物品经过回收处理，使一部分有用的产品、零部 件和材料重获使用价值，也使一部分废弃物晶得到有效处置。 逆向物流的流程如图2 - 1 。 卜 表示逆向物流= = = 冷表示正向物流 图2 - 1 逆向物流流程i 璺i f i g 2 - 1f l o wc h a r o f t h er e v e r s el o g i s t i c s e 塞銮迪厶堂亟堂位途童逆自物逋芏麴蹬径闷壁趣造 逆向物流( r e v e r s el o g i s t i c s ) 的概念可以追溯到很久以前，但是，准确地追溯也 是非常困难的。直到2 0 世纪9 0 年代，逆向物流的含义得到了大大的丰富。1 9 9 2 年，j a m e ss t o c k 在给美国物流管理协会( t h ec o u n c i lo f l o g i s t i c sm a n a g e m e n t ，该 协会在2 0 0 5 年已更名为“美国供应链管理协会”) 的一份研究报告中最早指出， 逆向物流是一种包含了产品退回、物料替代、物品再利用、废弃处理、再处理、 维修与再制造等流程的物流活动。 随着逆向物流理论的发展，美国供应链协会在其公布的供应链全景物 流词条术语2 0 0 3 年9 月升级版中，对逆向物流进行了重新解释：由于修理和信 誉问题，对售出及送达客户手中的产品和资源的回流运动所实施的专业化的物流 管理。 综合上述对逆向物流的定义，虽然陈述有不同，但是关于逆向物流的内涵却 是基本相同的，可以从逆向物流流动的对象、流动目的、活动构成等方面来了解 逆向物流的内涵。 从逆向物流流动的对象来看，逆向物流是产品、包装容器、包装材料及相关 信息，从它们的消费地沿着供应链渠道向上游或向处理设施点的流动过程。 从逆向物流的目的看，一是为了重新获得退货品、回收品或废弃产品的使用 价值，二是为了对最终产品废弃物进行i f 确的处置，避免对环境的危害。 从逆向物流活动构成来看，为了实现逆向物流的目的，逆向物流包括对产品 或包装物的回收、翻新、再循环等多种形式，另外还包括产品正向物流过程中的 资源缩减活动。 2 1 2 逆向物流的分类及特点 2 1 2 1 逆向物流的分类 由于逆向物流有不同的对象、不同的处理目的以及不同的处理方法。从不同 的角度、不同的依据和标准来进行分析，就会出现不同的分类结果。本文大致把 逆向物流分为四种类型。并用表2 一l 列出各自不同的周期、驱动因素、处理方式以 及例证。这四种类型分别为：( 1 ) 商业退货的逆向物流；( 2 ) 产品寿命终结的逆向物 流；( 3 ) 包装物回收的逆向物流；( 4 ) 维修退回的逆向物流。 j e 鏖銮适厶堂亟生位熊塞逆回物逋王牺路径四壁逝整 表2 - 1 逆向物流的分类 t a b 2 - 1c l a s s i f i c a t i o no f t h er e v e r s el o g i s t t c s 类别 周期 驱动因素处理方式例证 商业退货 再使川、再生产、零售商积压库存、时 未使用商品 短到中j l 】市场销售 再循环、再处理装、化妆品 退同还款 市场营销 再生产、再循环 电子设备的再生产， 产品寿命终结 地毯循环，轮胎修复 经完全使用后长期法规条例 再循环白色利黑色家用电器 需处理的产品 再生产、再循环、计算机组什及打印硒 资产恢复 再处理鼓 包装物回收经济再使用 托盘、条板箱、器皿 包装材料 短期 法规条例再循环包装袋 和产品载体 维修退回市场营销 有缺陷的家用电器、 中期 维修处理 缺陷或损坏产品法规条例 零部什、手机 2 1 2 2 逆向物流的特点 逆向物流与正向物流一起在供应链中形成闭环物流。所谓闭环物流就是指供 应链上的企业对物流活动进行的从最上游的供应地到最下游的最终用户的双向的 全过程的管理。它的最终目标是为了获得竞争优势，是对物流的双向的全过程的 高效率和高效益化。 但是与传统的正向物流相比，逆向物流又有以下特点： ( 1 ) 产品来源的分散性 逆向物流产生的地点、时间、质量和数量都是难以预见的。废旧物资可能产 生于生产领域、流通领域或生活消费领域，涉及任何领域、任何部门，在社会的 各个角落都不停地发生，j 下是这种多元性使逆向物流具有分散性。 ( 2 ) 产品品种的混杂性 回收的产品在进入逆向物流系统时往往难以划分为产品，因为不同种类、不 同状况的废旧物资常常是混杂在一起的。当回收产品经过检查、分类后，逆向物 流的混杂性便会随着废旧物资的产生而逐渐衰退。 ( 3 ) 产品分布的不确定性 回收的产品产生的地点分散无序、回收物品不可能集中和一次向接收点转移 9 j e 峦銮丝厶堂亟堂位途室逆囱物速互牺路径回壁援述 等，是从供应链的下游向上有传递实物和信息，所以很难预测何时何地，有多少 不同状况的商品，每种商品的数量和质量等进入回收流通的渠道，具有极大的不 确定性。 j 下是由于逆向物流具有的分散性、混杂性和不确定性都给逆向物流车辆路径 问题的合理优化提出了新的难题。 首先是逆向物流的分散性给进行取货车辆的配载提出了新的问题，如何规划 合理的车辆路径既可以及时地缩短物品的回收周期，又可以做到取货车辆的配载 合理化成为物流管理者一个重要的决策。 其次是逆向物流的混杂性对车辆路径问题的影响主要在于由于回收货物种 类、体积不同及形状的不规则造成了在车辆路径问题的安排上既要考虑配送车辆 的容量又要考虑到车厢和货柜的设计，从而达到车辆使用的最优化。 最后是逆向物流的不确定性对于车辆路径问题的影响较大，因为难以控制产 品回收的时| 日和空间，造成了安排车辆路径问题时对于安排车辆数、车型等都提 出了新的要求。若在有效承诺时间内不能完成任务，无形之中就降低了客户满意 度，只有在有效时间内完成任务才能提高服务质量。 总之，由于逆向物流天生的特点给逆向物流车辆路径问题提出了新的要求及 难题，随之合理的优化车辆路径就能够解决上述产生的问题，不仅节省企业的运 输资源、降低了费用，提高了企业的良好形象，而且成为企业新的利润增长点。 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 ) 、传统车辆路径问题( v e h i c l er o u t i n g p r o b l e m ，简称v r p ) 、带能力约束的车辆路问题( c a p a c i t a t e dv e h i c l er o u t i n g p r o b l e m ，简称c v r p ) 、带时间窗车辆路径问题( v e h i c l er o u t i n gp r o b l e mw i t ht i m e w i n d o w s ，简称v r p t w ) 、多车种车辆路径问题( f l e e ts i z ea n dm i xv e h i c l er o u t i n g p r o b l e m ，简称f s 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 hm u l t i p l eu s eo fv e h i c l e ，简称v r p m ) 、带回程取货的车辆路径问题( v e h i c l e r o u t i n gp r o b l e mw i t hb a c k h a u l s ，简称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 sa n dt i m ew i n d o w s ，简称v r p b t w ) 来 探讨。 o b 塞銮适厶堂亟堂垃迨塞逆囱物远至牺蹬径四墅趣述 2 2 1 逆向物流车辆路径问题介绍 退回产品或废弃产品的运输是逆向物流中最突出的问题之一。一般来说，这 些废旧产品从客户手中向未来处理场所设施点( 或从买主向物品来源地) 的物理 性移动，需要花费高昂的运输成本，这一成本将严重影响产品回收处理的整体经 济性。另外，有些废弃物的运输过程还会导致新的环境问题，要受到国家相关法 律法规的约束，因此，废旧产品的运输规划不能仅仅考虑路径最短目标。从决策 层次看，运输路径问题属于逆向物流规划中的策略层和运作层的管理问题。 逆向物流车辆路径问题主要分为两类： 一是v r p b 问题，本文研究的重点。v r p b 问题是基于企业对于产品及其包 装物的回收再利用产生的，企业通过回收产品及其包装用于新产品的制造，属于 企业内部物流，一般是与企业难向物流形成了闭环物流。v r p b 问题是v r p 问题 的延伸，这一类型的问题将节点分成两个集合，一为送货节点的集合，另一个为 取货节点的集合，当送货节点的集合或是取货节点的集合为空集合时，v r p b 问题 就变回为v r p 问题。 二是逆向物流中的多点对一点的车辆路径问题。这类问题的主体执行者一般 是第三方物流，从不同取货节点把废旧产品集中起来，然后向未来的处理场或该 物品制造厂家进行运输。其特点是与正向物流中的传统车辆路径问题相反，是多 个耿货节点对应一个处理中心。 在取送无交叉的v r p b 问题中，限制送货节点与取货节点不能混合作业，也 就是说车辆在每个路径中必须先服务送货节点后，才可以服务取货节点。这样的 考虑是为了避免在取货或送货后必须重新整理货柜物品之安排，来空出搬运与装 载货物的空间。v r p b 问题示意图如图2 2 。 如同正向物流中的v r p t w 问题一样，将v