（管理科学与工程专业论文）带时间窗的车辆路线问题研究.pdf

摘要 摘要 车辆路径问题( 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 的研究中具有举足轻重的作 用。本文在v r p 的既有研究文献基础上，对两大类型的v r p 的时间窗问题进行 了深入分析，针对具体的每一种v r p 的问题本文都建立了模型并设计了算法。 主要内容如下： 本文首先大量分析了研究v r p 问题的众多文献，主要针对有时问窗问题的 研究，总结出以往研究存在的薄弱环节。从求解方法上比较系统的分析了目前 常用的算法，对各类算法的优缺点进行了总结。以上述分析为基础并结合实际 情况，确立了本文的研究内容和研究方法。 对于带有时间窗的非满载问题，本文把研究范围锁定在多配送中心和软时 间窗限制。通过分析问题结构，设计了步骤清晰的求解策略，并开发出启发式 算法和亚启发式算法相结合的混合启发式算法，能够快速和高效的求解本类问 题。最后进行了算例验证。 有时间窗的满载v r p 问题是一个薄弱的研究领域。本文从实际角度出发， 扩展了理论模型，并引入了动态时间窗的概念，建立了一个考虑动态时间窗的 满载模型。通过分析满载问题与非满载问题在结构上的差异，本文设计了动态 构造的启发式算法，并通过参数控制，可很快求出带动态时间窗满载模型的满 意解，并给出了一个完整算例。在一定程度上扩展了满载v r p 的研究范围。 本文的研究有一定的理论创新和实际价值。 关键字：有时间窗的车辆路径问题，启发式算法，组合优化，非满载，满载 a b s 豫a c t a b s t r a c t v e h i d er o u t t a gp m b l e mb e l o n g st ot h er e a l m ：o fl o g i s t i c sr e s e a r c ha n d c o n t r i b u t e sm o r et ol o w i n gc o m p a n yo p e r a t i n gc o s t sa n di m p r o v i n gt h es e r v i c el e v e l d t i et ov a r i o u sv i e w , v r p sc a nb ec l a s s i f i e dt o t so ft y p e s a c t u a l l yr e s e a r c ho t iv e r y k h a do fv r p sh a sb e e ni n c r e a s i n gp r o m i n e n t l yi nr e c e n ty e a r s c o n s i d e r i n gt h e p r a c t i c a lw o r t h ，e s p e c i a l l yv i e w i n gt h em a r k c te n v i r o n m e n t so fa c h i e v i n gt h ec l i e n t s e r v i c el e v e lp e r f o r m a n c e t i m ew i n d o w si sv e r yi m p o r t a n tt ot h er e s e a r c ho fv r p 如 t h i sp a p e r , w ep u tf o r w a r dd e e pa n a l y s i so nt w om a i nk i n d so fv r p sw i t ht i m e w i n d o w sa n ds e tu p o p t i m i z a t i o nm o d e l ；e x p l o i te f f e c t i v ea l g o r i t h ma i m i n g t oe v e r y k i n do ft h e m 1 1 l l i sp a p e ri sa sf o l l o w s ： f i r s t l y , w ea n a l y z et o t so fa r t i e l e sr e l a t e dt ov r p sr e s e a r c ha n de s p e c i a l l y c o n s i d e r i n gt h es t u d yo ft i m ew i n d o w sd r a ws o m ec o n c t u s i o n so nt h ep a s tr e s e a r c h 撕 a d d i t i o n ，w es y s t e m i cs t u d yt h ec o n l m o na l g o r i t h m sa tp r e s e n ta b o u ts o l v i n gm e t h o d s a n ds u m m a r i z et h ee x c e l l e n c ea n dd e f e c to fe a c ha l g o r i t h m b a s e do l lt h ea b o v e a n a l y s i sa n dp r a c t i c a lf a c t o r sw ed e t e r m i n et h ec o n t e n ta n dm e t h o d st ob cr e s e a r c h e d i n t h i s p a p e r 、 s e c o n d l y , f o rt h en o n 艇1 t o a dv r p sw i t h ：t i m ew i n d o w sc o n s t r a i n e d ，w ef o c u s t h er e s e a r c hw o r ko nt h er e a l mo fm u l t id e p o t s ( d i s p a t c h e r 戚n t e r s la a ds o f tt i m e w i n d o w sc o n s t r a i n e d b a s e do na n a l y s i n gt h es t r u c t u r eo ft h i sp r o b l e m ，w ed e s i g nt h e c l e a rs t e p p e ds o l v i n gt a c t i c s a sw e l lam i x e dh e u r i s t i c si se x p l o i t e dw h i c hc a ns o l y e t h i sp r o b l e mr a p i d l ya n de f f e e t i v e l y a tl a s tw eg i v e8t e s te x a m p i et ov a l i d a t ei t t h i r d l y , a sw ea l lk n o w , f u l l 1 0 a dv r p sw i t ht i m ew i n d o w sc o n s t r a i n e da r e c o n s i d e r e dt h el e s sr e s e a r c h e dr e a l m w ee x t e n dt h et 1 1 e o r e t i c a lm o d e l sf r o mt h e p r a c t i c a lv i e w , i m p o r tan e wj d e ao fd y n a m i ct i m ew i n d o w sa n dc o n s t r u c taf u l l 一l o a d m o d e lw i t hd y n a m i ct i m ew i n d o w s v i aa n a l y i n gt h ed i f i e f e n c eb e t w e e nt h ef u l l 一l o a d a n dn o nf u l t 1 0 a d w ed e s i g nad y n a m i cc o n s t r u c t i n gh e u r i s t i c s t h i sh e u r i s t i c sc a n q u i c k l ys o l v et h ef u u - l o a dm o d e lw i t hd y n a m i ct i m ew i n d o w sc o n s t r a i n e db y p a r a m e t e r sa d a s t i te x t e n dt h er e s e a r c hr a n g eo ff u l l - l o a dv r p si nac e r t a i ne x t e n t t h i sp a p e r sr e s e a r c ht a k e sal i t t l e 也e o r e t i c a li n n o v a t i o na n dp r a c t i c a lv a l u e k e y w o r d s ：t i m ew i n d o w sc o n s t r a i n e dv r p s ，h e u r i s t i c s ，c o m b i n a t o r i a lo p t i m i z a t i o n ， n o nf u l l l o a d ，f u l l l o a d l l 学位论文版权使用授权书 本人完全了解同济大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：元象嗨 2 。年f 月日 原刨性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 签名：建靳垮 1 。6 年月啦日 第1 章引言 1 1 研究背景 第1 章引言 当前，现代物流已被公认为是企业在降低物质消耗、提高劳动生产率以外 创造利润的第三个重要源泉，也是企业降低生产经营成本，提高产品市场竞争 力的重要途径。据专家测算，现代物流成本约占企业经营成本的3 0 5 0 ， 当一个有效的物流系统与企业主要商业系统集成之后，可使仓储量降低5 0 ，准 时交货率提高4 0 ，营业收入增加1 0 以上。1 。在经济发达国家和一些经济水平 较高的发展中国家，现代物流水平已成为影响企业竞争力的关键因素。 与发达国家相比，我国的物流产业效率较低。根据全国第三产业普查资料， 我国交通运输、仓储、代理和批发等行业的成本费用之和占国民生产总值的比 重为1 5 左右，如果考虑其它相关流通环节的费用和流通过程中的物流损失，则 全社会物流费用支出约占国民生产总值的2 0 以上。而美国的全社会物流费用支 出仅占其国民生产总值的1 0 左右。在物流系统中，物流配送是一个重要环节， 它是指按客户( 包括零售商店、用户等) 的订货要求( 包括在货物种类、数量和时 间等方面的要求) ，在物流中心( 也称物流基地、物流据点，包括配送中心、仓 库、车站、港口等) 进行分货、配货工作，并将配好的货物及时送交收货人的物 流活动。物流配送过程主要包括以下作业环节：从生产工厂进货或运达并集结的 集货作业：根据各个客户的不同需求，在物流中心将所需要的货物挑选出来的分 货和配货作业：考虑配送货物的重量和体积，充分利用车辆的载重和容积的货物 配装作业：合理确定车辆配送路线并及时送货的作业。可见，物流配送是一种集 集货、分货、配货、配装、送货等多种功能为一体的物资流通方式。 在物流配送业务中，配送车辆调度问题的涉及面较广，需要考虑的因素较 多，对配送企业提高服务质量、降低物流成本、增加经济效益的影响也较大。 鉴于此，本文将着重研究带时间约束的物流配送车辆路径问题。因为随着市场 第1 章引言 经济条件下对配送服务水平要求的提高，时间因素在配送过程中越发显得重要。 在路径问题的研究中，最著名同时也是最原始的运输路径安排问题是旅行 商问题( t s p ) 。t s p 的描述如下。1 ：一个商人欲到i q 个城市推销商品，如何选择一 条道路使得商人从起点出发，每个城市走一遍后再回到起点所走的路径最短? 运 输问题是t s p 最自然的应用。如在校区内如何安排狡车路线接送学生的问题， 货舱中栈式起重机的路线安排，收部包的卡车行车路线安排等。t s p 在制造业中 也扮演着重要角色，如如何安摊枧器在一块电路扳或其他物体上钻孔等。 扩t s p 是t s p 妁扩展，它描述豹是这样一个河题。1 ：穰个商入要一起将n 个 城市走完，每个城市需要丑只能由一个商人来拜访一次，每个商入必须从出发 点出发。最后再返回出发点所在她。目的是确定m 条路径，捷所有商人走过的 总路程最短。剐才提副的如何安摊校车路线接送学生的阀题。如果学生住的地 方比较分散，则只派一辆校车去接送学生。不仅校车要绕报多路去接住在不同 地方的学生。非常耗时，丽且学生韵正常作息时间也会受到影响，有些学生为 了搭车必须很早起床。因此，派几辆校车同时去接住在不同地方的学生是比 较合实际舶。 、车辆路径问题( v e h i c l er o u t i n gp r o b l e m ，v p r ) 也是一个m - t s p ，只不过每 一个城市谢加了一个对货物的需求量，每一辆汽车都有一定的载重量( 不必都相 同) 。不过v r p 还是有别于m - t s p 的，m t s p 实质上只是由城市豹地理位置决定 的，而v r p 却不能，因为需求的加入构成了问题的一个约束条件。后来有人把 这种v r p 严格定义为c 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 gp r o b l e m ) ，因为每 辆汽车( 即每条路径) 装豹货物总量不能超过汽车的最大负载。 从以上分析可以看出，v r p 是比t s p 、和t s p 都要复杂韵一类运输路径安排 问题，同时也是更符合实际情况的一类模型。由于汽车都是有最大负载的，因 此前面提到的校车接送学生路线安排问题更切实际的模型应该是v r p ，这也进一 步说明了v r p 在现实生活中的实用性。再考虑到时间约束对整个模型的影响， 便构成了本文所研究课题的研究背景。 第1 章引言 1 _ 2 问题的提出 由上文分析可见，运输是物流系统中一个重要的部分，而对运输的研究中， 很大一部分是指对v r p 及其衍生问题的研究。根据不吲标准，v r p 可分为很多类 型。从现实约束来看，时间窗是一类非常重要的约束，因为作业时间直接影响 到对客户的服务水平。本文把有时间窗的v r p 称为v r p t w 。近年来，v r p t w 问题 的研究也比较多，但也有一定的局限性。一方面，从任务量和车辆载重上来讲， v r p 问题可根据单点任务量大小与载重量关系分为非满载和满载两种。大部分的 v r p 研究都集中于非满载的情况，对于满载的v r p ，研究相对要少的多，尤其是 带有时问窗的v r p f l ，研究更为少见。另一方面，从实际角度出发，随着企业规 模的扩大和市场经济以及协同合作的发展，车辆往往来源于不同的车场或配送 中心，因此仅仅研究单一车场的v r p 问题就不再适用了。所以，有时间窗( 尤其 是软时间窗) 的多车场( 多配送中心) 的非满载v r p 和满载v r p 是两类重要且有 待深入研究的回题。本文邵以这两类问题为研究对象。在相应的章节中，分别 以m d v r p s t w 和m d v r p f l s 、w 命名这两类问题。 1 3 研究文献综述 国外相关领域研究者对车辆路径问题的研究始于5 0 年代未，在理论研究和 实际应用两方面都已取得了非常显著的成果。随着研究的深八发展，如何使研 究的理论模型更贴切现实中的运输规划问题开始成为研究者们关注的焦点。由 于带时间窗的车辆路径问题在竞争激烈的当今社会具有十分现实的意义，近 1 0 - 1 5 年出现了许多关于带时间窗的车辆路径问题的研究文献。 b o d i n 等人( 1 9 8 3 ) 对一般的车辆路线规划问题作了详尽的综述“，s o l o m o n 和d e s l 、o s i e z ，s 等人( 1 9 8 7 ) 考虑将时间约束加入到一般的车辆路径问题中，最 甲对带时间约束的车辆路径问题进行了研究”1 ，d e s r o c h e r s ( 1 9 8 8 ) 进一步对 用于求解带耐问窗的车辆路径问题的各种优化方法做了简明的总结概括”。由于 用于求解带时问窗的车辆路径问题的各种优化方法做了简明的总结概括。由于 第1 章引言 1 - 2 问题的提出 由上文分析可见，运输是物流系统中一个重要的部分，而对运输的研究中， 很大一部分是指对v r p 及其衍生问题的研究。根据不同标准，v r p 可分为很多类 型。从现实约束来看，时间窗是一类非常重要的约束，因为作业时间直接影响 到对客户的服务水平。本文把有时间窗的v r p 称为v r p t w 。近年来，v r p t w 问题 的研究也比较多，但也有一定的局限性。一方面，从任务量和车辆载重上来讲， v r p 问题可根据单点任务量大小与载重量关系分为非满载和满载两种。大部分的 v r p 研究都集中于非满载的情况，对于满载的v r p ，研究相对要少的多，尤其是 带有时间窗的v r p f l ，研究更为少见。另一方面，从实际角度出发，随着企业规 模的扩大和市场经济以及协同合作的发展，车辆往往来源于不同的车场或配送 中心，因此仅仅研究单一车场的v r p 问题就不再适用了。所以，有时间窗( 尤其 是软时间窗) 的多车场( 多配送中心) 的非满载v r p 和满载v r p 是两类重要且有 待深入研究的问题。本文即以这两类问题为研究对象。在相应的章节中，分别 以m d v r p s t w 和m d v r p f l s t w 命名这两类问题。 1 3 研究文献综述 国外相关领域研究者对车辆路径问题的研究始于5 0 年代末，在理论研究和 实际应用两方面都已取得了非常显著的成果。随着研究的深入发展，如何使研 究的理论模型更贴切现实中的运输规划问题开始成为研究者们关注的焦点。由 于带时间窗的车辆路径问题在竞争激烈的当今社会具有十分现实的意义，近 如一1 5 年出现了许多关于带时间窗的车辆路径问题的研究文献。 b o d i n 等人( 1 9 8 3 ) 对一般的车辆路线规划问题作了详尽的综述“。，s o l o m o n 和d e s r o s i e r s 等人( 1 9 8 7 ) 考虑将时间约束加入到一般的车辆路径问题中，最 早对带时间约束的车辆路径问题进行了研究“，d e s r o c h e r s ( 1 9 8 8 ) 进一步对 用于求解带时间窗的车辆路径问题的各种优化方法做了简明的总结概括。由于 第1 章引言 时间因素在实际运输规划阀题中是很常见、很重要的因素之一，上世纪9 0 年代 以后带时问窗的车辆路径问题吸引了运筹学、人工智能领域学者的关注。 罚简单的车辆路径问题一样，带时间窗的车辆路径问题的求解也主要是基 于精确算法和启发式方法两大类方法。k o e n 嘲、d e s r o c h e r s ”3 、f i s h e r 嘲、k o h “” 等人将各种精确算法如分支定界算法等应用于v r i y f w 的求解中，成功的解决了 理论和现实中豹一些规模较小的v r p t w 。由于v r p t w 是n p h a r d 的睡题，这意 味着所有能精确求解这类问题的算法在最坏的情况下需要指数级韵时间。采用 精确算法虽然可以得到最优解，但需要耗费大量计算量和计算时河，只能用于 解决有限规模的闵题，不适用于现实中的大规模运输问题，过去的研究结果也 证明了这一点”3 。采用精确算法求解v r 阿并的另一个缺点是：精确算法往往是 针对县体的问题设计的，不具备普适性，因此精确算法虽然可以成功求得一个 闯题韵最优解，但对于同样嗣题舫其他情况可能就无法正确求解“。s o l o m o n ( 1 9 8 7 ) 最早将用于求解简攀锵韵路径构造启发式算法扩展应用于v r p t w 的 求解中，他韵研究结果表明这些启发式方法求解v r i y i w 问题鼢复杂度为0 ( n ) ，n 为有待访问的客户的数目。却可在多项式时间内得到问题的近似最优解，说明 了寤发式方法求解v r p t i ；f 的可行性和有效性。s o l o m o n 的研究为以后启发式方法 在带约束的车辆路径问题中的应用奠定了理论基础“3 。其他用于构建生成v r p t w 解的启发式方法还有p o t v i n 的并行插入法1 、k o s k o s i d i s 的一般分配法“”以及 k o n t o r a v i d s 韵贪心随机自适应搜索法。”等。在上面提到的方法柏基础上，许多 研究者提出了改进解的方法应用于v r i y f w 中，通过初始解中边的交换和节点的 交换来改进初始解的性能“”n 3 。由于启发式方法求解大规模复杂问题的优 越性，国内许多研究者都致力于设计新的高效省时的启发式方法来构建或改进 v r p t w 的解。近几年来禁忌搜索法、模拟退火及遗传算法等亚启发式方法陆续被 引入到v r p t w 的求解中，取得了显著优于传统启发式方法的结果。”3 。由于这 些启发式方法具有强大的全局优化性能和通用性，因此研究遗传算法等启发式 方法求解v r p t w 已成为目前研究者们关注的一个新领域。 4 第1 章引言 我国对货担郎问题的理论研究较多“”“”。”。“，但对车辆路径问题的研究在 9 0 年代以后才逐渐兴起，比国外相对落后。随着客户物质需求的多样性和不规 则性以及经济全球化趋势的发展，运输规划的重要性日益显著，近年来我国理 论界逐渐开始关注车辆路径问题的解决方法，已取得了较为显著的成果 。”。”。4 蚴1 。但总体来说我国目前对车辆路径问题的理论研究仍相对匮乏，有待 进一步的研究。 尤其值得一提的是v r p 中的满载类型，从国内外研究文献来看，目前进行 的研究相对较少。本文作者在国内外大型的学术数据库中，如e l s e v i e r 、e b s c o 、 s p r i n g e rl i n k 、b l a c k w c l l 、万方等，以满载或f u l ll o a d ( f u l lt r u c k l o a d ) 对文献标题 和关键字进行搜索，只有少数几篇与满载车辆调度模型及算法相关的文献。文 2 8 1 给出了一个基于放松约束条件下的网络流算法，但仅限于单车场问题；文 2 9 1 把其扩展成多车场问题；文【3 0 】建立了整数规划模型，并考虑软时间窗约束，设 计了一个分支定界的算法，但求解的规模受到限制，文 3 1 】引进了多货物品种和 多车型约束，建立了一个0 - 1 规划模型，并给出了基于贪婪算法和后悔成本的 混合算法：就带有静态时间窗的满载问题，文 3 2 、3 3 1 分别设计了禁忌搜索算法 和节约法进行求解。文 3 4 j j 给出了在调度解的基础上通过逐步修正获得可行解 的启发式方法，但应用于多车型问题时效果不佳。一般来说，满载运输的特点 是作业量大，则装载能力会对调度解产生影响，如果不考虑每一项任务的各车 次间由于装载能力产生的时闻窗的次序关系，所求解的可行性会明显降低。 1 4 研究方法 目前，车辆优化调度问题的求解方法非常丰富，g o l d e n ( 1 9 8 4 ) ， l a p o r t e ( 1 9 9 2 ) ，l a p o r t e 和o s m a n ( 1 9 9 5 ) 【1 5 【16 】等许多学者都对求解方法的分类 进行了研究，认为究其实质，基本上可以分为三类。 ( 1 ) 精确算法指可求出其最优解的算法，主要包括分支定界法( b r a n c ha n d b o u n d a p p r o a c h ) 、割平面法( c u t t i n gp l a n e s a p p r o a c h ) 、网络流算 ：去( n e t w o r kf l o w 第1 章引言 a p p r o a c h ) 、动态规划方法( d y n a m i cp r o g r a m m i n g a p p r o a c h ) 等。精确算法虽然能 够得出阀题的最优解，但是其计算量一般随着闯题规模得增大呈指数增长，因 此在实际中应用的范围有限。 ( 2 ) 由于该类问题的强n p 性，高效的精确算法存在的可能性不大，所以寻找 近似算法是必要和现实的，为此专家们把主要的精力放在构造高质量的启发式算 法上( j a m e s 和j i e f e n g ，1 9 9 9 1 1 7 1 ) 。目前已提出的启发式算法较多，分类也较多， 按c e s a rr e g o 的分类法有以下几类：构造算法( c o n s t r u c t i v ea l g r o i t h m ) 、两阶段 法( t w o p h a s ea l g o r i t h m ) 、不完全优化算法( i n c o m p l e t eo p t i m a z a t i o na l g o f i t h ) 等。启发式算法由于其简单易懂且计算时间较短也在求解n p 难题的方法中占有 重要的地位。 ( 3 亚启发式算法( m e t a h e u r i s t i c s ) 主要原理是从一初始解开始，通过对当前 的解进行反复局部扰动已达到较好的解。主要包括禁忌搜索算法( t a b us e a r c h ) 、 模拟退火算法( s i m u l a t e d a n n e a t i n g ) 、遗传算法( g e n e t i c a l r o r i t h i n ) 、神经网络算法 ( n e u r a ln e t w o r k s 。虽然亚启发式算法在求解弱p 四题中钧应用中取得了一定豹 成果，但总体来讲，仅仅是开始尝试阶段，还有待进一步豹研究。 本文中将针对不同的问题的特性，采用不同种类的算法，甚至采用混合算法 以求通过可行的算法求得质量较优的解。 1 5 本研究斜新点 ( 1 ) 从研究内容上来看，一般对v r p 的研究都是局限于单一类型，即非满 载的v r p 或满载的v r p 的研究。本文对两种v r p 问题都进行了研究，从一定程 度上构成了v r p 研究的整体性。 ( 2 ) 对于非满载的v r p ，本文把一般的研究范围扩展到多车场( 此类中多指 配送中心) 和软时问窗领域，在研究方法上，本文把启发式算法和亚启发式算 法相结合，在构造了较好初试解的基础上，用改进的遗传算法进行寻找，既提 第】章弓l 言 高了算法速度，又避免了陷入局部最优。 ( 3 ) 针对v r p f l 问题，本文建立了考虑动态时间窗的m d v r p f l s t w 模型，在 贪心算法的基础上，设计了巧妙的评估函数，动态构造了初始解，并通过一种 改进算法，最终求得带动态时间窗的满载v r p 的满意解。 1 6 论文结构安排 图论文结构框架图 本文按照如下方式组织：第一章绪论以后，第二章对v r p t w 的相关学术问 题展开进行阐述。首先介绍v r p 研究中的核心原始问题，对v r p 学术研究的渊 源有了了解。然后从不同的角度，对v r p 问题进行了分类，使得对v r p 的研究 体系有一个整体的认识。然后针对带时间约束的v r p ，对主要的研究算法进行回 顾，并主要介绍了应用中有着重要地位的遗传算法：第三章对非满载的v r p 第1 章引言 ( m d v r p s t w ) 进行展开研究，给出一种改进的两阶段式亚启发式算法；第四章 是本文的重点章节，主要针对扩展了的满载模型进行研究，给出一种动态构造 算法，拓展了满载v r p 韵研究领域。第五章是结论部分，对本文韵研究进行了 评价，并分析了进一步的研究方向。 8 第2 章v r p t w 问题描述与研究现状 第2 章v r p t w 问题描述与研究现状 2 1v r p t w 的原始问题描述 2 1 1 最短路问题 最短路问题【3 5 l 【3 6 】 3 7 1 ( s h o r t e s tr o u t em e t h o d ；s h o r t e s tp a t ht h o r y ) 简单来说 就是寻求在某网络中，从某起点至终点的最短路经。其数学描述为：在有向图 上寻求连接确定的起讫点间总的弧权重最小的可行路径。即： 给定一个赋权有向图d = ( v ，a ，w ) ，其中v = v i ，i = l ，2 ，n 表示 节点的集合；a = a i j | i ，j = 1 ，2 ，n ) 表示连接节点v i 、v j 的有向弧的集合； 表示弧a i j 的权( 可以是费用、h e f t 7 、距离等) ，w = w i ji i ，j = 1 ，2 ，- ，n ) 。 设v 。、v ，分别为d 中任意两点，p 。是从v 。到v t 的路径，在d 中，由于节点个数 是有限的，则p 。的个数也是有限的。于是求一条从v 。到v ，的最短路径阢* ，可 以表述为； w ( p s t * ) = m i ny w i j ，i ，j = 1 ，2 ，n 鳓 2 1 20 - 1 背包问题的数学描述与装箱问题的数学描述 车辆配载问题的原始问题可以描述为：有多个客户，其货品体积和重量均小 于单车装载重量和法定装载容积。为提高车辆装载效率、降低运输成本，如何 采用拼装的形式将多个客户的货品装载同一配送车辆上，有一辆车按某指定的 路径依次将货品送达客户，同时装载货品的车辆数尽可能少。这样的问题称为 车辆配载问题( 也称为车辆拼装问题) 。 第2 章v r p t w 问题描述与研究现状 研究车辆的配载问题，是要研究采用何种方法拼装，可以使装载重量和装载 体积最大、使车辆韵实载率最高? 车辆配载目的是要充分利用运输设施有效容 积与容重，提高车辆的实载率、降低运输成本。 最早对拼装问题的数学描述，可以追溯到o 一1 背包问题和装箱问题f 3 5 1 。o 一1 背包问题( k n a p s a c kp r o b l e m ) 可以描述为：有确定容积的背包和多个体积 不同、价值不同的物品，如何以最大的价值装包：装箱问题( b i n p a c k i n g ) 可 以描述为：如何以个数最少的体积为单位1 的箱子装入多个体积不超过单位1 的物品。 设有一个容积为a 、承重量为b 的背包，囊个体积为a i 、重量为籼、价值为 e i 的物品，欲装入背包中。若要使装入背包的物品价值总和最大，其线形整数规 划模型可以表述为： m i n 弋c i 备 ( 1 ) 双臣幺”娜。i 第2 章v r p t w 问题描述与研究现状 装箱问题可以看作是o 一1 背包问题的拓展，即装箱问题可以看作是多个o 一1 背包问题额组合。对于多个车辆的配载问题来讲，当物流中心的车辆都是型 号同一的标准车辆时，可以将车辆看作体积为单位1 的箱子，配装各种体积不 超过单位1 的货品，如何以最少的车辆配载最多的货品。车辆配载问题实质上 是o 一1 背包问题与装箱问题的合理整合问题，在实际应用中还有其它约束条件 的限制( 例如时间限制、客户装卸地点限制、交通条件限制等) ，使车辆配载问 题无法作为一个单独的问题应用于整个调度系统中，还必须与其他问题( 如车 辆路径问题、最短路问题、指派问题等) 在模型和算法上进行整合，才能生成 同一的、合理的调度方案。 2 1 3t s p 问题的数学描述 基于图论的t s p 模型【3 5 】【3 8 】【3 9 】可以表述为线形整数规划问题： m i nx d i j x o( 1 ) _ s 。r ，善x 2 1 ，1 = 1 ，2 ，3 ，n ； 2 j 莉= 1 扭 2 3 ，n ( 3 ) 一1 l 。驴i si - - 1 , 2 邓旧2 ，s c 恤轧小( 4 ) l x i i e 0 , 1 ) ，i , j = 1 ，2 3 一，n ( 5 ) 其中d i j 表示城市i 到城市j 的弧权重( 一般为城市间的距离) ，x l j 为决策变 量：当商人由城市i 去往城市j 时，x i j = l ，否则x i j = 0 。( 1 ) 式表示总行走路径 的距离之和最小，是目标函数；( 2 ) 式限定商人从城市i 出来一次；( 3 ) 式限定 商人进入城市j 一次( 即式( 2 ) ( 3 ) 表示商人在每个城市经过一次) ；( 4 ) 式约 束旅行商在任何一个城市的子集中不形成回路，其中s 表示n 个城市的集合，i 第2 章v r p t w 问题描述与研究现状 si 表示集合s 韵元素个数；( 5 ) 式中x * 为决策变量。当x i j = 1 时表示商人走行 豹路径包括城市i 到城市j ，当x i j = 0 时表示商人走行的路径中不包括从城市i 到城市j 的路径。但由于走行的路径不同，西与办不一定相等。当办= d o 时， 为对称的t s p 模型，当办一西时为非对称的t s p 模型。 仿照t s p 问题，车辆路径问题就可以看作是一辆配送车欲到r 1 个客户指定地 点配送货品，每两个客户之间的距离是知道的，如何选择一条路径使配送车辆 依次又不重复地走遍每个客户后，再回到起点且所走的潞径摄短。对于物流中 心的车辆调度来讲，需要考虑如何为配好货物的车辆制定运送线路，以便车辆 能以最短的时间和最短的路径依次送到各个客户手中，同时车辆本身豹运输费 用最小。 事实上t s p 模型中表示韵是两个城市阃的空间距离或说是直线距离，但在 车辆路径问题中，两个客户问的距离受到具体交通条件的影响，通常在处理点 对之间距离时，在求得直线距离的基础上乘以一个大于l 的口系数( 通常“= 1 2 1 ) 进行折算。 2 。2v r p t w 的分类 物流配送车辆调度问题可按照其构成要素划分为不同的种类。 ( 1 ) 按物流中心的数目分，有单物流中心问题( 配送系统中仅有一个物流中心) 和多物流中心阎题( 配送系统中存在多个物流中心) 。 ( 2 ) 按车辆载货状况分，有满载问题( 由于客户需求或供应的货物数量大于或 等于车辆的载重量，故完成一项配送任务需要一辆及其以上的配送车辆，配送 车辆需要满载运行) 、非满载问题( 由于客户需求或供应的货物数量小于车辆载重 量，多项配送任务可共用一辆配送车辆，车辆在配送过程中经常处于不满载状 态) 以及满载和非满载混合问题( 由于一部分客户需求或供应的货物数量大于或 等于车辆的载重量，而另一部分客户需求或供应的货物数量小于车辆的载重量， 第2 章v r p t w 问题描述与研究现状 造成一些配送车辆需要满载运行，而另一些车辆则经常处于不满载状态) 。 ( 3 ) 按配送任务特征分，有纯送货问题( 仅考虑从物流中心向客户送货，也称 为纯卸问题) 或纯取货问题( 仅考虑把各客户供应的货物取到物流中心，也称为纯 装问题) 及取送混合问题( 既考虑将客户需求的货物从物流中心送到各个客户，同 时考虑将客户供应的货物从客户取到物流中心，也称为装卸混合问题或集货和 送货一体化问题) 。为了便于叙述，本文将纯送货或纯取货的物流配送车辆调度 问题称为单向物流配送车辆调度问题，而将取送混合的物流配送车辆调度问题 称为双向物流配送车辆调度问题。 ( 4 ) 按客户对货物取( 送) 时间的要求分，有无时限问题( 客户对货物的取走或 送到的时间无具体要求) 和有时限问题( 客户要求将需求的货物在规定的时间窗 内送到，将供应的货物在规定的时间窗内取走，也称为有时间窗问题1 。有时限 问题又可以分为硬时间窗问题( 客户要求货物必须在规定的时间窗内送到或取 走，不能提前也不能拖后) 和软时问窗问题( 客户要求将货物尽量在规定的时间窗 内送到或取走，但也可以提前或拖后，只不过在提前或拖后时，要 对配送企业实施一定的惩罚1 。 ( 5 ) 按车辆类型数分，有单车型问题( 所有配送车辆的载重量相同1 和多车型 问题( 配送车辆的载重量不完全相同) 。 ( 6 ) 按车辆对车场的所属关系分，有车辆开放问题( 即车辆完成配送任务 后可以不返回其发出车场) 和车辆封闭问题( 车辆完成配送任务后必须返回其发 出车场、。 ( 7 ) 按优化目标数分，有单目标问题( 仅考虑一个配送目标) 和多目标问题( 同 时考虑多个配送目标1 2 3v i = i p t w 的研究方法回顾 求解物流配送车辆调度问题的方法很多，究其实质，可以分为精确算法和 启发式算法两大类。精确算法是指可求出其最优解的算法，主要有：分枝定界法、 第2 章v r p t w 河题描述与研究现状 割平面法、网络流算法、动态规划法等。由于精确算法的计算量一般随问题规 模的增大呈指数增长，在实际中其应用范围很有限。为此，专家们把精力主要 用在构造高质量的启发式算法上。下面对物流配送车辆调度问题的一些常用求 解方法进行评述，并对今年来研究较多的遗传算法进行了详细介绍。 2 3 1 精确算法 r 1 谍分割和列生成。v r p 的集分割是f l j b a t i n s k i l 4 0 】等人提出的。它直接考虑 可行解集合，在此基础上进行优化，因此建立的v r p 模型最为简单。其缺陷在于， 如果问题所受约束不严格，则所需要计算的状态空间非常大。另外，要确定每 个可行解的最小成本也是佯困难的事情。对于其中规模相对较小、约束严格的 问题，可通过线性松弛，引入割平面进行求解。在该方法中，原问题被转化为 简化问题，考虑的范嗣是所有可能的可行解的子集。在此基础上反复求解。通 过引入优化对偶变量向，对该简化闽题松弛，通过计算列的最小边际成本，确 定虽优解。其算法本质上是最短路径算法，同时结合了分枝定界算法。d e s r o c h e r s 用它求解有1 0 3 个客户的带时间窗口垂勺v r p 。 ( 2 ) 三下标车辆流方程。f i s h e r l 4 1 1 等人针对带能力约束、时间窗口以及无停留 时间的v r p ，提出了三下标车辆流方程。在该方程中，其中两个下标表示弧或边， 另外一个下标表示特定车辆的序号。基于b e n d e r s 的分解算法，他们提出了一种 启发式算法，保证在有限步内找到最优解。f i s h e r 等人用它计算了有5 0 1 9 9 个客 户的v r p 。m a r t e l l o 和d e s r o c h e r s 分别提出了相应的改进算法。 ( 3 ) 分枝定界算法。该算法是f i s h e r 4 2 】最早提出的。它的核心思想是将解空问 划分为若干个小的子空间，再依次搜索各个予空间。通过与当前最好解的比较， 可以剪去那些不可能产生最优解的分枝，只搜索那些能产生最优解的分枝。它 可以解决1 0 0 个客户的c v r p ，v r p t w 等。 总的来说，精确算法在可以求解的情况下，其解通常要优于近似算法。但 由于引入严格的数学方法，因而无法避开指数爆炸问题，从而使该类算法只能 1 4 第2 章v r p t w 问题描述与研究现状 有效求解中小规模的v r p t w 。 2 3 2 近似算法 在求解大规模v r p t w 时，近似算法总可以在有限时间里，找到满意的次优 解或可行解，这是精确算法难以做到的。因此在实际应用中，近似算法要更广 泛。常见的有特色的近似算法主要有两大类。第一类是h e u r i s t i c s ，这类算法只 搜索解空间中相对有限的一部分子空间，力求在比较合理的时间内取得比较好 的解。它又分为两小类算法：路径构造算法( 包括节约法，匹配算法，路径改进 算法等) ，两阶段算法( 先聚类后构造路径法，先构造路径后聚类法等) ，等等； 第二类是m e t a h e u r i s t i c s ，这类算法的侧重点放在搜索最有可能产生最优解的区 域，并对该空间进行比较全面的搜索。这类算法产生的解的质量通常比典型的 h e u r i s t i c s 要高。主要包括蚁群算法，遗传算法，禁忌搜索等算法。 2 3 2 1 启发式算法 ( 1 ) 节约算法( s a v i n g sa l g o r i t h m s ) 节约法是求解v r p 矛n v r p t w 的一种非常流行的方法。它是1 9 5 4 年由c l a r k e 和w r i g h t l 4 3 】基于d a n t z i g 和r a m s e r l 5 4 】的思想提出来的，因此也称之为 c l a r k e w r i g h t 算法。该算法最初按所需访问的客户数n ( 不含出发点)