（计算机应用技术专业论文）物流配送中车辆路径算法分析与研究.pdf

上海海事大学硕士论文物流配送中车辆路径算法分析与研究 摘要 现代物流作为一种先进的组织方式和管理技术，通过降低流通费用，缩短流通 时间，可以整合企业价值链、延伸企业的控制能力，加快企业资金周转。因此，随 着社会的发展，作为第三利润的源泉，物流的重要性逐渐显现出来，越来越受到各 个行业的重视。上到政府下到企业都纷纷探讨如何提高物流利润，使其成为一个重 要的发展行业。通过分析研究人们发现配送成本在物流的各项成本当中占有相当高 的比重，因此，对配送中心而言，合理的优化配送路径不仅可以简化配送程序、减 少配送频率：而且更重要的是可以降低配送费用，从而带来更大的效益，因此配送 路径的优化选择引起了各界人士的注意。 本论文的研究就是围绕物流配送路径优化问题而展开的，通过分析目前国内外物 流配送路径优化问题的研究现状，指出国内在路径优化方面存在的问题，提出本文所 要解决的问题。本文首先对车辆路径问题进行分析，并具体介绍了一些重要的求解算 法。然后，在对现有车辆路径问题求解算法迸行分析的基础上，本文选择利用遗传算 法求解v r p 问题。根据对遗传算法基本原理及其存在缺陷的分析，提出了两种方法对 遗传算法的进行改进。随后介绍了遗传算法基于自然数编码的编码理论，并且对遗传 操作进行了具体介绍；重点研究了有时间窗约束的车辆路径问题的求解方法，提出了 一种自适应混合遗传算法求解此类问题，并且通过对一个具体实例的分析，验证了此 算法的可行性及优良的寻优能力。另外，由于实际中出现的往往是一些非确定性信息， 如模糊信息等，研究确定性车辆路径问题的有效方法不一定能有效解决模糊车辆路径 问题，因此本文对具有模糊预约时间的v r p 问题进行了分析，对模糊车辆调度问题进 行了初步探讨，提出了两种求解此问题的方法，并且提出一种新型的遗传操作的设计， 最后对一个算例进行计算，提出引入用户主观决策的算法输出设计。 最后，对论文的主要工作进行了总结，并对未来研究加以展望。希望本次课题 的研究能对未来物流的实际应用能提供一些思路和方法。 关键字：车辆路径问题，遗传算法，时间窗，模糊 上海海事大学硕士论文 物流配送中车辆路径算法分析与研究 a b s t r a c t a sa na d v a n c e do r g a n i z a t i o nm e t h o da n dm a n a g e m e n tt e c h n o l o g y , m o d e m l o g i s t i c sh a sb e e nr e c o g n i z e da s ”t h et h i r dp r o f i ts o u r c e ”f o ra ne n t e r p r i s e i t i n t e g r a t e st h ev a l u ec h a i no fe n t e r p r i s e s r e i n f o r c e st h ec o n t r o lc a p a b i l i t ya n d a c c e l e r a t e sf u n dt u r n o v e rb yt h er e d u c t i o no fc i r c u l a t i o nc o s ta n dt i m e s o ，i t b e c a m em o r ea n dm o r ei m p o r t a n tf o rm a n yc o m p a n i e si no u rc o u n t r y f o rt h e b r i g h tf u t u r e ，b o t ht h eg o v e r n m e n ta n dc o m p a n yt a k et h ep r o f i to ft h ei n d u s t r yi n t o c o n s i d e r a t i o n ，a n dt r yt om a k ei ta ni m p o r t a n ti n d u s t r y b ys t u d y i n g ，t h el o g i s t i c r a t i o ni sab i gp r o p o r t i o ni nt h ec o s tc o n s t i t u t i o no ft h el o g i s t i c s f o rt h er a t i o n c e n t e r , o p t i m i z i n gt h er o u t eo fr a t i o nc a nn o to n l ys i m p l i f yt h er o u t e 。r e d u c et h e f r e q u e n c yo ft h ed e l i v e r y , b u ta l s ol o wd o w nt h ec o s ts oa st oc r e a t em o r eb e n e f i t t h em a i ni d e ao ft h et h e s i si ss t u d y i n gh o wt oo p t i m i z et h er o u t eo fr a t i o n b y a n a l y z i n gt h ee x i s t i n ga l g o r i t h m s i tp o i n t so u tt h ep r o b l e m st oe d u c et h em a i n i d e ao ft h e s i s f i r s t w ea n a l y z ev r pa n di n t r o d u c es o m ea l g o r i t h m st os o l v et h e p r o b l e m b a s e do ns t u d i e so nt h ee x i s t i n ga l g o r i t h m s ，w ec h o o s et h eg e n e t i c a l g o r i t h mt oo p t i m i z et h er o u t eo fr a t i o n a f t e ra n a l y z i n gt h ep r i n c i p i u ma n d l i m i t a t i o no fs i m p l eg e n e t i ca l g o r i t h m ，w eg i v et w on e wf e a s i b l em o d e so f o p t i m i z i n gt h er o u t eo fr a t i o n ，t h e nb a s e do nt h en a t u r a ln u m b e rc o d i n gt h e o r y , t h ev e h i c l er o u t i n gp r o b l e mw i t ht i m ew i n d o w si ss t u d i e d a n db yu s i n gan e w h y b r i dg e n e t i ca l g o r i t h ms o l v i n ga ne x a m p l eo ft h ev r p t v v w ev a l i d a t e f e a s i b i l i t ya n dg o o dp e r f o r m a n c eo ft h i sn e wa l g o r i t h m i nt h ec l a s s i c a lv e h i c l e r o u t i n gp r o b l e m s ，a l lk i n d so fi n f o r m a t i o na r ea s s u m e dt ob ed e t e r m i n a t e d b u ti n p r a c t i c e ，p l a n n e ro fr o u t e sa l w a y sm e e tw i t hu n c e r t a i ni n f o r m a t i o n ，s u c ha sf u z z y i n f o r m a t i o n c o n s e q u e n t l y , e f f e c t i v em e t h o d sf o rs o l v i n gd e t e r m i n a t e dv e h i c l e r o u t i n gp r o b l e m sc a n n o ts o l v ef u z z yv e h i c l er o u t i n gp r o b l e m se f f e c t i v e l y i ti s n e c e s s a r yt od os o m er e s e a r c ho nc h a r a c t e r i s t i c so ff u z z yv e h i c l er o u t i n g 上海海事大学硕士论文 物流配送中车辆路径算法分析与研究 p r o b l e m sa n dt od e s i g ne f f e c t i v em o d e l sa n da l g o r i t h m sf o ri t s ow eg i v em o r e e f f o r t so ns t u d y i n gt h ef u z z yv e h i c l er o u t i n gp r o b l e m w ei n t r o d u c et w o m e t h o d st os o l v et h i sp r o b l e ma n dg i v ean e wd e s i g no fg e n e t i co p e r a t i o n i nt h e l a s t w eg i v eae x a m p l eo fp 、，r pa n dp r o v i d ean e w d e s i g no f r e s u l to u t p u t i nc o n c l u s i o n ，w ep o i n to u tm a i nw o r ko ft h ed i s s e r t a t i o na n dt h eo r i e n t a t i o n o ff u t u r er e s e a r c hp r o s p e c t i v e f i n a l l y , ih o p et h ew o r ko ft h i sd i s s e r t a t i o nc a n p r o v i d eal i f f i ep r o f i tt of u t u r ep r a c t i c e s u nl i l i ( c o m p u t e r a p p l i c a t i o n ) d i r e c t e db ypr o f l i ug u a n g z h o n g k e y w o r d s , v r p , g e n e t i c a l g o r i t h m 。 r i m ew i n d o w s ，f u z z y 论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。 论文中除了特别加以标注和致谢的地方外，不包含其他人或其他机构已 经发表或撰写过的研究成果。其他同志对本研究的启发和所做的贡献均 已在论文中作了明确的声明并表示了谢意。 作者签名：易觑知日期：。7f ；，j 7 论文使用授权声明 本人同意上海海事大学有关保留、使用学位论文的规定，即：学校 有权保留送交论文复印件，允许论文被查阅和借阅；学校可以上网公布 论文的全部或部分内容，也可以采用影印、缩印或者其他复印手段保留 论文。保密的论文在解密后遵守此规定。 作者签名：知压瓦导师签名：i l ，j 分f 日期：加矽， | 。t 上海海事大学硕士论文 物流配送中车辆路径算法分析与研究 1 1 物流 1 1 1 物流的概念及发展 第一章引言 1 9 1 5 年，阿齐萧( 美) 最早提及物流概念，其后一直在不断发展。从原来企业 内部销售领域扩展到企业外部经营管理的其他领域，并在企业物流的基础上经历了产 品配送阶段、物流管理阶段和现代综合物流管理阶段【l 】。 1 9 8 6 年，美国物流管理协会( c 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 , c l m ) 将物流定 义为“为了满足顾客需求而规划、实施以及控制原材料，在制品库存，产成品以及相 关信息从起始点到使用点高效、低成本流动及存储的过程”。1 9 9 2 年，c l m 修订了对 物流的定义：物流是物料从供应商通过不同的设施到达顾客过程中的运输、存储、控 制，以及在每一个环节对于所有可回收物料的收集的整合。c l m 最新的定义认为 ( 1 9 9 8 年) ：物流是供应链的一部分，是为了满足顾客的需求，规划、执行并且控制 从源头到消费地点的产品、服务以及相关信息的正向、逆向流动以及存储，以达到高 效、低成本的目的。 激烈的竞争要求企业必须降低成本以求生存，因而，物流作为企业的“第三利润 源泉”日益受到社会的重视，物流产业得到了极大的发展。我国物流业也在这股热潮 中随着经济的发展和经济体制改革的进一步深化而成为市场经济中一个竞争激烈的 行业。“第三利润源泉”的说法主要出自日本 2 1 ，从历史发展来看，人类历史上曾经 有过两个大量提供利润的领域：资源领域及人力领域。在这两个利润源潜力越来越小， 利润开拓越来越困难的情况之下，物流领域的潜力被人所重视，按时间序列排为“第 三个利润源泉”。 上海海事大学硕士论文 物流配送中车辆路径算法分析与研究 1 1 2 物流的结构 从上述的概念介绍中，我们可以看出物流主要分为以生产领域的物流为主的生产 物流、以商业领域物流为主的商业物流以及从商业领域返回生产领域的回收物流三类 问题。尽管三类问题的特征各不相同，但是，在每一类问题的不同环节基本都包括了 相同的问题，如供应商、制造商、分销商、零售商的库存控制策略问题，原材料从供 应商向制造商、成品从制造商向分销商、分销商向零售商的运输问题以及制造商的选 址、分销商的物流网络设计问题等等。因此我们可以看出，从系统结构来看，物流可 以分为战略层、战术层以及运作层三层结构。 图1 1 物流层次结构嘲 战略层，主要指物流系统结构设计、各级节点( 供应商、制造商等) 的选址等。 战术层，指整个系统以及每个节点的设施规划、库存管理。 运作层，指具体的运作管理，如车辆调度、仓库管理、物料搬运等。 1 2 物流配送 1 2 1 物流配送的概念 中华人民共和国标准物流术语将配送定义为：在经济合理区域范围内，根 据用户要求，对物品进行拣选、加工、包装、分割、组配等作业，并按时送达指定地 点的物流活动。物流配送是物流活动中一个重要环节，也可以看作是物流过程的中转 型送货( 也称二次输送、支线输送、终端输送) 。在产品用户集中的区域，发货人按 2 上海海事大学硕士论文物流配送中车辆路径算法分析与研究 照用户的订货要求和时间计划，在物流中心配货，并将配好的货物采用汽车巡回运送 方式送交收货人。配送不是单纯的运输或是送货，而是运输与其它活动的组合，除了 各种“运”、“送”活动外，还要从事大量的集货、分货、配货、配装等工作，是配与 送的结合【3 1 。 配送业务在美国、日本等国家开展比较早，近几年来，在我国也有较快的发展。 目前己经形成了自身的特点： ( 1 ) 配送是从物流节点到用户之间的一种特殊送货形式； ( 2 ) 配送是连接了物流其他功能的物流环节，提高了物流系统的价值增值部分； ( 3 ) 配送是复杂的作业体系，通常伴随着较高的作业成本，但却能大大降低库 存成本以及快速反应商品市场需求变化； ( 4 ) 配送在固定设施、搬运设备、运送工具、组织形式、通信信息等方面可集 成系统化的运作体系。 1 2 2 我国物流配送的发展现状 经过二十年的改革开放和经济的持续快速发展，我国目前已初步具备了发展物流 管理和配送技术的经济环境和市场条件【4 】： ( 1 ) 市场供求关系己发生重大变化，市场竞争进一步加剧，初步形成了供求平 衡或供过于求的买方市场格局，为企业加强科学管理，发展物流管理和配送技术提供 了良好的经济环境条件。 ( 2 ) 我国物流产业有着巨大的发展潜力。美国工业界每年的物流成本达至9 4 0 0 0 亿美元，只要降低1 0 ，一年就可以节约4 0 0 亿美元，因此物流产业被形象地比喻为 “一座价值4 0 0 亿美元的金矿尚待开采”。据世界银行一份报告的估计，中国物流服务 成本大约占g d p 的1 8 ，比美国2 0 世纪9 0 年代中期9 5 的比重还高。从现状来看，我 国产品从出厂经过装卸、储存、运输等各个物流环节到消费者手中的流通费用占商品 价格的5 0 左右，而新鲜水果、易变质的食品、某些化工产品的流通费用有时高达商 品价格的7 0 ；我国汽车零配件的生产加工装配时间仅占2 ，而9 6 的时间是原材料、 零配件的储存、装卸和搬运时间。因此，现代企业竞争的焦点聚集在被称为企业“第 上海海事大学硕士论文物流配迭中车辆路径算法分析与研究 三利润源泉”的物流产业上。 ( 3 ) 现代信息技术和现代商品物流技术的进步为中国物流和配送的快速发展准 备了充分的技术基础。现代物流管理和配送技术中大量使用着先进的信息技术和商品 物流技术，这些技术在西方发达国家已日趋完善。目前己有相当多的物流和配送技术 开始进入中国并在企业中得到越来越广泛的应用，例如条形码技术、计算机支持的信 息管理技术、e d i 、砌r p 等。 ( 4 ) 政府对物流和配送的政策支持。为了大力促进流通体制改革和流通现代化 的进程，为了促进连锁经营等组织形式的发展，国家有关部门对商品物流和配送采取 了积极鼓励和支持的政策。 1 3 物流网络规划 物流网络是指由供应点、需求点、配送中心( 或其它物流服务设施) 等物流节点 所组成的分层配送网络，其中配送中心是为供应点需求点分别提供集货送货服务的 中介。一般地，每个需求点只由一个配送中心为其提供送货服务，而每个配送中心则 可能为所有供应点提供集货服务【5 】。 物流网络规划涉及如下优化闯题：( 1 ) 设施选址，即物流设施数量、位置、容量 等方面的决策优化；( 2 ) 服务分派，即确定物流设施与服务对象的对应关系；( 3 ) 路 径安排，即为每个设施的用户安排成本最少的运输路径。 如果假定物流网络规划过程中所考虑的因素都可以量化，则物流网络优化可以概 括为以下几类优化问题：决策中不考虑服务分派，这样的问题称为纯设施选址问题 ( f a c i l i t yl o c a t i o n p r o b l e m ) ；若同时考虑设施选址和服务分派问题，则称之为定位一 配给问题( l o c a t i o n - a l l o c a t i o np r o b l e m , l a p ) ；若同时考虑设施选址、服务分派和路 径安排问题，则称之为定位运输路线安排问题( l o c a t i o n - r o u t i n gp r o b l e m l r p ) 。 1 3 1 定位一运输路线安排问题l r p 定位一运输路线安排问题u 心可以表示为1 6 】：给定与实际问题相符合的一系列潜 4 上海海事大学硕士论文物流配送中车辆路径算法分析与研究 在的设施点，在这些潜在的点中确定出一系列的设施位置，同时要确定出一套从各个 设施到各个客户点的运输路线，确定的依据是满足问题的目标( 通常是总的费用最 小) 。客户点的位置和客户的需求量是已知的或可估算的，货物有一个或多个设施点 位置已知，问题的目标是把那些潜在的设施建立起来，以使总的费用最小。l r p 的实 质是l a 和v r p 的集成。 关于l r p 概念的研究可以追溯至1 j 1 9 6 1 年v o n b o v e n t e r 关于运输问题中的运输成 本和定位成本的相互关系。l i 心问题的早期研究集中在l r p 复杂性上，后来人们开始 意识到定位和运输决策间的协调性。l r p 的研究在上个世纪7 0 年代末和8 0 年代初得到 发展。而关于l r p 更普遍的工作是伴随着集成化物流理念和国际贸易配送体系的有效 性而并行产生的。但是早期的集成化l r p 问题仅限于单一设施。 1 3 2l r p 和l a 、v r p 的比较及相互关系 定位一配给问l a 可定义为：依据客户点的地理分布与货物分配的关系，确定出 某一地理范围内设施的数量和位置。j o h n c u r r e n t 等学者对此问题进行了综述研究， 并把l a 问题进行了分类。根据问题的目标函数来分类的，作为分类依据的目标函数 共分四种：( 1 ) 费用最小化；( 2 ) 客户需求导向；( 3 ) 利润最大化；( 4 ) 其他相关考 虑。 运输一车辆路线安排问题( 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 的目标函数是总费用最小。 定位、分配、路线之间相互影响，相互作用。 6 1 图卜2 定位、分配、路线三者之间的相互关系 上海海事大学硕士论文 物流配送中车辆路径算法分析与研究 1 4v r p 研究动态及水平 自从1 9 5 9 年d a n t i n g 和r a m s e r 提出车辆路径问题v r p 以来，由于其应用的广泛性 和经济上的重大价值，一直受到国内外学者的广泛关注。在经典v r p 的基础上，车辆 路径问题在学术研究和实际应用上产生了许多不同的延伸和变化型态，包括t s p ( 可 看作v r p 的一个特例，即当v r p 只包括一条路径，且没有能力约束时就成为t s p ) 、 带时间窗的车辆路径问题( v e h i c l e r o u t i n g p r o b l e m s w i t h t u n e w i n d o w s ，v r p t w ) 、， 随机需求车辆路径问题( v e h i c l e r o u t i n g p r o b l e m w i t h s t o c h a s t i c d e m a n d ，v r p s d ) 、 动态车辆路径问题( d y n a m i c v e h i c l er o u t i n gp r o b l e m s ，d v r p ) 等1 7 j 】。 早在6 0 年代c l a r k e 和w r i g h t 就提出的节约法( s a v i n g m e t h o d ) 。1 9 6 2 年，b a l i n s k i 等人首先提出v r p 的集分割，直接考虑可行解集合，在此基础上进行优化，建立了最 简单的v r p 模型。1 9 7 1 年，e i l o n 等人提出将动态规划法用于固定车辆数的v r p ，通过 递归方法求解。其后，c h r i s t o f i e l d s 提出了状态空间松弛，极大地减少了状态数量。 1 9 7 4 年，g i l l e t 和m i l l e r 提出的扫描法( s w e e p i n g m e t h o d ) 。1 9 8 1 年，c h f i s t o f i d e s 等人 提出了k 度中心树和相关算法，对固定车辆数m 的m - t s p 进行k 度中心树松弛。后来， m l f i s h e r x i j 这种方法做了进一步改进，可求解有1 3 4 个客户的v r p 。1 9 9 1 年， g e n d r e a u 等人【9 1 ，将禁忌搜索方法应用于v r p 。其后e t a i l l a r d 等人“0 1 通过按角度和路 径重心对原问题的空间进行分割，再用禁忌搜索结合模拟退火对子问题求解，实现了 对问题求解的并行化。1 9 9 6 年，j l a w r e n c e i l l l 将遗传算法用于冲的研究，并可有效 求解带时间窗口的v r p 。 此外，国外从实用化角度开展的研究也比较多，研究者将模型和算法方面取得的 进展应用于很多具体问题。也由此诞生了一些为企业车辆路径提供服务的专业化公 司，开发了各具特色的车辆路径软件，比较著名的有：美国e s r i 公司的a r e l o g i s t i e s 系统，r 舶d n e t 科技公司的r o a d n e t 5 0 0 0 系统，r o u t e s m a r t 科技公司的r o u t e s m a r t 系统， o p t r a k 软件公司的o p t r a k 系统，m m 的v s p x 系统，美孚的h p c a d 系统，另外还有日 本富士通的v s s 系统等。 国内v r p 的研究起步较晚，根据所能掌握的资料，国内最先对v r p 进行系统研究 的是郭耀煌教授，他及其学生从1 9 8 9 年起对多车场、多车型等类型问题进行了研究。 西南交大的李军针对有时间窗的车辆路线安排问题提出了一种利用节约法的启发式 6 上海海事大学硕士论文物流配送中车辆路径算法分析与研究 算法；浙江大学蔡延光【1 2 】等人运用模拟退火算法和遗传算法求解多重车辆调度问题， 并将其集成为智能算法库，作为设计智能运输调度系统的依据；东北大学的张潜m 等人提出一种先用优先级综合聚类分析法将客户分类，再用带有控制开关系统的改进 遗传算法求解多目标v r p 的优化方法；张乐诚【1 3 】等人研究了随机时间约束的车辆路径 问题：长沙理工大学陈曦【1 4 1 等人将变异粒子群算法运用于车辆路径优化问题；唐小明 等f ”】人研究了多指标的车辆模糊优化调度：西南交通大学的张建勇等人近年来对模糊 车辆路径问题做了大量的研究“6 , 1 7 , 1 s 】。 就收集到的资料看，国内学者在v r p 领域的研究主要具有如下特点：( 1 ) 研究者 群体小；( 2 3 有关术语不够统一；( 3 ) 研究范围较窄，研究的问题大多属于确定型问 题，尤其集中于有无时间窗的v r p ，关于动态或不确定性v r p 问题的研究较少；( 4 ) 研究多是侧重于学术研究，与实际应用尚有距离；( 5 ) 研究群体比较单一，就收集到 的资料来看，近年开始引起研究者重视的关于不确定问题的研究主要集中于很少的几 位研究者，如西南交通大学的张建勇博士等。 虽然国内外v i 己p 的研究已经有了一定的成果，但是事实上，除了少数几类特殊情 形的物流调运问题已经有了比较优秀的算法之外，实践中发生的多数物流调运问题还 没有很有效的算法。 1 5 本文研究的主要内容 根据相关理论的研究进展，我们认为现有启发式求解算法往往是针对车辆路径问 题的一些特殊情形的研究，算法的效率也仍然有待继续改进。因此，本文在阅读了大 量已有算法的基础上，对车辆路径问题的求解算法进行了研究，并提出用改进的遗传 算法求解较复杂的v r p 问题。论文具体安排如下： 第一章阐述本文的研究背景、意义和研究目的； 第二章对车辆路径问题进行分析建模，对v r p 问题的求解方法，以及基本问题进 行系统的阐述； 第三章主要介绍了遗传算法的发展历程、基本原理及其存在的缺点，并提出了对 遗传算法的改进； 7 上海海事大学硕士论文物流配送中车辆路径算法分析与研究 第四章是本文的重点部分，第1 节首先介绍了用遗传算法求解v r p 问题的基于自 然数编码的编码理论，并且对遗传操作进行了具体介绍；第2 节重点研究了有时间窗 约束的车辆路径问题的求解方法，提出了一种自适应混合遗传算法求解此类问题，并 且通过对一个具体实例的分析，验证了此算法的可行性及优良的寻优能力；第3 节主 要对具有糊预约时间的v r p 问题进行分析，提出了两类求解此问题的方法，并且提出 一种新型的遗传操作的设计，最后对一个算例进行计算，提出引入用户主管决策的算 法输出设计。 第五章对全文进行总结并且对今后的研究工作进行了展望。 8 上海海事大学硕士论文物流配送中车辆路径算法分析与研究 2 1 v r p 问题描述 第二章车辆路径问题研究 物流配送车辆优化调度问题最早是由d a a t z i n 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 r p ) 郭耀煌、李军在物流配送车辆优化 调度理论与方法1 1 9 】一书中将v r p 定义为：对一系列发货点和( 或) 收货点，组成 适当的行车路径，使车辆有序地通过它们，在满足一定约束条件( 如货物需求量、发 送量、交发货时间、车辆容量限制、行使里程限制、时间限制等) 下，达到一定的目 标( 如里程最短、费用极小、时间尽量少、使用车辆尽量少等) 。 般认为，当不考虑时间要求，仅根据空间位置安排线路时称为车辆路径问题 ( v e h i c l er o u t i n gp r o b l e m s ，简称v r p ) ；考虑时间要求安排线路时称为车辆调度问 题( v e h i c l es c h e d u l i n gp r o b l e m s ，简称v s p ) ；同时考虑空间位置和时间要求时称为 车辆路径和调度混合问题( v e h i c l er o u t i n ga n ds c h e d u l i n gp r o b l e m ，简称v r p & v s p ) 。 但是在许多场合，人们也将v r p 称为v s 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 ew i n d o w s ( 简称 v r p t w ) 。本论文遵照大多数人的习惯，对这几类问题不做严格区分，仍统称为v r p 。 2 2 一般v r p 模型 9 上海海事大学硕士论文物流配送中车辆路径算法分析与研究 2 2 1 模型中的决策变量 x i 业= y “= 如果第k 个运输工具从客户淫| j j ， 否则 客户i 的任务由车辆k 完成， 否则 2 2 2 模型中参数的含义 c i 广_ 从客户i 到客户j 的运输成本； g 广一客户i 需要运送的货物量 q 车辆容量 2 2 3 车辆优化调度数学模型 y 。= l x i 业= y q x 耻= y h x i 业= o 或1 y h = 0 或1 2 3 v r p 的分类 i = 1 ，2 ，l j = o ，1 ，；v k i = 0 ，1 ，；v k i , j = 0 ，1 ，f ；v k i = 0 ，1 ，；v k 自v r p 被提出以后，许多学者对v r p 从不同的角度，按不同的标准进行了多种 分类“9 1 。 1 0 上海海事大学硕士论文 物流配送中车辆路径算法分析与研究 按任务特征分，有纯装问题或纯卸问题( p u r e p i c k u p o r p u r e d e l i v e r y ，车辆在所 有任务点装货或卸货，即集货或送货问题) 及装卸混合问题( c o m b i n e dp i c ku pa n d d e l i v e r y ，每项任务有不同的装货点和卸货点，即集货、送货一体化问题) 。 按任务性质分，有对弧服务问题( 如中国邮递员问题) 和对点服务问题( 如旅行 商问题) 以及混合服务问题( 如交通车线路安排问题) 。 按车辆载货状况分，有满载问题( 货运量不小于车辆容量，完成一项任务需要不 只一辆车) 和非满载问题( 货运量小于车辆容量，多项任务用一辆车) 。 按车场( 或者货场、配送中心等) 数目分，有单车场问题和多车场问题。 按车辆类型数分，有单车型问题( 所有车辆容量相同) 和多车型问题( 执行任务 的车辆容量不全相同) 。 按车辆对车场的所属关系分，有车辆开放问题( 车辆可以不返回其发出车场) 和 车辆封闭问题( 车辆必须返回其发出车场) 。 按优化目标数来分，有单目标问题和多目标问题。 2 4 基本求解算法 v r p 的求解算法包括精确算法和启发式算法两大类别。由于v r p 为n p - h a r d 问 题，存在高效的精确算法的可能性不大( 除非p = - n p ) 。因此，学者们将主要精力集中 在构造高质量的启发式算法上。 2 4 1 精确算法 精确算法指可求出其最优解的算法，主要有： ( 1 ) 支定界法( b r a n c ha n db o u n da p p r o a c h ) ( 2 ) 割平面法( c u t t i n gp l a n e sa p p r o a c h ) ( 3 ) 网络流算法( n e t w o r kf l o wa p p r o a c h ) ( 4 ) 动态规划算法( d y n a m i cp r o g r a m m i n ga p p r o a c h ) 精确算法的计算量一般随问题的规模的增大呈指数增长，因此在实际中的应用范 上海海事大学硕士论文物流配送中车辆路径算法分析与研究 围很有限。 2 4 2 启发式算法 2 4 2 1 传统的启发式算法 ( 1 ) 线路构造算法( t o u rc o n s t r u c t i v ea l g o r i t h m ) 根据一些准则，每一次将一个不在线路上的点增加进线路，直到所有的点都被安 排进线路为止。构造算法是最早提出用来解决t s p 及v s p 的，这些方法一般速度快， 也很灵活，但这类算法有时找到的解离最优解差得很远。 ( 2 ) 两阶段法( t w o - p h a s ea l g o r i t h m ) 学者们通过对构造算法的研究，认为由构造算法求得的解可以被进一步改进，为 此提出了两阶段法。第一阶段得到一个可行解，第二阶段通过对点的调整，在始终保 持解可行的情况下，力图向最优目标靠近，每一步都产生另一个可行解以代替原来的 解，使目标函数得以改进，一直继续到不能再改进目标函数为止。 般第一阶段常用构造算法，在第二阶段常用的改进技术有2 o p t 、3 - o p t 和o r - o p t 交换法，这是一种在解的邻域中搜索，对初始解进行某种程度优化的算法，以改进初 始解。 些基于数学规划的算法也属于两阶段法，把问题直接描述成一个数学问题，根 据其模型的特殊构形，应用一定的技术( 如分解) 进行分划，进而求解已被广泛研究 的子问题( 如t s p 问题) 。如f i s h e r 和j a i k u m a r 的分派启发式算法等。 在两阶段法求解过程中，常常采用交互式优化技术，因而可以有效她反映决策者 的经验和知识，同时也增加了该方法在实践中被采用的可能。目前，两阶段法是研究 成果最丰富和应用最广泛的求解方法【1 9 1 。 上海海事大学硕士论文物流配送中车辆路径算法分析与研究 2 。4 。2 。2 现代优化算法 ( 1 ) 模拟退火( s i m u l a t e da n n e a l i n g ) 模拟退火算法是局部搜索算法的扩展，与局部搜索算法的不同之处是模拟退火算 法不仅接受邻域内比当前解更优的解，而且以一定的概率接受适当的“恶化解”。模 拟退火算法的基本步为1 2 0 1 ： s t c p l 任选或用其它方法产生一个初始解x o ，目标函数值f ( x o ) 。令x 尸) 【o ； s t e p 2 在解x t 的邻域n ( x t ) q b 随机选择一个墨若f ( x ) f ( x a ，则令x t + i - - - - x ；否则， 以概率p t 令x t + l - - - - - - - - - - - - - - - - - - - - - x ，或者以概率l - - p t 令x t + l - - x 。其中，p t 为舡) 一f ( x a 和t 的减函数，通常将p t 定义为 p = e x p ( - f ( x ) - f ( x a e0 其中，0 t 为第t 步迭代的温度； s t e p 3 令t = t + 1 ，若满足停止条件，则终止计算；否则，转s t e p 2 。 模拟退火算法通过温度参数0t 来控制算法的退火过程，0t 随着迭代次数的增加 逐渐减小，从而保证算法随着迭代次数的增加获得最优解的概率趋于l 。 ( 2 ) 禁忌搜索( t a b us e a r c h ) 禁忌搜索算法是局部邻域搜索算法的推广，禁忌搜索算法的特点是采用了禁忌技 术。所谓禁忌( t a b u ) 就是禁止重复前面的工作禁忌搜索算法用禁忌表( t a b ul i s t ) 记录下已经到达过的局部最优点，在以后的搜索中，乖j 用禁忌表的信息不再或有选择 地搜索这些点，以此来跳出局部最优点。 禁忌搜索算法( t a b us e a r c ha l g o r i t h m ) ： s t e p1 选择一个初始解x ，令当前最优解x * - - - - - - - - - - - - - - - - - - - - - - x ，令k = 0 ； s t e p2 令k = k + l ，在当前最优解的邻域n ( x ，k ) 中选出满足禁忌要求的候选集合 v 。在v + 中选择最优解y ，令x = y 。若职) 日”) ，则令x * - - - x 。更新禁 忌表； s t e p ，若符合停止运算准则，则停止；否则，转s t e p2 。 t a b us e a r c h 用于v r p 求解时，通常采用多路径间的k _ 交换方法来构造解的邻域 映射。为了增强算法的效率，许多研究者从禁忌对象选取、禁忌长度确定、特赦规则、 上海海事大学硕士论文物流配送中车辆路径算法分析与研究 终止原则等方面做了详细考虑和安排。例如，注意到最优路径含有边( 弧) 长度超过一 定限度( g r a n u l a r i t y t h r e s h o l d ) 可能住较小，t o t h 和v i g o ( 1 9 9 8 ) 提出了c n a n u l a r t a b u s e a r c h 方法，其基本思想就是在禁忌搜索过程中，不考虑那些超过长度限制的边( 弧) 。 从而极大地缩短了算法的时间。 ( 3 ) 遗传算法( g e n e t i ca l g o r i t h m ) 遗传算法模拟了自然界进化现象，在自然界的演化过程中，生物体通过遗传( 传 种接代，后代与父代非常相似) 、变异( 后代与父代不完全相似) 来适应外界环境， 一代又一代的优胜劣汰，发展进化。 g a 把搜索空间( 欲求解问题的解空间) 映射为遗传空间，既把每一个可能的解 编码为一个向量( 二进制或十进制数字串) ，称为一个染色体( c h r o m o s o m e 或个体) ， 向量的每一个元素称为基因( g e n e ) ，所有的染色体组成种群( p o p u l a t i o n ，或集团) 。 并按预定的目标函数( 或某种评价指标，如商业经营中的利润、工程项目中的最小费 用等) 对每个染色体进行评价，根据其结果给出一个适应度值。算法开始时先随机产 生一些染色体( 欲求解问题的候选解) ，计算其适应度，根据适应度对诸染色体进行 选择、交叉、变异等遗传操作，剔除适应度低( 性能不佳) 的染色体，留下适应度高 ( 性能优良) 的染色体，从而得到新的种群。由于新的种群成员是上一代种群中的优 秀者，继承了上一代的优良特性，因而明显优于上一代。算法就这样反复迭代，向更 优解的方向进化，直至满足某种预定的优化指标 关于遗传算法的详细情况，我们将在下章重点介绍。 2 5 基本问题分析 在第2 3 节介绍v r p 分类的时候，我们已经说过，按不同的标准，可以得到不 同的分类。例如按任务性质分，v r p 可以分为对弧服务问题( 如中国邮递员问题) 和对点服务问题( 如旅行商问题) 以及混合服务问题( 如交通车线路安排问题) 。同 时，在研究v r p 问题的求解方法时，我们介绍过的一类方法是应用一定的技术( 如 分解) 将v r p 问题进行分划，进而求解己被广泛研究的子问题。如f i s h e r 和j a i k u m a r 的分派启发式算法，将v r p 模型分解为一个分派问题和一个旅行商问题：先对每一 1 4 上海海事大学硕士论文 物流配送中车辆路径算法分析与研究 辆车将顾客进行分派，这通过解一般的分派问题来得到；分派一旦作出，通过应用一 些t s p 问题的求解方法来安排每辆车的行车线路。因此，本节中我们将着重研究几 个比较重要的v r p 基本问题。 2 5 1 两点间最短路问题 实际应用中当v r p 问题叙述为由一个供应点对一个客户的专门送货，且客户的 需求量接近或大于可使用车辆的额定载重量时，需要派一辆或多辆车一次或多次送 货。在这种情况之下，v r p 问题就转化为求解物流网络最短路的问题。这也是v r p 问题的一个最简单、最基本的问题。 两地之间的距离是指两点之间最短路径的长度。两点之间的路径可以有很多条， 在安排行车路线的时候，我们必须保证车辆走最短的路程，这是总成本最低的保证， 同时也是总路径最短的