（控制理论与控制工程专业论文）非限定车场车辆路径问题研究.pdf

at h e s i sf o rt h ed e g r e eo fm a s t e ri nc o n t r o l t h e o 眄a n d c o n t r 0 ie n g i n e e r i n g r e s e a r c ho fn o n n n i t ed e p o tv e h i c l er o u t i n gp r o b l e m b yw 抽gy a n m i n s u p e r v i s o r ：a s s o c i a t ep r o f i e s s o rw a n gl e i z h e n n o r t h e a s t e r nu n i v e r s i 够 j u n e2 0 0 9 独创性声明 本人声明所呈交的学位论文是在导师的指导下完成的。论文中取得的 研究成果除加以标注和致谢的地方外，不包含其他人已经发表或撰写过的 研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示诚挚 的谢意。 学位论文作者签名： 孓狍础 签字日期 ： 7 。卜4 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位 论文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印 件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文 的全部或部分内容编入有关数据库进行检索、交流。 作者和导师同意网上交流的时间为作者获得学位后： 半年日一年口一年半口两年口 学位论文作者签名：狍敏 签字日期：淅7 。7 。午 导师签名：王嗡览 签字日期： ) a 1 d 7 d 7 d 4 ， 引入新的边约束，研究满足经济管理实际需要的各种类型的车辆路径问题，同时构建高 质量和高鲁棒性的求解算法具有重要的理论意义和实践价值。 本文分析了多车场车辆路径问题的数学模型，定义了限定车场车辆路径问题和非限 定车场车辆路径问题，介绍了基本的遗传算法，针对现有非限定车场车辆路径问题数学 模型整合资源不优的缺陷，构建了非限定车场车辆路径问题的改进数学模型，同时，提 出了求解模型的可重复整数编码方法的遗传算法。 非限定车场车辆问题模型松弛了多车场车辆路径问题的多个假设条件，是允许需求 点被多次访问且集送一体化的开放式车辆配送模型，弥补了以往研究的多车场车辆路径 问题数学模型随机性差、不符合配送发展趋势的不足。但是目前研究的非限定车场车辆 路径问题的数学模型只考虑了最小化车辆旅行费用，资源消耗多。考虑到少出动一辆车 的费用要低于多出动一辆车但是车辆行驶距离小的总费用，本文在现有非限定车场车辆 路径问题单目标优化函数的基础上，构建了以车辆数为首要目标函数的多目标优化函数 模型。同时，通过引入标准化系数将多目标函数转化为单目标函数进行求解。鉴于遗传 算法对模型并无数学上的要求，且在求解中具有高鲁棒性和并行性，因此本文采用遗传 算法对模型进行求解。求解过程应用两次遗传算法内外循环进行寻优，先由其得到单车 需要运送的货物，再对单车路径进行优化，寻优过程不独立，易实现全局最优。基于本 文研究的非限定车辆路径问题允许需求点被多次访问的特点，提出了可重复整数编码方 法，并设计了相应的解码方案和遗传操作。 最后通过仿真验证了数学模型和算法的可行性，不仅优化了车辆路径，而且整合了 资源，降低了配送成本。 关键词：非限定车场；车辆路径问题；遗传算法；可重复整数编码 一i i ， 一 t l l ea n i c l ea i l a l y s e sm em o d c l i n go fm u l t i d 印0 tv 出c l er o u t i n gp r o b l 锄，d e f i n i t e f i n i t ed 印o t 冲a n dn o n f i n i t ed 印o tv r p ，i i l 缸d d u c e s t 1 1 eb a s i cg e i l e t i ca l g o r i m m ， c o n s t r u c t st h ei m p r o v e dm o d e lo fn f v i 冲i nm el i g h to ft h ee x i s t i n go n e si n a d e q u a c yh i n t e 簪a t i o no fr e s o u r c e s ，a n dp r o p o s e sm er 印e a t a _ b l ec o d i n g o fg a n f v 】强r e l a xm a n ya s s u m p t i o n so fm d v i 屺a l l o w st 1 1 er e q u i r e m e n tt ob ev i s i t c dm a l l y t i m e s t om e e tt l l es h o 币a l ls t o c h a s t i cd i 侬：r e n t i a l ，孤dt l l ed e v e l o p m e l l t 咖do fd i s t r i b u t i o n b u tm ee x i s t i n gm o d e lo fn f v i 心0 1 1 1 yc 0 n s i d e r e dm i l l i m i z i n gm et r a v d i n gd i s t 趾c e ， c o n s u m p t i o no fr e s o u r c e sa n dm o r c s om e 枷d ec o n s 饥l c t sd u a l - o b j e “v eo p t i m i z a t i o n 如n c t i o nt a l ( i n gi n t oa c c o u n tm e1 e s sc o s to f ac a ru s e dt ob em u c hl o w e rt h 柚t h em m l b e ro f c a rd 印l o y e d t h ep n m a 巧o b j e c t i v eo p t i m i z a t i o n 劬c t i o ni s m i l l i m i z e dt h em l m b e ro f v 出c l e s ，a n dm i n i m i z i n gt h et r a 、，e l i n gd i s t a l l c ei s t ob es e c o n d a 巧o n e s t h ed u a l 。o b j e c t i v e o p t i i i l i z 抓o n 缸1 c t i o ni i l t oas i n 西eo n et h i d u 曲t h es t a n d a r d i z e dp 聪u n l e t e re s t i m a t e s e w o f g e i l e t i ca l g o r i t h mh a sn om a m 锄a t i c sr e q u i r e m e n t so fm o d e lb u th i 曲r o b u s t n e s sa n d p a r a l l e l i s m ，t h ea n i c l eu s e sg a t os o l v em en f v i u m o d e l i n g s o l v i n gp r o c e s si sd i v i d e di n t o t w o ，t h ef i r s to n ei s t og e tt h eg o o d so fs i i l 西ev e _ h i c l ea 1 1 dm e no p t i m i z es i n 酉eve _ 嫩d ep a t h t h eo p t i m i z a t i o np r o c e s si sn o ti n i 印e i l d e n t ，a n de 嬲yt oa c m e v et h e 酉o b a lo p t i m 啪i i lt l l e a r t i c l e ，p r o p o s e st h er 印e a t a b l ec o d i n gc o n s i i i 甜n gf b a t u r eo fn f v i u ：d e s i 弘sc o r r e s p o n d i n g d e c o d i n gs c h 锄ea 1 1 dg e n e t i cm a l l i p u l a t i o n t h es i m u l a t i o nr e s u l t ss h o wm em o d e l sa n dm ea l g o 订t m i ca r ef e a s i b i l i t ) ra n de 衔c i e n t ， t l l e yn o to i l l yo p t i m i z em ev e l l i c l e sr o u t e s ，b u ta l s oc o n f o m l i t i e st h er e s o u r c e s ，a 1 1 dr e d u c et h e c o s to fm ed e l i v e r y ： k e y w o r d s ：n o n f i n i t ed e p o t ；v c 临c l ei 沁u t i n gp a o b l e m ；g e n e t i ca 1 9 0 r i t l l mr 印e a t a b l e c o d i n g i i i l 东北大学硕士学位论文 目录 目录 独创性声明i 摘要i i a b s t r a c t i i i 第1 章绪论l 1 1 课题的研究背景1 1 2 车辆路径问题研究发展综述。1 1 2 1 车辆路径问题研究现状1 l 。2 2 多车场车辆路径问题国内外研究现状3 1 3 本文的主要工作5 第2 章多车场车辆路径问题概述7 2 1 车辆路径问题概述7 2 1 1 车辆路径问题的基本概念7 2 1 2 车辆路径问题的数学模型7 2 1 3 车辆路径问题的构成要素9 2 2 多车场车辆路径问题1 1 2 2 1 多车场车辆路径问题描述1 1 2 2 2 多车场车辆路径问题的优化目标1 2 2 2 3 多车场车辆路径问题的数学模型1 3 2 2 4 多车场车辆路径问题的配送模式1 4 2 2 5 多车场车辆路径问题的分类1 4 2 3 小结1 6 第3 章遗传算法介绍1 7 t v 东北大学硕士学位论文 目录 3 1 遗传算法定义1 7 3 2 遗传算法的基本要素1 7 3 2 1 染色体编码1 8 3 2 2 个体适应度评价19 3 2 - 3 遗传操作1 9 3 2 4 控制参数设定2 1 3 3 遗传算法的运行过程2 2 3 4 遗传算法的特点及应用2 3 3 4 1 遗传算法的特点2 3 3 4 2 遗传算法的应用2 5 3 5 小结一2 6 第4 章非限定车场车辆路径问题2 7 4 1 限定车场车辆路径问题2 7 4 2 非限定车场车辆路径问题2 8 4 2 1 非限定车场车辆路径问题的货运模式2 8 4 2 2 非限定车场车辆路径问题的特点“2 9 4 2 3 非限定车场车辆路径问题的数学模型：2 9 4 3 非限定车场车辆路径问题的改进模型_ 3 1 4 3 1 模型建立的假设与前提3 1 4 3 2 非限定车场车辆路径问题的改进数学模型3 1 4 4 小结。3 2 第5 章非限定车场车辆路径问题的求解3 3 5 1 求解过程3 3 5 2 - 单车需要运送的货物的求解3 6 5 2 1 约束处理。3 6 。v 一 ， 目录 3 6 4 0 4 3 4 3 4 5 4 5 5 4 实验结果4 9 5 4 1 实例4 9 5 4 2 结果比较分析5 0 5 5 小结一5 2 第6 章结论5 3 参考文献5 4 致谢6 0 。v i - 东北大学硕士学位论文第1 章绪论 第1 章绪论 1 1 课题的研究背景 “十一五”纲要提出建设资源节约型社会的基本方针。物流作为现代服务业，为 国民经济的健康发展和社会生活水平的r 益提高提供重要的保障，如何建立资源节约型 物流，实现最大物流、最小成本，成为当前物流业发展的一大热点。运输是物流系统中 的关键环节，降低物流成本首要的是降低运输成本，而通过配送方案的规划，合理地选 择运输路径，避免迂回运输，降低空驶率，提高车辆的利用率，实现运输距离最短、运 输费用最小，是建立节约型物流的最有效途径。因此，物流配送过程中的车辆路径问题 ( 临c l er o u t i n gp r o b l 锄，v r p ) 成为现代物流活动中的一项关键技术。优化车辆使用方 案以及车辆行驶路径方案对于提高运输系统运行质量、提高客户满意度和增强企业的竞 争力具有重要的意义。冲不仅可以用来对配送管理中货物收集和配送问题进行建模， 而且可以用来对交通运输系统中许多应用问题进行建模，比如城市固体废物收集、维修 设备问题及d i a l - a r i d e 系统问题。 v 1 廿已经被证明是n p - h a r d 组合优化问题，构建高效的车辆路径问题求解算法是一 个具有挑战性的研究课题。目前精确算法仅可以处理较小规模的车辆路径问题，对于较 大规模的车辆路径问题，算法计算时间随问题规模的增长呈指数化增加。因此国内外学 者们将研究的目光转向利用现代启发式算法在可接受的中等规模的计算时间内发现问 题的好的解和次优解。同时随着社会经济的不断发展，为了满足经济管理的实际需要， 学者们将不同类型的边约束引入到车辆路径问题，不断拓展车辆路径问题的研究空间。 但是目前建立的车辆路径问题的扩展问题的数学模型中车场和服务点的关系已经不满 足物流配送的发展趋势，这就迫切需要研究新的车辆路径问题模型及高质量的求解算 法。 1 2 车辆路径问题研究发展综述 1 2 1 车辆路径问题研究现状 经过几十年的研究发展，v r p 研究取得了大量成果。下面从v r p 的现有研究型态 和求解方法两个方面介绍v r p 的研究现状。 1 2 1 1 车辆路径问题型态 针对实践中的具体问题，在基本v r p 的基础上不断发展，产生了许多不同的延伸 和变化型态，主要体现在配送车辆的种类、约束条件以及优化的目标等方面。如：多配 问题( v e h i c l e r o u t i n gp r o b l e i t l sw i t hm u l 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 m b l e m sw i mb a c k l l a u l s ，v r p b ) 、随机需求车辆路线问题( v c h i c l er o u t i n g p r o b l 锄w i t hs t o c h a s t i cd e l l l a i l d ，v r p s d ) 等。 1 2 1 2 车辆路径问题求解算法 综合过去有关车辆路线问题的求解方法，可以分为精确算法( e x a c ta l g o r i t l 1 ) 与启发 式解法( h 嘶s t i c s ) ，其中精密算法有分支界限法、分支切割法、集合涵盖法等；启发式 解法有节约法、模拟退火法、确定性退火法、禁忌搜寻法、基因算法、神经网络、蚂蚁 殖民算法等。1 9 9 5 年，f i s h 一1 】曾将求解车辆路线问题的算法分成三个阶段。第一阶段 是从1 9 6 0 年到1 9 7 0 年，属于简单启发式方式，包括有各种局部改善启发式算法和贪婪 法( 骶e d y ) 等；第二阶段是从1 9 7 0 年到1 9 8 0 年，属于一种以数学规划为主的启发式解 法，包括指派法、集合分割法和集合涵盖法；第三阶段是从1 9 9 0 开始至今，属于较新 的方法，包括利用严谨启发式方法、人工智能方法等。 由于v r p 是n p - h a m 问题，难以用精确算发求解，启发式算法是求解车辆运输问 题的主要方法，多年来许多学者对车辆运输问题进行了研究，提出了各种各样的启发式 方法。车辆运输问题的启发式方法可以分为简单启发式算法、两阶段启发式算法、人工 智能方法建立的启发式方法。 ( 1 ) 简单启发式算法 简单启发式方法包括节省法或插入法、路线内间节点交换法、贪婪法和局部搜索 法等方法。节省法或插入法( s a v i n g so ri n s e n i o n ) 是在求解过程中使用节省成本最大的可 行方式构造路线，直到无法节省为止。交换法则是依赖其他方法产生一个起始路线，然 后以迭代的方式利用交换改善法减少路线距离，直到不能改善为止。1 9 6 0 年，c l 破e 和w r i g h t 【2 】首先提出一种启发式节省法( s a v i n g sm e t h o d s ) 来建立车队配送路线。简单启发 式方法简单易懂、求解速度快，但只适合求解小型、简单的v r p 问题。 ( 2 ) 两阶段启发式算法 两阶段方法包括先分组后定路线( c l u s t e rf i r s t r o u t es e c o n d ) 和先定路线后分组( r o u t e f i r s t c l u s t e rs e c o n d ) 两种启发式策略。前者是先将所有需求点大略分为几个组，然后再对 2 东北大学硕士学位论文第l 章绪论 各个组分别进行路线排序；后者则是先将所有的需求点建构成一条路线，再根据车辆的 容量将这一路线分割成许多适合的单独路线。 ( 3 ) 人工智能算法 1 9 9 0 年以来，人工智能方法在解决组合优化问题上显示出强大功能，在各个领域得 到充分应用，很多学者也将人工智能引入车辆路线问题的求解中，并构造了大量的基于 人工智能的启发式算法。禁忌搜索法( t s ) 基本上是属于一种人工智能型( a i ) 的局部搜寻 方法，w i l l 莉首先将此算法用来求解v r p ，随后亦有许多位学者也发表了求解强的 t s 算法。西南交通大学的袁庆达【3 】等设计了考虑时问窗口和不同车辆类型的禁忌算法， 这种算法主要采用g e n i u s 方法产生初始解，然后禁忌算法对初始解优化。模拟退火方 法具有收敛速度快，全局搜索的特点，o s m a i l 【4 】对冲的模拟退火算法进行了研究，他 提出的模拟退火方法主要适合于解决路线分组。遗传算法具有求解组合优化问题的良好 特性，h 0 1 1 a n d 首先采用遗传算法( g a ) 编码解决v 1 冲t w 问题。文献【5 】将蚂蚁算法这种 新型的生物优化思想扩展到物流管理中的车辆路径问题。o m b u k i 【6 】提出了用遗传算法进 行路线分组，然后用禁忌搜索方法进行路线优化的混合算法。b e l l t 和、h e n t e l l r y c k 【7 j 则首先用模拟退火算法将车辆路线的数量最小化，然后用大邻域搜索法( 1 a r g e n e i 曲b o r h o o ds e a r c h ) 将运输费用降到最低。 同时还有遗传算法、禁忌搜索混合【8 】，模拟 退火、蚁群算法混合【9 】等混合算法，以及基于扫描的短暂无序神经网络算法【1 0 】等等。 1 2 2 多车场车辆路径问题国内外研究现状 上面介绍的用于单车场车辆路径问题的算法为多车场车辆调度提供了思路，多车场 的车辆调度问题的处理方法比单车场条件下更加复杂。国外有很多学者正在研究这个问 题并且取得了一些成果。 1 4 2 1 国外研究现状 在m d v r p 模型方面，s t e f 锄i m i c h 【1 1 】建立了多配送中心、多车型、集送混合业务 的车辆调度模型，但实际上解决的是个总配送中心，多个分配送中心之间货物调配的 车辆调度问题。车辆的出发点和终点都是各个分配送中心并且各个配送中心的车辆数是 无限多，并且各业务的时问窗比较窄，业务量也比较多，这样分配送中心与总配送中心 之问的配送一般都是满载直送。j i a nh u y u p oc h a n 构造了具有服务优先级的车辆优化 模型12 1 。c u r r i e 等建立了多车场满载运输问题的整数规划模型。e r g u l l 等【1 4 】把问题简 化为路线覆盖问题( l a n ec o v e rp r o b l 锄，l c p ) 。g r o n a l t 等【1 5 】建立了整数规划模型。其中 约束条件带时间窗的研究较多一些【1 6 2 4 1 。 在解决多车场车辆路径问题上，最早有t i l l m a i l 【2 5 1 和c l a r k e 提出的节约法【2 6 】。该算 3 c o n s 仃u c t i o n ) 建立粗略的路径( d r a rr o u t i n 曲，之后基于禁忌搜索建立详细的优化路径 ( d e t a i lr o u t i n 曲。 任务 一一。川草拟( d r a r ) 路径优化 分配1 l 详细( d e t a i l ) 路径优化岭 ( a ) 一阶段解决方法( b ) 两阶段解决方法 图1 1 一阶段、两阶段解决方法 f i g 1 1o i l e - s t a g e 、t w o - s t a g es o l v i n g 同时车辆调度算法还有精确算法【3 l 3 2 1 、变邻域搜索( v a d a b l en e i g h b o r h o o ds e a r c h ， v n s ) 【3 3 l 采用多个邻域结构，同时进行邻域的变化，域之间进行交换( 交叉) 、启发式算 法 3 4 】、蚁群算法【3 5 】、人工免疫算法【3 6 1 、遗传算法【3 7 】、分层多重结构的( h i 碱i c a lm u l t i p l e x s t r u c t u r e ，h i m s ) 【粥】的计算模型等。 1 4 2 2 国内研究现状 国内对v r p 的研究相对较少，主要研究对象是旅行商问题( t r a v e l i n gs a l e s m 锄 p r o b l e n l ，简称t s p ) 、中国邮递员问题( c h i n e s ep o s t i n a l lp r o b l 锄，简称c p p ) 、有向中国 邮递员问题( d i r e c t e dc h i n e s ep o s 仃n a l lp r o b l e m ，简称d c p p ) 等，系统性研究还尚未见到。 关于m d v r p 就更加少了，目前可查的相关书籍仅有2 0 0 1 年出版的李军、郭耀煌物 流配送车辆调度优化。李军，郭耀煌【3 9 j 结合s w e 印算法和s a v i n g 算法，给出了多 车场转化为单车场的处理方法。但没有给出分解点6 的设定标准，且分配的结果并不十 分理想。钟石泉，贺国光【4 0 】提出针对物流配送中的多车场车辆调度问题提出了两种多车 场的智能处理方法：引入一个虚拟车场，把多车场转化为单车场的智能方法；多车场同 时优化的方法。这两种思路最终还是通过禁忌搜索法来实现的，但是，没有说明禁忌搜 索法能否很好的实现这两种思路。邹彤、李宁、孙德宝、李菁【4 i 】应用遗传算法对多车场 4 东北大学硕士学位论文笫l 章绪论 车辆调度问题进行了探讨。该遗传算法的编码方法，考虑到车辆数量的优化，是一种较 好的编码思路。李臻，雷定猷对多车场满载且送取任务一一对应的问题进行了研究， 引入重载点的概念以及运用组合优化的方法丰富了多车场满载车辆调度理论。郎茂祥【4 3 】 提出了采用距离最近分配法将多配送中心车辆调度问题分解为多个单配送中心车辆调 度问题进行求解的策略。王素欣等【删构建了以订单为基准、将货运关系明细化的车辆路 径问题模型。模型求解中约束条件考虑较多的是带时间窗的m d 冲【4 5 墩】。陈美军等【5 3 】 提出了先采用聚类蚁群算法将多车场带时间窗的车辆路径问题分解为若干个单车场车 辆路径问题，然后对多车场问题应用改进蚁群算法进行优化的求解思路。杨元峰阱】构造 出一种改进的模拟退火遗传算法。钟石泉【5 5 】针对多车场一体化车辆调度问题提出了改进 的遗传算法，采用了动态染色体和基于自然数的一体化配送路径表示方式。同时，还有 解析算法【5 6 】、禁忌算澍5 7 ，5 8 1 、扫描式算法和节约算法【5 9 1 、遗传算法【6 0 ，6 1 1 等。 1 3 本文的主要工作 针对国内外学者研究多需车场车辆路径优化问题的现状，本文开展并完成了以下方 面的工作： ( 1 ) 深入研究了非限定车场车辆路径问题。模型以配送货物为基准，把货物的起 点和终点表示出来，将货运关系明细化，只需要知道货物的起点和终点即可对车辆路径 进行优化。在其最小化车辆行驶距离的单目标优化函数的基础上，建立了考虑最小化车 辆数作为首要目标的双目标优化函数。 ( 2 ) 应用遗传算法对模型进行了求解。在求解问题的过程中，深入研究了遗传算 法的编码方式，采用了基因值可重复的整数编码方式，并设计了相应的解码方案和遗传 算子操作。整个求解过程分为两步，先得到单车需要运送的货物，再优化单车路径。最 后通过实例验证了模型的合理性以及算法的高效性。 论文共由六章构成。 第1 章阐述了车辆路径优化问题的研究背景，讨论了国内外对车辆路径问题及多车 场车辆路径问题的研究现状，同时给出了本文研究的内容。 第2 章主要介绍了多车场车辆路径问题，包括数学模型、配送模式及分类。多车场 车辆路径问题是车辆路径问题的扩展问题，因此在介绍多车场车辆路径问题之前，简单 介绍了车辆路径问题。 第3 章对遗传算法进行概述，首先介绍了遗传算法的基本思想、组成要素以及运行 过程，其次分析了遗传算法的特点和应用领域。 第4 章首先分析了限定车场车辆路径问题研究模型中的一些局限性，介绍了初步探 5 东北大学硕士学位论文第l 章绪论 讨的非限定车场车辆路径问题的货运模式、特点以及现有的单目标优化函数模型，在此 基础上构建了改进的双目标优化函数模型。 第5 章应用遗传算法进行求解。整个求解过程分为两步：第一步先求出单车需要运 送的货物，第二步进行单车路径优化。结合问题的实际情况及数学模型，采用了可重复 整数编码方式，并构造了相应的解码方法。最后设计了相关的仿真实验，并做比较验证 了算法的更优性。 第6 章对全文做出总结，系统的归纳了在论文完成过程中得到理论研究成果，展望 了未来的研究趋势。 6 东北大学硕士学位论文第2 章多车场车辆路径问题概述 第2 章多车场车辆路径问题概述 多车场车辆调度问题( m d v r p ) 是基本车辆路径问题( v r p ) 的扩展，在介绍多车场车 辆路径问题之前，先对车辆路径问题进行简单介绍。 2 1 车辆路径问题概述 2 1 1 车辆路径问题的基本概念 车辆路径问题( v e h i c l er o u t ep r o b l e m ，v r p ) 最早由学者d a i l t z i g 和r 锄s e r 于l9 5 9 年 首次提出【6 2 】，他们把服务对象称为顾客( c u s t o m e r 或c o n s 啪神，把满足顾客的需求称为 服务( s e n ，i c e ) ，把顾客的所在位置称为需求节点( n o d e ) ，把提供服务所使用的车辆称为服 务车辆( v e h i c l e ) ，把车辆的出发点称为配送中心( d 印o t ) 。 v i 冲是一个典型的组合优化问题，通常定义为：对一系列装载点和( 或) 卸货点， 组织适当的行车线路，使车辆有序地通过它们，在满足一定的约束条件( 如货物需求量、 发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等) 下，达到一定的目 标( 如路程最短、费用最少、时间尽量少、使用车辆数尽量少) 。基本的冲见图2 1 。 o o o o 圈 o o o 圈物流公司中心仓库或车场 。顾客 位置分散的顾客、配送中心路径优化结果 图2 1 基本车辆调度问题 f i g 2 1t h eb a s i cv r p 2 1 2 车辆路径问题的数学模型 v r p 可以看成是旅行商问题( t r a v e l i n gs a l e s m a np r o b l e i l l ，t s p ) 和装箱问题 ( b i n p a c k i n gp r o b l e m ，b p p ) 的组合问题： t s p ：如果假设车辆的装载能力为无穷大，这样就可以得到一个多旅行商问题 ( m u l t i p l et r a v e l i n gs a l e s m a np r o b l e i t l ，m t s p ) 。而一个m t s p 问题可以转化为一个等价的 t s p 问题：将代表车场的0 点复制七一1 次( 七为车辆数) ，并且设车场以及这些复制点之 间的路径距离为o 。 7 东北大学硕士学位论文 第2 章多车场车辆路径问题概述 b p p ：如果假设顾客点以及车场与顾客点之间的路径长度均为o ，这样问题就可以 转化为一个装箱问题。 因此，基于上述两种松弛，一个v r p 的可行解是一个对应于上述问题的t s p 巡回 ( t o 眦) ，该巡回必须满足装箱条件( 比如对应七个路线的顾客点的需求和不超过车辆的装 载能力) 。由于t s p 和b p p 均为n p - h a r d 问题，作为两者的组合问题，婢也是一个 n p - h a r d 问题。 从图论的角度，v r p 可以表示为一个完备图g = ( y ，么) ，y = 0 ，l ，2 ，咒) 表示顶 点集，其中o 表示车场。矿= ( 1 ，2 ，1 ) 表示顾客点集。4 = ( f ，) lf ，j y ，i j f ) 表示 弧集或边集。 对于v i 冲定义如下的符号： c ：f ：对于每一条弧( f ，) ，f ，赋一个非负的权重勺，表示顾客点或者顾客点和车 场之间的旅行费用等，对应于所有弧的费用q ，就构成了车辆路径问题的费用矩阵 c = ( 勺) 。 办：车辆路径问题中，两个节点间的空间距离。若c ：f ，= 和吒= 叱，称该问题为 对称车辆路径问题，否则称为非对称车辆路径问题。在文献中有些v r p 测试问题假设 节点间的旅行费用等于旅行距离，即勺= 毛。 q ：车辆的最大装载能力。 z ：顾客点f 的需求。 蘸：顾客点f 的车辆服务时间。 m ：服务车辆数，在车辆路径问题中假设所有的车辆都是同型的( h o m o g e n e o u s ) ， 也就是具有相同的最大装载能力和最大的车辆行驶距离约束。具有不同类型车辆的冲 称为异型车辆路径问题。 r ：车辆集，r = ( 1 ，2 ，垅) 。 r ：车辆路线，r = ( o ，0 ) ，f r 。 一般v r p 具有层次目标函数( h i e r a r c h i c a lo b j e c t i v e ) ，最小化车辆数和最小化车辆旅 行费用，在文献中一般以车辆数作为首要优化目标函数，在此基础上使得对应的车辆旅 行费用最小，下面给出v r p 的数学模型。 对于每一条弧，定义如下变量： f 1若车辆1 ，从顾客点f 行驶到顾客蔚 2 1o否则 f 1顾客点l 韵需求由车辆，睐完成 此产1o 否则 8 东北大学硕士学位论文 第2 章多车场车辆路径问题概述 v r p 问题的数学模型可以表示为： m i n f ( x ) = m ，+ 勃，c ：f ， ( 2 1 ) f = li = l f = o ，= ov = i s t l v _ ，( 2 2 ) v = l f = o 一嘞= o v p 矿，y r( 2 3 ) f = o ，= o = 1v ( 2 4 ) v ；i 唾q vv 尺 ( 2 5 ) f = i = v - ，v 尺 ( 2 6 ) f - l 式中，f ( x ) 表示目标函数；m 为一个无穷大的整数，通过在目标函数中引入参数 m ，能够保证算法在求解车辆路径问题时以车辆数为第一优化目标，以车辆旅行费用 作为第二优化目标，也就是一个具有较少车辆数的解比一个具有较大车辆数但是较小车 辆旅行距离的解好。约束条件( 2 2 ) 表示每个顾客点至少被车辆服务一次；约束条件( 2 3 ) 为车流约束，它要求一辆车到达一个节点( 车场或者顾客点) 完成服务后必须离开这个 节点；约束条件( 2 4 ) 表示顾客点f 只能由一辆车来服务；约束条件( 2 5 ) 为车辆能力约束， 它表示车辆y 服务的路线上的顾客点的需求之和不能大于车辆的装载能力q ；约束条件 ( 2 6 ) 表示顾客点_ ，只能由来之其它顾客点f 的所有车辆中的一辆车来服务。 2 1 3 车辆路径问题的构成要素 一个典型的车辆路径问题的特征要素主要包括以下几个方面：道路网络( r o a d n e t 、o r k ) 、顾客点( c u s t o m 砷、车场点( d 印o t ) 、车辆( v e h i c l e ) 、边约束( s i d ec o n s t r a i n t ) 和运 作目标( o p e r a t i o n a lo b j e c t i v e ) 。为叙述问题方便，这里我们将车辆配送和收集的对象统称 为货物。下面我们分别给出这些核心要素的主要特征。 2 1 3 1 道路网络 道路网络是货物运输的基础，它是构成车辆路径问题的最核心的要素之一。道路网 络通常用一个由节点( v 鲥e x ) 和弧( a r c ) 组成的赋权图( w e i 曲t e dg r a p h ) 来表示。其中节点表 示车场点或者顾客点，弧代表道路网路中顾客点和车场点间或顾客点间的道路联接。根 据运输网络中联接两点间的道路特征的不同，相应地弧可以分为有向弧和无向弧。有向 弧是指车辆仅可以向一个方向行驶的道路，比较典型的是城市交通网络中单向行驶的道 路，无向弧是指车辆可以在两个方向上行驶的双向道路。对应于每条弧，赋有一个非负 的费用权重，根据实际研究的需要，可以赋予它不同的含义，例如可以表示两点间的旅 9 东北大学硕士学位论文第2 章多车场车辆路径问题概述 行距离、旅行时间等。通常假设车辆路径问题中，节点间的费用满足三角不等式约束。 在关于车辆路径问题的研究文献中，根据节点间的双向费用权重是否相等，可以将问题 分为对称车辆路径问题和非对称车辆路径问题。相应地非对称车辆路径问题的道路网络 用有向图表示，对称车辆路径问题中的道路网络用无向图来表示。 2 1 3 2 顾客点 顾客点是一个统称，其可以表示实际车辆路径问题中任意类型的服务对象，比如零 售商店、分销点、宅急送中的个体家庭、货物配送分支点等。对应于顾客点其典型的特 征属性包括以下几个方面： ( 1 ) 顾客点对应于车辆路径问题表示的网络图中一个节点； ( 2 ) 顾客点有一个服务需求量，其可以是从车场点给顾客点配送的货物量，也可以 是需要从顾客点收集到车场点的货物量； ( 3 ) 顾客点服务时间，其可以表示顾客点的货物卸车时间或者货物收集时间； ( 4 ) 顾客点服务时间窗或时间期限对应于某些类型的顾客点可能其有一个服务时 间窗口，它指每天车辆可以对顾客点开始服务的时间区间，包括允许的最早开始服务时 间和最迟允许开始服务时间。而对于某些特殊的车辆路径问题，顾客点仅有一个允许的 最迟开始服务时间； ( 5 ) 顾客点其它约束，比如对于本文后面给出的带拖车车辆路径问题中，由于受交 通条件的制约，某些顾客点只能由部分类型的车辆对其进行配送或收集服务。 2 1 3 3 车场点 在表示车辆路径问题的网路图中，除了顾客点，另一类重要的节点就是车场点。车 场点是每条车辆路线的起点或终点，车辆从车场点对顾客点进行货物配送或者从顾客点 收集货物到车场点。车场点驻扎有一组车辆来完成对顾客的配送或收集服务。一般文献 中研究的车辆路径问题中均假设仅有一个车场点。 2 1 3 4 车辆 v i 冲中由一组车辆完成对顾客点的货物配送或货物收集服务，其典型的特征主要包 括以下几个方面： ( 1 ) 车辆类型：在一般的v i 冲文献中均假设车辆同质在实际的配送管理中车队一 般是由具有不同装载能力不同固定成本以及可变成本的异型车辆组成； ( 2 ) 车辆装载能力：其可以表示车辆最大的载重量或最大的装载货物容量等； ( 3 ) 车辆成本：这里的车辆成本主要是指使用车辆的固定成本以及可变成本，可变 成本可以是单位公里的费用或单位时问的费用等； 1 0 东北大学硕士学位论文第2 章多车场车辆路径问题概述 ( 4 ) 车辆持续期：货物配送或者货物收集的车辆有一个最大允许行驶距离或时间约 束，对应于实际问题可以表示车辆司机最大的r 工作时间； ( 5 ) 车辆组成：这里说的车辆组成是指对于一些特殊的车辆路径问题中，货物配送 或者收集的每一个车辆由卡车和拖车两部分组成，受交通等条件的制约，某些顾客点只 有卡车可以通达，其服务只能由卡车来完成。 2 1 3 5 边约束 这里说的边约束是指车辆路线必须满足的约束条件。车辆路径问题的边约束主要有 以下几种类型： ( 1 ) 每条车辆路线上服务的顾客点总的需求量之和不能大于车辆的装载能力； ( 2 ) 每条车辆路线的车辆行驶的距离或行驶时间不能大于其最大持续期； ( 3 ) 每个顾客点的需求必须被满足； ( 4 ) 每个顾客点的需求只能由一辆车完成服务且只能被访问一次。 2 1 3 6 运作目标 根据实际研究的车辆路径问题属性特征的不同，总体上车辆路径问题的优化运作目 标可以分为多目标和单目标两类。文献中典型的单目标优化函数主要有： ( 1 ) 最小化旅行距离； ( 2 ) 最小化车辆数； ( 3 ) 最小化总的运输费用，运输费用主要包括车辆固定成本、可变成本等； ( 4 ) 层次化优化目标函数，以车辆数作为首要的优化目标，在此基础上优化对应的 车辆旅行距离。 多目标主要是指研究的车辆路径问题需要同时优化多个目标函数，比如需要同时考 虑最小化旅行距离、最小化驾驶员薪酬以及最小化车辆数。由于实际配送管理中，许多 车辆路径问题均为多目标情况下的决策优