（管理科学与工程专业论文）满载车辆调度问题研究.pdf

摘要 摘要 满载车辆调度问题是物流运输领域中一个非常值得研究的问题。物质流通 成本的相当一部分发生在具体的车辆运输中，因而稍微的节约都会导致流通成 本的大幅下降。通过科学合理的方法确定运输路线和时间，不仅可以降低运作 成本，还可以加快物质配送速度、提高运营效益和保证顾客服务水平。但是由 于具体的调度问题中存在各种各样的约束条件和优化目标，使得车辆调度成为 运输运作中的一个难点。本文重点研究具有时间窗约束等多种约束条件的满载 车辆调度问题。 首先介绍了课题的研究背景和研究现状，对车辆调度问题目前的研究进展 情况进行简要的回顾并对当前研究存在的问题做出总结。进而确立本文的研究 内容和研究框架。 而后描述了满载车辆调度问题，包括定义、研究目标、构成要素和问题分 类。在此基础上介绍了目前用于解决该问题的几种优化算法，既有分支定界、 列生成等精确算法，也有节约法、遗传算法等启发式算法。并重点研究了调整 的节约算法在满载车辆调度中的应用，针对带最长时限和时间窗约束的静态满 载问题，建立了相应的数学模型并构造了基于节约法的启发式算法来求解问题。 再者重点研究了约束规划及其在车辆调度中的应用软件产品d i s p a t c h e r 。介 绍了约束规划的特点与实质，建模的一般步骤与建模技巧，模型的解搜索框架 及关键要素一约束一致与约束传播。简要介绍了d i s p a t c h e r 的应用特点与建立车 辆调度模型的主要要素及其意义；并详细介绍了d i s p a t c h e r 求解车辆调度模型的 算法一两阶段方法，并对其初始解构造算法和改进算法做出了详细的说明与分 析。 然后重点研究了启发式算法和约束规划软件一车辆调度产品d i s p a t c h e r 在 一个实际满载车辆调度问题中的应用。通过介绍了w 公司的车辆运营业务特点， 清晰描述了该问题涉及的要素，分析了现存车辆调度方案的合理之处与问题所 在，对于不当之处从策略层和执行层给出应对策略。根据分析的结果，针对问 题特点给出两类方法，第一类应用启发式调度算法解决其废钢模块车辆调度问 题；第二类以d i s p a t c h e r 为建模平台，嵌套前面介绍的初始解构造算法和改进算 法来解决其钢渣模块的车辆调度问题。根据客户出示的用户报告和收集到的数 摘要 据进行的绩效分析表明，调度方案取得了不错的优化效果。 最后总结了本文的研究内容，并对进一步的研究进行了展望。 关键词：满载车辆调度问题，启发式算法，约束规划 i l 一 垒堕! 型 a b s t r a c t v e h i c l es c h e d u l i n gp r o b l e mw i t hf u l l - l o a d sh a sl o n gb e e nah o tr e s e a r c hi s s u ei n l o g i s t i c s & t r a n s p o r t a t i o ni n d u s t r y a s t h e t r a n s p o r t a t i o n c o s t o c c u p y a g r e a t p r o p o r t i o ni nt h ec i r c u l a t i o nc o s to fg o o d s ，as m a l ld e c r e a s eo fi tw o u l dc a u s eag r e a t d e a ls a v i n g s as c i e n t i f i ca n dr a t i o n a lv e h i c l es c h e d u l i n gm e t h o dw i l ln o to n l yr e d u c e t h ec o s t ，b u ta l s oi n c r e a s et h ec i r c u l a t i o ns p e e d ，i m p r o v et h eo p e r a t i o ne f f i c i e n c ya n d r a i s et h es e r v i c el e v e l h o w e v e r , t h e r ee x i s tm a n yc o n s t r a i n t sa n d o p t i m i z a t i o nt a r g e t s ， w h i c hc a u s ei td i f f i c u l tt os o l v e s o ，h o wt os o l v et h ev s p f lw i t hm u l t i c o n s t r a i n t si s t h et o p i ct h i sp a p e rf o c u s e so n t h i sp a p e rb e g i n sb yi n t r o d u c i n gt h eb a c k g r o u n da n dt h ea c t u a l i t yo ft h er e s e a r c h o fv s p f l , r e v i e w st h el i t e r a t u r ei nt h i sf i e l da n ds u m s u pt h es h o r t c o m i n g se x i s t e di n t h er e s e a r c h t h ec o n t e n ta n dt h ef r a m eo ft h er e s e a r c ha r ea l s op u tf o r w a r di nt h i s p a r t n e x t ，t h ev s p f li sd e s c r i b e di nd e t a i l ，i n c l u d i n gi t sd e f i n i t i o n ，o b j e c t i v ea n ds o r t s o nt h i sb a s i s ，t w ok i n d so fs o l v i n gm e t h o d sa r ei n t r o d u c e d o n ei st h em a t hm e t h o d ， s u c ha sb r a n c h i n ga n dc o l u m n - g e n e r a t i o n t h eo t h e ri st h eh e u r i s t i cm e t h o d ，s u c ha s s a v i n ga n dg e n ea l g o r i t h m a f t e r w a r d s ，a ni m p r o v e dm e t h o db a s e do ns a v i n gi s d e v e l o p e dw h i c ha i m st om i n i m i z et h ev e h i c l ec o s t a f t e rs u m m a r i z i n gt h r e eb a s i c r o u t es t r u c t u r e sa n da d d i n gb o t hf i x e da n dv a r i a b l ec o s t so fv e h i c l e si n t os a v i n g c a l c u l a t i o n ，ao p t i m i z e dr o u t ew a sg o tb yc h o o s i n gt h ec o n n e c t i n gt e c h n i q u el i k e s a v i n g m a x i m i z a t i o no ro p p o r t u n i t y s a v i n gm a x i m i z a t i o n i tp r o v e st o g e t a n o p t i m i z e dr e s u l tv i at h ee x a m p l e f u r t h e r m o r e ，c o n s t r a i n tp r o g r a m m i n g ，an e wi d e au s e dt os o l v ev s p f l , i sp u t f o r w a r d i t sc h a r a c t e r , e s s e n t i a l ，m o d e l i n gp r o c e d u r e sa n ds k i l l s ，s o l v i n gf l a m ea n d k e yi s s u e sa r ea l lp r e s e n t e di nt h i sp a r t d i s p a t c h e r , as o f t w a r et o o lw h i c ha p p l i e dt h e c p t h o u g h ta n d u s e dt os o l v et h el a r g e s c a l ev s pi sa l s or e f e r r e di nt h i sp a r t t h e n ，av s p f lw i t hm u l t i c o n s t r a i n t s i n p r a c t i c e i sd i s c u s s e d a f t e rt h e d e s c r i p t i o no ft h i sp r o b l e m ，w ea n a l y z e dt h ec o n d i t i o nc a r e f u l l y , a n dc o n s t r u c tt h e j i i a b s t r a c i s o l u t i o nt oi t i nt h i sp a r t ，w em o d e lu s i n gd i s p a t c h e r , w h i c hc a ne a s i l ya d dk i n d so f c o n s t r a i n t si n t oi t ；w es o l v eu s i n gt w o p h a s em e t h o da n dc pt h o u g h t t h es o l u t i o n p r o v e st ob es u c c e s s f u la f t e rt h ea n a l y s i so fi t sp e r f o r m a n c e f i n a l l y , t h ep a p e rs u m m a r i z e st h em a i na c h i e v e m e n to ft h es t u d ya n dp o i n to u tt h e f u t u r es t u d yd i r e c t i o n k e y w o r d s ：v s p f kh e u r i s t i c s ，c o n s t r a i n tp r o g r a m m i n g 学位论文版权使用授权书 本人完全j ，解同济大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电了版 本；学校有权保存学位论文的e 剧本和电子舨，并采用影e 、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在一i 以赢利为目的的前 提卜，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：? # 磊 磷f 月牛闩 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名；学位论文作者签名： 年月 目年月日 同济大学学位论文原郇性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及韵研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 签名：；反绲 沙一年r 月目 第1 市绪论 1 1 研究背景 第1 章绪论 随着经济的发展，物流对经济活动的影响日益明显。据专家测算，现代物 流成本约占企业经营成本的3 0 5 0 ，当一个有效的物流系统与企业主要商业系 统集成之后，可使仓储量降4 k i 5 0 ，准时交货率提高4 0 ，营业收入增加1 0 以 上1 1 j 。现代物流已被公认为是企业在降低物质消耗、提高劳动生产率以外创造利 润的第三个重要源泉，也是企业降低生产经营成本，提高产品市场竞争力的重 要途径【2 1 。 据中国物流与采购联合会、中国物流信息中心统计，1 9 9 1 2 0 0 4 年，反应 物流需求规模的全社会物流总值从3 万亿元上升到3 8 4 万亿元，增长了1 2 8 倍， 年均增长2 1 7 ，大大高于同期g d p 的年均增速。物流总值的高速增长，表明 经济增长对物流的需求越来越大，经济发展对物流的依赖程度也越来越高。同 期，我国全社会物流总成本从5 1 8 2 亿元扩张到2 9 1 1 4 万亿元，增长了5 6 倍， 年均递增1 4 ，高于经济年均递增4 个百分点左右。但这种增长势头趋于减缓， 1 9 9 12 0 0 4 年，物流总成本占g d p 总值的比例从2 4 下降到2 1 3 。其中， 运输成本占社会物流总成本的比重为5 7 ，保管成本占社会物流总成本的比重 为2 9 ，管理成本占社会物流总成本的比重为1 4 。这说明我国物流总效益在 提高。但物流成本总体水平仍然偏高，与美国、t q 本、欧盟国家比要高出8 1 0 个百分点【3 j 。在这种形势下，研究如何通过实旌科学的物流管理，以提高物流效 率、降低物流成本、提高服务质量是十分必要的。 物质配送系统是物流系统设计的一个重要组成部分，它分为三个层次：战 略层、策略层、操作层。配送节点设施( 比如车场、工厂、仓库) 的选址、数 量及网络布点属于战略决策，一旦决定，就对整个系统有着长远的影响；车队 规模、车队组成、货运方式、承运商选择和节点库存属于策略决策；而车辆配 送路线、时间表设计等则属于操作层决策【4 】。 物质配送操作层主要包含两个问题，一是车辆路线安排，二是车辆时间安 排；我们将其统称为车辆调度问题。由于物质配送的相当一部分成本发生在具 弟1 审绪论 体的车辆运输中，因而即使是稍微的节约都会导致成本的大幅下降；此外合理 的车辆调度通过加快配送速度、提高反应速度能够快速满足客户要求，提高客 ，1 的满意度；而对于调度人员， 一个快速调度信息系统也会大大降低其工作强 度、提高调度效率。易见，车辆调度合理与否对物质配送速度、成本、效益和 顾客服务有着很大的影响，采用科学、合理的方法来确定运输路线和时间，是 物资配送中非常重要的项工作。 国外将车辆调度问题归结为v r p ( v e h i c l er o u t i n gp r o b l e m ，即车辆路径问 题) 、v s p ( v e h i c l es c h i e d u l i n gp r o b l e m ，即车辆调度问题) 和m t s p ( 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 ，却多路旅行商问题) 1 5 l 。在现实生产和生活中，邮 政投递问题、飞机、铁路车辆、水运船舶及公共汽车的调度问题、电力调度问 题、管道铺设问题、计算机网络拓扑设计问题等都可以抽象为物流车辆调度问 题。它是对一系列发货点和( 或) 收货点，构造适当的行车路径，使车辆有序地通 过他们，在满足一定约束条件的情况下，达到一定的目标。该问题于1 9 5 9 年由 d a n t z i g 和r a m s e r l 6 l 提出后，很快便引起运筹学、应用数学、组合数学、图论与 网络分析、物流科学、计算机应用等学科的专家以及运输计划制定者的极大重 视，并一直是运筹学与组合优化领域的前沿与热点问题。 车辆调度问题可按照其构成要素划分为不同的种类， b o d i n , g o l d e n ，d e s r o c h e r s l 7 】【8 】等人从不同的角度，按不同的标准进行了多种分类。 ( 1 ) 按物流中心的数目分，有单物流中心问题( 配送系统中仅有一个物流中心) 和多 物流中心问题( 配送系统中存在多个物流中心) 。 ( 2 ) 按车辆载货状况分，有满载闯题、非满载问题。 ( 3 ) 按客户对货物取( 送) 时闻的要求分，有无时限问题( 客户对货物的取走或送到 的时间无具体要求) 和有时限问题( 客户要求将需求的货物在规定的时间窗内送 到，将供应的货物在规定的时间窗内取走，也称为有时间窗问题) 。 ( 4 ) 按车辆类型数分，有单车型问题( 所有配送车辆的载重量相同) t 和多车型问题 佰a 送车辆的载重量不完全相同) 。 ( j ) 按车辆对车场的所属关系分，有车辆开放问题( 即车辆完成配送任务后可以 不返回其发出车场) 和车辆封闭问题( 车辆完成配送任务后必须返回其发出车 场) 。 ( 6 ) 按配送任务特征分，有纯送货问题( 仅考虑从物流中心向客户送货，也称为 纯卸问题) 、或纯取货问题( 仅考虑把各客户供应的货物取到物流中心，也称为 第1 章绪论 纯装问题) 、及取送混合问题( 既考虑将客户需求的货物从物流中心送到各个客 户，同时考虑将客户供应的货物从客户取到物流中心，也称为装卸混合问题或 集货和送货一体化问题) 。 1 2 研究现状 在过去的数十年中，国内外对物流运输车辆调度问题作了大量而深入的研 究。研究证实了车辆调度问题具有复杂的计算性质，是一个典型的n p i j 题【9 】：依 据问题分类提出了许多类算法。算法多是针对非满载车辆问题进行的，对于满 载车辆调度成果较少。满载问题较为复杂，通常混合有时间窗、多车场、集送 一体化的特点，因而要研究满载问题，必须要首先研究以下几类问题及其解决 方法。 ( 1 ) v r p t f f ( 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 ，带时问窗的车辆调 度问题) d e s r o c h e r s ”】利用列生成方法解决了多达5 0 个访问点和一些接近t 0 0 个访问点 的车辆运输问题；k o h l 和m a d s e n 1 1 】利用拉格朗日松弛方法将所有访问点都需要 满足的约束从约束集合中移去，从而将问题分解成有时间和载重限制的最短路 问题，并应用捆绑方法解决了多达1 0 0 个访问点的车辆调度问题；p a d b e r g 和 r jn a l d i 1 2 1 则首次利用切平面法求解大型旅行商问题；a r a q u e 1 3 1 利用分支定界法 求解了车辆调度问题；c o o k 和r i c h 1 4 】利用“t w o p a t h ”切割方法和并行计算求 解了多达2 0 0 个访问点的v r p t w ：而j o n a t h a nf b a r d ，g e o r g e k o n t o r a v d i s 和g a n g y u l l 5 1 设计了一种混合算法，即用切平面方法解决混合整数规划，用启发式方法 解决分离问题，取得了良好的效果；d k g u p t a ，b r u n o “】对普通的v r p t w 给 出了禁忌搜索算法；b e r t h o l d 、m a l m b o r g 、o c h i 、姜大立、李大卫、李军、谢 秉磊、张涛等人都曾利用遗传算法求解物流配送路径优化问题，并取得了一些研 究成果。 ( 2 ) m d v s p ( m u l 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 ，多车场车辆调度问题) b a l l 【1 7 】最早提出了多车场问题，在其文献中他设计了这样一种启发式算法：先 求路径，再路径聚群，从而解决问题；s k i t t 和l e v a r y l l 8 l 则在其文献中，把所有 可能路径看为变量，建立一个整数规划模型，从而提出了一种基于列生成的启 发式算法求解多车场问题：d e l l 和a m i c o l l 9 1 提出了一种更为有效的启发式算法： 第1 章绪论 纯装问题) 、及取送掘合问题( 既考虑将客户需求的货物从物流中心送到各个客 户，同时考虑将客户供应的货物从客j 取到物流中心，也称为装卸混合问题或 集货和送赁一体化问题) 。 1 2 研究现状 在过去的数十年巾，国内外对物流运输车辆调度问题作了大量而深入的研 究。研究证实了车辆调度问题具有复杂的计算性质，是个典型酐j n p l d 题【9 】；依 据问题分类提出了许多类算法。算法多是针对非满载车辆问题进行的，对于满 载车辆调度成果较少。满载问题较为复杂，通常混台有时间窗、多车场、集送 一体化的特点，因而要研究满载问题，必须要首先研究以下几类问题及其解决 方法。 ( 1 ) v r p l l w ( v e h i o 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 5 ，带时问窗的车辆调 度问题) d e s r o c h e r s ”】利用列生成方法解决了多达5 0 个访问点和一些接近) 0 0 个访问点 的车辆运输问题；k o h l $ 1 m a d s e n ”】利用拉格朗口松弛方法将所有访问点都需要 满足的约束从约束集合中移去，扶而将问题分解成有时问和载重限制的最锕路 问题，并应用捆绑方法解决了多达1 0 0 个访问点的车辆调度问题；p a d b e r g ； 1 r in a l d i ! t z l 则首次利用切平而法求解大型旅行商问题；a r a q u e ”1 年4 用分支定界法 求解了车辆调度问题：c o o k 和r j c h l l 4 j 利用“t w o p a t h ”切割方法和并行计算求 解了多达2 0 0 个访问点的v r p t w ；而j o n a t h a nf b a r d ，g e o r g e k o n t o r a v d i s 和g a n g y u t ”i 设计了一利- 混合算法，即用切平面方法解决混合整数规划，用启发式方法 解决分离问题，取得了良好的效果；d k g u p t a ，b r u n o “j 对普通的v r p t w 给 出了禁忌搜索算法；b e r t h o l d 、m a l m b o r g 、o c h i 、姜大立、李大卫、李军、谢 秉磊、张涛等人都曾利用遗传算法求解物流配送路径优化问题，并取得了一些研 究成果。 ( 2 ) m d v s p ( m u l t id e p o zv e h i c l ee e h e d u l i n gd r o b l e m ，多车场车辆调度问题) b a l l 最早提出了多车场问题，在其文献中他设计了这样一种启发式算法：先 求路径，再路径聚群，从而解决问题；s k i t t 和l e v a r y ”】贝q 在其文献中，把所有 可能路径看为变量，建立一个整数规划模型，从而提出了一种基于列生成的启 发式算法求解多车场问题；d e l l 薄l a m ic o i ”1 提出了一种更为有效的启发式算法： 发式算法求解多车场问题；d e l l ；f 1 a m i e 0 1 1 9 1 提出了一种更为有效的启发式算法： 第1 章绪论 把所有访问点和路段组成个网络，通过寻求最短路，移除不能行走的路段， 然后利用网络单纯型算法求解。使得完成任务使用的车辆数最少：d e s r o s i e s 2 0 l 把多车场问题转化为非对称的旅行商问题，利用e a r p a n e t o 和，r o t h l 2 l 】设计的求解 旅行商问题的算法解决该问题；r i b e i r o 和s o u m i s 2 2 j 提出一种集合分解方法，通 过设计列生成方法得到一个高效的分支定界方法解决了拥有太多变量的线性规 划问题；l o b e l1 2 3 1 设计了种算法，对于具有多种货物流的网络框架，通过求解 拉格朗臼约束解决多车场问题。而对于带时间窗的多车场车辆调度问题， b i a n c 0 1 2 4 1 首次对此作了探讨，镳设计了一种基于分解思想的算法，在分支定界 过程中，通过取变量酌上下界来减少变量数目；d e s a u l n i e r s 2 5 ) 把m d v s p t w 转换 成非线性整数网络流问题，在分支定界算法中嵌套列生成按巧和无回溯的深度 搜索来求解问题。 ( 3 ) p d p ( p i c k u pa n dd e l i v e r yp r o b l e m ，集送货一体化问题) 集送一体化最初研究是针对一辆车的配送闯题而进行韵，p s a r a f i 一”l 提出了一 种动态规划算法规划车辆配送路线，该方法只能解决访阀点很少的调度问题； s e x t o n 和b o d in 1 2 7 呗0 把该问题分离为路线划分主问题和路线调度子问题，并设立 线性规划模型进行求解；v a nd e rb r u g g e n 2 8 1 在弧交换的基础上设计了两阶段启 发式算法和模拟退火算法，取得不错的效果。对于多车辆的集送货问题，d u m a s 2 9 l 利用列生成方法来解决具有容量、时间、优先权限约束韵最短路问题： s a v e l s b e r g h l 3 0 l 在其文献中把集送一体化问题分为因部分：静态单车辆p d p 、静 态多车辆p d p 、动态单车辆p d p 、动态多车辆p d p ，并建立了一个通用模型，对各 种特点的集送问题进行了分析；w i l l i a m 和b a r n e s l 3 1 1 给出了一个交互的禁忌搜索 算法，该算法对违反约束设立惩罚成本，目标是使总费用最小；w p n a n r y 和 i 】w b a r n e s 3 2 1 设计了解决带时间窗集送问题的禁忌搜索算法；j a w 3 3 l 设计了一个 三阶段算法，首先分组，通过划分时间段把入物分为不同的几个任务组，然后 聚群，把同一组的相邻的任务聚在一起，分配一辆车来执行，最后进行路径规 划，对每一辆车进行线路优化。 ( 4 ) v r p f 。( v e h i c l er o u t i n gp r o b l e mw i t hf u l ll o a d s ，满载车辆调度问题) d e s r o s i e r s ，l a p o r t e * b s a u v e 3 4 1 率先研究了满载情况，目标是空载里程最短， 在其文献中建立了一个基于扩展图模型，把访问点和路段分别看作图中的点和 弧，构造了一个基于解决非对称旅行商问题的分支定界方法；rhc u r r i e 和s s a l h i 3 5 】研究了货物不同、车辆类型不同、带时间窗韵满载车辆调度问题；他们 第1 章绪论 把该问题首先建成0 1 规划问题，然后构造了个混合算法，该算法动态的选择 贪婪算法和后悔成本算法，是一个多层构造算法；s u n d a r a r a j a n a r u n a p u r a m ，k a m l e s hm a t h u r 军f f d a n i e ls o l o w p q 对满载车辆调度中的整数规划提 出了一个新的分支定界方法，在分支定界树的每个分支点用列生成法来解决线 性约束，该文献的最大特点就是构造了一个解决列生成子问题的动态规划算法一 标号法；m a n f r e dg r o n a l t 3 7 探讨了带有时间窗的满载问题，对于模型中的整数 规划问题，文献给出了四种基于节约法的启发式算法一节约法、节约改进法、 机会节约算法、同步节约算法，并对四种方法进行了算例分析，文章最后还对 时间窗的松紧情况进行了敏感性分析；国内郭耀煌、李军【3 8 】分析了满载车辆调 度问题的特点，提出了一种实用性很强的交互式优化方法，把复杂的调度问题 的多个目标置于求解的不同过程，对得到的解进行调整，连通化处理，构造成 网络线路，再对线路运用2 一交换，3 一交换等方法平衡线路，最终得到问题的满 意解；张明善和唐小我【3 9 i 对多车场满载的车辆调度问题建立了网络流模型，给 出了一个基于网络流最优解的启发式算法，该算法对每一条路线的确定总是基 于修改后的网络流模型的最优解，大大提高了算法结果的优化质量。 文献表明，现在车辆调度研究中的主要算法为： ( 1 ) 精确算法 精确算法主要包括三种技术：分支定界、列生成和拉格朗日松弛。 ( 2 ) 启发式算法 启发式算法主要包括遗传算法、禁忌搜索、模拟退火、蚁群算法等。 ( 3 ) 约束规划 约束规划是新技术，使用者可使用开发好的包含通用求解程序的约束规划系统 来解决问题。 实际中遇到的车辆调度问题多是由以上问题组成的混合问题，解决方法也 往往需要多种方法联合来解决。研究中存在的问题如下： ( 1 ) 当前研究集中于具有单一约束条件( 主要是时间窗) 的满载车辆调度问题， 然而实际上与约束条件还包括车辆与货物的匹配关系、车辆的容积率、车辆的 行驶路线限制等问题，因此理论与实践差距还较大。 ( 2 ) 当前的满载车辆调度算法多采用数学规划和各种启发式算法，算法性能和锵 的质量在面对大规模问题时得不到保证。现在国外对约束规划的研究非常热， 但国内对其认识还比较浅，难于应用。 第1 章绪论 ( 3 ) 以往满载车辆调度问题的研究都是基于静态、平稳的任务，而对动态任务， 应急情况进行的调度问题研究较少，现有理论难以解决实际生活中多变的车辆 调度问题。 1 3 本文研究内容 本文以w 公司车辆优化调度项目为背景，该项目所要解决的问题属于满载车 辆调度问题，同时又具有时间窗，多车场，集送一体化的特点。因此本文的研究内 容是有多种约束条件的满载车辆调度问题。其主要包括三方面的内容： 第一部分研究传统的满载车辆优化调度理论及相应方法并提出了基于节约法的 启发式算法。研究的方法有线性规划方法、节约法、遗传算法。 第二部分研究分析约束规划技术及应用该技术开发的用于解决车辆路径优化问 题的软件产品d i s p a t c h e r 。主要分析约束规划的精神思想并对d i s p a t c h e r 中的 算法构造做基本的探讨。 第三部分以d i s p a t c h e r 为平台，研究w 公司满载车辆优化调度问题，对该实际 问题进行分析。建模，选择适当豹算法，给出解决方案并加以评价。 1 4 本文研究框架 满载车辆调度问题分析 传统解决算法 部分算法改进 约束规划 车辆优化调度软件d i s p a t c h e r w 公司满载车辆调度问题分析 w 公司满载车辆调度解决方案 图1 - 1 研究框架豳 文章首先对满载车辆调度问题进行了较为详细的分析，包括闯题定义、组 第1 章绪论 成要素和分类等。在此基础上，分两块研究该问题的解决方法，其一是传统的 精确算法和启发式算法，其二是约束规划方法。对于前者，研究分析了线性规 划方法、节约法和遗传算法，并构造了基于节约法的改进的启发式方法；对于 后者，研究了约束规划的一般理论，并介绍了基于约束规划机制的用于解决车 辆调度的软件产品d i s p a t c h e r 。而后，以一个实际满载车辆调度问题为研究对象， 综合应用上述方法进行求解。 第2 审满载车辆训度问题概述及优化算法 第2 章满载车辆调度问题概述及优化算法 2 1 满载车辆调度问题概述 2 1 1 问题描述 满载车辆调度阚题由b a l ，b o d i n ，g o l d e n 4 0 1 等人于1 9 8 3 年提出，其典型背景 就是生产流通过程的运输组织和实施。大型企业转播枢纽及物流配送中心之间 往往存在大宗货物的运输，需要车辆多车次满载执行，从而产生了满载车辆调 度问题。 满载车辆调度问题又称多重运输调度闯题，在一个存在供求关系的系统 中，有若干个货栈，若干个车场，以及若干辆车，车辆幽车场出发最后回到车场， 在货栈i 到j 有5 。( 车辆实际载重的整数倍) 的货物由车辆来运输，在给定的 约束条件下，求出完成这些运输任务使得成本最小的车辆调度方案。 捌2 一l 满载车辆调度网络模型 运用网络模型，能够较为直观地说明问题( 如图2 一1 ) ，满载车辆调度问题的 网络模型可描述如下： 设g = ( v ，e ) 是一个边赋权连通网络，v 是顶点集，表示货栈与车场，e 是( 无向) 边 集表示运输的距离、时间或费用等；定义? = ( 6 ，。) ，。为供求矩阵，6 。 o ( 为整 数) ，表示i 到j 的货运数( 车辆实际载重的整数倍) ：w = ( 矾，w ：，w x ) 为车辆配 置向量，w ，( w i 0 ，整数) 表示车场i 处车辆配置数： 要求：完成供求矩阵的运输任务，满足约束条件 问题：求使总成本最低的运输调度方案。 第2 章满载车辆调度问题概迷及优化算法 2 1 2 问题构成要素 物流配送车辆调度问题主要包括货物、车辆、物流节点、运输网络、约束 条件和目标函数等要素。 ( 1 ) 货物。货物是配送的对象。将每个物流节点需求或供应的货物看成一批货物， 每批货物包括品名、包装、重量、体积、要求送到或取走的时间和地点、能否 分批配送等属性。品名和包装，是选用配送车辆的类型以及决定浚批货物能否 与其它货物装在同一车辆内的依据。重量和体积是进行车辆装载决策的依据。 送到或取走时间和地点是制定车辆的出行时间和配送路线的依据。允许分批配 送，是指某个节点的需求或供应的货物可以用多辆车分批执行。 ( 2 ) 车辆。车辆是货物的运载工具。其主要属性包括：车辆的类型、装载量、一 次运输的最大行驶距离、执行任务前的停放位置及完成任务后的停放位置等。 ( 3 ) 物流节点。是指进行集货、分货、配货、配装、送货作业的配送中心、仓库、 车站、港口、客户、车场等。其属性包括需求或供应货物的数量、需求或供应 货物的时间、需求或供应货物的次数及需求或供应货物的满足程度等。 供应货物的次数及需求( 或供应) 货物的满足程度等。 ( 4 ) 运输网络。运输网络是由顶点( 指物流节点) 、无向边和有向弧组成的。边、 弧的属性包括方向、权值和交通流量限制等。 ( 5 ) 约束条件。满载车辆调度问题应满足的约束条件主要包括： 货物与运输车辆的匹配要求。 物流节点对车辆类型、时间窗的要求。 网络路径对车辆，时间窗的要求。 车辆的最长工作时间和最大运输距离及最大实载量要求。 ( 6 ) 目标函数。对物流配送车辆调度问题，可以只选用一个目标，也可以选用多 个目标。经常选用的目标函数主要有： 运输总里程最短。运输里程与配送车辆的耗油量、磨损程度以及司机疲劳程 度等直接相关，它直接决定运输的成本，对运输业务的经济效益有很大影响。 配送车辆的吨位公里数最少。该目标将配送距离与车辆的载重量结合起来考 虑，即以所有配送车辆的吨位数( 最大载重吨) 与其行驶距离的乘积的总和最少 为目标。 综合费用最低。降低综合费用是实现配送业务经济效益的基本要求。在物流 第2 章满载车辆调度问题概述及优化算法 配送中，与取送货有关的费用包括：车辆维护和行驶费用、车队管理费用、货物 装卸费用、有关人员工资费用等。 准时性最高。由于客户对交货时间有较严格的要求，为提高配送服务质量， 有时需要将准时性最高作为确定配送路线的目标 运力利用最合理。该目标要求使用的较少豹车辆完成配送任务，并使车辆的 满载率最高，以充分利用车辆的装载能力。 劳动消耗最低。即以司机人数最少、司机工作时间最短为目标。 2 1 3 问题分类 物流配送车辆调度问题可按照其构成要索划分为不同的种类。 ( 1 ) 按车场数目分为单车场问题和多车场问题。单车场问题中所有车辆来自同一 个车场；多车场问题中可以根据目标不同选择不同车场的车辆。 ( 2 ) 按车辆类型分为单车型问题和多车型问题。单车型问题所有车辆的吨位、专 用性一样：多车型问题中有不同类型的车辆，视赞物特点、路径要求等约束进 行选择。 ( 3 ) 按车辆对车场韵所属关系分为开放车场问题和封阂车场问题。开放车场问题 中车辆完成配送任务后可以不返回其发出车场t 封闭车场问题中车辆完成配送 任务后必须返回其发出车场。 ( 4 ) 按物流节点、网络路径对货物取送时间的要求分为无时间窗问题和有时阆窗 问题。无时间窗问题中物流节点与网络路径对货物的取送或通过时间无具体要 求；有时问窗问题则要求货物的取送或通过要在规定的时间内，其又分为硬时 间窗问题和软时间窗问题：前者要求货物的取送或透过必须在规定的时间内， 既不钱提前也不能拖后，后者要求货物的取送或通过尽量在规定的时间内，倘 若提前或拖后则要实施一定的惩罚成本。 ( 5 ) 按运输任务的确定性分为静态调度词题和动态调度问题。在静态调度问题中 所有任务都是事先确定的，不会变动；而在动态调度问题中任务是不确定的， 随着任务的执行，不断有新任务产生，既有任务也可能会变动，大大增加了调 度的难度。 ( 6 ) 按优化目标分为单目标问题和多目标问题。单目标问题只考虑某个目标：多 目标问题则同时考虑若干个目标，求取能使总目标最优的调度方案。 1 0 第2 章满载车辆调度问题概述及优化算法 2 2 满载车辆调度优化算法 满载车辆调度优化方法是满载车辆调度的核心技术，它直接决定了车辆的 使用效率和企业运作成本。它通过利用逻辑、分析、定量化的方法，根据预先 设定的优化目标，在满足各种预设的约束条件下，对有限的运输资源进行最合 理的统筹安排。随着计算机技术的发展，优化算法不断完善，求解能力不断提 高，优化方法在车辆调度领域的应用条件日臻完善。优化方法包含两种基本方 法：一种是数学规划方法，它是利用经证明的数学方法和模型来求解出最优的 可行解，具有求解效率高、结果可靠的特点，适合求解车辆调度中约束条件少、 小规模优化问题。另一种优化方法是启发式方法，它解决问题时强调“满意”， 而不去追求最优性和探求最优解，由于车辆调度问题规模较大，计算复杂，考虑到 实际需求和花费代价，现实生活中经常应用该类方法。 我们对后面各种方法所解决的问题说明如下：一批车辆，分别属于不同的车 场，用来完成给定的一组任务。每个任务都是将货物从一个节点运输到另一个节 点所有任务数量都超过车载量并受到起点，终点或道路时间窗的约束。并假设： ( 1 ) 所有任务事先给定，调度问题是静态的。这样，调度计划是在完全信息的条件 f 得到的。 ( 2 ) 所有任务都是满载的。即在任何时刻一辆车上至多只能有一项任务，该任务 从从一个发货节点直接运输到收货节点。 ( 3 ) 车辆类型单一，适宜执行所有任务。 ( 4 ) 车场是封闭的。即每个车场的车在执行任务完毕后必须再回到原来车场。 ( 5 ) 一辆车的行车线路的间不能超出某个规定的最大时限，这有利于车辆保养和 人员安全。 ( 6 ) 相关的时间窗应该被严格执行。 ( 7 ) 目标暂不确定，应用具体方法时再做规定。 一些公用表达式说明如下： i 表示非负整数： r 代表所有可行路线集合( 可行路线就是满足各种约束的路线) ： v 表示车场集合；w 。表示车场p 。的车辆数目，d 。，d 。分别表示车场v j 最多可以 发、收的车辆数：v 。表示车辆n 。所在的车场； 第2 章满载车辆调度问题概述及优化算法 q 表示任务集合；d 。表示完成任务q 。( 任务又称为重载点) 需用的重载车次数目； 正s ，表示任务吼的最早开始阼f f b q ；l f 瓦，表示任务q 的最晚结束时间： a 表示车辆集合：a ；表示第i 辆车； _ r k 。，q ，) 表示任务q ；的发货点到任务q ，的收货点所用的时i b q ； c l q 。，q ，) 表示任务q ，的发货点到任务q ，的收货点的空驶成本； l 表示执行一次任务q ，的时间，包括旅行时问，装车时间，卸车时间； m a x d u r a t i o n 表示一辆车允许行驶的最长时间； m a x l e n g t h 表示一辆车允许行驶的最大距离。 2 2 1 线形规划方法 假设目标是确定合适的路线使得完成既定任务的成本最小化。鉴于满载车 辆调度的特点，成本最小化与空驶成本最小化等价。 参数：x r 是决策变量，表示应用线路r 的车辆数目； c 表示该线路上的空驶成本； s 表示决策变量牟，韵可能取值集合； p 。表示线路r 上经过任务氆所在路段的车次数目。 y 。 0 ，1 ) ，当从车场v 。出发沿路线r 行驶时值为1 ，否则为0 。 相应的模型1 4 1 1 1 4 2 】【4 3 1 表示如下： i p ( s ) m i n i m i z e z = 罗c ，茗，： 怠 s u ”e c 。荟y v 峨。刨： 薹p ，一d n q t q ： x s ： x 一i ，r er 1 分支定界 应用分支定界方法【4 5 l 来求解该整数规划问题i p ( s ) ，将与之相应的线形规 划问题称为l p ( s ) 。 第2 章满载车辆调度问题概