（交通运输规划与管理专业论文）基于改进遗传算法的城市配送车辆调度优化研究.pdf

摘要 随着市场经济发展步伐的加快，作为“第三利润源泉”的物流对经济活动的影 响日益明显，越来越引起人们的重视。而随着城市经济的发展和城市规模的扩大， 我国的城市配送需求日趋旺盛。在城市配送业务中，配送线路安排的合理与否对 配送速度、成本、效益影响很大，特别是多用户配送线路的确定更为复杂。采用 科学、合理的方法来进行配送线路优化，是物流配送中非常重要的一项活动。因 此，本文围绕城市配送中车辆调度问题展开了分析，具体进行了如下研究： 首先，对城市配送相关理论进行分析，提出了多配送中心的配送模式，在对 有时间窗的多车场车辆调度问题进行描述的基础上，建立了有时间窗的多车场车 辆调度的数学模型。 其次，根据车辆调度问题的数学模型，提出了基于改进遗传算法的解决方法。 在基于直观客户编码方式上提出改进的带有车辆编号和排序值的编码方式；在选 择方法上，将最优个体复制到下一代后对剩下的染色体采用了轮盘赌选择法；在 交叉算子上根据编码方式构造了性能较好的改进路径交叉算子；加快了算法的求 解效率和收敛速度。 最后，运用提出的改进遗传算法对有时间窗的多车场车辆调度模型进行了算 例分析与验证；并与传统处理方法及整体方法进行比较，通过实验分析，改进遗 传算法在求解效率和结果上都明显优于传统处理方法和整体方法。 关键词：城市配送；车辆调度问题；路径交叉算子；改进遗传算法；优化 a b s t r a c t w i t ht h ed e v e l o p m e n to fm a r k e te c o n o n l y ，l o g i s t i c s ，a s ”t h et h i r dh e a d s p r i n g0 f p r o f i t s ”h a sag r e a ti n f l u e n c eo nt h ea c t i o n0 ft h ee c o n o m y w h i c hc a u s e dp e o p l em u c h t h o u g h t f u lo f b u t ，w i t ht h ei n c r e a s i n gd e v e l o p m e n to fu r b a ne c o n o m ya n du r b a n s c a l e ，o u rc o u n t r y su r b a n d i s t r i b u t i o nd e m a n di sm o r ca n dm o r et h r i v e i nu r b a n d i s t r i b u t i o nb u s i n e s s ， t h ep l a n n i n g0 fv e h i c l er o u t i n gi nd i s n l b u t i o nw i l lt a k eg r e a t e f i c c to nt h ee f f c i e n c y ，c o s ta n db e n e f i t ，e s p e c i a l l yi nd i s t r i b u t i n gf o rm u l t ic o n s u m e r as c i e n t i f i ca n dr c a s o n a b l em e t h o dt ov e h i c i es c h e d u l i n gi sa ni m p o n a n to p e r a t i o ni n l o g i s t i cd i s t r i b u t i o n t h i sp a p e rh a sc a f r i e do na n a l y s ea r o u n dv e h i c l er o u t i n gp r o b l e m 0 fu r b a nd i s n j b u t i o na n dh a sd o n es o m er e s e a r c h e s ，w h i c hm a i n l yi n c l u d e st h en e x t c o n t e n t s ： f i r s t ，t h i sp a p e ra n a l y s e sr e l a t i v e dt h e o r yo fu f b a nd i s t r i b u t i o n ， i n t r o d u c e s d i s t r i b u t i o nm o d eo fm u l i t i d e p o t ，b u i l d st h em o d e lo fm u l t i - d e p o tv e h i c l es c h e d u l i n g p r o b l e mw i t l lt i m ew i n d o w sb a s e do nn a t u r a ld e s c r i p t i o n t h e r e a f t e r a i m砒 t h ep r o b l e m ，t h i sp a p e rc o n s t m c t e sa ni m p r o v e d g e n e t i c a l g o r i t h m ，w h i c hp u t si na ni m p m v e dc o d i n gm o d ew i t hv e h i c l e sc o d ea n ds o n v a l u e b a s e do ni n t u i t i o n a lc u s t o m e r ，sc o d e ；o nt h ec h o i c ew a y ，t h eb e s tc h r o m o s o m ew i nb e c o p i e dt 0t h en e x tg e n e r a t i o n ，t h e nt h er e s tc h r o m o s o m ew i l lb ec 托a t e dw i t hd i s h w a g e rc h o i c ew a y ； i ti n 仃o d u c e st h ew e l lp e r f o m a n c er o u t ec r o s s o v e ro p e m t o r a c c o r d i n gt ot h ec o d i n gm o d e ，w h i c he n h 柚c e ss o l v i n ge f ! f i c i e n c ya n ds p e e do ft h e a l g o r i t h m l a s t ，t h em u l i t i d e p o tv e h i c l es c h e d u l i n gp r o b l e m sm o d e l i st e s t e d 觚dv e r i f i e d w i t ht h ei m p r o v e dg e n e t i c a l g o r i t h mt h r o u g hd a t ae x p e r i m e n t a n dt h ei m p r 0 v e d g e n e t i ca l g o r i t h mc o m p a f e s w “ht m d i t i o n a l a l g o r i m ma n di n t e g r a t e da l g o r i t h m t h r o u g he x p e r i m e n ta n a l y s i s ， w h o s ee f f i c i e n c ya n dp e r f o 衄a n c ei s s u p e r i o r t o 仃a d i t i o n a la l g o r i t h ma n di n t e g f a t e da l g o r i t h m k e yw o r d s ：u r b a d i s t r i b u t i o n ；v e h i c i es c h e d u h n gp r o b l e m ；r o u t ec r o s s o v e r o p e r a t o r ；i m p r o v e dg e n e t i ca l g o r i t h m ；o p t i m i z a t i o n 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论又是卒人任导帅的指导下独立进行研究所取得的 研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均 已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。 作者签名：江刘量 日期：印年j 月z 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权长沙理工大学可以将本学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“”) 作者签名： 导师签名： 注飙墨 3 砷孬取f 日期。叼年s 月2 乙日 日期：砷岁月乙日 ， 第一章绪论 1 1 研究问题的提出及意义 1 1 1 问题的提出 城市是一个国家或地区的政治、经济和文化中心，是人类集中、高效率利用自 然资源、空间资源和智力资源创造物质文明和精神文明的载体，也是区域经济发展 的主要推动力，在区域经济发展中居支配和主导地位。随着市场经济发展步伐的加 快和城市规模的不断扩大，作为“第三利润源泉”的物流对经济活动的影响也日益 明显，其地位和作用显得比任何时候都更为重要。 城市化水平是物流业发展的一个重要条件，反过来物流产业的发展也伴随着城 市化。物流业的兴起，给城市的发展带来了新的商机和契机，城市的现代化必须以 物流的现代化为依托，城市的发展离不开城市物流的发展和完善。近年来，随着大 批量、少批次的物流配送活动逐步被小批量、多批次所取代，个性化、多样化的市 场需求越来越占有更多的市场份额，城市配送已成为现代物流活动的中心环节和最 终目的。可以说，城市配送是城市经济和商品市场发展的产物，同时，城市配送又 服务于城市经济，并且是城市经济的一个有机组成部分。 城市配送过程主要包括从配送终端即城市配送中心根据各个顾客的不同需求， 在配送中心将所需要的货物挑选出来配货；并考虑配送货物的质量和体积、充分利 用车辆的载重或容积来进行车载货物的配装从而确定配送车辆及路线的优化方案。 由于从事物流配送尤其是从事城市配送的汽车货运工作条件复杂，不仅货运点多、 货物种类繁多、道路网复杂，而且配送服务区内配送网点分布不均匀。因此，设计 合理、有效的车辆调度方案，尽量减少车辆数量和配送里程就成为非常实际的问题。 配送中心作业的重点是如何有效的使用车辆并决定最经济的行驶路线，使商品能够 在最短的时间内送达顾客手中。 本文所要研究的正是上述城市配送中车辆调度的优化问题，即对于一系列装货 点和( 或) 卸货点，组织合适的行车线路，使卸货车辆有序地通过它们，在满足一 定的约束条件( 如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限 制、时间限制等) 下，达到一定的目标( 如里程最短，费用最少，时间尽量少，使 用车辆数量尽量少等) 。通过制定合理的配送路径，迅速而经济地将货物送到客户 手中，实现对车辆合理有效的利用，从而节省大量的时间和成本。 根据我国城市的发展进程得知，我国的城市规模都比较大，并且交通拥挤，再 者城市配送均为短距离、短时间、多客户的配送，则单车场难以保证配送的及时性 并会导致配送成本的增大，多车场是解决这一问题的有效途径。有时间窗约束的多 车场车辆调度问题( m u l t i p l e - d e p o tv c h i c l es c h e d u l i n gp r o b l e mw i t ht i m ew i n d o w s m d v s p t w ) 更加符合城市配送车辆调度的特点。并且在城市配送范围内，多车场 车辆调度问题的应用也越来越广泛，如在传统汽车配送领域的牛奶配送、生鲜食品 配送、垃圾车辆线路优化、连锁店送货线路安排等。从配送成本上考虑，在规模较 大的城市内单一配送中心的成本也比较高。多数物流公司一般都会在一个大中型城 市设立多个配送中心。 因此在提出配送车辆调度问题优化研究的基础上，本论文进一步明确了研究的 问题：如何降低城市配送费用，提高城市配送效率是城市配送研究的直接目的，而 多车场带时间窗的车辆调度优化问题在城市配送中起到了举足轻重的作用，正是本 论文所要研究的问题。 1 1 2 研究的意义 在配送活动中，送货是核心。在物流活动中，送货的实际形态就是货物的运输。 但是配送运输与通常的远途运输有很大的区别，通常的远途运输是区域与区域之间 的运输；而配送运输是短途运输，通常面对众多的用户，适合批量小、种类多的商 品运送，因此配送运输路线短但繁杂。同一线路往返次数多且线路较为固定，即使 一条线路一次节约费用不多，但由于次数多乘数大，总费用能降低很多。合理规划 配送运输路线对配送成本的影响要比一般运输大得多，配送路线的合理与否对配送 速度、成本、效益以及客户的满意度影响很大，因此，设计合理、有效的车辆路线 方案，对企业和社会都具有十分重要的意义。 对企业而言：( 1 ) 优化配送路线，可以提高配送效率，对配送车辆做到物尽其 用，尽可能的降低货物单位配送成本。( 2 ) 通过为配送设定固定的路线，安排固定 的车辆和司机，可方便客户收货的安排和联络。通过特定车辆路线，可满足客户的 特殊送货要求，提供个性化的配送服务，能极大地提高客户满意度。( 3 ) 有利于企 业提高效益。 对社会而言，合理的安排车辆路线，会使配送运输合理化，消除不合理的现象， 节省运输车辆，缓解交通紧张状况，减少噪声、尾气排放等运输污染，为保护生态 平衡、创造美好家园作出贡献。 几乎所有的城市物流运输都是利用道路实现的。因为一方面道路运输能提供比 铁路运输更便捷的、低费用的和高水平的配送服务；另一方面，城市物流越来越多 地倾向于短距离和短时间运输。只有道路运输方式可以满足这一要求，但是城市物 流运输给城市交通带来的高负荷、多拥挤以及交通污染使得城市交通管理部门越来 越多地对货物运输车辆实施交通限制管理。这对城市物流的发展无疑会带来负而影 响，如何在城市货运车辆通行管制约束下合理有效地指派配送车辆的装载和走行路 径，是城市物流调度部门急需研究解决的问题。 本文在认真分析国内外v s p 研究的基础上，提出了城市配送范围下的带时问 2 窗的多车场v s p ，这是针对配送终端提出的城市范围的研究并对m d v s p t w 进行 数学建模，根据模型分析知，多配送中心的车辆路径优化模型是复杂的，综合性强 的n p 问题，许多物流专家对类似模型的优化求解方法孜孜以求。而解决优化方面 的问题，遗传算法具有很大的优势。在此，将新的改进遗传算法运用到建立的模型 中，通过c + + 语言编程实现，说明该算法可以有效地求得m d v s p t w 的优化解， 是求解v s p 的一个较好方案。这对物流配送企业实现配送线路优化、降低成本和 提高物流经营管理水平、更快的响应顾客、最终增加企业的竞争力具有重要的参考 价值。 1 2 国内外研究现状 1 2 1 国内外配送业发展现状 ( 1 ) 国内配送业发展现状 我国政府部门有组织、有计划地推动商品物流配送工作，是从2 0 世纪9 0 年 代初开始的。经过多年的发展，我国配送业在配送规模、配送形式、配送设施设备 以及配送服务等各发面都已经得到了一定程度的发展。 上海已有大小配送中心上百家，主要是各连锁公司、便利公司、专卖店公司和 各行各业内部的配送中心。具有一定规模的配送中心主要有华联、农工商等几家大 型超市公司。 北京市已初步形成以大型物流基地为核心，综合性物流配送区和专业性物流配 送区为节点的，覆盖全市、辐射全国的物流网络体系框架，基本形成了两家年配送 额6 0 8 0 亿元的现代化物流配送集团。 截至2 0 0 3 年7 月，深圳市登记注册经营含仓储、配送业务的企业共8 9 7 家。 列为重点商贸流通配送企业有3 0 多家，物流配送品种近两万种。随着以第三方物 流业务和第四方物流业务为重点的综合型专业物流企业迅速成长，推动了包括采购 分拨、批发配送、展览配送、拍卖配送、代理批发和网络批发等物流配送业务和专 业市场的快速发展，一些物流企业开始为全球著名跨国公司提供专业物流服务，跻 身全国同行前列，为深圳现代物流业发展迈出了坚实步伐。 近年来，随着连锁商业的发展，配送中心的建设受到重视，特别是连锁企业自 建配送中心的积极性很高。 ( 2 ) 国外配送业发展现状 物流配送在发达国家已有几十年的历史，目前配送中心、加工中心等物流中心 遍布整个美国、日本和西欧。一些发达国家现已基本上构筑起了不同层次的物流配 送体系。 美国的物流配送业发展起步早，经验成熟，尤其是信息化管理程度高，从2 0 世纪6 0 年代起，商品配送合理化在发达国家普遍得到重视。为了向流通领域要效 3 益，美国企业采取了以下措施：一是将老式的仓库改为配送中心；二是引进电脑管 理网络，对装卸、搬运、保管实行标准化操作，提高作业效率；三是连锁店共同组 建配送中心，促进连锁店效益的增长。美国连锁店的配送中心有多种，主要有批发 型、零售型和仓储型三种类型。 在日本，零售业是首先建立先进物流系统的行业之一。便利店作为一种新的零 售业迅速成长，现已遍及日本，正影响着日本其他零售商业形式。这种新的零售业 需要利用新的物流技术，以保证店内各种货物的供应顺畅。日本的物流配送具有以 下特点：第一，分销渠道发达。许多日本批发商过去常常把自己定位为某特定制造 商的专门代理商，只允许经营一家制造商的产品。为了保证有效地供应商品，日本 许多物流公司不得不对旧有的分销渠道进行合理化改造，更好地做到与上游或下游 公司的分销一体化。第二，频繁、小批量进货。日本的物流配送企业的很大一部分 服务需求来自便利店，便利店依靠的是小批量的频繁进货，只有利用先进的物流系 统才有可能发展连锁便利店，因为它使小批量的频繁进货得以实现。第三，物流配 送体现出共同化、混载化得趋势。共同化、混在化货物配送使原来按照不同生产厂、 不同商品种类划分开来得分散得商品物流转变为将不同厂家的产品和不同种类的 商品混合起来配送的聚合商品物流，从而得以发挥商品物流的批量效益，大大提高 了配送车辆的装载率。第四，合作型物流配送。在日本，生产企业、零售企业与综 合商社、综合物流公司之间基本上都存在一种长期的物流合作关系。并且这种合作 关系还随着日本工业生产的国际化延伸到国外。第五，政府规划在现代物流配送发 展过程中具有重要作用。 在欧洲各国，尤其是德国，物流配送是指按照用户的订货要求，在物流据点进 行分货、配货以后，将配好的货物送交收货人的活动。德国的物流配送产业是第二 次世界大战以后，随着现代科技的兴起和经济的高速发展而逐步发展起来的。特别 是近1 0 年来，德国的物流配送已经摒弃了商品从产地到销地的传统配送模式，基 本形成了商品从产地到集散中心，从集散中心( 有时通过不止一个集散中心) 到达 最终客户的现代模式。整个德国，可以说德国的配送已经形成了以最终需求为导向， 以现代交通和高科技信息网络为桥梁，以合理分布的配送中心为枢纽的完备的运行 系统。在总结德国零售业发展的经验时可以看出德国是十分重视按照连锁经营的规 模和特点来规划配送中心的，往往是在建店的同时就考虑了配送中心的建设布局。 发达国家的配送已经成为了制造商和经销商普遍接受和采用的物流方式，而且 还在迅速发展。主要表现在以下几个方面：配送的规模日趋扩大，配送中心的数 量明显增加。配送技术和设备更加先进。配送方式多样化。配送服务质量明 显提高。 1 2 2 国内外车辆调度模型研究现状 配送车辆的优化问题一般可根据空问特性和时间特性分为车辆路径规划问题 4 和车辆调度问题。当不考虑时间要求，仅根据空间位置安排车辆的线路时称为车辆 路径规划问题( v i 心一v e h i c l er o u t i n gp r o b l e m ) ；考虑时间窗要求安排运输线路时称 为车辆调度问题v s p ( v s p v e h i c l es c h e d u l i n gp r o b l e m ) 。某些学者将有时间要求的 车辆路径规划问题称为v e h i c i 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 的基础上，车辆路径问题在学术研究和实际应用上产生了许多不 同的延伸和变化型态，包括t s p ( 可看作v i 冲的一个特例，即当v r p 只包括一条 路径，且没有能力约束时就成为t s p ) 、带能力约束的车辆路径问题( c a p a c i t a t e d v e h i c l er o m i n gp r o b l e m s ，c v l 冲) 、带时间窗的车辆路径问题( v e h i c l er o u t i n g p m b l e m s w i t ht i m 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 s1 ) i ，i t hd e f i n e dt i m e ，v r p d t ) 、多车型车辆路径问题( f l e e ts i 柚dm i xv e h i c l er o u t i n gp r o b l e m s f s v r p ) 、车辆多次使用的车辆路径问题( v c h i c l e r o u t i n gp r o b i e m sw i t hm u i t i p l eu s eo fv e h i c l e ，v r p m ) 、考虑回路的车辆路径问题 ( 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 跚l s ，v r p b ) ，随机需求车辆路径问题( v e h i c l e r o m i n gp r o b l e mw i t hs t o c h a s t i cd e m 柚d ，v r p s d ) 、动态车辆路径问题( d y n 锄i c v 曲i c l er o m i n gp r o b l e m sd v r p ) 、满载，非满载v r p 、双向v r p ，多车场带时间窗的 车辆调度问题( m u l t i p l e d e p o tv c l l i c l es c h e d u l i n gp r o b l e mw i t ht i m ew i n d o 、w ， m d v s p t w l ”。 根据上述v r p 的提出及研究的不断发展，目前国内外学者研究的有以下几种 模型： ( 1 ) 带车辆容量约束的单车场v r p ( c a p a c i t a t e dv e l l i c l er o u t i n gp r o b l e m c v l 疆) 。即任意车辆在服务客户过程中负载不能超过该车辆总负荷，费用函数为总 路程或总时间，目标为使总路程数最小或总时间最短，这是一类比较基础的v r p 哺1 。 ( 2 ) 带时间窗的车辆路径问题( v c h i c l er o u t i n gp r o b i e m w i t ht i m e w i n d o w s ，v r p t w ) 。服务顾客户须在各自要求的时间窗口【e ；，l 。】内进行服务，否 则将被拒绝服务( 硬时间窗) 或交付惩罚费用( 软时间窗) ；同时配送中心也有时间窗， 即发车时间和收车时间。惩罚费用将以等待费用，误工费用，加班费等形式体现”1 。 ( 3 ) 多车型车辆路径问题( m i x e d m e t e r o g e n e o u sf l e c tv c h i c l er o u t i n g m f v r p m f v r p ) 。车型不同，则载重量、车辆折旧费、燃油费、维修费、路桥费 也会不同，设计模型均须将此考虑在内“”。 ( 4 ) 多车场车辆路径问题( m u l t i p l e d e p o t v 乩i c l ei b u t i n gp r o b l e m ) 。多个车 场可发出和接收车辆，各车场协调派车到货场完成配送任务，设计模型考虑各车场 派出车辆数不大于各车场的车辆总数，车辆须回到原车场，车辆须从车场出发1 。 ( 5 ) 带回程运输的车辆路径问题 ( v c h i c l er o u t i n g p r o b l e mw i t h b a c l d l a u l s ，v r p b ) 。这种类型中，为不使车辆超载，当一条线路同时存在去程客户 和回程客户时，须先服务该路线所有去程客户后再服务回程客户“”。 5 ( 6 ) 分割送货车辆路径问题( v e h i c l er o u t i n gp r o b i e mw i t hs p l i td e l i v e r i e s v r p s d ) 。这种类型中，可由多辆车服务同一个客户，从而提高车辆载重利用率“”。 ( 7 ) 开放式车辆路径问题( o p e nv c h i c l er o u t i n gp r o b l e m ，0 v r p ) 。这是一类比 较难解决的v r p ，通常与多配送中心问题结合求解更有意义。它的主要特点是车 辆配送完成任务后有三种选择：或者停留在最后一个服务客户处，或者返回原配送 中心，或者返回就近的其他配送中心“。 ( 8 ) 随机需求车辆路径问题( v e h i c l er o u t i n gp r o b l e mw i t hs t o c h a s t i cd e m a n d ， v r p s d ) 。考虑的是随机顾客和随机需求量车辆路径问题的模型，设计模型假设顾 客需求不可分割n ”。 ( 9 ) 动态随机车辆路径问题( v e h i c l er o u t i n gp r o b l e mw i t hd y n a m i c s t o c h a s t i c ) 。这类问题的研究比随机车辆路径问题更为复杂，在以往的研究中，动 态随机v r p 的建模方法主要有m a r k o v 决策、排队沦和网络方法。其中： m a r k o v m i n k o 行提出了一类求解动态调度问题的m a r k o v 决策模型“；s w i h a r t 等提 出了求解单车辆装卸混合问题的排队论模型“”；b e r t s i m a s 等提出的求解动态旅行 修理员问题和多车辆有容量约束的动态车辆路径问题的排队论模型“”以及p a l e t t a 提出的求解动态旅行商问题的网络模型“”。 ( 1 0 ) 多目标的车辆路径问题( m u l t i o b i e c t i v ev e h i c l er o u t i n gp r o b l e m ) 。这类问 题起源于许多复杂系统的设计、建模和规划问题。郭伏等建立了以到达时间准时为 主要目标，以总成本最低次之的多目标定位运输路线安排问题模型1 。 1 2 3 国内外车辆调度模型求解算法研究现状 求解物流配送车辆调度问题的方法很多，究其实质，可以分为精确算法和启发 式算法两大类。目前国内外研究v s p 的求解算法已有不少文章： 精确算法指可求出其最优解的算法，主要有：( 1 ) 分枝定界算法( b r a n c ha n d b o u n d ) ，分枝定界算法由l a p o r t e 等人提出，k r a l p h s ，l k o p m a n 用并行分枝 分割算法得到了t s p 和c v r p 较为满意的解瞻”。( 2 ) k 阶中心树和相关算法，1 9 8 1 年，c h r i s t o f i d e s 等人提出了k 度中心树和相关算法，对固定车辆数的m t s p 进行k 度中心树松弛算法求解瞪”。( 3 ) 动态规划法。1 9 7 1 年，e i l o n 等人提出将动态规划 法用于固定车辆数的v r p ，通过递归方法求解了该模型扭”；c h r i s t o f i e d 用动态规 划放宽空间变量，可求解有5 0 个客户的v r p ”“；1 9 8 0 年，p s a r a n i s 在解决动态单 车辆d i a l a r i d e 问题时，采用基于l a g m n g i a n 松弛和乘子调整技术的静态算法，当 输入发生更新，采用动态规划重新优化o ”。( 4 ) 集分割和列生成法。1 9 6 2 年，b a l i n s k i 等人首先提出v r p 的集分割直接考虑可行解集合，在此基础上进行优化，求解了 最简单的v r p 模型“；r a o “7 1 等人引入了列生成方法进行求解，其本质为最短路 径算法结合分枝定界算法。 6 精确算法基于严格的数学手段，在问题可求解的情况下，计算结果优于启发式 算法，但由于无法避免计算量的指数爆炸问题，精确算法只能有效地解决小规模的 v l 冲，各算法所适用的问题特点也不同。 启发式算法是在状态空间中的改进搜索算法，它对每一个搜索位置进行评价， 得到最好的位置，再从这个位置进行搜索直到目标。由于v r p 是强n p 难题，高 效的精确算法存在的可能性不大，为此要构造高质量的启发式算法。现有文献中提 出的启发式算法有以下几类：( 1 ) c l a r k e w r i g h t 节约算法。由c l a r k 和w r i g h t 提出， 用来解决车辆数不固定的v r p ：而在1 9 6 9 年，t i l l m 锄第一次提出了基于c w 节 约算法的随机需求量车辆路径问题的算法，当车辆空使或超载时处以惩罚”。 ( 2 ) s w p 算法。1 9 7 4 年，w r e n ，g i l l e t t 等人提出s w e e p 算法( 扫描法) 用于求解简 单v r p 问题乜”；最近，郎茂祥采用此方法将多配送中心车辆调度问题分解为多个 单配送中心问题进行求解并得到了验证”。( 3 ) 两阶段算法。f i s h e 提出用两阶段 优化方法解决带有时间窗的v r p 问题“。( 4 ) 禁忌搜索( t a b us e a r c ht s ) 。l a p o n e 用禁忌搜索提高了求解v r p 问题的精度。“；t a i l l a r d 。3 1 按角度和路径重心，对问 题的空间进行分割，再用禁忌搜索结合模拟退火算子问题求解，实现求解的并行化； 1 9 9 9 年，国内学者张涛等用禁忌搜索和3 o p t 组合优化方法解决多车队运输调度问 题”；钟石泉等人提出一种多车场的智能处理方法，利用禁忌算法优化了容量约 束的多车场配送路线问题o ”。( 5 ) 模拟退火算法( s i m u l a t e d a 蚰e a l i n g ) 。它是基于 m o m e c a r l 迭代求解思想的随机搜索算法，t e o d o r o v i 【3 8 1 等人利用模拟退火算法求 解v r p 中的无时间窗单向问题；2 0 0 4 年，蔡延光等用模拟退火和禁忌搜索求解带 时问窗的多重运输调度问题。”。( 6 ) 遗传算法( g e n e t i ca l g o r i t h mg a ) 。1 9 9 3 年， j o e 【3 耵用遗传算法求解了v r p t w ，但是存在“早熟收敛”的问题；2 0 0 0 年，谢秉 磊等人将货运量约束和时间窗约束转化为目标约束，设计了基于自然数编码的可同 时处理软、硬时间窗约束的遗传算法，实验分析获得了较好的结果”；张丽萍等 人通过引入新颖交叉算子，构造了一种改进遗传算法来求解单一配送中心的 v r p t w “”；邹彤，李宁等根据车辆行驶路径最短建立了多车场车辆路径( m d v r p ) 模型。提出了一种新的遗传算法编码表示，并用遗传算法直接对模型进行了求解 “。( 7 ) 混合遗传算法。郎茂祥，胡思继用遗传算法结合爬山算法构造混合遗传算 法求对简单v r p 模型进行求解，证实得到的结果比遗传算法求得的结果要优“”。 张建勇等人通过引入决策者主观偏好的概念，提出了解决模糊需求信息条件下 v r p 的一种基于模糊可能性的混合遗传算法，并在最小化车辆行驶距离的目标下， 通过随机模拟研究了决策者的主观偏好对最终决策目标的影响“。( 8 ) 蚁群算法。 b e m db u l l n h e i m “”等利用简单a c o ，求解了较大规模带时间窗的v r p ；陈幼林等 用改进蚁群算法将v r p t w 转化为t s p 进行了求解用实例验证了方法的可行性h ”。 国外几位专家对多配送中心车辆调度问题进行了研究，并取得了一些很有价值 7 的研究成果。其中，g u yd e s a u l n i e r s 等研究了有时间窗的多配送中心车辆调度问 题”；t a i h s iw u “6 1 等人将多配送中心车辆调度问题分解成两个子问题：多配送中 心的选址问题和一般的单配送中心车辆调度问题；s t e f a ni r n i c h 研究了多车型取送 混合的多配送中心车辆调度问题“”。而国内对配送车辆调度问题的研究主要集中 在单配送中心问题上，对多配送中心车辆调度问题的研究相对较少。国内较有影响 的学者李军，郭辉煌”在2 0 0 1 年将多配送中心的车辆调度问题用s 霄e e p 算法转化 为单车场问题进行了研究；天津大学钟石泉等人提出一种多车场的智能处理方法， 利用禁忌算法设立虚拟车场从整体上优化了多车场配送路线问题姐”：用遗传算法 进行优化研究的基本为单车场v r p 问题，仅有周彤等“采用遗传算法对无时间窗 限制的以距离最短为目标函数的多车场车辆调度问题进行了优化。 1 3 主要研究内容及方法 根据城市配送系统中配送中心数目的多少，城市配送车辆调度问题有单配送中 心问题和多配送中心问题之分。在现实城市配送体系中，常常出现多个配送中心的 情况。因此，对多配送中心车辆调度问题的研究具有重要的现实意义。考虑到国内 对配送车辆调度问题的研究主要集中在单配送中心问题上，对多配送中心车辆调度 问题的研究相对较少，且研究方法多采用传统的处理方法。因此，本文在研究国内 外车辆调度优化问题的模型及算法的基础上，提出了城市配送范围下的车辆调度优 化问题，并拟采用定性分析和定量分析相结合的方法，构建了城市配送范围下的多 车场带时间窗的v s p 模型，运用改进遗传算法对模型进行寻优，确定整个运营配送 网络的配送线路和配送车辆，达到车辆调度优化的目的。主要研究内容如下： ( 1 ) 通过参阅大量国内外研究文献，了解国内外物流配送中v s p 的模型及求 解方法，为本文模型的提出和求解奠定理论基础； ( 2 ) 描述本文模型研究的问题，根据特殊的配送条件即在城市范围内，短距 离的配送下，设立一定的假设条件再结合实际，建立带时间窗多车场车辆调度问题 的数学模型。 ( 3 ) 将建立的车辆调度模型看作一个复杂的组合优化问题，根据求解问题的 特征及常用求解算法的比较分析，提出新的求解算法即改进遗传算法，对编码方式 及交叉算子进行改进设计算法。用c + + 语言对算例编写程序对模型求解，确定各个 配送中心服务的客户及配送车辆的行驶路线。 1 4 本章小结 本章首先介绍了论文的研究背景及意义，结合当前国内外配送业的发展现状， 提出了城市配送发展的重要性。同时通过国内外车辆调度问题模型及求解算法研究 现状的分析，确定了论文的研究内容、主要研究方法和研究思路。 第二章城市配送相关问题分析 2 1 配送的分类分析 所谓配送就是按照客户的订货要求和时间计划，在物流节点( 仓库、商店、货 运站、物流中心等) 进行分拣、加工和配货等作业后，将配好的货物送交收货人的 过程。 配送是物流中一种特殊的、综合的活动形式，是商流和物流的紧密结合。配送 几乎包括了所有的物流功能要素，是物流的一个缩影或在某小范围内全部物流活动 完成将货物送达的目的；特殊的配送还要进行加工活动。它的目标指向是安全、准 确、优质服务和较低的配送费用。 按照不同方式配送可分为四类。 ( 1 ) 按配送组织者不同可以分为： 配送中心配送：组织者是专职从事配送的配送中心。规模较大，储存量也较 大，可按配送需要储存各种商品。配送中心专业性强，和用户建立固定的配送关系， 一般实行计划配送，所以，需配送的商品往往都有自己的库存，很少超越自己经营 范围。配送中心的建设及工艺流程是根据配送需要专门设计的，所以配送能力大， 配送距离较远，配送品种多，配送数量大，可以承担工业企业生产所需主要物资的 配送，配送中心配送是配送的重要形式。 商店配送：组织者是商业或物资的门市网点。主要承担零售，规模一般不大， 但经营品种较齐全。除日常零售业务外，还可根据用户的要求将商店经营的品种配 齐，或代用户外订外购一部分商店平时不经营的商品，和商店经营的品种一起配齐 送达用户。配送实力很有限，往往只是小量、零星商品的配送，配送半径也较短， 所以更为灵活机动，可承担生产企业重要货物的配送和对消费者个人的配送，是配 送中心配送的辅助及补充形式。 ( 2 ) 按配送服务范围可分为： 城市配送：城市配送亦即只能向城市范围内的众多用户提供的配送服务。由 于在城市范围内，货物的运距比较短，因此，这类物流配送在从事( 或组织) 送货活 动时，一般都使用载货汽车。又由于使用汽车配送机动性强、供应快、调度灵活， 因此，在实践中依靠城市配送中心能够开展少批量、多批次、多用户的“门到门” 配送活动。 区域配送：这是一种以较强的辐射能力和库存准备，向省际、全国乃至国际 范围的用户进行配送的物流活动。美国沃尔玛公司属下的配送中心，荷兰n e d l l o y d 集团所属的“国际配送中心”，以及欧洲其他国家批发公司所属的配送中心( 如： 9 瑞典n a g 公司所属乔鲁德市布洛配送中心) 开展的就是这种区域配送。 区域物流 配送有三个基本特征：其一，经营规模比较大，设施和设备齐全，并且数量较多、 活动能力强。其二，配送的货物批量比较大而批次较少。其三，在配送实践中，区 域配送中心虽然也从事零星的配送活动，但这不是它的主要业务。很多区域配送中 心常常向城市配送中心和大的工商企业配送商品，因而，这种配送中心是配送网络 或配送体系的支柱。 ( 3 ) 按配送时间及数量分有： 定时配送( 时配送) 规定的时间间隔进行配送，每次配送的品种及数量可以 事前拟定长期计划，也可以配送之前以商定的联络方式( 如电话、计算机终端输人 等) 进行通知。 定量配送：按规定的批量进行配送，但不严格确定时间，只是规定在一个指 定的时间范围中配送。 定时定量配送：规定准确的配送时间和固定的配送数量进行配送。 定时、定路线配送：在确定的运行路线上制定到达时间表，按运行时间表进 行配送，用户可在规定路线站及规定时间接货。 即时配送：不预先确定不变的配送数量，也不预先确定不变的配送时间及配 送路线，而是完全按用户要求时间、数量进行配送的方式。 ( 4 ) 按配送货物种类分有： 家电配送；化妆品配送；医药品配送；日用品配送；新鲜食品配送； 服饰产品配送；汽车零件配送；电子产品配送；书籍产品配送等等。 2 2 城市配送概念分析 ( 1 ) 城市配送( c i t yd i s t r i b u t i o n ) 城市配送亦即只能向城市范围内的众多用户提供的配送服务。由于在城市范围 内，货物的运距比较短，因此，这类物流配送在从事( 或组织) 送货活动时，一般都 使用载货汽车。又由于使用汽车配送机动性强、供应快、调度灵活，因此，在实践 中依靠城市配送中心能够开展少批量、多批次、多用户的“门到门”配送活动。 因为城市配送中心的服务对象多为城市圈内的零售商、连锁店和生产企业，所 以，一般来说，它的辐射距离都不远。在流通实践中，城市配送中心是采取与区域 配送中心联网的方式运作的。当前，我国一些试点城市所建立或正在建立的配送中 心( 如北京食品配送中心、无锡市各专业物资配送中心) 绝大多数都属于城市配送 中心。在国外，有很多配送中心也属于城市配送中心。 ( 2 ) 配送网络( d i s t r i b u t i o nn e t w o r k ) 配送网络是由顶点( 指配送中心、客户、停车场等) 、无向边和有向弧组成的， 边、弧的属性包括方向、权值和交通流量限制等。配送网络中边或弧的权值可以表 l o 示距离、时问或费用。边或弧的权值变化可分为以下几种情况： 固定，即不随时间和车辆的不同而变化； 随时间而变化； 随车辆不同而变化； 既随时间不同而变化，又随车辆不同而变化。 对配送网络权值间的关系可以要求其满足三角不等式，即两边之和大于第三 边。也可以不加限制。配送网络见示意图2 1 。 图2 1配送网络不惹图 ( 3 ) 城市配送网络( c i t yd i s t r i b u t i o nn e t w o r k ) 本文中定义的城市配送网络，是由城市中配送活动的集结点( 包括配送中心、 客户设施) 和能够将这些节点连接起来的交通、通讯干线( 配送中心与客户之间的 直达配送路线、客户与客户之间的车辆运行线路) 所组成。节点活动的场所( 节点) 包括配送中心、客户、物品的供方和需方；线路活动是运输工具在配送线路上的运 动形成的，它反映了节点之间物品的传递关系。所以配送网络通常用节点和节点之 间物品的传递关系来表示。本文正是