（管理科学与工程专业论文）需求不确定条件下的车辆线路规划问题研究.pdf

p 一：，? 1 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究作出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名f 留红杪 日期：少细年5 月多汐曰 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版，有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆、院系资料室被查阅，有权将学位论文的内容编入 有关数据库进行检索，可以采用复印、缩印或其他方法保存学位论文。 保密论文保密期满后，适用本声明。 学位做作者签名馏书新躲席函葫 日期：归年j 月宇口日日期：州6 年多月罗日 需求不确定条件下的车辆线路规划问题研究 专业：管理科学与工程 硕士生：雷炜 指导教师：宋海清副教授 摘要 伴随着我国物流产业的快速发展，一大批的物流企业如雨后春笋般涌现，尤 其是国内众多的民营企业加入到物流行业中来，物流公司的迅猛发展促使了行业 内部竞争加剧，加之国际原油价格上涨，低碳生活的普及，物流企业的面临着成 本上涨的巨大压力。因此，如何能够存保证现有的服务水半基础上，降低成本成 为物流企业管理者和物流领域研究者们关注的重点。 构建合理的运输网络以及对现有运输线路进行优化能够有效地节约企业的 运输成本，车辆路线问题( v r p ) 的理论研究和现代通讯于段的发展极大的推动 了运输i 】c ) 9 络合理化构建的进程。但是，在车辆路线问题的理论研究中，人们通常 假设企业所面对的客户需求是确定的，这与客户需求经常变动的实际情形很1 、：相 符，从而极大地限制了研究在企业中的运用范围。 本文针对车辆路线问题中需求不确定的情况进行研究，分别建立了确定性需 求下和分布需求下的车辆路线规划模型，并进行求解。首先，依据运输企业的客 户历史半均需求和运营数据，计算固定出车成本和运营成本，建立在确定性需求 下的基于成本的目标函数及相应的约束条件：然后，根据所建立模型是线性规划 模型的特点，采用线性规划软件进行；在确定性需求模型的基础上，建立需求服 从概率分布的车辆线路规划模型，并用启发式算法对模型进行求解；最后通过算 例分析，对所建立的两个模型进行验证，并对分布需求下的模型进行一段时间的 模拟，检验模型的能否达到所要求的服务水- 甲。 关键词。需求升i 确定，车辆线路规划，两阶段启发式算法 r e s e a r c ho nt h ev e h i c l er o u tp l a n n i n gw i t hu n c e r t a i n d e m a n d m a j o r ：m a n a g e m e n ts c i e n c ea n de n g i n e e r i n g n a m e ：l e iw e i s u p e r v i s o r ：a s s o c i a t ep r o f e s s o rs o n gh a i q i n g a b s t r a c t f o rt h ep a s tf e wy e a r st h ec h i n e s el o g i s t i c si n d u s t r yh a sb e e nw e l c o m i n ga b o o m i n gd e v e l o p m e n ta n dab u l ko fl o g i s t i c sc o m p a n i e sw e r ee s t a b l i s h e d ，e s p e c i a l l y t h el a r g en u m b e ro fd o m e s t i cp r i v a t ee n t e r p r i s e se n t e rt h el o g i s t i c si n d u s t r y t h ef a s t g r o w i n go ft h el o g i s t i c si n d u s t r yh a sa l s op r o m o t e ds e v e r ec o m p e t i t i o n m e a n w h i l e t h ei n t e r n a t i o n a lc r u d eo i lp r i c e sr i s i n ga n dt h ep o p u l a r i t yo fl o w - c a r b o nl i f ei n c r e a s e t h ep r e s s u r ei nc o s tr i s i n go ft h el o g i s t i c se n t e r p r i s e s t h e r e f o r e ，h o wt or e d u c et h e c o s tb a s e do ne n s u r i n gt h ee x i s t i n gc u s t o m e rs e r v i c el e v e rh a sb e e nd r a w i n gm o r ea n d m o r ea t t e n t i o no f l o g i s t i c sc o m p a n i e sa n dl o g i s t i c sr e s e a r c h e r s i tc a ne f f e c t i v e l ys a v et h ec o s to ft r a n s p o r t a t i o nc o m p a n i e sb yc o n s t r u c t i n ga r e a s o n a b l et r a n s p o r tn e t w o r ka n do p t i m i z i n gv e h i c l e t h et h e o r e t i c a lr e s e a r c ho nt h e v e h i c l er o u t i n gp r o b l e m ( v l 冲) a n dt h ed e v e l o p m e n to fm o d e mc o m m u n i c a t i o n m e a n sg r e a t l yf a c i l i t a t e dt h ec o n s t r u c t i o np r o c e s so ft h er e a s o n a b l et r a n s p o r tn e t w o r k h o w e v e r , i nt h et h e o r yr e s e a r c ho nt h ev e h i c l er o u t i n gp r o b l e m ，p e o p l eo f t e na s s u m e t h a tc o m p a n i e sf a c et oi d e n t i 匆c u s t o m e rn e e d s t h i sa s s u m p t i o nd o e sn o tm a t c ht h e a c t u a ls i t u a t i o nt h a tc u s t o m e rd e m a n do f t e nc h a n g e s s ot h et h e o r yr e s e a r c h e su s i n g i nt h ee n t e r p r i s ew a sg r e a t l yl i m i t e d t h i sp a p e rc a r r i e so u tr e s e a r c ho nt h em o d e la n da l g o r i t h m st os o l v et h ev e h i c l e r o u t i n gp r o b l e mw i t hu n c e r t a i nd e m a n d f i r s t ，b a s e do nh i s t o r i c a lc u s t o m e r s a v e r a g e d e m a n da n do p e r a t i o n a ld a t a ，t h ef i x e dc o s t sa n do p e r a t i n gc o s t sa lee s t i m a t e da n da m a t h e m a t i c a lm o d e li se s t a b l i s h e db a s e do nt h ec o s t s t h eo b j e c t i v ei st om i n i m i z e l i t h et o t a lc o s t 晰t ht h ec o r r e s p o n d i n gc o n s t r a i n t s s e c o n d ，a c c o r d i n gt ot h ee s t a b l i s h e d m o d e li sal i n e a rp l a n n i n gm o d e l ，u s el i n e a rp r o g r a m m i n gs o f t w a r et os o l v et h em o d e l b a s e do nt h ed e t e r m i n i s t i cd e m a n dm o d e l ，e s t a b l i s ht h ev e h i c l er o u t ep l a n n i n gm o d e l w i t hd i s t r i b u t i o nd e m a n da n du s eh e u r i s t i ca l g o r i t h mt os o l v et h em o d e l f i n a l l y , u s ea n u m e r i c a le x a m p l et o t e s tv a l i d a t i o no ft h et w om o d e l sa n dd os i m u l a t i o no nt h e d i s t r i b u t i o nd e m a n dm o d e lt e s tw h e t h e rt h em o d e lc a na c h i e v et h er e q u i r e ds e r v i c e l e v e l k e yw o r d s ：d e m a n du n c e r t a i n t y , v r p t w o - p h a s eh e u r i s t i ca l g o r i t h m 目录 第1 章 绪论。1 1 1 研究背景1 1 2 问题的提出2 1 3 研究的目的及意义3 1 4 研究思路和论文结构安排4 第2 章文献综述5 2 1 车辆路线问题概述5 2 2 不确定性需求下的车辆路线规划问题综述9 2 3 车辆路线问题求解方法概述12 2 4 本章小结1 7 第3 章不同需求下的运输线路安排。1 9 3 1 问题的描述19 3 2 问题的假设2 0 3 3 确定性需求下的车辆线路规划模型2 1 3 4 需求不确定下的车辆线路规划模型2 3 3 4 相关数据的说明及计算2 7 3 5 本章小结2 8 第4 章 算例分析。3 0 4 1 确定性需求模型算例分析3 0 4 2 不确定需求模型算例分析3 2 4 3 模拟实验3 9 4 4 本章小结4 2 第5 章总结与展望4 4 5 1 本研究的主要工作总结。4 4 5 2 需要进一步研究的i 口j 题4 5 参考文献4 6 l r 付j 5 乏5 0 附录1 ：求解4 个嘲点配送计划的u n 程序代码5 0 附录2 ：节约算法求解2 0 个网点配送计划的j , v a 程序5 3 附录3 ：最近插入法计算2 0 个网点路线规划的渊蛆程序5 8 j 舌记6 ：! i 、， 1 1 研究背景 第1 章绪论 在物流研究领域内，物流配送中车辆路线问题一直是物流理论研究和实践工 作中关注的焦点，这是因为运输成本在整个物流成本中占有较高的比例，优化后 的车辆路线安排不但能带来巨大的成本节约，还能提高顾客的服务水甲。正如国 务院发布的物流业调整和振兴规划指出的那样：“物流业是融合运输业、仓 储业、货代业和信息业等的复合型服务产业，是国民经济的重要组成部分，涉及 领域广、吸纳就业人数多，促进生产、拉动消费作用大，在促进产业结构调整， 转变经济发展方式和增强国民经济竞争力等方面发挥着重要作用 ( 国务院办公 厅，2 0 0 9 ) 。正因为物流业在国民经济发展中的特殊地位，国家不断加大对物流 行业发展的支持力度，2 0 0 9 年国家更是把物流业纳入十大振兴产业之一，力争 改善物流企业经营困难的状况，并通过加大对物流企业兼并重组的政策支持力 度，到2 0 1 1 年培育一批具有国际竞争力的大型综合物流企业集团。 改革开放2 0 年来我国物流业发展在国民经济高速增长的同时也得到了快速 发展，我国的物流业总产值一直呈上升趋势，2 0 0 8 年全国社会物流总额达8 9 9 万亿元，比2 0 0 0 年增长4 2 倍，年均增长率为2 3 ( 国务院办公厅，2 0 0 9 ) 。但 是，相比其他发达国家，我国物流业的差距还相当明显，中国物流与采购联合会 常务副会长丁俊发表示，从中国物流业的总体来衡量，落后先进国家二十至三十 年。我国大部分物流企业仍是传统的运输企业，停留在粗放经营的层面，经营质 量和效益小理想，这就导致我国的物流成本远高于国际水平，我国全社会物流成 本占g d p 的比重连续7 年在2 1 3 上下徘徊，而国外物流发达国家的水甲是在1 0 左右。全国政协外事委员会副主任周可仁在湖南的一次研讨会上，披露了中国仓 储协会相关调查数据：据4 完全统计，目前中国生产企业原材料物流5 0 靠供货 方提供，另有3 0 靠自己，第三方物流仅占1 9 ，而在社会化配送发展最好的u 本，第三方物流业占整个物流市场比例高达8 0 0 5 。成品销售方面，在中国2 7 的 执行主体是生产者，5 5 0 5 是部分自理和简单外包相结合，仅有1 8 0 5 来自第三方物 流，而这一领域美国有5 7 0 5 的物流量是通过第三方物流完成。可见，我国的物流 水平还有很大的提升和改进空间。而在物流费用中，运输费用通常占到物流总费 用的一半以上。来自中国物流信息中心的统计数据显示：2 0 0 8 年我国社会物流 总费用为5 4 5 4 2 亿元，同比增长1 6 2 ，运输费用为2 8 6 6 9 亿元，同比增长1 3 2 ， 运输费用占整个社会物流总费用的5 2 5 6 ，货运总量为2 4 5 亿吨，其中公路货 运总量为1 8 2 亿吨，占总货运量的7 4 2 8 ( 中国物流信息中心，2 0 1 0 9 ) 。从以上 数据可以看出要提升我国的物流服务水半，运输是关键，而在几种运输方式中， 公路运输又是目前我国货运主要方式，因此提高公路的运输效率，节约公路运输 成本是我们提高我国物流水甲的一个主要方向。 众所周知，车辆利用率的高低于运输效率和运输成本有很大的关系，而车辆 利用率高低，又随着车辆行驶路线的小同而4 同。因此，在满足配送任务要求的 前提下，选择经济效益好的行驶路线，是物流配送中一项十分重要的工作。本文 针对车辆路线规划问题进行研究，提出网点需求不确定的路线规划，以帮助配送 企业在一段时期内维持路线规划的稳定性，在满足客户服务的同时，保持较低的 管理成本。 1 - 2 问题的提出 根据国家统计局统计2 0 0 7 年我国社会消费品零售总额为8 9 2 1 0 亿元，其中 批发和零售业为7 5 0 4 0 3 亿元，占整个社会消费品零售总额的8 4 1 1 ( 中国国家 统计局，2 0 0 8 ) 物流运输是整个批发和零售业的支撑，也是售批发零行业成本的 一个重要来源。另据艾瑞咨询 2 0 0 9 年上半年中国网络购物市场发展报告数 据显示，2 0 0 9 年上半年中国网络购物市场规模突破千亿元，达到1 0 3 4 6 亿，同 比2 0 0 8 上半年高速增长9 4 8 ，相比传统的买卖交易，网络购物市场对物流运 输的依靠程度更大。因此，切实提高物流运输企业或部门的运输效率对于我国经 济发展意义重大。 2 一般的生活消费品向批发商或零售商运输，常常以很小的订单批量( 一些行 业平均每单低于l o o k g ) ，配送中心将多个客户的订单进行整合后由同一辆车来 进行配送，这样可以极大地提高车辆的利用率，同时也节省了配送时间。配送中 心在整合客户订单时，必须提前知道客户的位置以及需求的数量。全球定位系统 ( g p s ) 、地理信息系统( g i s ) 等先进技术配送中心可以准确得到客户的位置及 最短的行车路线。客户的具体位置短期内是不会发生变化的，但是客户的需求却 不是，季节、突发事件等都会影响到客户的需求。这也导致路线规划不是一项确 定的工作，一旦制定出来就可以永远4 i 变。 本文就针对配送线路规划中客户需求，分两个部分进行分析，第一部分是研 究一段时间内需求确定情况下的路线规划。以总运营费用最小化为目标，以车辆 载重，网点需求等为约束条件建立模型，求解模型可以得出确定需求下的路线规 划。第二部分是研究一段时间内客户需求服从正态分布时的路线规划，得到的路 线规划具有一定的灵活性，只要客户的需求服从之前假设的分布，就可以按照规 划的路线进行配送。在建立模型的基础上，通过算例的计算分析，可以得到具体 的线路规划，最后通过模拟一段时间内客户的需求，验证规划的线路能甭保证应 有的客户服务水平。 1 3 研究的目的及意义 随着人们生活水平的提高，顾客对物流配送服务水平的要求也越来越高，研 究能够满足客户需求4 i 断变化的配送网络规划，有助于提高物流配送企业的服务 水_ 甲，增强企业的竞争力。另外，配送企业也期望公司做出的路线规划能够具有 一定的持续性，而不是当顾客的需求发生变化时，公司就必须改变现有的规划。 本文主要是针对那些需求在一段时间内相对稳定，也就是一段时间内需求服 从同一分布的一般消费品配送网络进行规划。一旦规划做出之后，只要客户的需 求服从假设的分布，就可以遵照这个规划进行配送。相比通过假设客户需求是确 定的，做出的路线规划，这种规划具有弹性，允许客户需求一定范围的波动。本 研究的意义在于放宽了客户需求确定性的限制条件，增加了路线规划的可适用 3 性，既保持了目前配送网络相对固定的好处，又增加了配送系统的灵活性；通过 算例分析和一段时间的模拟，对模型进行检验；本研究方法可以推广到需求服从 其它分布的应用中，对物流企业改善现有运输网络和降低运营成本都有可借鉴的 价值。 1 4 研究思路和论文结构安排 越来越多的v r p 研究者注重研究理论与企业实际相结合，研究中加入客户需 求的不确定性，车辆运行时间的彳、= 确定性等复杂因素，但是这吏切合企业的实际。 因为随着时间的推移，各种信息在不断更新，影响已有的线路规划。相比以前的 经典v r p 问题，它们更符合现实生活中实际情形，对物流企业的车辆路线安排有 更大的指导作用。 本文在借鉴前人研究的基础上，首先引入简单的线路规划，假定客户的需求 是确定的，建立运营费用最小化模型。在确定性需求模型的基础上，放松确定性 需求的限制，建立模型，利用启发式方法对模型进行求解，得出需求服从正态分 布的车辆路线规划。 论文的内容安排如下： 第1 章为绪论，介绍研究背景、研究内容、研究意义以及整个研究思路与内 容安排。 第2 章是文献综述，先对相关的概念进行简单介绍，然后是综述国内外学者 对车辆路线问题的研究，包括研究的切入点，所采用的方法，得出的结论等。 第3 章提出假设，分别构造确定性需求和服从分布需求的费用最小化模型， 提出求解的方法。 第4 章构造算例，对上一章提出的模型进行检验，并通过一段时间的模拟检 验服从分布需求的模型的表现。 第5 章为研究结论和展望，对本文的结论进行了阐述，总结了本文的不足并 对本文的后续研究进行了展望。 4 第2 章文献综述 2 1 车辆路线问题概述 2 1 1 基本的车辆路线问题 车辆路线问题( v e h i d er ) u t i n gp r o b l e m ，v f 码通常定义为：对一系列给定的 分散嘲点，确定适当的配送车辆行驶路线，使其从配送中心出发有序地通过网点 最后返回配送中心，并在满足一定约束条件下( 如车辆载重量限制、网点需求得 到满足、取送货时间要求、每辆车任务量均衡等) ，达到一定的目标( 如总行程 最短、费用最少、车辆利用率最高、服务满意度最高等) ( 李军，2 0 0 0 ) 。该问题 于1 9 5 9 年由d a n t z i g 和p e m s e r l a l ( 1 9 5 4 ) 率先提出，很快便引起了运筹学、应 用数学、图论与网络分析、物流科学、计算机应用等学科专家以及运输计划制定 者的极大重视，成为运筹学与组合优化领域的前沿与热点问题。在众多学科专家 对该问题进行理论研究和实验分析下，车辆路线问题的应用也有了极大地发展， 它已1 仅限于汽车运输领域，在水运、航空、工业管理等领域都有广泛地应用， 车辆路线问题已经成为运输配送中的核心问题。 可以通过一个简单的例子对车辆路线问题加以说明，工厂将生产好的产成品 送到配送中心，配送中心根据客户的订单需求，将相应种类和数量的产品通过车 辆存客户指定的时间内运送到客户手中。一些客户需要配送的货物量往往小于运 输车辆的容量，通常几个相近客户的货物就可以集中起来，由一辆车来进行配送。 类似的问题都可以归结为v f p 问题，如图2 - 1 所示。 5 曰 图2 - 1 基本车辆路线示意图 2 1 2 拓展的车辆路线问题 根据具体情况，基本的车辆路线问题在学术研究和实际应用中有4 同的变 形。在上述问题中，茗运输使用的车辆有多种车型可供选择则成为多车种车辆路 线问题( r e e t9 z e a n dm i x v e h i d ep o u t i n gp r o b l e m 。f z 3 a ：p ) = 如果加入客户被访问 的时间窗约束就称为带时间窗的车辆路线问题( v e h i d ep o u t i n gp r o b l e mw i t h 1 1 m ew i n d o w s , v f p t w ) = 如果允许车辆一天之内完成多个行程则成为车辆多次 使用的车辆路线问题( v e h i d ep o u t i n gp r o b l e mw i t hm u l t i p l eu s e ro fv e h i d e ， 例) 。此外，按物流中心或车场的数目分，有单车场车辆路线问题( v e h i d e p o u t i n gp r o b l e mw i t hs n g l ed e p o t ) 和多车场车辆路线问题( v e h i d ep o u t i n g p r o b l e m w i t hm u l t i p l ed e p o t s ) = 根据车辆在网点完成装卸任务情况可以将v f p 问 题分为纯装或纯卸车辆路线问题( p u r er c k u po rp u r ed e l i v e r yv m 和集送货一体 化的车辆路线问题( v e h i d ep o u t i n gp r o b l e mw i t hr c k u pa n dd e l i v e r y , v f f f e ) ) = 根 据所配送客户的需求在制定路线计划时是否确定可分为确定性需求的车辆路线 问题和非确定性车辆路线问题；根据配送货量与车辆容量的关系可以将v f p 问 题分为满载问题( b a l i 等，1 9 8 3 ) ( 大型企业中转枢纽及配送中心之间往往存在大 宗货物的运输，需要车辆多车次满载执行，从而产生了满载车辆调度问题) 和非 满载问题( 货量小于车辆容量，一辆车一次行程可以完成多个网点的配送) ：根 据车辆发送和返回地是否相同可以将v f p 分为封闭的v r p ( 车辆完成配送任务后 6 必须返回其发出车场) 和开放的v f p ( 即车辆完成配送任务后口j 以不返回其发出 车场) 。表2 - 1 列出了基本车辆路线问题变形的方向。 表2 - 1 车辆路线问题变形因素 车辆路线问题 客户车辆成木货物信息车场 ， 需时订优型数最司还 加 兼保数是 求问 单 先号量大机输班容鲜量否 种窗分级里休成成性性返 类 拆程 息 本本回 时 间 目前，车辆路线问题主要是从客户、车辆、成本、货物信息、车场信息五个 方向出发，进行各种变形。图2 - 2 显示了主要几种变形的车辆路线问题之间的关 系。 图2 - 3 各种变形的车辆路线问题之间的关系 动态车辆路线问题就是车辆路线问题的一个重要扩展。早期的车辆路线问题 7 基本是静态的，人们一般在进行车辆路线规划之前假定所有的信息( 包括顾客需 求信息、车辆信息、路况信息等) 都是确定的，路线规划员获知了所有的信息， 并且这些信息不会随时间而改变。在这样的假设下做出的路线规划也是相对固定 的，但是现实生活中存在大量的不确定性。反映到v p p 问题中，可能会出现不确 定的客户需求，交通拥挤，车辆故障等情况，这些一 确定信息随时间的推移而出 现，为了更好地满足客户的需求，需要不断地调整车辆运行路线来应对这些不断 出现的不确定性情况。 1 9 8 6 年，f b w e l l ( 1 9 8 6 ) 在他的一个动态车辆调配问题的随机模型最早 提到了“动态车辆”，但当时他并没有给出动态车辆路线问题定义。到1 9 8 8 年， p s a r a f t i s ( 1 9 8 8 ) 通过对比静态车辆路线i 、口j 题和动态车辆路线问题，得到了动态 车辆路线问题比较准确的定义，并归纳了动态车辆路线问题的基本特征。他给出 的动态车辆路线问题的定义：如果车辆路线问题输出的是一条预先规划好的线 路，这条线路是根据事先知道的信息进行优化后计算得出来的，并i f l 它4 、= 会被重 新优化，那么这个问题就是静态的车辆路线问题。反之，如果车辆路线问题输出 的不是一条预先规划好的线路，而是一条根据时间推移，输入相应的信息作出调 整的线路，这种车辆路线问题就是动态的。可见，在他的定义中，时间因素对问 题分类起关键性的作用，根据路线规划员在做规划之前是否已知相关信息来区分 动态和静态车辆路线问题。 根据动态车辆路线规划问题中出现的不确定性信息可将该问题分为以下三 类( 郭凤鸣，2 。1 0 6 ) ： 1 、对需求预测4 、= 确定性引起的问题( 如需求数量、需求时间的f i 确定) 往往 导致不确定需求的动态车辆路线规划问题，目前动态车辆路线研究就主要集中在 对该类问题的研究中。 2 、由对提供服务的车辆、司机的4 、= 确定性引起的问题。在安排车辆路线的 过程中，除了要考虑顾客需求外，服务资源和服务设施的1 确定性也构成了一类 重要的动态车辆路线规划问题。 3 、由路线网络性能不确定性引起的问题。路线网络性能的不确定性可能涉 及旅行时间( 因天气变化或交通堵塞) 或路线网络容量的4 确定性。 8 目前研究最多的是第一种，即需求一 确定下的动态车辆路线问题。经典的车 辆路线问题研究假设的前提条件是客户的需求和其它的限制条件是不会随时间 而改变，而需求不确定的动态车辆路线l 口j 题研究的是客户的需求是随时间的推移 而不断发生改变的，这种在现实生活中很普遍的情形，但是在理论研究中要想完 全考虑这种情况却非常困难，研究者通常是通过假设客户的需求是服从某一已知 分布的，来近似模拟现实生活中的情形。 2 - 2 不确定性需求下的车辆路线规划问题综述 2 3 1 国外相关研究 t i ll m a n ( 1 9 6 9 ) 是第一个提出求解随机性需求车辆路径问题算法的人。在他 所研究的案例中，有几个车场，同时一旦车辆超出载重或装载量过低的时候，就 给一个惩罚。1 9 9 5 年p s a r a f t i s ( 1 9 9 5 ) 发表了一篇综述，对动态v r p 作了一个 全面的回顾。p o w e l l ( 1 9 9 5 ) 等人集中研究了基于4 确定性的规划模型。g e n d r e a u 和p o t v i n ( 1 9 9 8 ) 着重研究车辆路线规划前的需求预测，另外他们指出不应该把 研究的焦点只集中到服务请求在一定的时空范围内出现的不确定性上，而应该考 虑多种小确定性，如客户需求的取消或服务的延迟。b e r t s i m a s ( 1 9 9 3 ) 提出了 应用于解决有容量约束的4 、= 确定动态调度问题的简单策略。s w i h a r t ( 1 9 9 9 ) 等 人分析了用于集送货的实时单车辆路线问题的策略。这些策略归纳起来有这样几 种：先来先服务( 路线规划员根据需求到达的顺序安排车辆) ；最近服务原则( 车 辆优先对最近的未完成服务的客户进行服务) ：旅行商问题策略( 将客户分成几 个组，确定了一个组之后就可以转化成一个旅行商问题，在一个小组内部找出最 优线路) 。随着研究的深入，当考虑的客户和车辆数目增多的时候，上述几种简 单的策略已经无法完成复杂的线路网路的规划，人们更偏向于采用启发式算法来 求解。r o y ( 1 9 8 4 ) 等人提出了一种插入算法，先对当前已知需求的客户进行线 路规划，将之后明确需求的客户插入到当前路线中的最合适位置。为了更快地得 到较好的结果，人们又转向使用一些改进的启发式算法，如遗传算法，模拟退火 9 算法等。采用这些启发式算法可以采用并行实现的策略，通过并行计算可以大大 缩减计算时间。l e o n o r ab i a n c h i ( 2 0 0 5 ) 等人研究了带有概率需求的旅行商问题， 并运用改进的2 - o p t 和卜1 交换法进行求解。表2 2 列出来早期对不确定性需求 的车辆路线问题有重要贡献的文献。 表2 - 21 9 7 8 - 1 9 9 5 年不确定性需求v r p 问题研究重要文献回顾( m i c h e l 等，1 9 9 6 ) d e m a n d a u t h o r sy e a r m o d e lc h a r a c t e r i s t i c sa n dc o n t r i b u t i o n s d i s t r i b u t i o n s a v i n gh e u r i s t i c ( p e n a l t ye q u a lt o g o l d e n ，s t e w a r t 1 9 7 8 泊松分相 c c p s u mo fr e t u r nt r i p s ) s t e w a r t ，g o l d e n 1 9 8 0c c pe x t e n s i o no fg o l d e na n ds t e w a r t s t e w a r t1 9 8 1 s p r h e u r is ti c sa n dl a g r a n g e a nm e t h o d b o d i n ，g o l d e n ， 1 9 8 3 正态分布、二项分t r a n s f o r m a t i o no fs v r pi n t o a s s a d ，b a l l布、泊松分布 c c p d e t e r m i n is t i cv r p d r o r ，t r u d e a u 1 9 8 6 仃何分布c c p ，s p rp r o p e r t i e s ，s a v i n g sh e u r i s t i c j a i l l e t 1 9 8 7f 自努利分布o n ev e h i c l e ，o 一1 d e m a n d s ，p r o p e r t i e s o n ev e h i c l e 。0 一l d e m a n d s 。p r o p e r t i e s ， b e r t s i m a s1 9 8 8伯努利分布 h e u r i s t i c sw i t hw o r s t c a s e p e r f o r m a n c e l a p o r t e ， 正态分布、二项分c c p 。 v a r i a b l ed e p o tl o c a t i o n ，e x a c t l o u v e a u x ， 1 9 8 9 布、泊松分布 b p m c o n s t r a i n tr e l a x a t i o na l g o r i t h m s ， m e r c u r e n 3 0 ，b o u n d e dp e n a lt ym o d e l l a p o r t e ， 1 9 9 0任何分布s p r m o d e l ，b o u n d s ，p r e v e n t i v er e t u r nt r i p s l o u v e a u x b o u z d i e n e - a y a r i ， 1 9 9 3 任何分布s a v i n g sh e u r i s t i c ，s p l i td e l i v e r i e s d r o r ，l a p o r t e b a s t i a n ， 1 9 9 2任何分布 c c p ，s p r m o d e l ：t i m e d e p e n d e n tt r a v e li n g r i n n o o yk a n s a l e s m a np r o b l e m d r o r 。l a p o r t e 。 1 9 9 3 任何分布c c p ，s p r r e s t r i c t e df a i l u r e s m o d e l s ，h e u r i s t i c l o u v e a u xa n de x a c ta l g o r it h m s e x a c ti n t e g e rl 。s h a p e da l g o r it h m s g u i n 1 9 9 4 离散、连续分布 s p r f o rd i s c r e t ec a s e 。n 7 0 c c p ：机会约束规划( c h a n c ec o n s t r a i n e dp r o g r a m m i n g ) ：s p r ：带资源限制的随机规划 ( s t o c h a s t i cp r o g r a m m i n gw i t hr e c o u r s e ) ：b p m ：有界的惩罚模型( b o u n d e dp e n a l t y m o d e l ) 近来的许多文献都是关于车辆路线理论在实际生活中运用，研究者通过对现 有算法的改进帮助企业或政府部门改善他们的运输网络，取得了一些较好的结 果。f a b i e n ( 2 0 0 9 ) 等人考虑加拿大魁北克地区的一个运输公司，该公司主要是 1 0 接受来自某石油公司的外包运输任务，负责给该石油公司旗下的部分加油站配送 各种汽油。每个加油站有一个最大和最小需求，但是作者只考虑了一天的路线安 排，这一规定大大简化了问题的难度，也把原本是随机的路线规划问题转化成了 静态的车辆路线规划，本文最重要的一点是考虑了每个加油站有配送时间窗要 求。最后作者采用了两阶段的启发式算法，先考虑顾客的时间窗要求产生一些可 行路线，再根据客户的需求量和其他要求对车辆路线进行优化。d r i k ( 1 9 9 5 ) 等 人就研究了在b a n g k o k 的城市公交系统，这个城市的公交系统是由b m t a 公司负 责，该公司拥有1 6 5 条线路，5 0 0 0 多辆公交车。每天的交通状况都4 同而日经 常发生变化，由于每天的交通状况都4 同而日经常发生变化，为了应对这种情况， 公司管理当局就决定每天把车辆和售票员排队，临时分配路线。这种方式显然很 不科学，出现的问题的确也很多。很多线路公交车安排过于精密，即使是非高峰 时期，也可能是几分钟一辆，而相反有的线路车辆严重4 、= 足，导致公众意见很大。 往往是局部效果有些改善，但是整体服务能力却1 强，从而影响公司的服务水半。 针对这种情况，作者提出分两步来安排。首先在不考虑实际中客车载客容量限制 的条件下，根据顾客需求计算出需要的路线。第二步，考虑车辆数目限定的条件 下，检查、修改第一步中的路线，用一个非线性整数规划模型来构造这个问题， 目标是在客车容量限制的条件下，尽量减少实际线路安排与需求之间的差距。这 是个典型的动态随机规划在现实生活中应用的例子。j i n g q u a n1 i ( 2 0 0 8 ) 等人 研究了巴西南部最大的城市阿雷格里港的固体垃圾回收车辆路线安排问题。在考 虑车辆路线安排的时候4 仅考虑了满足需求和成本最小同时也考虑了各个垃圾 回收中心的垃圾接受量的平衡。构造模型时，先小考虑回收中心处理垃圾量半衡 的问题，将问题构造成一个最小费用网络流问题，先求解。最后在目标函数中加 入惩罚项，当某回收中心接受的垃圾超出该中心的处理能力时就给一个很大的惩 罚。还有一些研究者把车辆路线问题扩展到其他领域，比如h u e y - k u oc h e n ( 2 0 0 9 ) 等人就把研究某易腐食品生产企业产品生产和产品的配送过程，将两者结合在一 起综合考虑，最后建立了一个p s - v r p t w - p 模型，为企业的生产和运输提供决策 参考。 2 3 2 国内相关研究 国内对于动态车辆路线规划研究起步比较晚，大多是对求解方法的改进或应 用类，理论研究方面的文献比较少。其中谢秉磊( 2 0 0 2 ) 等人回顾了国外相关学 者的文献后，根据动态车辆路线问题中不确定性信息类型和求解的模型对动态车 辆路线问题进行分类，指出了未来研究动态车辆路线问题的几个方向。郭耀煌 ( 2 0 1 0 4 ) 等针对需求不确定的v f r 研究了顾客需求量4 、= 可分割情况下的、f 砌 的两个预优化策略( 单回路策略和多回路策略) ，分析了预优化策略与重优化策 略的渐近性能，并将遗传算法和模拟退火算法进行修正用于求解该问题，得到了 比较不错的结果。张建勇( 2 0 0 4 ) 等人则将决策者主观偏好的概念引入到单车场 单车辆实时动态模糊车辆调度问题，利用一种基于模糊可能性的动态启发式算法 求解了在决策者主观偏好值给定情况下，具有不确定需求的单车场单车辆实时模 糊车辆调度问题。郭耀煌和钟小鹏( 2 0 0 6 ) 分析了顾客需求以泊松流形式出现， 现场服务时间服从一般分布的动态车辆路线问题，并提出了两种服务策略，顺序 服务策略和中点改进策略，利用排队论、几何概率论等领域的知识分别求出了这 两种策略的系统时间，最后通过仿真数据试验验证了这两种策略的有效性。刘士 新( 2 0 0 8 ) 等设计了在动态环境下进行车辆路线优化的导向局域搜索算法。在产 生初始解以后的动态求解过程中，4 再对车辆之间的顾客进行调整，而是应用 2 一o p t 局域搜索算子更新车辆服务顾客的顺序，也就是针对每辆车的形势线路 求解一个旅行商问题，建立了在动态环境下车辆执行运输任务过程的仿真模型， 应用算法根据交通路网的实际情况实时优化车辆路线。 2 3 车辆路线问题求解方法概述 车辆路线问题的求解算法大体上可以分为两类：一类是精确性算法，一类是 启发式算法。 1 2 这是运用图论的方法，把从配送中心向所有客户配送的路线集合当作一个运 输网络，每条线路对应为一条弧，车辆的载重限制就是该条弧的最大流