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

西南交通大学硕士研究生毕业论文第1 页 摘要 物流配送活动中，车辆的行车路线规划问题是配送合理化的核心问题，对于企业提 高服务水平、降低物流成本、增加经济效益有很大的影响。为了实现配送活动成本最小化 和效益最大化，针对越来越多的退货物流和回收物流，在配送的同时回收货物将是现代逆 向物流的主要发展方向，因此对具有同时配送和回收需求的车辆路径问题进行研究，具有 一定的理论价值和现实意义。 本文主要对具有同时配送和回收需求的车辆路径问题( v r p s p d ) 进行了研究，在分析了 各种常规约束条件的前提下，提出了本文的研究对象，即有可选模糊时间窗的v r p s p d 。 论文主要从以下方面对问题进行了分析和研究。 l 、阐述了车辆路径问题的概念，按照不同的标准对车辆路径问题的分类进行了总结， 并回顾了车辆路径问题的求解模型及算法； 2 、在考虑多车型且车辆有载重量限制、最大行驶距离限制等约束下，通过引入模糊 预约时间和可选时间窗的概念，从顾客满意度的角度研究了模糊不确定信息条件下的多目 标具有同时配送和回收的车辆路径优化问题，建立了求解此问题的多目标混合整数规划模 型。 3 、在介绍标准遗传算法构成及特点的基础上，首先通过对各个编码方式及遗传算子 的简单分析，选出求解本文模型的基于自然数编码的方式及合适的便于处理的遗传算子。 其次为了构建合适的适应度函数，首先对三个目标进行无量纲处理，之后提出通过加权求 和的方式将多目标转化为单目标，再将转化后的目标函数直接作为适应度函数。最后设计 了求解多目标规划的混合遗传算法，并用该算法对随机加权和固定加权情况下，分别进行 了算例仿真并都在迭代一定代数之后达到了收敛解，并且对客户满意度对规划结果的影响 进行了研究，算例仿真结果表明满意度的变化对结果没有明显的影响。 关键词：车辆路径；模糊时间窗；可选时间窗；同时配送和回收；混合遗传算法；无量 纲 西南交通大学硕士研究生毕业论文第1 i 页 a b s t r a c t i nt h e1 0 9 i s t i e sa n dd i s t r i b u t i o na c t i v i t i e s ，v e h i c l er o u t i n gp r o b l e mi st h ec o r ei s s u eo f t h e r a t i o n a l i z a t i o no fd i s t r i b u t i o n ，w h i c ha l s oh a sa g r e a ti n f l u e n c ef o rt h ee n t e r p r i s e st oi m p r o v e s e r v i c el e v e l s ，r e d u c el o g i s t i c sc o s t sa n di n c r e a s ee c o n o m i ce f f i c i e n c y i no r d e rt om i n i m i z e d i s t r i b u t i o nc o s t sa n dm a x i m i z er e t u r n s ，f o rt h e g r o w i n gn u m b e ro fr e t u r nl o g i s t i c sa n d r e c y c l i n gl o g i s t i c s ，p i c k i n g - u pa tt h es a m et i m eo fd e l i v e r i n gw i l lb et h em a i nd i r e c t i o no f d e v e l o p m e n to fm o d e mr e v e r s ed i s t i i b u t i o nl o g i s t i c s ，s oi th a sac e r t a i nt h e o r e t i c a lv a l u ea n d p r a c t i c a ls i g n i f i c a n c et or e s e a r c hv 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 pa n d d e l i v e r y ( v r p s p d ) t h i sp a p e rm a i n l ys t u d yt h ev r p s p dp r o b l e m ，a f t e ra n a l y z i n ga v a r i e t yo fc o n v e n t i o n a l c o n s t r a i n t s ，w ep r o p o s et h eo b j e c to ft h i ss t u d y ：v r p s p dw i t hf u z z ya n da l t e r n a t i v et i m e w i n d o w s t h i sp a p e rm a i n l y a n a l y z e sa n ds t u d i e sf r o mt h ef o l l o w i n ga s p e c t s 1 ，w h i c hm a i n l yd e s c r i b e st h ec o n c e p to fv r p ，s u m m a r i z e st h ec l a s s i f i c a t i o no fv e h i c l e r o u t i n gp r o b l e ma c c o r d i n gt od i f f e r e n tc r i t e r i a ，a n dr e c a l l e dt h ev e h i c l er o u t i n gp r o b l e m s o l v i n gm o d e l sa n da l g o r i t h m s ； 2 ，i nc o n s i d e r i n gt h em u l t i v e h i c l e ，v e h i c l el o a dl i m i t sa n dt h em a x i m u mt r a v e ld i s t a n c e l i m i t a t i o n sc o n s t r a i n t s ，t h r o u g ht h ei n t r o d u c t i o no f f u z z ya p p o i n t m e n tt i m ea n dt h ec o n c e p to f a l t e r n a t i v et i m ew i n d o w s ，w es t u d yt h e m u l t i - o b je c t i v e v e h i c l er o u t i n g p r o b l e mw i t h s i m u l t a n e o u sp i c k u pa n dd e l i v e r yf r o mt h ep e r s p e c t i v eo ff u z z yc u s t o m e rs a t i s f a c t i o nu n d e r t h ec o n d i t i o no fu n c e r t a i ni n f o r m a t i o n ，a n da n a l y z e st h ea l g o r i t h mo f t h i sm o d e l j 3 ，a f t e ri n t r o d u c i n gt h ec o m p o s i t i o na n dc h a r a c t e r i s t i c so ft h es t a n d a r dg e n e t i ca l g o r i t h m ， f i r s to fa l l ，t h r o u g ha n a l y z i n gt h ec o d i n gm e t h o da n dt h e g e n e t i co p e r a t o r s ，w ec h o o s eac o d i n g m e t h o dw h i c hb a s e do nn a t u r a ln u m b e r s ，a n dt h r e ea p p r o p r i a t eg e n e t i co p e r a t o r sw h i c ha r ee a s y t od e a lw i t h s e c o n d ，i no r d e rt ob u i l das u i t a b l ef i t n e s sf u n c t i o n ，a f t e rd i m e n s i o n l e s st h et h r e e o b j e c t i v e s ，w et r a n s f o r mm u l t i p l eo b j e c t i v e si n t oas i n g l eo n eb yw a yo fw e i g h t e ds u m m a t i o n ， a n dt h e nt r a n s f o r mt h eo b j e c t i v ef u n c t i o nd i r e c t l ya saf i t n e s sf u n c t i o n ；f i n a l l yd e s i g na h y b r i d g e n e t i ca l g o r i t h mt os o l v i n gm u l t i o b j e c t i v ep r o g r a m m i n g ，a n du s et h i s a l g o r i t h m f o r r a n d o m 。w e i g h t e da n df i x e d w e i g h t e dc a s e sr e s p e c t i v e l y ，a n da f t e rac e r t a i ng e n e r a t i o n so f i t e r a t i o n sc o n v e r g e n c eo ft h eo p t i m a ls o l u t i o nh a sb e e ng o t e n ，w h i c hd e m o n s t r a t e st h e f e a s i b i l i t y a n de f f e c t i v e n e s so ft h ea l g o r i t h m a n ds t u d yt h e i m p a c to fc u s t o m e rs a t i s f a c t i o no nt h e o u t c o m eo fr o u t i n gp l a n n i n g ；e x a m p l es i m u l a t i o nr e s u l t ss h o wt h a tc h a n g e si ns a t i s f a c t i o nh a s n os i g n i f i c a n te f f e c to nt h er e s u l t s k e y w o r d - v e h i c l er o u t i n g ；f u z z yt i m ew i n d o w ；a l t e r n a t i v et i m ew i n d o w ；s i m u l t a n e o u s d e l i v e r ya n dp i c k u p ；h y b r i dg e n e t i ca l g o r i t h m ；d i m e n s i o n l e s s 西南交通大学曲南父逋大罕 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国 家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权西南交 通大学可以将本论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复印手段保存和汇编本学位论文。 本学位论文属于 1 保密口，在年解密后适用本授权书； 2 不保密幺使用本授权书。 ( 请在以上方框内打“4 ”) 学位论文作者签名： 夺华 指导老师签名： 赴彩圣 肚彩圣 日期： a 。p ，o日期： 弘，o 甲、t 孑 西南交通大学硕士学位论文主要工作( 贡献) 声明 本人在学位论文中所做的主要工作或贡献如下： 1 论文在对相关文献进行深入研究的基础上，总结了国内外关于v r p s p d 问题的模型 及算法，针对以往约束条件少、车辆数固定、单车型的情形，结合v r p s p d 问题的特殊性， 建立了适用于多车型、多时间窗、( 车辆数确定或不确定) 需求确定的v r p s p d ( v r p ) 的混 合整数规划模型，这一模型稍作变换即可用于其它v r p 问题，对未来的研究有参考价值。 2 鉴于目前国内外关于v r p s p d 的研究大多数都局限于单个目标，本文在考虑现实情 况建立多目标模型的基础上，提出了先对各个目标进行无量纲处理，之后通过加权的方式 将多个目标转化为单个目标作为适应度函数，用混合遗传算法进行仿真求解。 本人郑重声明：所呈交的学位论文，是在导师指导下独立进行研究工作所得的成果。 除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的研 究成果。对本文的研究做出贡献的个人和集体，均己在文中作了明确的说明。本人完全意 识到本声明的法律结果由本人承担。 学位论文作者签名：套华 日期：加卢年厂月o 日 西南交通大学硕士研究生毕业论文第1 页 第1 章绪论 随着社会经济的快速发展和市场竞争的日趋激烈，成本和能源问题目益成为企业发展 中的重要问题，如何减少成本、提高能源利用率成为企业提高核心竞争力、实现可持续发 展所面临的重大课题。由于物流成本在商品成本中占据了相当大的比重，控制物流成本必 然成为企业降低成本减少损耗的重要手段，配送( 运输) 成本作为物流成本的主要组成部 分也势必会成为研究热点。车辆路径问题就是研究如何优化配送( 运输) 成本的一类组合 优化问题。本文对车辆路径问题的一个重要研究分支即带时间窗约束的具有同时配送和回 收需求的车辆路径问题进行了研究，建立了相应的数学模型并利用启发式算法对问题进行 了仿真求解。 1 1 论文的选题背景和研究意义 现代所说的物流是指为了满足消费者的需求，把物资供应、产品制造运输以及销售 等市场情况统一起来加以考虑的一种战略措施。物流可以为企业带来大量直接和间接的利 润，被称为“第三方利润源泉”，其作用越来越受到人们的重视。 经济学家斯通博士在对美国零售企业的研究中发现，在美国的三大零售企业中，商 品物流成本占销售额的比例在沃尔玛是1 3 ，在凯马特是8 7 5 ，在希尔斯则为5 。 如果年销售额都按照2 5 0 亿美元计算，沃尔玛的物流成本要比凯马特少1 8 6 2 5 亿美元， 比希尔斯少3 2 5 亿美元，其差额大得惊人3 。由此可以看出，一个良好的物流配送系统 可以成为一个企业高速发展的有力保障。而通过分析研究发现，在物流配送系统中，配送 成本( 运输成本) 占有相当高的比重，因此对配送中心而言，合理的优化配送路径不仅可 以简化配送程序、减少配送频率、提升配送效率而且更重要的是可以提高资源利用率节约 配送成、在满足客户需求的同时可以使企业获得较大的利润。因而逆向物流中车辆路径规 划问题已成为当前国内外物流领域研究的热点。 物流配送车辆优化调度问题最早是由d a n t z i g 和r a m s e r 于1 9 5 9 年首次提出的，国 外将物流配送车辆优化调度问题归结为v e h i c l er o u t i n gp r o b l e m 和v e h i c l es c h e d u li n g p r o b l e m ，是一类具有极强应用性的优化调度问题，它在物流配送、交通运输等领域获得 了广泛的应用，其范例大量存在于日常生活之中k 1 。车辆路径问题中的调度对象除了车辆 外还可以是航班、轮船；调度目标除总费用最小外还可以是总距离、总时间最短，而它们 的共同之处在于都是通过选择适当的行车线路来优化成本。问题一般认为，不考虑时间要 求，仅根据空间位置安排路线时称为车辆路径问题( v e h i c l er o u t i n gp r o b l e m ，简记v r p ) ： 考虑时间要求安排路线时称为车辆调度问题( v e h i c l es c h e d u li n gp r o b l e m ，简记v s p ) ：同 时考虑时间要求和空间位置时称为r o u t i n g 和s c h e d u l i n g 混合问题。也有些学者不区分， 西南交通大学硕士研究生毕业论文第2 页 只是加上具体约束定语，例如将有时间要求的车辆调度问题称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 ew i n d o w s ( v r p t w ) 阳1 。本文中将其统一称为v r p 问题。 1 2 问题的提出 在以往的研究中，基于正向物流和逆向物流的不同关系，延伸出了许多不同种类的 v r p ，如带回程取货的车辆路径问题h 。1 ( v e h i c l er o u t i n g p r o b l e mw i t hb a c k h a u l s ，v r p b ) 、 具有混合配送和回收的v r p 哺1 ( v e h i c l e r o u t i n gp r o b l e mw i t h m i x e dp i c k u p sa n d d e l i v e r i e s 。v r p m p d ) 、配送和回收问题( p i c k u pa n dd e l i v e r y ，p d p ) 睁1 2 1 等，但由于这些 问题通常将正向物流和逆向物流分开来考虑( 即单向配送) 往往导致一些不必要的浪费， 并且在现实应用中受到限制。 考虑到在许多实际问题中，客户可能在配送的同时也有回收需求。例如，在向零售商 配送饮料和其它有外包装的货物时，客户可能要求同时回收空的饮料瓶和包装材料。如果 将配送和回收过程分开来进行会造成店主一些额外的劳动和时间浪费，因此他们不愿意接 受这种分开进行的独立服务，而且分开来进行独立的服务也会造成配送中心成本的增加。 因此，把正向物流和逆向物流统一起来加以考虑不但客户乐于接受而且也提高了配送中心 的工作效率降低了配送中心的各项成本。这种把正向和逆向物流统一起来考虑的v r p 被称 为具有同时配送和回收需求的车辆路径问题( 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 s p i c k u pa n dd e l i v e r y ，v r p s p d ) 。 v r p s p d 问题由m i n 于1 9 8 9 年首次提出，采用先对各个客户节点进行聚类，然后对每 个类别中的客户进行排序，将v r p s p d 转化为几个t s p 问题进行优化的方法，解决了车辆数 确定、车辆有容量限制情况下，1 个中心图书馆与2 2 个地方图书馆之间图书的发送和回库 问趔1 3 】。v r p s p d 可以简述为：确定车辆( 数量确定或不确定) 访问所有客户的路径，假设所 有的客户既有需要配送中心配送的货物也有需要被回收的货物，要求在满足所有客户的只 接受一次访问，并且每条路径上客户的需求量( 配送和回收需求) 之和不超过为该条路径 服务车辆承载能力的约束条件下，使得整个配送活动的总成本( 如距离、时间等) 最小n 1 7 1 。 此问题中车辆要同时服务顾客配送和回收需求，是一个更强的约束条件。 由于逆向物流需求具有分散性及其发生的时间、地点、体积、重量的不确定性等特点， 使得逆向物流的车辆路径优化问题与正向物流配送相比具有特殊性和复杂性，因此需要结 合逆向物流自身的特点来探讨逆向物流车辆路径优化的理论、模型和方法问题。目前我国 对逆向物流的研究尚不成熟，关于逆向物流中具有同时配送和回收的车辆路径( v r p s p d ) 问题研究的比较少，而现实中具有同时配送和回收服务的需求却很大，而且此问题的约束 条件多而且复杂，比如配送中心个数、车辆载重量约束( 如何确定车辆出发时的装货量) 、 车辆属性约束( 单车型还是多车型、有无最大运行时间或最大行驶距离限制) 、客户的时 间窗约束( 硬时间窗还是软时间窗、多时间窗还是单时间窗) 、客户需求量是否确定、客 西南交通大学硕士研究生毕业论文第3 页 户是否确定等，为此选择具有同时配送和回收需求的车辆路径问题研究作为论文的选题， 对问题进行广泛和深入的研究，建立相应的理论和方法，具有一定的理论和现实意义，既 可以促进运筹学学科的发展，又可以加速物流配送管理和交通运输管理学科的发展；既能 适应新时代对物流配送和交通运输生产组织提出的新要求，又能改进运输管理水平、提高 客户满意度、降低配送成本，提高运输效益。 1 3 国外研究现状 1 3 1 国外研究现状 比起众多研究v r p 和v r p t w 问题的文献资料，研究v r p s p d 的文献较少。许多关于集 货v r p 研究发的文献其实都指的是v r p b ( v r p 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 ) 和v r p b m ( m i x e dv 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 ) o p 先送货后取货的车辆路径问 题和没有送取货顺序之分的混合送货和取货的车辆路径问题，此类问题把客户点分成两种 类型，即需要送货服务的顾客( 1 i n e h a u l s ) 和需要回收服务的顾客( b a c k h a u l s ) ，在每一 个客户点只进行单纯的配送服务或单纯的回收服务，有可能会造成对同一客户点访问两 次，造成资源浪费。 m i n 于1 9 8 9 年在文献 1 3 首次提出v r p s p d 问题，这类问题不再把客户分为两类，即取 消了配送与回收的服务先后次序，并且允许同一客户可以同时有配送需求和回收需求。 文献 1 8 使用先聚类后排序以及3 - o p t 算法求解了一个仓库下多辆车的v r p s p d 问题； 1 9 研究了只有一辆车可以为客户进行配送服务的v r p s p d 问题，只有一辆车要服务完所 有的客户这类似于t s p 问题，因此作者采取先解决单路径的t s p 问题，而后在该路径上安 排配送和回收的次序的方法来解决此v r p s p d 问题；文献 2 0 从逆向物流的角度建立了 v r p s p d 的数学模型，提出了一种基于插入的启发式算法和基于车辆服务自由度的插入准 则，通过保持较高的当前车容量，增大了车辆访问其他剩余客户的自由度。 文献 2 1 用分支定界法和分支价格法解决了客户有时间窗约束的v r p s p d 问题；文献 2 2 在对路径分割算法和扫描算法的应用进行改进的基础上，提出了两种局部搜索启发式 算法，并建立了v r p s p d 的一种可替代的数学模型，用求解v r p b 问题的方法解决配送中心只 有一辆车的v r p s p d 问题；文献 2 3 在文献 2 2 的研究基础上首次提出了配送车辆有最大 行程约束的v r p s p d 的数学模型，用禁忌搜索算法和混合的局部优化算法对该问题的有 5 0 - 4 0 0 个结点城市的算例进行了算例仿真。 文献 2 4 首次将改进了的a c s 算法用于解决有车辆装载能力限制约束的v r p s p d 问题； 文献 1 4 对v r p s p d 问题进行了详细的描述，对其发展历程中的回程取货的v r p 问题、混 合v r p 问题和具有同时配送和回收的v r p 问题( v r p b v r p m p d v r p s p d ) 进行了详细 的描述和比较，并简要介绍了各问题的研究现状，通过算例验证了局域搜索算法和禁忌搜 西南交通大学硕士研究生毕业论文第4 页 索算法的混合启发式算法对客户数从5 0 - 4 0 0 的v r p s p d 问题求解可以得到有效且高质量的 解；文献 1 5 给出了求解v r p s p d 问题的构造算法、局域搜索算法和禁忌搜索算法，而且 每种算法都给出了有简单需求的算例，并通过有复合需求的( 即配送需求量和回收量都是 一定范围内的均匀分布且回收量是需求量的函数) 实验指出局域搜索算法求解此问题在解 的精度和求解时间方面都比较好。 文献 2 5 对单类型车辆有容量限制、每条路径有最大服务时间限制、每个客户结点回 收量和配送需求量己知约束下的v r p s p d 问题建立了以最小化运输成本( 包括每辆车的固 定成本和运输成本) 为目标的数学规划模型并运用粒子群算法对该问题进行求解。 1 3 2 国内研究现状 国内对于v r p s p d 问题的研究开始的比较晚，目前关于这方面的文献资料也比较少 文献 2 6 研究了单车型、需求量( 配送量和回收量) 己知，同时具有载重约束和时间 约束的双向运输( 配送和回收一次进行) 路径优化问题( d p v r p t w ) 。建立了此问题的以总 行驶里程最小为目标的混合整数规划模型，构建了启发式算法一节约法来求解此模型，并 且运用案例对模型和算法进行了验证。 文献 2 7 研究了车辆可在送货的同时完成取货任务的双向路径问题。建立了多车型、 需求量已知、有载重量和路径长度限制，以配送里程最短为目标的基于问题直观描述的数 学模型；构造了求解该问题的一种新的模拟退火算法；用实例验证了此算法对于该问题的 优越性，并且通过比较说明采用双向配送策略求解装卸混合车辆路径问题对于配送企业具 有节省配送车辆、减少配送里程，从而降低配送成本、提高经济效益的重要意义。 文献 6 研究了在客户处可以同时完成送货和取货任务的带时间窗回程取货的车辆路 径问题( v r p b t w ) ，建立了多车型、有载重量限制、每个节点的取送货量已知、每个节点 的取送货时间( 时间窗) 己知以总费用最小为目标的数学模型，并采用遗传算法、分支定 界法，整数规划法相结合求解该问题，并通过算例验证了此将启发式算法和精确算法相结 合的解法具有鲁棒性好，求解速度快的优点。 文献 1 7 对具有同时配送和回收的车辆路径问题( v r p s p d ) 进行了简单的描述、建立 了单车型、车辆容量有限的、以总费用最小化为目标的数学规划模型、设计了求解该问题 的混合遗传算法并通过与j a nd e t h l o f f 提出的启发式算法比较验证了此算法的优越性。 硕士毕业论文文献 2 8 中主要研究了单车型有最大容量限制的v r p s p d ，建立了此问题的 数学模型，对模型的算法复杂度进行了分析，设计了基于新的适用于v r p s p d 的节约值计 算公式的节约法构造遗传算法初始种群的思想，并对问题进行了仿真求解。文献 2 9 在对 v r p s p d 问题基于有向带权图的描述下，利用混合蚁群算法对有5 0 个节点的带容量限制的 v r p s p d 算了进行了仿真求解。 文献 3 0 给出了单车型、需求量( 配送量和回收量) 已知、车辆容量限制、最大行驶 西南交通大学硕士研究生毕业论文第5 页 距离限制情况下v r p s p d 问题的混合整数规划模型，在传统蚁群算法的基础上首次提出了 感应因子、期望程度因子、距离性比因子及加速因子的概念，在信息素更新方面融入了当 前距离的路径特征，构建了求解该问题的全新的自感应蚁群算法，并通过仿真实验证明了 此算法的有效性。文献 3 1 研究了具有车辆最大行驶距离限制的v r p s p d 问题( m l v r p s p ) ， 建立了单车型、有载重量限制，需求量已知等约束下该问题的混合整数规划模型，并构造 了改进的蚁群算法对问题进行求解，利用实例仿真验证了该算法对m l v r p s p d 问题的有效 性； 文献 3 2 研究了有时间窗的具有同时配送和回收的车辆路径问题( v r p s d p t w ) ，作者 考虑了单配送中心单车型具有容量限制的情况，并用改进的遗传算法仿真求解了具有8 个节点的v r p - s d p t w 。文献 3 3 研究了单配送中心、单车型有容量限制和硬时间窗约束的 v r p s p d ( v r p s p dw i t hh a r dt w ) ，建立此问题的数学模型，并用混合启发式算法对问题 进行了仿真求解，并对有时间窗的v r p s p d 和无时间窗的v r p s p d 的仿真结果进行了比较。 由上面对国内外关于v r p s p d 问题研究的文献概述来看，近年来对v r p s p d 问题的研究 主要都是关于确定需求( 配送量和回收量均已知) 的，并且在约束方面仅仅针对单类型车 辆有容量限制、路径长度限制等单个约束或两个约束组合来建立单目标整数数学规划模 型，在算法方面有精确算法和启发式算法运用的启发式算法比较多，如遗传算法、禁忌搜 索算法、局域搜索算法、粒子群算法、模拟退火算法、蚁群算法等，学者们还研究出了求 解该问题的多个算法相结合的混合启发式算法。但由于分支定界法等精确算法在解决大规 模规划问题方面效果不是太好，所以大多数都采用启发式算法来求解此问题。 虽然对问题的研究约束条件越来越复杂，且求解算法也从分枝定界等精确算法发展启 发式算法，但问题仍然有进一不研究的空间。以往的研究中大多数只考虑v r p 问题中几个 属性( 车型数目、车辆属性、时间窗性质) 中的一个或两个，很少有将其联合起来考虑的。 对于具有同时配送和回收的v r p 研究的还很少。在约束方面考虑的仅仅是一般的单车型、 有容量约束或路径长度限制，几乎很少有考虑多车型、时间窗约束，也没有研究车辆数目 不确定、具有模糊预约时间、多车型等单个约束或组合约束的v r p s p d ；在模型方面，几 乎都是最小化车辆配送里程( 或费用) 为目标建立单目标数学规划模型，没有人考虑多目 标的情况。 由于现实生活中人们选择接受服务的时间段并不是确定的唯一的，即人们可能在一 天中的几个时间段都可以接受服务且每个时间段内都有一小段特别倾向的服务时间( 比如 上午8 ：0 0 - 1 2 ：0 0 ，下午1 5 ：0 0 1 8 ：0 0 两个时间段，并且在这两个时间段内客户更愿 意在9 ：0 0 - 1 0 ：0 0 或1 6 ：0 卜1 7 ：o o 接受服务) 。但对于具有同时配送和回收的v r p s p d 加入这些约束后的理论研究比较困难，前人对有模糊时间窗、可选时间窗等约束的v r p s p d 问题并没有进行研究，并且对于不确定需求的v r p s p d 问题却几乎没有人研究过。因此本 论文拟在前人研究的基础上，把经典v r p 中研究需求确定环境下考虑可选时间窗和模糊时 间窗的方法结合起来应用到v r p s p d 问题中，并用混合的遗传算法对其进行仿真求解。 西南交通大学硕士研究生毕业论文第6 页 1 4 本文的研究内容及技术路线 本文的研究对象是经典车辆路线问题的一个扩展：具有同时配送和回收的车辆路径问 题，在国内外学者对此问题( v r p s p d ) 研究的基础上，假定所有客户节点的需求量都小于 等于所有车辆载重量限制，且配送中心到最远客户的直接行驶距离小于等于所有车辆行程 限制，即每辆车至少可以服务一个客户且所有客户都可以被车辆服务到；所有客户点的需 求遵守“后到先装 原则，且不考虑货物装卸产生的费用；各客户点之间及配送中心与客 户点之间的最短距离采用欧式距离公式计算，且距离对称并满足三角不等式。在考虑单个 车场多车型非满载且商品可混装的前提下，提出了将经典v r p 中需求确定情况下考虑可选 时间窗和模糊时间窗的方法结合起来应用到v r p s p d 问题中，并对需求随机情况下的 v r p s p d 问题做了相应的研究，建立了需求确定和需求随机情况下的车辆路径优化模型。 并通过对模型的分析，使用改进的混合遗传算法进行算法的设计和模型的仿真求解。在实 际应用中，对于单纯送货或单纯取货的客户，只需把模型中客户的取货量或送货量设为零， 就能使用本文提出的方法求解。 1 4 1 论文研究的主要内容 第一章，绪论。本章阐述提高物流服务水平、降低物流成本的必要性和重要性，由此 引出研究车辆路线问题的重要性及迫切性，并分析了在目前物流发展状况下同时进行配送 和回收的物流运作模式的重要意义。本章还介绍了国内外对此问题的研究现状，并指出国 内外学者研究成果的不足之处。 第二章，车辆路径规划问题分析。本章介绍了物流配送中逆向物流的构成、实施逆向 物流的意义，按照不同的分类标准对车辆路径问题的分类进行了总结，回顾了车辆路径问 题的求解模型及算法。 第三章，具有可选模糊时间窗的v r p s p d 研究。这一章为本文的核心章节，在考虑多 车型且车辆有载重量限制、最大行驶距离限制等约束下，通过引入模糊预约时间的概念， 从顾客满意度的角度研究了模糊不确定信息条件下的多目标具有同时配送和回收的车辆 路径优化问题，建立了求解此问题的多目标整数规划模型。 第四章，求解v r p s p d 的混合遗传算法。本章首先选出求解本文模型的基于自然数编 码的方式及合适的便于处理的遗传算子。其次为了构建合适的适应度函数，提出了通过随 机权系数加权求和的方式将多目标转化为单目标，再将转化后的目标函数直接作为适应度 函数。最后设计了求解多目标规划的混合遗传算法。 第五章，算例仿真。本章对上一章设计的求解有模糊预约时间的v r p s p d 的混合遗传 算法进行算例仿真，并对随机加权和固定加权两种构造适应度函数的方式进行比较、对基 于不同优先级的加权方式进行比较并对客户的两个模糊时间窗的不同满意度比较。 西南交通大学硕士研究生毕业论文第7 页 第六章，结论与展望。对本文的研究成果进行了概括，总结了论文的不足之处，并对 下一步研究工作进行了展望。 1 4 2 本文的技术路线 示 一v 一 所厂l 西南交通大学硕士研究生毕业论文第8 页 第2 章车辆路径问题的分类及求解方法概述 2 1 车辆路径问题的分类 车辆路径问题( v e h i c l er o u t i n gp r o b l e m ，v r p ) 通常被描述为：配送中心用多台配送 车辆( 车辆数确定或者不确定) 对客户进行配送和回收服务，将客户需要的货物从配送中 心送到各个客户，并把客户需要被回收的货物从运到配送中心，其中，每个客户的具体位置 已定，配送需求量和回收需求量一定，车辆最大载重量、最大行驶里程一定，要求在满足如 下条件的基础上，合理的安排车辆的配送路线，使得整个配送活动的配送距离或配送费用 等最小，约束条件：1 ) 配送过程中每台配送车辆的载货量不超过车辆的最大载重量限制； 2 ) 每条配送路径的总长度不超过配送车辆的最大行驶里程限制；3 ) 每个客户的配送需求 必须满足，且需要被回收的货物必须取走3 。v r p 问题根据不同的标准可分为不同的类别， 下面从两个分类标准进行介绍b 。引。 2 1 1 逆向物流车辆路径问题根据装卸顺序不同的分类 按照装卸顺序的不同可分类如下： ( 1 ) 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 ) ：先送货后取货的车辆路径问 题。此问题将所有的客户分成了两类，即有配送需求的客户( 1 i n e h a u l s ) 和有回收需求的 客户( b a c k h a u l s ) 。要求配送车辆只能在服务完所有有配送需求的客户之后才能开始进行 回收服务，即只有当所有的l i n e h a u l s 被服务完之后，才能够考虑b a c k h a u l s 的需求。 ( 2 ) v r p b m ( ( m i x e d 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 ) ：混合送货和取货的车 辆路径问题。这类问题在送货和取货方面没有了先后顺序之分，即配送和回收可以以任意 的次序进行，1 i n e h a u l s 和b a c k h a u l s 可以以任意的排列被访问。 混合的送货取货v r p b m 与先送货后取货的v r p b 通常也被统称为v r p b 问题。 ( 3 ) v r p s p d ( v 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 dd e l i v e r i e s ) 具 有同时配送和回收的车辆路径问题：运输网络中有一系列客户点，每个顾客i 有一定的回 收需求量r 和( 或) 一定的配送需求量r ，这些客户点由一些有容量限制的车辆服务，每个 车辆从配送中心出发( 载有所有客户配送需求量之和的货物) 并返回配送中心( 载有所有 客户回收需求量之和的货物) ，每条路径的每个节点不可以将送货和取货分开独自进行服 务，即客户只接受一辆车的一次服务并且每个节点上车辆的载重量都不能超过其容量限制 1 4 , a s 。v r p s p d 是v r p 的一种扩展，它可以和混合的送取货问题相互转化，即v r p b m 可 西南交通大学硕士研究生毕业论文第9 页 以被看作是v r p s p d 中顾客的配送或回收两种需求之一的需求量为0 。通过将每个同时有 配送和回收需求的客户分解为两个只有单一需求的客户，具有同时配送和回收需求的v r p 可分解为混合的送货取货问题。其模型如图2 1 所示【3 引。 v r p b v e u p b m t p s p d 口d e p o t o d e l i v e r yc l i e n t a p i c k u p d e l i v e r yr o u t e 。p i c k - u pr o u t e 冷“m i x e d ”r o u t e 图2 - 1 有回收和配送需求的v r p 2 1 2 按问题涉及因素的可知性分类 按问题涉及因素的可知性，可将v r p 分为确定性v r p 和不确定性v r p ，其中不确定性 v r p 又可分为随机和模糊两类。 ( 1 ) 确定型v r p ：确定是指配送中涉及到的各个因素都是确定的，这里所说的因素 包括配送中心及各个客户的位置、客户的需求量、车辆在各路段的行驶时间、车辆的数量、 及车辆要访问的客户。确定型车辆路径优化问题是指在以上各因素都确定的情况下，如何 安排车辆的配送路线，使得整个配送活动的费用( 也可以是运行距离) 最少。 ( 2 ) 不确定型v r p ：不确定型车辆路径优化问题是指，车辆路径优化中所遇到的所 有或部分因素是随机( 模糊) 的。这些不确定的因素包括各路段车辆行驶时间、客户点位 置、车辆属性以及客户的需求量等等，这类车辆路径优化称为不确定或随机( 模糊) 型车 辆路径优化问题。在此问题中车辆也必须从配送中心出发，完成配送( 回收) 任务，最后 西南交通大学硕士研究生毕业论文第1 0 页 回到配送中心，其目标往往是车辆完成配送的总时间期望最少，或总费用的期望最小。但 同一客户的配送( 回收) 需求可以由同一辆车多次完成或多辆车完成，即在不确定问题中 客户的需求是可分的。 根据上述不确定因素，可将不确定性车辆路径问题( 这里只考虑随机情形即 s t o c h a s t i cv e h i c l er o u t i n gp r o b l e m ) 分为以下6 个子问题。 1 ) 顾客随机的旅行商问题：即t s p s c( t h et r a v e l i n gs a l e s m a np r o b l e mw i t h s t o c h a s t i cc u s t o m e r s ) ，此问题中每个客户节点r 的存在概率为r ，即客户节点的存在与否是 随机的。 2 ) 具有随机旅行时间的t s p 问题：即t s p s t ( t h et r a v e l i n gs a l e s m a np r o b l e mw i t h s t o c h a s t i ct r a v e lt i m e s ) ，此问题中顾客是确定的，但两点间的旅行时间是一个随机变量， 该问题的目标一般是最大化运输车辆在规定的期限内完成整个履行任务线路的概率。 3 ) 车辆数不确定的t s p s t 问题，即m t s p s t ( t h em t r a v e l i n gs a l e s m a np r o b l e mw i t h s t o c h a s t i ct r a v e lt i m e s ) ，此问题将t s p s t 扩展到m 辆运输车辆，此处m 为一个随机变量， 考虑到每辆车的启动成本( 固定成本) 通常都大于其运输成本，因此在考虑问题总