（管理科学与工程专业论文）需求可拆分的物流车辆路线问题研究.pdf

同济大学硕士学位论文 摘要 摘要 车辆路线问题是物流运作与管理中的一项重要问题。在很多情况下，车辆 运输成本是物流成本最主要的组成部分，因此通过优化车辆路线安排可以有效 地降低物流成本，同时也是提高物流服务水平的主要手段之一。 在大部分车辆路线问题的研究中，都预先设定了一个条件，就是每个客户 的需求( 指小于车辆最大运载能力的需求) 必须由一辆车在一次服务中完成。 但实际的物流运作中，在能满足服务要求的前提下，有时通过需求的拆分可以 更好地降低运输成本，特别是在需求量普遮较大的情况下。因此作者针对这一 实际情况，选择需求可拆分的物流车辆路线问题作为本文的研究主题。 本文主要通过分析、建模、算法设计这一过程对需求可拆分的物流车辆路 线问题进行了深入的研究，研究重点在于如何利用亚启发式算法求解需求可拆 分的物流车辆路线问题。主要内容如下： 首先，在阅读大量文献的基础上对需求可拆分的物流车辆路线问题的研究现 状进行了综述，同时对车辆路线问题进行了全面的概述，以此作为进一步研究 的基础。 其次，通过对问题的分析，建立了需求可拆分的物流车辆路线问题的一般模 型和整数规划模型，对可行解的特性进行了分析，证明了判断解是否可行的三 个重要判据，并对需求拆分的意义进行了简单的分析。 然后，本文针对需求可拆分的物流车辆路线问题的整数规划模型。设计了利 用禁忌搜索进行求解的算法，其中重点设计了符合需求可拆分的物流车辆路线 问题特点的邻域搜索方法，以及通过引入邻域搜索范围的自适应策略对禁忌搜 索算法进行了改进。并对算法进行了算例验证。 此后本文又根据需求可拆分物流车辆路线问题的整数规划模型的特点，将问 题转化为单位需求客户的车辆路线问题，并设计了求解该问题的遗传算法。在 设计过程中，本文引入可行化算子和可行化概率参数来抑制由于不良拆分而引 起的群体质量恶化问题。最后利用算侧对算法进行了验证。 最后对全文进行了总结，并对进一步的研究进行了展望。 关键词：需求可拆分的车辆路线问题，车辆路线问题，禁忌搜索算法，遗传算 法 堕莲查兰堡主堂壁笙苎 翌至 a b s t r a c t v e h i c l er o u t i n gp r o b l e m ( v r p ) i sab a s i c i s s u ei nl o g i s t i c sa n d t r a n s p o r t a t i o n m a n a g e m e n t t h e e n t e r p r i s e c o u l dr e d u c et h e t r a n s 口o r t 8 t i o nc o s ta n di m p r o v et h es e r v i c el e v e lb yo p t i m i z i n gt h e v e h i c l er o u t i n ga n ds c h e d u l i n ga st h et r a n s p o r t a t i o nc o s ti so f t e nt h e l a r g e s tp a r to fl o g i s t i c sc o s t i nm o s to fv r pr e s e a r c h ，ac o n d i t i o nh a sa l w a y sb e e nd e f i n e dt h a to n e c u s t o m e rm u s tb es e r v i c e db yo n ev e h i c l e o fc o u r s e ，i nt h i sp r o b l e mt h e d e m a n do ft h ec u s t o m e ri sl e s st h a nt h ec a p a c i t yo ft h ev e h i c l e h o w e v e r ， s o m ec o s ts a v i n gc o u l db eo b t a i n e db ys p l i t i n gt h ec u s t o m e rd e m a n di n r e a lo p e r a t i o n s ，e s p e c i a l l yw h e nam a j o r i t yo fc u s t o m e rh a v eh e a v yd e m a n d s ow ec h o o s e dt h es t u d yo fs p l i td e l i v e r yv e h i c l er o u t i n gp r o b l e m ( s d v r p ) a st h et o p i co ft h i sp a p e r i nt h i sp a p e r ，t h er e s e a r c ho ns d v r pi sc o m p o s e do fa n a l y s i s ，m o d e l i n g a n dt h eh e u r i s t i c sd e s i g n t h em o s ti m p o r t a n tp a r ti sh e u r i s t i c sd e s i g n f i r s t l y ，w er e a dal o to f1 i t e r a t u r ea n dt r yt of i n do u tt h eg e n e r a l s i t u a t i o no ft h er e s e a r c ho ns d v r p w ea l s or e a l i z et h ep a n o r a m ao fv r p a n da 1 1t h e s ea r et h eb a s i co ft h er e s e a r c hi nt h i sp a p e r s e c o n d l y ，w ee s t a b l is hag e n e r a lm o d e la n dain t e g e rp r o g r a m sm o d e l o fs d v r p t h e nw er e s e r c ht h ep r o p e r t yo ft h el e a s i b l es o l u t i o na n dp r o v e t h r e ei m p o r t a n tc r it e r i o n t h i r d l y ，b a s e do nt h ei n t e g e rp r o g r a m sm o d e l ，w ed e s i g naa l g o r i t h m u s i n gt a b us e a r c ht os o l v et hs d v r p i nt h i st a b us e a r c ha l g o r i t h m ，t h e m o s ti m p o r t a n ti s s u ei st h ed e s i g no fn e i g h b o r h o o ds e a r c hm e t h o d ，w ec a l l i ta s1t one x c h a n g em e t h o d w ea l s od e s i g nas e l f a d a p tn e i g h b o r h o o d s e a r c hs t r a t e g yt oi m p o r v et h ee f f i c i e n c yo ft a b us e s r c h tl a s t t h i s t a b us e a r c ha l g o r i t h mi sv a l i d a t e db yat e s te x a m p i e f o u r t h l y ，w e1 0 0 kt h es d v r pi n t e g e rm o d e la sav r pw i t ho n eu n i td e m a n d c u s t o m e ra n dd e s i g nag e n e t i ca l g o r i t h mt os o l v et h i sv r p i nt h i sd e s i g n ， w ep u tf o r w o r das p e c i a lo p e r a t o rw h i c hi sc a l l e da sf e a s i b l eo p e r a t o r t os o l v et h et e n d e n c yo fo v e r s p l i t a tl a s t ，t h i sg e n e t i ca l g o r i t h mi s v a l i d a t e db yat e s te x a m p l e f i n a l l y ，w es u m m e r i z et h em a i na c h i e v e m e n t0 it h i sp a p e ra n dp o i n t 同济大学硕士学位论文 摘要 o u tt h ef u t u r er e s e a r c hd i r e c t i o n k e y w o r d s ：s d v r p ，v r p ，t a b us e a r c hh e u r i s t i c ，g e n e t i ca l g o r i t h m v 同济大学硕士学位论文 版权使用授权书 学位论文版权使用授权书 本人完全了解同济大学关于收集、保存、使用学位论文的规定，同意如下各项内容： 按照学校要求提交学位论文的印刷本和电子版本；学校有权保存学位论文的印刷本和 电子版，并采用影印、缩印、扫描、数字化或其它手段保存论文：学校有权提供目录 检索以及提供本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有关 部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前提下，学校可以适 当复制论文的都分或全部内容用于学术活动。 学位论文作者签名： 沪。6 年月i 日 衙轨 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 年月日年 月日 同济大学硕士学位论文 原创性声明 同济大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原刨性声明的法律责任 由本人承担。 i i 签名：蔫瓤 口口6 年弓月j日 同济大学硕士学位论文 第一章引言 1 1 研究的背景 第一章引言 当今的中国，全球化和信息化大潮翻涌而来，市场环境正在发生深刻的转变。 一方面，经济的全球化使企业获得了更为广阔和多元化的市场空间；另一方面， 信息化的发展使得顾客的需求日渐趋向多样化和个性化。面对这样的转变，企业 必须紧跟顾客的需求，通过多品种、少量化、短周期的产品生产和快速的产品配 送来满足顾客日益增长的服务要求。在这个过程中，物流作为连接企业与供应商、 企业与顾客的主要纽带，正在起到越来越重要的作用。此外，随着生产水平的提 高，企业从降低物质消耗、提高劳动生产率的过程中挖掘利润的空间正不断减小， 而现代物流作为企业降低经营成本、提高市场竞争力的重要途径，日益成为创造 利润的第三个重要源泉。 根据中国物流与采购联合会统计，代表我国物流社会需求规模的社会物流总 额2 0 0 4 年达到了3 8 4 万亿元“1 ，而1 9 9 5 年这一数字仅为1 0 2 万亿元0 1 ，增长 了3 7 9 倍，远高于2 3 3 倍的同期g d p 增长，2 0 0 5 年我国社会物流总额更预计 可增加到4 8 万亿元。这些数据表明，近十年来我国物流产业的增长十分迅猛， 而楚体国民经济的增长对物流的依赖也越来越强。另一方面，按照全国经济普查 调整后的统计数据计算，2 0 0 4 年全国物流费用占g o p 的比率为1 8 8 ，2 0 0 5 年 这个数据有望降为1 8 5 | j 6 ，但与欧美日等国家相比，这数字仍要高出5 8 个 百分点，这表明我国的物流成本水平与发达国家相比仍然偏高，效益不够理想， 因此如何提高物流管理水平，降低物流成本、提高物流运作的效率显得十分迫切。 从全国社会物流总费用构成情况来看，2 0 0 4 年，物流运输费用为1 6 5 5 8 亿元， 占社会物流总费用的5 6 9 ，比上年提高0 7 个百分点：包括仓储在内的物流保 管费用为8 4 6 7 亿元，占社会物流总费用的2 9 1 ，比上年下降0 4 个百分点： 物流管理费用为4 0 8 9 亿元，占社会物流总费用的1 4 ，比上年下降0 3 个百分 点。这些数据表明，运输费用是物流费用的最主要构成部分，且其所占比重仍在 不断增加。考察全国社会物流运输费用的构成，可以看到公路运输费用为7 5 9 9 亿元，比上年增长1 1 3 ，占运输总费用的4 5 9 ，基本相当于铁路、水路、航 空、管道等其它运输方式的费用总和。因此可以得出结论，提高运输效率尤其是 公路运输的效率是改善我国物流整体管理运作水平的重中之重。 提高公路运输效率的关键在于车辆运输的合理化。目前，随着我国经济的发 展，物流逐步趋向集约化、专门化和一体化，越来越多的企业都将物流作业外包 周济大学硕士学位论文 第一章引言 给专业的物流企业进行运作，如第三方物流企业。对于这些物流企业来说，如何 既满足众多客户对于服务水平的要求又能节约成本，是摆在管理者面前的主要问 题。对于大部分物流企业来说，车辆运输是其主要的服务手段，车辆运输管理的 好坏直接决定了服务水平的高低，同时车辆运输成本也是企业运作成本的重要组 成部分，在很大程度上决定了企业运作成本的高低。在这种情况下，合理安排行 车路线，实现运输车辆的优化调度是解决所面临问题的主要途径之一，因此，对 车辆路线问题进行深入地酽究具有相当的实际意义。 车辆路线问题( v e h i c l er o u t i n gp r o b l e m ，简称v r p ) 自1 9 5 9 年由d a n t i g 和r a m s e r 0 3 提出以来，一直是网络最优化问题中最基本的问题之一，由于其应用 的广泛性和经济上的重大价值，多年以来始终受到国内外学者的广泛关注。该问 题一般可以定义为：对一系列装货点和( 或) 卸货点，组织适当的行车路线，使 得车辆有序地通过它们，在满足一定的约束条件( 如货物的需求量、发送量、交 发货时间、车辆容量或载重限制、行驶里程限制、时间限制等) 下，达到一定的 目标( 如路程最短、费用最少、时间尽量少、使用车辆尽量少等) “1 。车辆路线 问题的实际应用包括配送中心配送、公共汽车路线制定、信件和报纸投递、工业 废品收集等等。近些年，来随蓑研究的深入，问题的形式又有进一步的发展，车 辆路线问题己不仅仅局限于车辆运输，在水运、航空、通讯、电力、工业管理、 计算机应用等领域也得到了一定的应用。 路线问题最早也是最著名的基本问题是旅行商问题( t r a v e l i n gs a l e s m a n p r o b l e m ，简称t s p ) ，它是运筹学、图论以及组合优化中的著名难题。t s p 问题 可以描述为：一个商人欲到n 个城市推销商品，如何选择一条路线使得商人从起 点出发，经过每个城市一次最后回到起点，而且要求所走过的路线最短。在这个 基础上，后来又发展出了多旅行商问题( m t s p ) ，也就是由m 个商人来共同完 成走遍n 个城市。而车辆路线问题从本质上讲也是一个m t s p ，它与m t s p 的 不同之处在于它为每个访问点都附加了一个货物需求量，同时每量车辆都设定了 载重量或容量限制，要求每条路线上的货物总量不能超出车辆的最大载重或最大 容积，这相当于为i i l t s p 增加了一个重要的约束条件，因此使得问题变得更加 复杂和困难。 从国内外以往的研究来看，车辆路线问题可以按不同的标准进行划分，其中 最基本的一种分类方式就是根据需求量和车辆载重量( 容积) 的关系划分为非满 载和满载两种，目前的研究主要集中针对非满载的情况。在这些非满载车辆路线 问题的研究中，大部分都基于一个前提条件，就是每个客户点的需求量仅能由一 辆车来完成，即需求不可拆分。但在实际应用中，有时会存在这样的情况，相当 部分或全部任务点的需求量都较大，在这种情况下，如果仍要求只能由一辆车来 2 同济大学硕士学位论文 第一章引言 完成必将造成车辆的空载率提高，从而浪费了车辆资源。举个简单的例子，有一 个车场和三个任务点，每个任务点有3 个箱子( 大小相同) ，而每辆车最多只能 装载5 个箱子，要求车辆从车场出发到各个任务点装货后返回车场，在需求不可 拆分的情况下必须使用3 辆车来完成任务，每辆车的空载率为4 0 ；如果需求 可以拆分，则只需要2 辆车就可以完成任务，车辆的平均空载率为l o ，效率 显著提高。一般认为，派出一辆车的固定费用远高于车辆行驶费用“1 ，因此，研 究需求可拆分的车辆路线问题具有一定的实际价值。 从国内外研究文献来看，需求可拆分的车辆路线问题最早由d r o r 和 t r u d e a u 。”在1 9 8 9 年提出，目前已经成为车辆路线问题中一个较新的分支。近年 来对需求可拆分的车辆路线问题的研究已经取得了一定的进展，但总体来说相关 的文献和成果仍较少，很值得进一步的深入研究。 在目前的研究中一般将不考虑时间限制的车辆路线安排问题称为车辆路线 问题( v r p ) ，而将考虑时间限制的车辆路线安排问题称为车辆调度问题( v e h i c l e s c h e d u l i n gp r o b l e m ，简称v s p ) ，但也有相当部分的研究者认为两者是一致的， 并不加以区分。本文由于在研究需求可拆分的车辆路线问题时未考虑时间限制， 因此将需求可拆分的车辆路线问题称为s d v r p ( s p l i td e l i v e r yv e h i c l er o u t i n g p r o b l e m 或v e h i c l er o u t i n gp r o b l e mw i t hs p l i td e m a n d ) 问题，而将v r p 和 v s p 统称为v r p 。 1 2 国内外研究现状 国外学术界对于s d v r p 的研究兴起与上世纪8 0 年代末。d r o r 和t r u d e a u “b “” 首先在其发表的文章中正式提出并定义了s d v r p ，指出了s d v r p 是一种约束松弛 的v r p ，即取消了在一般v r p 中对除车场外每个任务点的需求只能由一辆车完成 的约束，这一约束松弛可以使得车辆数量和路线总长都可以得到节约。同时，他 们对需求和车辆载重进行单元化，即设定每辆车的最大载重位k ，而每个任务点 的需求是小于k 的整数，在此基础上构造了s d v r p 的整数规划模型，也称为 k - s d v r p 模型，这一模型至今仍是研究s d v r p 的主要数学模型。 此后十几年中，对s d v r p 的研究可分为对s d v r p 本身特性的研究和对问题求 解的算法研究这两类。d r o r 、t r u d e a u “”“叮针对k - s d v r p 模型证明了当k 2 时， s d v r p 是一个n p h a r d 难题，并对解的特性进行了研究，证明了在一个s d v r p 优 化解的两条不同路线中最多只会存在一个的相同需求点，同时提出了k - s p l i t c y c l e 的概念，证明了一个s d v r p 优化解不会存在k - s p l i tc y c l e ，以上两条定 理被后来的研究者作为判断解是否优化和可行的个基本判据。b e l e n g u e r 、 同济大学硕士学位论文 第一章引言 m a r t i n e z 和m o t a ”在非满载范围内提出了降低了约束的s d v r p 整数规划模型， 在此基础上为s d v r p 构建了一个多面体模型，并从这一多面体模型出发对s d v r p 的多项特性进行了分析；a c h e t t i 和s p e r a n z a 田3 等人探讨了研究s d v r p 的意义和 s d v r p 应用的条件。指出了当平均需求大于l 2 并小于2 3 时，利用s d v r p 模型 进行求解所带来的解的优化程度最大，。 此外，一些研究者还对s d v r p 进行了扩充，如f r i z z e l l 和g i f f i n 。”将时 间限制引入了s d v r p ，构造了带时间窗的s d v r p ，简称s d v r p t w 问题，并给出了 求解s d v r p t w 问题的思路；l e e 、m a r i n a m l 等人提出了需求可拆分的多车场路线 问题，即m s d v r p ；n o w a k 和m a c i e k 将需求可拆分引入了装卸混合的v r p ，简称 s d p d p 问题。这些问题的提出丰富了s d v r p 的研究内容。 从检索到的文献来看，求解s d v r p 的算法主要集中在精确算法和启发式算法 上，算法需要解决的一个关键点是如何对需求进行合理优化的拆分。d r o r 首先 提出了一种解决s d v r p 的节约式插入算法，并对小规模问题进行了求解。 b e l e n g u e r 、m a r t i n e z 和m o t a 。2 1 在其所建立的s d v r p 立方体模型的基础上，设计 了一种以割平面法为主的混合算法来解决整数规划问题，并对有包含5 0 个需求 相对较小的点的问题进行了求解，取得较好的效果。l e e 、m a r i n a o ”等人结合动 态规划和最短路径接近法构造了一种三阶段启发式方法求解m - s d v r p 。f r i z z e l l 和g i f f i n 1 q l 1 t l 提出了一种两阶段启发式爬山算法来求解s d v r p t w 问题，第一阶 段通过d u c ( d y n a m i cu r g e n c yc l a s s i f i c a t i o n ) 方法构建路线，第二阶段利用 客户交换搜索来对初始解进行优化，在求解的过程中他们提出了用道路网格使问 题求解得到了一定的简化。s i e r k s m a 、t i j s s e n 和m u l l a s e r i l 、d r o r “”分别在 各自的文章中设计了利用列生成算法求解s d v r p ，但在求解前对需求拆分设定了 假设条件。f e d e r g r u e n 和s i m c h i l e v i “o 提出将同一个客户点的d 。个需求转化 成d ；个相互间距离为0 的客户，并在这个基础上进行算法框架的研究。 相对来说，利用亚启发式算法求解s d v r p 的研究还比较少。从目前文献检索 到的情况来看，a r c h e t t i 、h e r t z 、s p e r a n z a t i n l 及h o 和h a u g l a n d 3 在各自的 文章中提出利用禁忌搜索算法求解s d v r p 和s d v r p t w 的思路，其算法主要是一个 三阶段的启发式算法，第一阶段通过先安排路线再分组的算法产生初始解，这个 初始解中已经包含了需求的拆分，第二阶段对利用禁忌搜索算法对初始解进行优 化得到更高质量的解，第三阶段再对得到的解进行路线内的优化，求出最终解。 在他们的算法过程中，主要的需求拆分在第一阶段已经确定，在后面的优化过程 中只是将拆分的需求当做不同的需求点来对待，并进行部分拆分点的调整，由于 算法中的邻域搜索方法不够全面，因此所得到的解并不能保证其需求拆分是优化 合理的。在这些文献中，作者利用该种算法对s o l o m o n 的v r p 数据集进行了测试 4 同济大学硕士学位论文 第一章引言 计算，取得了满意的结果，但由于s o l o m o n 数据集中各个需求点的平均需求量很 小，因此这一三阶段启发式算法在求解平均需求量较大的s d v r p 时的效果仍不得 而知。 总体来讲，s d v r p 是v r p 的一个较新分支，目前对这一问题的研究还比较少， 特别是在利用亚启发式算法进行求解的方面。由于s d v r p 的复杂性决定了利用精 确算法和传统的启发式算法计算很难取得满意的解，而现代亚启发式算法的特点 又比较符合求解s d v r p 的要求，因此有必要在这方面进一步深入探讨。 1 3 论文的研究内容 从文献检索的结果来看，与v r p 的其它分支相比，目前对s d v r p 的研究还比 较少，尤其在利用现代亚启发式算法解决s d v r p 方面还比较少有人涉及，因此本 文的主要研究在于尝试利用禁忌搜索算法和遗传算法来求解s d v r p ，具体研究内 容如下： 第一部分：了解s d v r p 和v r p 的研究现状，利用相关文献进行文献综述。 第二部分：对s d v r p 进行描述分析，建立相应的数学模型，对在车辆路线安 排中采用s d v r p 模型进行求解的意义和最佳的应用条件进行一定的分析。 第三部分：分别设计求解s d v r p 的禁忌搜索算法和遗传算法，对两种算法的 具体实现细节进行深入研究，通过编程来实现算法，并进行算例验证。 第四部分：通过案例对s d v r p 的实践应用进行了介绍。 其中，第三部分是本文研究的重点。 1 4 论文的结构安排 本文的各章节内容安排如下： 第一章，引言。这一章首先介绍本文的研究背景，通过文献综述对s d v r p 的 研究现状进行分析，然后给出论文的研究内容和结构安排。 第二章，物流车辆路线问题的概述。这一章主要从v r p 的基本定义和描述、 v r p 的分类和v r p 的算法这三方面对v r p 进行了概述。 第三章，需求可拆分车辆路线问题的建模与分析。在这一章中主要对s d v r p 进行了描述和数学建模，对s d v r p 解的特性进行了分折，并简单分析了适合s d v r p 应用的范围。 第四章，利用禁忌搜索算法求解需求可拆分的车辆路线问题。在这一章中根 据s d v r p 的特点对禁忌搜索算法进行了详细的设计，主要的设计集中在邻域搜索 同济大学硕士学位论文 第一章引言 计算，取得了满意的结果，但由于s o l o l f l o f l 数据集中各个需求点的平均需求量很 小，因此这一三阶段启发式算法在求解平均需求量较大的s d v r p 时的效果仍不得 而知。 总体来讲，s d v r p 是v r p 的一个较新分支，目前对这一问题的研究还比较少， 特别是在利用亚启发式算法进行求解的方面。由于s i ) y r p 的复杂性决定了利用精 确算法和传统的启发式算法计算很难取得满意的解，而现代亚启发式算法的特点 又比较符合求解s d v r p 的要求，圆此有必要在这方面进一步深入探讨。 1 3 论文的研究内容 从文献检索的结果来看，与v r p 的其它分支相比，目前对s d v r p 的研究还比 较少，尤其在利用现代亚启发式算法解决s d v r p 方面还比较少有人涉及，因此本 文的主要研究在于尝试利用禁忌搜索算法和遗传算法来求解s d v r p ，具体研究虎 容如下： 第一部分：了解s d v r p 和v r p 的研究现状，利用相关文献进行文献综述。 第二部分：对s d v r p 进行描述分析，建立相应的数学模型，对在车辆路线安 排中采用s d v r p 模型进行求解的意义和最佳的应用条件进行一定的分析。 第三部分；分别设计求解s d v r p 的禁忌搜索算法和遗传算法，对两种算法的 具体实现细节进行深入研究，通过编程来实现算法，井进行算例验证。 第四部分：通过案例对s d v r p 的实践应用进行了介绍。 其中，第三部分是本文研究的重点。 1 4 论文的结构安排 本文的各章节内容安捧如下： 第一章。g f 言。这一章首先介绍本文的研究背景，通过文献综述对s d v r p 的 研究现状进行分析，然后给出论文的研究内容和结构安排。 第二章，物流车辆路线问题的概述。这一章主要从v r p 的基本定义和描述、 v r p 的分类和v r p 的算法这三方面对v r p 进行了概述。 第三章，需求可拆分车辆路线问题的建模与分析。在这一章中主要对s d v r p 进行了描述和数学建模，对s d v r p 解的特性进行了分析，并简单分析了适合s d v r p 应用的范围。 第四章，利用禁忌搜索算法求解需求可拆分的车辆路线问题。在这一章中根 据s d v r p 的特点对禁忌搜索算法进行了详细的设计，主要的设计集中在邻域搜索 据s d v r p 的特点对禁忌搜索算法进行了详细的设计，主要的设计集中在邻域控索 同济大学硕士学位论文 第一章引言 的方法和领域搜索范围的自适应策略上，并对算法进行了算例验证。 第五章，利用遗传算法求解需求可拆分的车辆路线问题。在这一章中提出了 在s d v r p 整数规划模型的基础上将客户需求拆分为单位需求客户，然后利用遗传 算法进行求解，对遗传算法的各个要素都进行了设计，并引入了可行化算子来保 证算法的效率，最后用算例对算法进行了验证。 第六章，案例分析。 第七章，总结与展望。 本文的全文结构如图i - i 所示。 图卜1 论文结构示意图 6 同济大学硕士学位论文 第二章物流车辆路线问题的概述 第二章物流车辆路线问题的概述 物流车辆路线问题自提出以来一直受到数学、管理学、计算机应用等众多学 科的研究者和运输管理者的极大重视，已经成为运筹学与组合优化领域的前沿与 研究热点。通过各学科学者丈量的理论研究和实验分析，目前物流车辆路线问题 的研究已经取得了很大进展，主要表现在研究的范围不断加宽、和实际应用的结 合不断加深、求解的新算法和算法组合不断涌现。 需求可拆分的物流车辆路线问题是物流车辆路线问题的一个较新的研究分 支，在对其进行研究时借鉴物流车辆路线问题的一些理论和算法是必不可少的， 因此在展开研究以前对物流车辆路线问题的研究现状有一个全面的认识是非常 重要的。 2 1v r p 基本概述 2 1 iv r p 的描述 车辆路线安排问题最早由d a n t i g 和r a m s e r “在1 9 5 9 年提出，其应用背景在 物流领域处处可见，比如零售业的门店配送、邮政快递行业的快件投取等等，对 于从事这些业务的企业来说，合理解决车辆路线安排问题是企业面临的最基本的 管理运作问题。 物流车辆路线问题可以直观描述为：在一个存在供求关系的系统中，有若干 台车辆、若干个物流中心和客户，要求合理安排车辆的行车路线和出行时间，从 而在给定的条件下，把客户需求的货物从物流中心送到客户处，或( 并) 把客户 供应的货物从客户处取到物流中心，在这过程中追求成本的最小化。 也可以利用网络模型对v r p 进行如下描述：设g = ( v ，e ，a ) 是一个连通的混合 网络，v 是顶点集( 表示物流中心、客户、停车场等) ，e 和a 分别为无向的边集 和有向的弧集，e 中的边和a 中的弧均被赋权( 可以表示配送的距离、时间或费 用) ，v ，e j ，a 分别为v ，e ，a 的子集，求满足约束条件( 包括客户的货物需求 或供应数量约束、需求或供应时间约束、配邀车辆一次配送的最大行驶距离约束、 车辆的最大载重量约束等) 并包含v ，e ，a ，的一些巡回路线，使目标函数取得 优化，目标函数可以取路线总里程最短、车辆总吨位公里数最少、运输总费用最 低、运输总时间最少、使用的车辆数最少、车辆的满载率最高等。 从文献检索的结果来看，自提出以来v r p 的研究主要按两个方向进行，一个 同济大学硕士学位论文 第二章物流车辆路线问题的概述 方向是根据实际应用中的情况，为v r p 设定不同的约束条件和优化目标，从而衍 生出许多特定的v r p ，并建立模型：另一个方向是运用不同的算法来解决v r p a 2 1 2物流车辆路线问题的构成要素 构成物流车辆路线问题主要要素包括：货物、车辆、物流中心、客户、运输 网络、约束条件和目标函数等，具体说明如下 1 ) 货物。货物是车辆运输的对象，也是构成需求的主要因素。可将每个客户需 求( 或供应) 的货物看成一批货物。每批货物都包括品名、包装、重量、体积、 要求送到( 或取走) 的时间和地点、能否分批配送等属性。货物的品名和包装， 是选用配送车辆的类型以及决定该批货物能否与其它货物装在同一车辆内 的依据。 2 ) 车辆。车辆是货物的运载工具。其主要属性包括：车辆的类型、装载量、一 次配送的最大行驶距离、配送前的停放位置及完成任务后的停放位置等。 3 ) 物流中心。也称为物流基地、物流据点，主要是指进行集货、分货、配货、 配装、送货等物流作业的中心、仓库、车站、港口等等。在具体的v r p 中， 物流中心的数量可以是一个或一个以上；物流中心的位置可以是确定的，也 可以是不确定的；对于某个物流中心，其供应的货物可能有一种，也可能有 多种；供应的货物数量可能能够满足全部客户的需求，也可能仅能满足部分 客户的需求。 4 ) 客户。也称为用户，客户的属性包括需求( 或供应) 货物的数量、需求( 或供 应) 货物的时间、需求( 或供应) 货物的次数及对服务的要求等等。在v r p 中， 客户是最主要的因素，客户的地理位置决定了取货点的位置，客户的需求是 v r p 中约束条件的主要来源。 5 ) 运输网络。运输网络是由顶点( 指物流中心、客户、停车场) 、无向边和有向 弧组成的。边、弧的属性包括方向、权值和交通流量限制等。 6 ) 约束条件。物流v r p 应满足的约束条件主要包括：满足所有客户对货物品 种、规格、数量的要求；满足客户对货物发到时间范围的要求；在允许 通行的时间进行配送( 如有时规定白天不能通行货车等) ；车辆在运输过程 中的实际载货量不得超过车辆的最大允许装载量，或货物的体积总和不能超 过车辆的容积。在物流中心现有运力范围内。 7 ) 目标函数。对物流配送车辆调度问题，可以只选用个目标，也可以选用多 个目标。经常选用的目标函数主要有： 运输总里程最短。运输里程与车辆的耗油量、磨损程度以及司机疲劳 程度等直接相关，由于运输里程计算简便，它是确定路线时用得最多的目标。 同济大学硕士学位论文 第二章物流车辆路线问题的概述 配送车辆的吨位公里数最少。该目标将运输距离与车辆的载重量结合 起来考虑，即以所有配送车辆的吨位数( 最大载重吨) 与其行驶距离的乘积的 总和最少为目标。 综合费用最低。综合费用最接近企业的实际管理，一般来说综合费用 包括：车辆维护和行驶费用、车队管理费用、装卸费用、人员工资费用等。 准时性最高。由于客户对交货时间有较严格的要求，为提高服务水平， 有时需要将准时性最高作为确定车辆路线的耳标。 运力利用最合理。该目标要求使用的较少的车辆完成配送任务，并使 车辆的满载率最高，以充分利用车辆的装载能力。 劳动消耗最低。即以司机人数最少、司机工作时间最短为目标。 2 。2v r p 的分类 针对众多特定的v r p ，b o d i n 刚、s a v e l s b e r g h ”1 、t o t h 和v i g o 。1 等许多学者 对其从不同角度按不同的标准进行了分类，具体总结如图2 一l 所示。 表卜1v r p 分类情况表 类方法分类后的问题 按车辆载货情况分满载问题和非满载问题 有时间窗的闯题和无时限的问题。其中有时 按时间限制情况分间窗的问题还可以分为软时问窗、硬时间窗 以及混合时阃窗问题 按车场( d e p o t ) 的数量分单车场和多车场问题 按取送货任务特点分纯装( 或纯卸) 问题和装卸混合问题 按车辆类型分 单车型问题和多车型问题 按需求或订单是否可拆分需求可拆分问题和需求不可拆分问题 按需求是否确定分静态问题和动态问题( 可临时插单问题) 按订单是否有优先级分有序访问问题和无序访问问题 按是否有道路条件限制有道路条件限制和无道路条件限制问题 需要指出的是这些分类问题并不是孤立的，具体到每个v r p ，一般都是以上 多个分类问题的组合，正因为如此，再结合不同的算法，才使得v r p 的研究呈现 出酉花齐放的状况。近1 5 年来，研究最热门的闯题当属有时间窗的v r p ( v e h i c l e 9 同济大学硕士学位论文 第二章物流车辆路线问题的概述 r 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 ) ，s o l o m o n 啪等众多学者n o m l 。 都对v r p t w 进入了深入的研究，并创造性地引入了多种算法，这也为解决其它 v r p ( 包括s d v r p ) 提供了很好的借鉴。 2 3v r p 的求解算法 目前解决v r p 的算法主要包括三大类：精确算法、启发式算法和亚启发式算 法。此外，近年来国内外还出现了利用约束规划( c o n s t r a i n tp r o g r a m m i n g ，简称 c p ) 技术求解v r p “3 1 的新方法。 2 3 1精确算法 精确算法是指可以求出问题的最优化解的算法。主要包括：分枝界定法、割 平面法、网络流算法、动态规划法、集分解和列生成法等等。由于v r p 是n p h a r d 难题，存在高效精确算法的可能性不大，精确算法往往只能解决一部分小 规模的v r p 。 2 3 1 1 动态规划算法 动态规划算法( d y n a m i cp r o g r a m m i n ga p p r o a c h ) 是一种常用的运筹学方法， 它适于解决这样的问题：某个大问题可以划分为几个阶段，每个阶段形成一个子 问题，各个阶段是相互联系的，每个阶段都要做出决策，并且某个阶段的决策， 常影响下一阶段的决策，从而影响整体决策。在动态规划求解过程中，作为整个 过程的最优策略具有这样的性质：无论过去的状态和决策如何，对其决策所形成 的状态而言。余下的诸决策必须构成最优策略，这是动态规划的最优化原理。利 用这个原理可以把多阶段决策的求解过程看成是一个连续的递推过程，由后向前 逐步推算。在求解时，各状态前强的状态和决策，对其后面的子问题而言，只不 过相当于其初始条件而己，并不影响后面过程的最优策略。 用动态规划法求解v r p 的思路如下：用0 表示物流中心，i 表示客户 ( f _ 1 , 2 ，3 ，工) ；设s = 1 , 2 ，3 ，上) 表示所有客户的集合；若用s ，s2 7 - ”，s 。分别表示 第1 ，2 ，k 条配送路线上的客户的集合，k 为所需的车辆数，则有： s = s iu 岛u u s k ，s ，n s k = 妒，- ，k ，工七= 1 , 2 ，3 ，足。 设从0 出发，用最合适的路线向量( - ，21 ，2 ，3 ，。，足) 送货再回到0 的距离为 n ，一、 c “婶，则车辆路线问题的目标是使总运输距离y d ( s ，) 最小 1 0 同济大学硕士学位论文 第二章物流车辆路线问题的概述 用f ( u ) 表示使用第k 辆车，对部分客户的集合u 送货时的最小运输距离。 由最优化原理可得下面的递推公式： ，11 、 f ( u ) = 嬲( 五t ( u u + ) + d ( v + ) 、117 上式中，最合适的部分集合u 是使总送货距离为最小的s 的最合适部分 s l ，s 2 ，s a ，s i 。 从理论上讲，利用动态规划法可以求得v r p 的精确最优