（系统工程专业论文）复杂约束车辆调度模型与算法研究.pdf

复杂约束车辆调度模型与算法研究 摘要 在经济全球化和信息化的浪潮中，现代的物流业已经从为社会提供传统的运 输服务，扩展到以现代科技、管理和信息技术为支柱的综合物流系统。随着信息 技术的发展，物流调度的优化问题已成为研究的一个热点问题。车辆路径问题装 卸货问题及其所属的物流调度问题的研究从上个世纪六十年代就开始已经开始。 经过近半个世纪的研究先后提出了t s p 、v r p 、p d p 等问题，并针对性的提出了 多种算法取得了一定的成果。本文首先讨论了在实际应用中的车辆调度优化理论 和方法，总结分析了近二十年v r p 研究所取得的一些成果，包括算法的原理和适 用范围，对该问题的精确解法和启发式解法进行了分析比较。然后在这个基础上， 探索了在现实的复杂的约束、目标函数下的车辆调度模型和算法。主要的工作有 以下几方面： 1 分析了现实物流配送系统的业务流程和存在的问题，分析了现实问题中存在 的复杂约束和目标。并结合现实的需求，建立了配送车辆路径调度问题的一 般模型。为下一步算法的展开打下了基础。 2 根据该问题的特点，提出了一种道路网络自动生成算法以得到更加贴近现实 的算例。然后基于道路网络信息，设计了一种多层次的优化算法，先在基础 地理信息数据上进行预处理，并采用稀疏矩阵压缩技术、离线搜索、建立最 佳路径库等方法，大大提高了算法的效率和灵活性。 3 分析了现实问题的复杂约束和目标，建立了车辆调度问题的形式化模型，包 括简单约束模型和复杂约束的模型。根据各个层次的模型，提出了改进的节 约算法求解问题。然后提出了一种基于字典序的剪枝搜索算法实现了对复杂 约束问题的高效率搜索。并对算法的性能作了深入的分析与比较。 4 在v r p 问题的基础上研究了装卸货问题区别v r p 和p d p 的不同。并对实际 的时间窗约束的装卸货问题做了重点研究，基于解决v r p 问题的同样思想， 提出了全局优化的剪枝搜索算法。 5 ，针对大规模的v r p 问题和p d p 问题，在分析了精确解法种种局限性之后引入 了聚类思想。讨论了基于欧氏距离定义的聚类算法的局限性，提出了一种基 浙江大学硕士学位论文 v 于最短路径的聚类算法。并和全局优化的搜索算法结合，提高了v r p 和p d p t w 问题的求解规模和效率，同时详细分析了算法的性能和效果。 关键词：物流配送车辆调度问题优化模型时间窗全局优化启发式算法聚类 分析 v i 复杂约束车辆调度模型与算法研究 a bs t r a c t w i t ht h eg l o b a l i z a t i o na n di n f o r m a t i o no ft h e e c o n o m y ，m o d e r nl o g i s t i c sh a s e x p a n d e d f r o m p r o v i d i n g t h e s o c i e t y t r a d i t i o n a l l r a n s p o r t a t i o n s e r v i c et ot h e i n t e g r a t e dl o g i s t i cs y s t e mw i t ht h es u p p o r to fm o d e ms c i e n c e ，i n f o r m a t i o nt e c h n o l o g y a n d m a n a g e m e n t v e h i c l es c h e d u l i n gi st h ek e yp r o b l e mi nt h el o g i s t i c ss c h e d u l i n g i t c a n o p t i m i z et h ew h o l es y s t e ma n dm a k e f u l lu s eo f t h er e s o l l r c eo f t h es y s t e m w i t h p o p u l a r i z a t i o no f i n t e r n e ta n d d e v e l o p m e n t o fe l e c t r o n i cc o i n l 2 q e r c e ，v e h i c l er o u t i n g p r o b l e m r p ) a n d t h e p i c k u p a n d d e l i v e r yp r o b l e m ( p d p i a t et h et w o s u b p r o b l e m sf o c u s e d o nr e c e n t l y w e p e r f o r m at h o r o u g hr e s e a r c ho f t h e s e i m p o r t a n t p r o b l e m si n t h e l o g i s t i cs c h e d u l i n g f o c u s i n go nt h em o d e l sa n da l g o r i t h m so f p h y s i c a l d i s t r i b u t i o nv e h i c l e r o u t i n gp r o b l e m s ，t h i s t h e s i s m a i n l y i n c l u d e st h e f o l l o w i n g c o n t e n t s ： o nt h eb a s i so f a n a l y z i n g t h ee l e m e n t so f p h y s i c a l d i s t r i b u t i o nv e h i c l e s c h e d u l i n gs y s t e m a t i c a l l y ，t h i st h e s i sb u i l d st h em o d e lo fv e h i c l e sr o u t i n gp r o b l e m w i t h o u tt i m ew i n d o w sa n dw i mt i m ew i n d o w s t h e c o m p l e x c o n s t r a i n t sa n d o b j e c t i v e f u n c t i o n sw e r ei n c l u d e di nt h em o d e l a st h ei n f o r m a t i o no fr o a dn e t w o r ki st h ef o u n d a t i o no ft h ea l g o r i t h m s ，w es e t f o c u so nt h ec o n s t r u c t i o na n da b s t r a c t i o no ft h et o p o l o g i c a ls t r u c t u r eo fr e a l i s t i cr o a d n e t w o r k a na u t o m a t i cc o n s t r u c t i o nm e t h o da n dap r e p r o c e s sa l g o r i t h mw a sb u i l ti n t h et h e s i s t h es a m p l ei n s t a n c e sw e r eb u i l tu s i n gt h ea u t o m a t i cc o n s t r u c t i o nm e t h o d w i t ht h ep r e p r o c e s sa l g o r i t h m ，t h el i b r a r yo fs h o r t c u tr o u t ec a nb ea c h i e v e d ，a n dt h e e f f i c i e n c ya n df l e x i b i l i t yo f t h es o l v i n g p r o c e s sw a si m p r o v e dr e a s o n a b l y w i t ht h em o d e lo fv r p t h ec o m p l e xc o n s t r a i n t sw e r ea n a l y z e d i na d d i t i o n ，t h e h e u r i s t i c a l g o r i t h m n a m e dm o d i f i e dc w a l g o r i t h m w a s p u t f o r w a r d a st h i s a l g o r i t h mc a n n o te n s u r et h eq u a l i t yo f t h er e s o l u t i o n , ag l o b a lo p t i m i z a t i o na l g o r i t h m n a m e dm o d i f i e de x h a u s ts e a r c hw a s p u tf o r w a r di nt h i st h e s i s f u r t h e r m o r e ，t h ed e t a i l o fa l g o r i t h mf o rs o l v i n gd e l i v e r yv e h i c l er o u t i n gp r o b l e mw i t l lc o m p l e xc o n s t r a i n t s 浙江大学硕士学位论文v 1 1 w a sd e v e l o p e d n u m e r i c a lr e s u l t so ns a m p l ei n s t a n c e sd e m o n s t r a t et h ev a l i d i t ya n d e f f i c i e n c yo f t h eg l o b a lo p t i m i z a t i o na l g o r i t h m p d pi sa n o t h e ri m p o r t a n tp r o b l e mi nt h el o g i s i cs c h e d u l i n gp r o b l e m i ti st o a r r a n g et h eo p t i m a lr o u t e sf o raf l e e to fv e h i c l e st os a t i s f yt h er e q u i r e m e n t so f t h e c u s t o m e r s o nt h eb a s e o ft h em o d e lw i t h c o m p l e xc o n s m n t s ，t h eg l o b a l o p t i m i z a t i o na l g o r i t h mw a sd e v e l o p e d a f t e rt h ea n a l y s i so ft h ee x a c ta n dh e u r i s t i ca l g o r i t h m st ov r pa n dp d p t h e c l u s t e r i n gm e t h o dw a su s e dt os o l v et h ea b o v et w op r o b l e m s c l u s t e ra n a l y s i sw a s u s e dt o g a t h e rt h ec u s t o m e r sc l o s et o e a c ho t h e ra n dc o n s t r u c tt h ei n i t i a ls o l u t i o n r o u t e s t h eg l o b a lo p t i m i z a t i o na l g o r i t h mw a se x p l o i t e dt o g e tt h eg l o b a lo p t i m u m s o l u t i o nf o re a c hc l u s t e r t h em e t h o di m p r o v e st h es c a l ea n de f f i c i e n c yo fv r pa n d p d p t w n u m e r i c a lr e s u l t so ns o l o m o nb e n c h m a r k p r o b l e m s d e m o n s t r a t et h e v a l i d i t ya n de f f i c i e n c yo f t h ei m p r o v e dg l o b a la l g o r i t h m k e y w o r d s ：d e l i v e r y ；l o g i s t i cs c h e d u l i n g ；v e h i c l er o u t i n gp r o b l e m ( v i 疆) ； p i c k u pa n dd e l i v e r yp r o b l e m ( p d p ) ；g l o b a lo p t i m u m ；h e u r i s t i ca l g o r i t h m ；t i m e w i n d o w ；c l u s t e ra n a l y s i s 浙江人学硕士学位论文 致谢 三年的研究生生涯，短暂却十分充实，一直以来我得到导师邵之江教授给予 的学习上的悉心指导和生活上的热情关怀。导师敏锐的探索力、广博的知识、严 谨的治学态度、勤恳的工作作风一直影响着我，这将使我受益终生。在本文即将 完成之际，谨向我的恩师表示衷心的感谢和诚挚的敬意! 我要深深感谢我的家人，尤其是我的母亲，是她一直以来给予的无私理解和 支持，才能使我全身心的投入到学习和工作中。 由衷感谢钱积新教授给予的亲切关心和支持。 衷心感谢王永铭、张伸广、陈韬、蒋维、郑小青等同学们，他们与我进行了 许多有益的交流和讨论，并提出了不少宝贵的意见和建议。 衷心感谢王慧教授、梁军教授、马龙华副教授、赵均副教授、陈曦副教授、 周立芳副教授、赵豫红副教授等诸位老师对我一向的关心和帮助。 感谢邓赤女士在工作和生活上所给予的帮助，在此一并致谢。 感谢同实验室的同学陈韬、吴浩、吴军强、李田鹏、杨丽莎、王明兴、张敏 惠和熊丽，两年多来我们共同创造了和谐的集体氛围，为本文的工作提供了舒适 的环境。 谨以此文献给所有关心和帮助过我的老师、同学、朋友和家人! 杨宏峰 2 0 0 5 年3 月 于求是园 浙江大学硕士学位论文 1 1 引言 第一章绪论 “流通是经济上未开发的领域，是一块经济界的黑暗大陆”。这是著名的管 理学者，被称为管理学之父的美国人德鲁克( p e t e r d r u c e r ) 对流通领域发掘潜力 的形象比喻。 在经济全球化和信息化的浪潮中，现代的物流业已经从为社会提供传统的 运输服务，扩展到以现代科技、管理和信息技术为支柱的综合物流系统。随着 物流系统的集约化、一体化的发展。配送不仅仅是一种优化的物流方式，而且 促进了流通方式的巨大变革，充分满足客户的需求，有效的解决了库存和资金 占用上的瓶颈，成为物流活动中的一个的关键环节。而且从我国的实际情况出 发，在物流的理论和实践中，配送都是一种对我国经济发展作出巨大贡献的非 常有价值的方式。配送是在集货、配货的基础上，按照货物类别、品种搭配、 数量、时间等要求进行运送。而进行配送系统的优化，从技术上来说，主要就 是对配送车辆的优化调度，包括集货线路优化，送货线路优化，货物配装优化 以及集货、配装和送货一体优化：对配送车辆进行优化调度，可以提高物流服 务质量，创造经济效益、实现物流的社会化，科学化。所以对车辆调度优化理 论和方法的深入研究是物流社会化，集约化发展的基础。自1 9 5 9 年d a n t z i g 和 r a m s e l 首次提出车辆优化调度问题以来，很快引起了运筹学，应用数学，图论 和网络分析，物流科学、管理科学、计算机应用科学等领域的专家的浓厚兴趣， 一直以来是运筹学与组合优化领域的研究热点问题，学者们尝试用各种办法包 括各种精确算法和启发式方法求解，虽然取得了一定的进展，但是在解决实际 应用中的车辆调度问题却往往不尽人意。本文主要讨论了在实际应用中的车辆 调度优化理论和方法，分析了实际问题中存在特点，根据合理的假设和条件， 提出了一种基于道路网络信息的求解实际车辆调度问题的全局优化算法，然后 讨论了结合聚类算法的v r p 问题求解，并分析了若干实例，验证了算法的有效 性。 复杂约束车辆调度模型与算法研究 1 2 研究背景 1 2 1 物流的意义和发展 物流是指在合适的时间，将合适的物品以适当的数量准确的送到客户手中， 美国物流管理委员会( c o u n c i lo f l o g i s t i c sm a n a g m e n t ) 这样定义物流：物流是供 应链的一部分，是为了满足顾客的需求，以高效、低成本为目标，规划、控制 及实施从源头到消费地点的产品、服务以及相关信息正向、逆向地流动及存储 的过程( l o g i s t i c si st h a tp a r to f t h es u p p l yc h a i np r o c e s st h a tp l a n s ，i m p l e m e n t s ，a n d c o n t r o l st h e e f f i c i e n t ，e f f e c t i v e f o r w a r da n dr e v e r s ef l o w a n d s t o r a g e o f g o o d s ，s e r v i c e s ，a n dr e l a t e di n f o r m a t i o nb e t w e e nt h ep o i n to fo r i g i na n dt h ep o i n to f c o n s u m p t i o n i no r d e rt om e e t c u s t o m e r s r e q u i r e m e n t s ) 。物流是社会化大生产和社 会分工深化的产物，它联结生产与消费，使货畅其流，物尽其用，促进生产不 颤发展，满住日益增长的社会消费需要( 唐纳德等，1 9 9 8 ) 。 物流的活动广泛的存在于日常生活、企业经营以及军事活动中。工业化社 会形成以后，发达国家物流领域的发展大体可以分为两个阶段，第一个阶段是 和大生产相伴随的物流革命。第二阶段是和信息化相呼应的物流服务与供应链 革命。2 0 世纪以来，世界的经济和工业技术有了很大的发展，工业化水平从机 械技术开始，一直到大生产、专业化、自动化、集成化( 马士华等，2 0 0 1 ) 。但 是物流的发展却始终滞后于工业经济的发展，一直到2 0 世纪的后期，物流领域 的发展程度仍然落后于工业经济的发展程度。正因为如此，才有物流是“一块 经济界的黑暗大陆”是说法。究其原因，物流系统往往没有个确定的覆盖范 围。不可能像工业系统一样，在个工厂的范围内形成一个封闭的系统。物流 系统受地域和人类活动复杂性的影响，有着太大的开放性。这就决定了它更加 需要依靠信息的获取和交流，依靠信息技术来维系系统的运行。但是开放系统 信息技术的难度和成本远远高予基本封闭的生产系统。这是物流系统的技术进 步滞后于工业系统技术进步的重要原因。2 0 世纪8 0 年代以后，微电子技术、 信息科学、网络通信领域的新技术，有力的推动了新经济的形成，也推动了物 流领域的技术进步，将与大工业相适应的物流系统变成了信息化支持和带领的 现代物流。 浙江大学硕士学位论文 1 9 9 3 年美国的总物流成本为6 7 0 0 亿美圆，约占g d p 的1 1 ，超过了社会 保险、医疗服务以及国防开支的比例，居首位。到2 0 0 0 年，美国的总物流成本 超过9 0 0 0 亿美圆，约占g d p 的1 0 ，为当年的第二位。由于物流和信息技术 的发展，美国物流成本占g d p 的份额逐年下降。从2 0 世纪8 0 年代的1 6 持 续下降到了9 0 年代的1 0 左右( 丁立言等，2 0 0 2 ) 。 与发达国家相比，我国的物流产业效率较低，由于长期以来受“重生产， 轻流通”的计划经济思想的影响，我国的流通行业远远滞后于国民经济的发展。 根据中国物流与采购联合会统计，2 0 0 1 年，中国与物流相关的年总支出约1 9 0 0 0 亿人民币。物流成本占g d p 的比重位2 0 左右。而美国的全社会物流费用支 出仅占其国民生产总值的1 0 左右。如果我国的物流成本从目前的2 0 降至 1 0 左右，这将是一个巨大的利润源泉( 高自友等，2 0 0 2 ) 。另据有关资料，目前 我国一般工业品从产品出厂经过装卸、储存、运输等各个物流环节到消费者手 中的流通费用约占商品价格的5 0 左右；而新鲜水果、易变质食品、某些化工 产品的流通费用有的高达商品售价的7 0 8 0 ：我国汽车零配件的生产中，其加 工装配时间仅占2 ，而9 8 的时间是原材料、零配件的储存、装卸和搬运时间； 在各种产品的生产和流通环节中还有大量原材料、零部件和产品的“库存”( 朱 道立等，2 0 0 2 ) 。这些费用和时间上的消耗和大量存在的“库存”正是潜在的实 施物流管理的镊域，这为物流的发展留下了巨大的空间。在这种形势下，研究 如何通过实施科学的物流管理，以提高物流效率、降低物流成本、提高服务质 量是十分必要的。 1 2 2 物流系统运行中的配送优化调度 配送是物流中一种特殊的、综合的活动形式，是商流与物流紧密结合，包 含了商流活动和物流活动，也包含了物流中若干功能要素的一种形式。物流配 送是物流系统中的一个重要环节，它是指按客户( 包括零售商店、用户等) 的订 货要求( 包括在货物种类、数量和时间等方面的要求) ，在物流中心( 也称物流基 地、物流据点，包括配送中心、仓库、车站、港口等) 进行分货、配货工作，并 将配好的货物及时送交收货人的物流活动。配送是物流中一个重要的环节，是 直接与消费者相连的环节，是一个体现了服务质量和水平的关键环节。由于配 复杂约束车辆调度模型与算法研究 送是对顾客服务的最后一环，因此，配送的地位十分突出，如何实现快速而准 确的配送是企业在经营方面必须解决的重要课题。目前我国的物流配送基本上 还停留在“只送不配”的水平上，造成物流配送效率低下，车辆空驶严重，物 流配送成本很高，服务质量却很低。鉴于此，研究运用科学方法合理组织物流 配送，对配送车辆进行优化调度，以提高企业的服务质量、减少库存、降低经 营成本、增加经济效益是十分必要的。另外，随着电子商务、e d i 的发展，存 储已经不是必然的环节，通过高效、准时的配送体系，零库存这个曾经的幻想 也已经被许多企业实现。从此企业就可以摆脱沉重的库存包袱，将大量的资金 解放出来。看板生产、准时供应、精益生产等新型，高效的产业模式也得到了 发展。高质量的配送服务的深刻意义在于：这不仅仅是一种优化的物流方式， 丽且促进了供应方式的巨大变革，充分的满足了客户的需求，有效的解决了用 户在库存和资金占用方面的后顾之忧。对配送车辆优化调度理论和方法进行系 统的研究是物流集约化发展，建立现代调度系统的基础。 1 3 研究动态和目前待解决的问题 1 3 1 问题简介 车辆优化调度问题最早是由d a n t z i g 和r f l l y i s e r 于1 9 5 9 年首次提出的，自 此，很快引起了运筹学、应用数学、图论和组合数学、计算机应用科学、管理 科学、物流科学等领域的专家的极大兴趣，成为运筹学与组合优化领域的一个 热点问题。通过各学科专家的不懈努力，进行了大量的理论研究和实验分析， 取得了很大的进展。对该问题的一般描述为，对一系列装货点和卸货点，组织 适当的行车路线，使车辆有序地通过他们，在满足一定的约束条件自q 情况下( 如 容量，时间，里程，优先级等) ，达到一定的优化目标( 如路程最短，费用最少， 时间最短等) 。目前国内外专家对此问题的研究已经有了很大的进展，在 c h r i s t o f i d e s ( 1 9 8 5 ) 编辑的论文集，以及l a p o r t 1 9 9 2 ) ，s a l h i ( 1 9 9 3 ) 等的综述文章 中都进行了详尽的描述。在问题的定义上，也有学者根据问题的空间特性和时 间特性的相对重要性来划分，仅根据空间位置安排线路时称其为v e h i c l e r 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 l i n gp 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 h t i m ew i n d o w s 。在这里，为简单起见，我们统称为v e h i c l e r o u t i n gp r o b l e m ，即 v r p 问题。 1 3 2v r p 问题的特征与分类 自从v r p 问题提出以后，b o d e i n ( 1 9 8 3 ) 、a s s a d ( 1 9 8 8 ) ，以及中国的祝崇隽 ( 2 0 0 1 ) ，李军、郭耀煌( 2 0 0 1 ) 等许多学者对其从不同角度，按不同的标准进行 了多种分类。 按已知信息的特征分，可分为确定性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 p 集货、送货一体化问题) 。 按任务的性质分，有对弧服务问题( 类似中国邮递员问题) 和对点服务问题 ( 类似旅行商问题) 以及混合服务问题( 如交通车路线安排问题) 。 按车辆载货状况分，有满载问题和非满载问题( 多项任务共用一车) 。 按配送中心与客户分布的关系分，有单中心问题和多中心问题。 按运输车辆的类型数目分，有单车型问题( 相同容量) 和多车型问题。 按运输车辆路线的类型分，有车辆开放问题( 车辆路线可以开放，车辆可以 步返回出发结点) 和车辆封闭问题( 车辆必须返回出发点) 。 按优化的目标数目来分，有单目标优化问题和多目标优化问题。 根据具体的情况，针对不同类型的v r p 问题的算法也有所不同。 1 4 v r p 问题算法 前面提到，经过多年的研究发展，v r p 已经衍生出多种不同类型的问题。 其求解算法从早期的精确算法研究，发展到了9 0 年代的各种h e u r i s t i c s 算法 研究，以及遗传算法、禁忌搜索、模拟退火和神经网络等智能化方法的研究。 针对丰富多变的车辆优化调度问题，求解的方法也非常丰富，g o l d e n ( 1 9 8 4 ) ， 6复杂约束车辆调度模型与算法研究 l a p o r t e ( 1 9 9 2 ) ，李军、郭耀煌( 2 0 0 1 ) 等许多学者都对其求解方法进行了研究和 分类。从本质上来说，基本可以分为精确算法和启发式算法两大类。 精确算法指那些理论上可以求得最优解的算法，目前应用在v r p 问题中的 精确算法主要有：分枝定界算法0 3 r a n c ha n db o u n da p p r o a c h ) ，割平面算法 ( c u t = t i n gp l a n e sa p p r o a c h ) ，网络流算法( n e t w o r kf l o wa 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 ) 。 f i s h e r ( 1 9 9 4 ) 等人针对带能力约束、时间窗口以及无停留时间的v r p ，提 出了三下标车辆流方程。在该方程中，其中两个下标表示弧或边，另外一个下 标表示特定车辆的序号。基于b e n d e r s ( 1 9 8 8 ) 的分解算法，他们提出了一种启 发式算法，保证在有限步内找到最优解。f i s h e r 等人用它计算了有5 0 1 9 9 个 客户的v r p m a r e l l o 和d e s r o c h e r s ( 1 9 8 9 ) 分别提出了相应的改进算法。 但是由于v r p 问题是n p h a r d 问题，精确算法的计算量一般随问题规模 的增大而呈指数增长，从而使该类算法只能有效求解中小规模的v r p 问题，而 对大规模的v r p 问题使用启发式算法是必要和现实的选择。目前的启发式算法 基本有两大类。第一类是h e u r i s t i c s ，这类算法只搜索解空间中相对有限的一 部分子空间，力求在比较合理的时间内取得比较好的解。它又分为两小类算法： 路径构造算法( 包括节约法，匹配算法，路径改进算法等) ，两阶段算法。 构造算法( c o n s t r u c t i v e a l g o r i t h m ) ，即根据一些准则，在算法的每一步，不 在线路上的点添加进线路，把当前的线路构形统另外的构形进行比较并加以改 进，后者或是依据某个判别函数，产生最大限度的节约构形，或者是以最小代 价把一个不在当前构形上的需求对象插入进来，最后得到一个包括所有点的可 行构形。( c l a r k ea n dw r i g h t ，1 9 6 4 ：m o l ea n dj a m e s s o n ，1 9 7 6 ) 。构造算法最初 是用来解决t s p 问题的，这类方法速度快也很灵活，但是有时得到的解离最优 解差的比较远。 两阶段法，通过对构造算法的改进，人们提出了两阶段法，第一阶段得到 一个可行解，第二阶段通过对解的调整，在保持解的可行性的前提下，逐步向 最优解靠近，( g i l e t ta n dm i l l e r ，1 9 7 4 ；b o c t o r a n d l a p o r t e ，1 9 9 6 ) 其中第一阶段 常常用构造算法，第= 阶段常用2 - o p t 、3 - o p t 交换法。另外一些基于数学规 划的算法也属于两阶段法，把问题直接描述成一个数学规划问题，根据其模型 浙江大学硕士学位论文 的特殊结构，应用一定的技术进行划分，进而求解已被广泛研究过的子问题。 ( f i s h e ra n dj a i k u m a r ，1 9 8 1 ) ，包括先聚类后构造路径法，先构造路径后聚类法 等。 启发式算法里面还有一类是m e t a h e u r i s t i c s ，这类算法包括了许多比较复 杂的或者基于概率搜索的启发式规则，一般都是从一个初始解开始，通过对当 前解的领域搜索或者局部扰动( p e r t u r b a t i o n s ) 达到较好的解，包括禁忌搜索算 法f g e n d r e a u 、h e r t za n d l a p o r t e ，1 9 9 4 ；j i e f e n g a n d j a m e s ，1 9 9 6 ；b a r b a r o s o g l u ， 1 9 9 9 ) ，模拟退火算法( s i m u l a t e da n n e a l i n g ) ，遗传算法( g e n e t i ca l g o r i t h m ) ，神 经网络算法( n e u r a ln e t w o r k s ) 。由于对解空间进行比较全面的搜索，这类算法 产生的解的质量通常比典型的h e u r i s t i c s 要高。 禁忌搜索算法是一种通过领域搜索以获取最优解的方法，g l o v e r ( 1 9 8 9 ) 曾 叙述了它的基本原理。g e n d r e a u t ( 1 9 9 3 ) 等人最先将该方法应用于v r p 。先构造 系列的解，然后对所得解不断地进行改进。该算法所得的解不一定是可行的， 它们对可行性的偏离程度是通过目标函数里的惩罚函数来体现的。它是针对 v r p 的比较好的启发式算法，可以成功地应用于许多经典的v r p 。其后 e t a i l l a r d f ( 1 9 9 4 ) 等人通过按角度和路径重心对原问题的空间进行分割，再用 禁忌搜索结合模拟退火对子问题迸行求解，实现了对问题求解的并行化。 模拟退火算法，这是一种源于5 0 年代，基于m o n t e c a r l o 迭代求解思想的 随机搜索算法，最早由m e t r o p o l i s 在1 9 5 3 年提出，k i r k p a t r i c k ( 1 9 8 3 ) 成功地将其 应用在组合优化问题中。近年来，o s m a n ( 1 9 9 3 ) ，t e o d o r o v i c ( 1 9 9 2 ) ，蔡延光( 1 9 9 8 ) ， 刘浩( 2 0 0 1 ) 等人利用模拟退火算法求解物流配送车辆调度问题，取得了一些研 究成果。但上述研究也多限于对无时限单向物流配送车辆调度问题或满载物流 配送车辆调度问题的求解。 遗传算法是美国m i c h i g a n 大学的j h o l l a n d ( 1 9 7 5 ) 于本世纪末提出了一种新 的并行优化搜索方法：遗传算法是一种基于进化论优胜劣汰、自然选择、适者 生存和物种遗传思想的随机优化搜索算法，通过群体的进化来进行全局性优化 搜索。j l a w r e n c e ( 1 9 9 2 ) 最先将该方法用于v r p 的研究，并可有效求解v r p t w 鉴于传统的遗传算法是个大范围、粗粒度的寻优算法，因此b a r m i e r ( 1 9 9 5 ) 将 它与约束满足问题的技术相结合，通过遗传算法来处理参数的子域( 基因的适应 复杂约束车辆调度模型与算法研究 度是通过对解的计算得到的) ，从而减少搜索空间，降低问题目标函数和遗传算 法约束的复杂度。我国张涛等人则通过遗传算法来保证搜索的全局性，用3 - o p t 算法来加强局部搜索能力，得到针对v r p 的混合算法( 张涛等，1 9 9 9 ) 。遗传算 法的最大优点是通过群体间的相互作用，保持己经搜索到的信息，这是基于单 次搜索过程的优化方法所无法比拟的。但是，遗传算法也存在着计算速度较慢 的问题。 1 5v r p 问题计算复杂性与面向应用的算法 对于组合优化问题，我们关心的往往不是最优解的存在性和唯一性，而是如 何找到有效的算法求得一个最优解。 v r p 问题提出以后，有不少学者和专家都对他的计算复杂性进行了研究和 探讨。一般来说，车辆路径调度问题属于组合优化问题，组合优化问题通常都 有大量的局部极值点，且往往是不可微、不连续、多维、多约束条件且高度非 线性的n p 难题。k a r p ( 1 9 7 2 ) 证明了旅行商问题( t r a v e l i n gs a l e s m a np r o b l e m ，简 称t s p ) 为n p 难问题，p a p a d i m i t r i o u ( 1 9 7 6 ) i 正明了多重旅行商问题( m u l t i p l e t r a v e l i n gs a l e s m a np r o b l e m ) 为n p 难问题，e d m o n d s 和j o h n s o n ( 1 9 7 3 ) 证明了中国 邮递员问题的复杂性y 口o ( n 3 ) 。d a n t z i g 和f u i l ( e r s o n ( 1 9 5 4 ) 证明了有确定开始时间 的v r p 问题的复杂性# j o ( n 3 ) 。s a v e l s b e r g h ( 1 9 8 5 ) 和s o l o m o n ( 1 9 8 6 ) 提出有时间窗 约束的v r p 比一般的v r p 更复杂。并证明有时间窗约束的冲不仅问题本身是 n p 难问题，而且在车辆数量固定的时候，找到一个可行解也是n p 难问题。 对于这些复杂的组合优化问题，一般都是运用一些启发式算法来得到问题 的近似最优解。前面提到的禁忌搜索法、模拟退火法、遗传算法等都属于启发 式算法，总的说来，这些方法往往都过于复杂，运算量过大，涉及复杂的领域 转换和求解策略，在实际中不容易实现和应用。而且，研究表明，这些i 司题往 往无法找到一个全局最优的解，解的有效性依赖于对性能需求的标准及现实中 运作的条件。此外，顾客需求的个性化及要求企业响应市场的敏捷性，往往在 配送过程中加入了更多的不确定性及复杂性约束。所以这些使得启发式算法的 思想已不能适合敏捷化配送的要求。在本文中，我们将分析现实物流配送系统 的业务流程和存在的问题，根据配送合理化的判断标准，结合现实的需求，建 浙江大学硕士学位论文 立了配送车辆路径调度问题的一般模型。然后基于模拟现实的道路网络信息， 提出了一种求解实际的车辆调度问题的全局优化算法，讨论了与其他启发式算 法以及聚类算法的结合，并结合若干实例，对算法的有效性进行了评估。 1 6 本文内容概要 如前所述，论文的第l 章分析了研究物流配送车辆调度问题对于企业提高服 务质量、降低物流成本、增加经济效益和增强市场竞争力的重要现实意义；说 明了求解物流配送车辆调度问题对于解决v r p ，v s p ，m t s p 具有普遍的借鉴意义。 第1 章还对物流配送车辆调度问题的结构要素进行了系统分析，介绍了近二十年 v r p t w 研究所取得的一些成果，包括算法的原理和适用范围，并分析了在现实环 境下应用各种算法求解车辆路径调度问题的优缺点。然后简单介绍了算法的实 验评价标准，为各种算法的比较提出了一些建议。 论文的第2 章分析了现实物流配送系统的业务流程和存在的问题，提出了 配送合理化的判断标准。并结合现实的需求，建立了配送车辆路径调度问题的 一般模型。为下一步算法的展开打下了基础。 论文的第3 章根据运行的实际情况，分析了结合道路网络信息进行调度优 化存在的问题。如果优化调度算法直接分析路网信息，则在这些信息中有大量 的多余数据，而且路径的信息本身也是在不断的变化中，其计算的开销和算法 的效率都将是难以接受的。所以我们结合了最短路径算法，设计了一种多层次 的启发式优化算法，先在基础地理信息数据上进行预处理，得到更加精练的的 数据，然后在进行全局优化的搜索。并采用离线搜索、建立最佳路径库，以提 供启发式搜索算法所需的最短路径相关数据，大大提高了算法的效率。而且， 在上述算法框架的基础上，还可以根据环境和优化目标的变化实时调整算法， 提高了算法的灵活性。另外，本章还根据坐标数据提出了一种构造更加贴近实 际的算例的方法。最后用这些算例对算法进行了验证和分析。 论文的第4 章根据前面已经讨论了的物流配送车辆调度问题的模型，深入 分析了现实问题的复杂约束。为了获得最有效率的车辆调度结果，综合考虑实 际上的各项约束和评价指标，将约束条件都将纳入到模型中。对单纯的调度问 题来说，这些约束都属于额外约束式( s i d ec o n s t r a i n t ) ，其存在使问题的求解 0复杂约束车辆调度模型与算法研究 更为困难。因此，在解决现实的问题时我们尝试以启发式算法求解。启发式解 法的确能成功的求解大型问题，而所需的运算时间也较短，唯一不链保证的是 所得解的品质。故在求解任何车辆巡回问题时，选择算法是必须考虑兼顾求解 所需的运算时间与所得解的品质。本章提出了一种全局优化的剪枝搜索算法求 解调度优化问题，并对算法的性能作了深入的分析与比较。 论文第5 章首先针对实际中广泛存在的多车辆路径调度问题，讨论了算法的 改进，包括解的表达和算法步骤上的改进。但是对于大规模的问题，改进算法 的效率还是不尽入意。作者提出了一种先聚类后求解的方法，聚类就是根据样 本的特性，将其中相对来说相似接近的样本划分为一类。我们根据问题的特点 提出了一种基于数据预处理的距离度量指标，将基于最短路径值距离定义的聚 类算法引入到v r p 和问题中。同时通过实验分析了各种聚类算法的特点，提出 了适应于v r p 问题的基于最短路径距离指标的完全连接距离聚类算法和平均连 接距离聚类算法。并用实际的数据分析验证了算法的效果。 论文的第6 章将总结本文的主要工作和研究结论，并对需要迸一步研究的方 向进行简要说明。 浙江大学硕士学位论文 第二章物流配送车辆调度模型 2 1 业务流程分析 物流配送企业，每天都要面对将不同的物流结点的物资按需求运送到多个需 求点的运输调度问题。如何及时、准确、高效、合理的运送到需求点，在很大程 度上取决于车辆调度的水平高低。我们可以从车辆的分配、路径的选择、人员的 安排等方面入手，以实现提高物流效率、减少物流成本的目标。现实实用的调度 模型就需要可描述的特定日标，和实现条件，并求解在此目标下优化的调度方案。 所以，必须首先分析现实物流配送系统的业务流程和存在的问题 在现实的物流配送业务中，配送的对象、品种、数量等都较为复杂，为了做 到有条不紊地组织配送活动，应当遵照一定的工作程序进行。一般情况下，配送 组织工作的基本程序和内容如下： 1 拟订配送计划，根据用户的订货合同，确定用户的送达地、接货人、接货 方式、货种、规格、数量、送货时间及送接货