（交通运输规划与管理专业论文）配送中随机型车辆路线优化研究.pdf

论文独创性声明 本论文是我个 在导师指导下进行的研究工作及取得的研究成果论文 中除了制加以标注和致谢的姐坊外r 不包含其他人或其他机构已经发表或 撰写过的研究威果其他同志对本研究的启发和所做的贡献均已在论文中作 了明确的声明并表示了诲臆 竹卑獬：边盗拯日期：2 翌生：! ：! 本刖同意t 海海运学院菊r 关保留、使用学位论文的规定，即：学校有权 保留送交激印件，允许沦史被查阅和借阅：学校可以上网公布论文的全 部或都分内容，可以采用影印、缩印或者其它复翻手段保存论文保密的沦 摘要 发达国家从上世纪八十年代就对随机型的车辆路线问题进行了研究，已有许多关 于随机型车辆路线问题的文献，但是在随机型车辆路线问题的研究上还存在许多不足 的地方，决大多数研究是有关单个随机因素的车辆路线问题，而对需求和时间都随机 的车辆路线问题的研究很少。 国内，由于物流业发展较晚，对车辆路线问题的研究也比较晚。目前对车辆路线 问题的研究很多，但基本上都集中于确定型的车辆路线问题的研究，而对随机型车辆 路线问题的研究还很少，随着我国物流业的发展，随机型车辆路线问题的研究将有着 巨大的实际价值。 本文首先对配送中车辆路线问题的任务、重要性进行了说明。由配送中随机因素 的普遍性引出了研究随机型车辆路线的必要性，并根据随机因素的类别，对随机型车 辆路线进行了分类。然后对各类型随机型车辆路线的研究现状进行了系统综述，并指 出了目前研究中存在的不足，最后指明了本文研究的内容和方向。 第二章中第一节对车辆路线的基本问题和确定型车辆路线问题的基本解法进行 了阐述。第二节说明了随机型车辆路线中预先设定车辆路线的目标、在随机型的配送 中的服务策略以及服务策略对车辆路线的影响，和随机因素变为确定的时间( 信息) 对车辆路线的影响等问题。 第三章分析和研究客户随机的旅行商路线、客户随机的车辆路线、需求随机的车 辆路线，在前人研究的基础上，本文提供了比较完善的计算路程期望的公式。根据确 定型车辆路线的节约算法，本章提出了随机型车辆路线的节约算法。本章中还对以上 两种节约算法的不同点进行了研究。 第四章，本章先对时间随机的旅行商车辆路线问题和时间随机的车辆路线问题进 行了研究，着重研究了时间服从连续分布的随机型车辆路线问题，并构建了优化车辆 路线的数学模型。本章还给出了模型的解法。最后，对需求和时间都随机的车辆路线 问题进行了研究，给出一个比较完善的求车辆路线期望总费用公式。 最后本文的研究进行了总结，并指明了进一研究的方向。 关键字：配送，车辆路线，随机，节约算法 a b s t r a c t d e v e l o p e dc o u n t r i e sb e g a nt or e s e a r c hs t o c h a s t i cv e h i c l er o u t i n gp r o b l e m ( s v r p ) i n 19 8 0 s a n dt h e r eh a v eb e e ns o m ec o n c e r n e da r t i c l e s s o m ea r t i c l e sa l r e a d yh a v ew e l i i i l u s t m t e ds o m ec h a r a c t e r ea n dp r e p e r t i e so fs v r p b u tt h e r ea r es h o r t a g e st os t u d yo ns v r p e s p e c i a l l ys t u d yo fs v r pi sa l m o s tc o n c e n t r a t e do ns v r pw i t ho n l yo n es t o c h a s t i cf a c t o r s u c h a sv r pw i t hs t o c h a s t i ct r a v e i - r i m e s ，v r pw i t hs t o c h a s t i cd e m a n d sa n dv r pw i t hs t o c h a s f i c c u s t o m e r s 1 1 1 eg o a lo ft h i sd i s s e r t a t i o ni st op e r f e c ts t u d yo fs v r p a n ds t u d yv r pw i t h s t o c h a s t i ct r a v e it i m e sa n dd e m a n d s t h e r ea r es o m er e s e a r c h e so rv r pi no u rc o u n t r y b u tm o s to fw o r k sa r ef o c u s e do nt h e d e t e r m i n i s t i cv 隅i nw h i c ht h e r ei sn ou n c e r t a i n t yf a c t o r s o i i t e r a t u r eo fs v r pi sl a c k i n gi n o u rc o u n t r y w n ht h ed e v e l o p m e n to fl o g i s t i c si no u rc o u n t r y t h er e s e a r c ho ns v r pi sr e a l l ya m a t t e ro fg r e a ts i g n i f i c a n c e c h a p t e ro n eo f t h ed i s s e r t a t i o ni n t r o d u c e st h ec o n c e p t so fd i s t r i b u t i o na n d v e h i d er e u t i n g p r o b l e m t h ei m p o r t a n c eo fv f i p b e c a g s ev e h i c l e sm e e ti o t so fs t o c h a s t i cf a c t o r sd u d n g d i s t r i b u t i o n s t u d yo fs v r pi sv e r yi m p o r t a n ta n ds i g n i f i c a n t a c c o r d i n gt os t o c h a s t i cf a c t o r s ，t h e s e c o n ds e c t i o nc l a s s i f i e st h es v r pa ss i xk i n d s t h et h i r ds e c t i o no fc h a p t e ro n eg e n e r a l i z e s t h es t u d i e so fs v r pa n ds h o r t c o m i n go fs t u d i e so fs v r p ，d e m o n s t r a t e st h es t u d y i n gd i r e c t i o n a n dc o n t e n t so ft h i sd i s s e r t a t i o n t h ef i r s ts e c t i o no fc h a p t e rt w og e n e r a l 泣o dt h es h o r t e s tr o u t i n gp r o b l e m v e h i c l er o u t i n g p r o b l e ma n db a s i ca l g o r i t h m - s a v i n g sa l g o d t h mo fv r p t h es e c o n ds e c t i o ni n t r o d u c e st h e o b i e c t i v e so fs v r p 。s e r v i c es t r a t e q i e so fd i s t r i b u t i o n ，t h ee f f e c tt h a ts e r v i c es t r a t e g i e sh a v eo n s t o c h a s t i cv e h i c l er o u t i n g 。a n dt h ei n f l u e n c eo ft h et i m eo fs t o c h a l s t i cf a c t o rm a k i n gc e r t a i n c h a p t e rt h r e e r e s e a r c h e s t r a v e l i n g s a l e s m a nr o u t i n gp r o b l e mw i t hs t o c h a s t i c c u s t o m e r s v e h i d er o u t i n gp r o b l e mw i t hs t o c h a s t i cc u s t o m e r sa n dv e h i c l er o u t i n gp r o b l e m w i t hs t o c h a s t i cd e m a n d s t h e s er e s e a r c h e sp e r f e c tt h es t u d i e so fs v r p t h ec h a p t e rp r o v i d e s ag o o df o r m u l ao fc a l c u l a t i n ge x p e c t e dd i s t a n c eo fs t o c h a s t i cv e h i c l er o u t i n gb a s e do nf 1 u i t so f f o r m e rr e s e a r c h e s t h ec h a p t e ra l s op r o v i d e sas a v i n g sa l g o r i t h mo fs v r pi na c c o r d i n gw i t h t h es a v i n g sa l g o r i t h mo fd e t e r m i n i s t i cv e h i c l er o u t i n gp r o b l e m s 。a n dm a k e so u tt h ed i f f e r e n c e s b e t w e e nt h es a v i n g sa l g o r i t h mo fs v r pa n dt h es a v i n g sa l g o r i t h mo fc e r t a i nv e h i c l er o u t i n g p r o b l e m s c h a 【p t e rf o u rr e s e a r c h e st r a v e l i n gs a l e s m a nr o u t i n gp r o b i e mw i t hs t o c h a s t i ct r a v e i t i m e s ，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 ct r e v e it i m e sa n dv e h i c l er o u t i n gp r o b l e m w i t hs t o c h a s t i ct r a v e it i m e sa n ds t o c h a s t i cd e m a n d s t h ec h a p t e rc o m p l e t e st h es t u d i e so f t h ef i r s tt w op r o b l e m s t h ec h a p t e rp r o v i d e sam o d e lo fe v e r yp r o b l e mt h a ti su s e dt oo p t i m i z e v e h i c l er o u t i n g ，a n do p t i m i z i n ga r i t h m e t i c t h et h i r ds e c t i o nd e v e l o p saf o r m u l ao fc o m p u t i n g t h ee x p e c t e dd i s t a n c e so fv e h i c l er o u t i n gw i t hs t o c h a s t i ct r a v e lt i m e sa n ds t o c h a s t i c d e m a n d s i nt h ee n d ，d i s s e r t a t i o ns u m su pt h es t u d i e s ，a n dm a k eo u tt h ed i r e c t i o no fn e x tr e s e a r c h 2 a i j i a ow a n g ( t r a n s p o r tp l a n n i n ga n dm a n a g e m e n t ) d i r e c t e db yx u c f c n gw a n gp r o f e s s o ra n dg a n gz h a op r o f e s s o r k e y w o r d s ：d i s t r i b u t i o n ，v e h i c l em u t i n g ，s t o c h a s t i c ，s a v i n ga l g o r i t h m 引言 进入二十一世纪，随着科学技术的进步和生产力的发展，顾客消费水平的不断提 高，企业之问的竞争日益加剧，加上政治、经济、社会环境的巨大变化，使得接个市 场需求的不确定性增加。企业面对着变化快速且无法预测的市场经济，为了提高竞争 力，所有企业都在不断探索降低费用、提高利润的途径。由于从生产过程中减少费用 已非常困难，人们开始将目光投向流通领域。流通领域在经济发达国家被视为继原材 料、劳动力以外的“第三利润源泉”，是“降低成本的最后处女地”。 在经济全球化和信息化的推动下，现代物流业已从为社会提供传统运输服务，扩 宽到以现代科技、管理和信息技术为支柱的综合物流系统。现代物流全面溶汇了经济 科学、技术科学及管理科学，揭示了运输、储存、装卸搬运、包装、流通加工、物流 信息等物流各要素的内在联系。 在现代物流集约化、一体化的发展中，配送是直接与消费者相连的重要环节，其 核心部分是配送车辆的集约、货物配装及送货过程。而配送车辆路线优化是物流系统 优化、物流科学化的关键一环。为了提高车辆装载能力的利用率，减少车辆的空驶里 程，提高配送的经济性，必须根据各有关道路情况、客户需求情况、车辆情况，为车 辆设定一定目标下最佳路线。 目前，在物流高度发达的美、日、欧等国的配送技术水平已达到了相当高的水平， 在配送的各环节已都实现了信息化和计算机化。如在配送劳动手段方面，到上世纪 8 0 年代，发达国家的配送系统己普遍采用了计算机系统、自动搬运系统、大规模分 拣、光电识别等技术。 我国上世纪九十年代中期才开始研究物流，配送中车辆路线的研究也始于那个 时候。到目前为止，对车辆路线的研究只局限于确定型的车辆路线问题。配送中我们 所遇到的往往是随机型的配送问题，如客户的不确定，客户的需求不确定，以及车辆 行驶时间的不确定性等等。因此对随机型的车辆路线问题进行研究，对优化车辆路线， 优化配送系统，以至物流系统是非常必要的。 本文对研究随机型车辆路线问题的必要性，客户随机、需求随机、时间随机、需 求和时间都随机的车辆路线优化进行了比较深入的分析，并在分析基础上有不同程度 的研究。 第一章问题的提出和研究现状 第一节配送和车辆路线优化 一、雕送 配送一般定义为，配送是根据客户的订货要求，在配送中心或物流结点进行货物 的集结与组配，以最适合的方式将货物送达客户的全过程。配送是物流中一种特殊的、 综合的活动形式，是商流与物流的紧密结合。从物流来讲，配送是物流中直接与消费 者相连的环节，配送的距离较短，位于物流系统中接近用户的一端，处于支线运输、 二次运输和末端运输的位置，印到最终用户的物流。由于它直接影响着物流的成本和 客户的满意度，因此配送是影响物流提供者利润的关键一环。 配送实际是一个物品集散过程，这一过程包括集中、分类和散发三个步骤。这三 个步骤由一系列配送作业环节组成，通过这些环节的运作，使配送的功能得以实现。 配送一般流程图见卜图卜l 。 蓬妪困岖叫蛩 图1 1 配送流程图 由于信息技术的发展，新的物流配送模式中存储已不是必然的环节。因此配送主 要包括以下几个部分： ( 1 ) 集货 集货是配送的首要环节，是将分散的，需要配送的物品集中起来，以便进行分拣 和配货。为了满足特定用户的配送要求，有时需要从几家甚至数十家供应商处，将预 定的物品集中到一处。集货足配送的准备工作。配送的优势之一，就是通过集货形成 规模效益。 ( 2 ) 分拣 将需要的物品从仓储地方拣取出来，配备齐全，并按配装和送货要求进行分类， 送入指定地方堆放的作业。 ( 3 ) 配货 配货是将拣取分类完成的物品经过配货检查，装入容器和做好标记，再运到发货 准备区，待装车后发货。 ( 4 ) 车载货物的配装 配装也称配载，指为充分利用运输工具( 如货车、轮船等) 的载重量和容积，采 用先进的装载方法，合理安排货物的装载。配载，将多个用户的货物或同一用户的多 种货物合理地装载于同一车辆上，不但能降低送货成本，提高企业的经济效益，还町 以减少交通流量，改善交通拥挤状况。 ( 5 ) 送货 送货，是按照配送计划和事先设定的配送路线，将配载好的货物送达到用户指定 地点，并与用户进行交换。如何确定最佳路线，如何使配装和路线有效结合起来，是 配送的项重要的任务，也是难度较大的工作。 在不同的市场环境下，为了满足不同产品、不同仓业、不同的流通环境的要求， 在配送组织活动过程中，可以采取不同的配送形式来满足用户的需要。根据配送组织 过程的两大要素，即配送的时间和配送货物的数量不同，配送活动分为定时配送，定 量配送，定时定量配送，定时、定线配送和即时配送等几种不同的组织形式。 二、车辆路线优化 ( 一) 车辆路线问题 车辆路径问题( v e h i c l er o u t i n gp r o b l e m ) 是由d a n t z i g 和r a m s e r l 9 5 9 年首 次提出，很快就引起了重视，成为运筹学与组合优化领域的前沿和研究热点。 在许多配送系统中，管理者需要采取有效的配送策略以提高服务水平、降低货运 费用，其中，车辆路线问题是需要解决的一个重要问题。车辆路线优化，就是为了解 决车辆路线问题，为了提高车辆装载能力的利用率，减少车辆的空驶里程，提高配送 的经济性，在配送中事先根据各有关道路情况、客户需求情况、车辆情况，根据一定 的目标，为车辆设定最佳路线。 车辆的最佳路线，必须满足如下条件： ( 1 ) 满足所有客户的需求。 ( 2 ) 不使任一辆车超载。 ( 3 ) 每一辆车每天的总运行时间或行驶里程不超过规定的上限。 ( 4 ) 能够满足用户到货时间的要求。 ( 二) 车辆路线优化的重要性 如果在配送中车辆路线设定不合理，或者在设定路线时缺乏科学的方法，孤立地 处理货物配送问题，将会造成不合理的配送运输。这些不合理的配送运输主要表现在 以下几个方面： ( 1 ) 运输工具的装载率低下； ( 2 ) 运输工具的空驶率高； ( 3 ) 车辆路线迂回； ( 4 3 配送运输倒流； ( 5 ) 过远配送运输； ( 6 ) 不能满足客户地要求( 时间) ； ( 7 ) 增加设施的投入，从而增加了配送的成本。 送货是配送活动的核心。在物流活动中，送货的实际形态就是货物的运输。但是 配送运输与通常的远途运输有很大的区别，通常的远途运输是区域与区域之间的运 输；而配送运输通常是短途运输，通常面对众多的用户，适合批量小、种类多的商品 运送，因此配送运输路线短但繁杂。同一路线往返次数多且路线较为固定，即使一条 路线一次运输节约费用不多，但由于次数多乘数大，总费用能降低很多。一般城市交 通路线又较复杂，如何组合成最佳路线，如何使配装和路线有效搭配，是难度较大的 工作。 由于配送运输独有的特点，合理规划配送运输路线对配送成本的影响要比一般运 输大得多，配送路线的合理与否对配送速度、效益以及客户的满意度影响也很大，特 别是多用户配送线路的确定更为复杂。采用科学的、合理的方法确定配送线路，是配 送活动中非常重要的一环。 进行配送系统的优化，其主要是优化车辆路线和优化配送车辆调度。在国外，类 似的工作已广泛地应用于生产、生活的各个方面，如报纸投递及线路的优化、牛奶配 送路线的优化、电话预定货物的车辆载货和线路设计及垃圾站选址优化、连锁店的送 货及路线优化等等。 优化车辆路线，科学地进行配送车辆调度，就会改善配送运输系统，从而使配送 运输合理化，主要体现在以下几个方面： ( 1 ) 节约配送成本 通过提高运输工具的装载率、降低运输工具的空驶率及减少配送中的不合理运输 缩短运输里程，可以减少货物单位配送成本。 ( 2 ) 提高客户服务质量 通过为配送设定固定的路线，安排固定的车辆和司机，可方便客户收货的安排和 联络。通过特定车辆路线，可满足客户的特殊送货要求，提供个性化的配送服务。 ( 3 ) 节省运力和能源 配送运输合理化，消除了不合理的现象，节省了运力，降低了能源消耗。 配送车辆路线优化，是配送系统优化的关键一环，也是电子商务活动不可缺少的 内容。对车辆路线优化的理论和方法进行系统研究是物流集约化、发展智能交通运输 系统和开展电子商务的基础。 ( 三) 车辆路线优化的任务 优化的配送系统需要利用多种配送技术和方法来提高配送效率，降低配送费用， 最大限度地降低车辆空驶率，提高配送作业的柔性和灵活度。集货是指车辆从配送中 心出发，到各厂家装货，装满后返回配送中，t l , 仓库。在满足各厂家发货要求的情况下， 按什么路线行驶，可使总费用最少，即集货优化问题。配送中心的送货作业是指按照 顾客的需求，将运输车辆装满货，送到客户处后再返回到配送中心。 车辆路线优化的任务是为车辆安排发送、集货的路线，也就是通过优化路线，为 车辆设定为客户发送货物或从客户处集货的次序，使得车辆完成配送作业的总行驶路 程，或时间，或总费用最少。在配送中集货和发送的实质是相同的，在以后的研究中， 只研究发货的情况。 在货物量较少时，用一辆车完成一项任务，车辆不能满载，利用率就低，可考虑 用一辆车完成多项任务。如图卜2 所示。 图i - 2 配送任务分配和车辆路线 ( 四) 车辆路线优化的分类 车辆路线优化中，根据因素是否确定，可分两种情况：第一种为确定型的车辆 路线优化，第二种为随机型的车辆路线优化。 i 、确定型的车辆路线优化 确定型的车辆路线优化是指，配送中的因素都是确定的情况下，如客户需求是确 定的，车辆在各路段的行驶时间是确定的，车辆的数量是确定的，以及车辆要访问的 客户也是确定的情况下，优化车辆配送路线，使得费用最少。 在确定型的车辆路线优化中，配送中心管理人员所为车辆确定访问客户的最佳路 线辆路线必须满足： ( 1 ) 车辆从配送中心出发，完成配送任务，回到配送中心； ( 2 ) 每个客户由一辆车完成发送任务，且每辆车只能访问客户一次； ( 3 ) 车辆线路上的配送总任务不能超过车辆容量： ( 4 ) 发生费用最少( 或总路程最短、时间最短) 。 2 、随机型的车辆路线优化 在车辆路线优化中所遇到的所有因素，或者部分因素是随机的而非确定的，如各 路段车辆行驶时间是不确定的，以及客户的需求是不确定的等等，那么把这类车辆路 线优化称为随机型的车辆路线优化。 当然，在随机型下车辆也必须从配送中心出发，完成配送任务，回到配送中心， 但是同一客户的需求可以由多辆车或同一辆车多次送货完成。且在随机的车辆路线优 化中，其目标往往是车辆完成配送的总时间期望最少，或总费用的期望最小。 第二节研究随机型车辆路线优化的必要性 一、确定型车辆路线优化的研究概况 1 、确定型车辆路线优化研究现状 n c h r is t o f i d e sa m i n g o z z ia n dp t o t h1 9 8 1 11 ，对单车场的车辆调度进行 了研究，建立了比较系统的数学模型，其安排车辆路的目标是车辆行驶里程最短，并 对车辆路线里程的下界进行了研究，也提出一种车辆路线问题的精确解法。1 9 8 4 年 g 1 a p o r t ey n o b e r tm d e s r o c h e r s 1 3 对有车辆容量和行驶里程限制的车辆路线 问题进行了研究，且建立了线性的数学模型，用松弛问题进行求解。在这之后， m a r s h a l ll - f i s h e r 9 31 9 9 4 年，j o h n c u r r e n ta n d 1 a s a np i r k u i i o 1 9 9 4 年，j i e f e n g x uj a m e sk e l l y 1 2 1 9 9 6 年也对单车场的车辆路线问题进行了研究。 1 9 8 8 年m o s h ed r o r 和p i e r r et r u d e a u ，对客户需求可通过多辆车多次发送( s p l i t d e l i v e r y ) 满足客户需求情况下的车辆路线问题进行了研究，提出了比较完整的数学 模型，说明了通过多辆车多次发送节省配送成本的潜力。m a r s h a l l1 f i s h e r 、 b a o x i n gt a n ga n dz h a n gz h e n g 8 1 9 9 5 年，对集货和送货的联合车辆路径问题进 行了研究。 我国，1 9 9 6 年姜大立和杨西龙 6 对简单的v r p 问题进行了研究。李明善和唐小 我 3 2 0 0 2 年对简单的有时间窗限制的v r p 问题进行了研究。李军和郭耀煌 1 对车 辆调度问题进行了比较全面的研究，如集货或送货非满载车辆优化调度，集货和送货 一体化非满载车辆优化调度，单车型满载车辆的优化调度，以及多车型的满载车辆的 优化问题等。 2 、确定型车辆路线优化的求解状况 v r p 问题的求解方法可分为七类： l 、先分组后安排线路方法( c l u s t e rf i r s t - - r o u t es e c o n d ) 这种方法，先将点进行分组，同组点的任务指定由同一辆车完成，然后对同组内 的点和配送中心设计一条费用最小的路线。 2 、先安排线路后分组方法( r o u t ef i r s t - - c l u s t e rs e c o n d ) 这种方法首先构造一条线路( 通常不能满足所有约束条件) ，然后根据具体条件 将线路分成一些较短的车辆线路。在具体问题中，一般是先解经过所有点的旅行商问 题，形成一条线路，然后根据具体的约束对它进行分割。如最短路法( t h es h o r t e s t p a t ha p p r o a c h ) 、匹配算法( m a t c h i n ga p p r o a c h ) 、集划分算法( s e tp a r t i t i o n i n g a p p r o a c h ) 等都属于此类。 3 、节约插入算法( s a v i n g so ri n s e r t i o nm e t h o d ) 这种方法根据节约费用的大小增加边，直到所有的点都联入车辆线路，如 c l a r k e w r i g h t 节约算法。 1 9 7 9 年c h r i s t o f i d e s ，m i n g o z z ia n dt o t h 用二阶段算法求解v r p 。算法的第一 阶段，根据最小的费用插入步骤，构造h 条线路；第二阶段，以h 条线路开始，通 过比较顾客插入线路所改变的费用，将顾客都插入到线路中。 4 、改进交换算法( i m p r o v e m e n to re x c h a n g em e t h o d ) 在始终保持解可行的情况下，力图向最优解靠近，每一步都产生另一个可行解以 代替原来的解，使目标函数得以改进，一直继续到不能改进为止。 5 、数学规划算法( m a t h e m a t i c a lp r o g r a m m i n ga p p r o c h ) 把问题直接描述成一个数学规划问题，根据其模型的特殊构形，应用一定的技术 进行划分，进而求解已被研究过的子问题，如分配启发式算法。 1 9 8 1 年f i s h e ra n dj a i k u m a r 的分配式算法，就是将车辆路线问题的数学模型构 造成指配问题，目标函数系数矩阵是指配给某一车辆的点集的最优旅行商线路费用矩 阵。在求解中，将很复杂的系数矩阵，用线性近似值代替。求解分两步进行，第一步， 为每辆车选种子顾客，开始车辆仅服务于它的种子顾客，形成种子路线；第二步，通 过解指配问题，将其余的顾客分配给种子路线。 6 、交互式优化法( i n t e r a c t i v eo p t i m i z a t i o nm e t h o d ) 求解中加入决策者的决策和选择，在求解中，往往需要决策者决定参数值改变的 方向。 7 、确切算法( e x a c ta l g o r it h m s ) 此类算法能得到问题的最优解，但是当需要配送的顾客数量大，且约束条件比较 复杂时，它在实际中往往不可行。 二、随机型车辆路线优化研究的必要性 ( 一) 因素随机的普遍性 确定型的车辆路线问题，在处理过程中，所有的参数都是确定性的，没有涉及不 确定的参数，在安排车辆路线开始认为可得到所有涉及到车辆路线选择和调度的信 息。 但在实践中不确定在许多方面存在，包括： ( 1 ) 车辆数量 车辆的损坏以及配送中的耽搁等，都使可利用车辆数是不确定的。 ( 2 ) 车辆容量 车队中不同容量的车辆构成是不确定的，且可利用车辆的容量也是不确定性。 在配送过程中，往往保留一部分的运输能力用于其它用途，这些不确定性因素导致 车辆调度过程中的车辆容量的不确定性。 ( 3 ) 车辆的行驶时间 由于不同交通情况，使得车辆在两客户问的路段上行驶的时间是随机的。如下 雨天的行驶时间要比通常情况下的时间要长，道路的拥挤程度、道路上的交通事故 等等都使得车辆的行驶时间是随机的 ( 4 ) 客户的位置 在实践中客户的位置，以及客户间的最短距离都是不精确的。车辆，如海上运 输的船舶一样，驶往下一客户，有时都是不确定的。 ( 5 ) 客户的需求 客户需求的确切数量信息的取得可能发生在设定车辆路线时，或者车辆从车场 出发开始送货时，或者车辆到达客户门前时，甚至车辆完成发送任务前。 ( 6 ) 需要发送服务的客户 由于定货的取消，或者客户在特定期间内对车辆配送没有需求，都将导致在某一 时间段内需要车辆发送的客户都是随机的。为得到更优的结果，在建模和求解时，我 们必须考虑这些随机因素。否则得到的结果是次优的。 ( 二) 随机因素对车辆路线选择的影响 在确定型的v r p 中，一个客户的需求，由一辆车辆且仅此车辆一次发送货物就满 足此客户的需求。也就是在确定型的v r p 中，分送( s p l i tac u s t o m e r sd e m a n di n d i f f e r e n tv e h i c l e s ) 是不允许的。但在随机型的v r p 中，车辆多次发送满足客户的 需求是允许的。假如车辆到达客户处时才能确定客户的需求，车辆按预定的路线为客 户发送货物，如果在某一客户处累积需求( 加上此客户的需求) 超过车辆容量，即车 辆在此客户处货物发送完了，但还没有满足此客户的需求，这时为了满足此客户的需 求，牟辆只能回到配送中心装货，然后回到还没有满足需求的客户处，继续未完成的 配送任务。 在随机v r p 中，当车辆空车时，如果未完成配送任务，可回到配送中心装货，然 后继续配送。但是，随机型的车辆路线优化，必须考虑车辆回到配送中心装载货物， 会产生一些费用或增加车辆的行驶里程。而在确定型的车辆路线优化中，没有这种情 况的出现。因此确定型和随机型两种车辆路线优化的结果是不同的。如图卜3 所示“。 1 3 a1 - 3 一b 图1 - 3 确定型和随机型车辆路线比较 1 - 3 a 为优化后的确定型车辆路线，1 - 3 一b 为优化后的随机型优化车辆路线。尽管确定 型的v r p 是随机型的v r p 的特殊情况，但图中可知，车辆路线是完全不同的。 ( 三) 随机型车辆路线优化的复杂性 确定型v r p 是一个n p ，随机型v r p 是在v r p 基础上，带有不确定性的因素，因 此随机型的v r p 比确定型的v r p 更难求解。李军和郭耀煌 1 研究了旅行商问题和有 向旅行商问题都是n p 问题。中国旅行商问题的复杂性为o ( v 3 ) ，有向旅行商问题的复 杂性为o f v 3 l o ga ) 。有确定开始时间的车辆调度问题的复杂性为o ( v 3 ) 。而随机型的 车辆路线问题都比上述几种问题复杂，可以说是错综复杂。如， 4 中求解的复杂性 也为o ( v 3 ) ，求解时需要考虑2 ”1 种情况，有2 n 约束条件。 随机型车辆路线问题的算法，大多是启发式算法，而且是由确定型的车辆路线的 算法改造来的。 第三节随机型车辆路线优化研究现状和研究方向 一、研究现状 ( - - ) 客户随机的旅行商路线问题( t r a v e l i n gs a l e s m a np r o b l e mw i t hs t o c h a s t i c c u s t o m e r st s p s c ) 1 9 8 7 年p j a l l e t 1 3 对客户随机的旅行商问题( t r a v e l i n gs a l e s m a np r o b l e m w i t hs t o c h a s t i cc u s t o m e r st s p s c ) 进行了研究，给出了旅行商路线的路程期望表 达式，假设客户中有m 个客户每次都有配送需求，另有n 个客户是否需要配送是随机 的，且需要配送的概率为p ，如果旅行商路线为t = ( 1 ，2 ，n + m ，1 ) ， 1 3 给出的e l l t 为： e l t 2 p 2 【( 1 邓) 7 础】+ p ( 1 一p ) “瑶”+ ( 1 一p ) “础， 其中或：d 。( 了了万_ i ) ，r 【o , - - , n - 1 】，其中可，再忑，再了代表的是路线中 不需要访问的随机客户，碟j 表示在路线中，在两个每次都需要访问的客户问出现不 1 0 需要访问的随机客户中数量为0 和n l 之间的可能情况下的路线期望。碟：表示需求 随机的客户都不要访问情况下的车辆路线。 1 3 还对e l l 。 进行了证明。其最重要的 贡献是对p t s p 和t s p 两种情况下的路线进行了比较，最后得出了p t s p 路线解的一些 性质。 m g e n d r e a ug l a p o r t er s e g u i n 1 4 ，对随机型车辆问题的研究进行了回顾， 此文提到b e r t s i m a s ( 1 9 8 8 ) 年在他的博士论文以及b e r t s i m a sa n dh o w e l l ( 1 9 9 3 ) 1 5 给出了p t s p 的另外一些更深入的性质。 0 b e r m a n 1 6 中讨论了两个问题：在访问顺序给定的情况下，发现最优的车辆驻 地；在给定驻地的情况下，寻找最优的预定路线。对于第二个问题， 1 6 用分枝一定 界算法求解，其算法是建立在运输问题的关键结果上，有2 n 个约束条件的运输问题 肯定有一个下限。其最优车辆路线的设定，也建立在任何客户都有需求的概率相等的 基础上。并且在文中指出，在实践中，分枝一定界法不需得出完整的分枝一定界树，在 分枝一定界过程中取得的任一结果都可与在分枝一定界树上所有点的最小下限比较。 ( 二) 客户随机的车辆路线问题( 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 c c u s t o m e r sv r p s c ) v r p s c 是t s p s c 的扩展。m g e n d r e a ug l a p o r t er s e g u i n 1 4 ，对其进行了回 顾，并指出各文献在这问题上的贡献。c d j w a t e r s 1 4 ，对预先设定的车辆路线的 行驶里程和再优化的车辆路线的行驶里程进行了比较。 d j b e r t i s i m a sp j a i l l e ta r o d o n i 1 7 ，考虑在一个完整的网络图上，每 个客户需要访问的概率为p 情况下的联合优化问题，并且介绍了预先优化策略和再 优化策略思想，讨论了预先优化在多种境况下的适用性，证明如果客户的位置在一个 平面上是随机分布的，这时，预先优化策略和再优化策略是非常相近的( 通过证明) 。 1 7 中，如果车辆路线为t = ( 1 ，2 ，n ，1 ) ， 1 7 给出的e l t 为： e l t 卜善荟( dp f p ，n ( 1 - a ) + 善善州棚a p ，职1 - n ) 玎( 1 一a ) 并指出v r p s c 的求解的复杂度为o ( v 2 1 。 ( 三) 需求随机的车辆路线问题( v e h i c l er o u t i n gp r o b l e m w i t hs t o c h a s t i cd e m a n d v r p s d ) 综观v r p s d 的文献，对v r p s d 的模型构建可分为三类：第一类是受完成配送任务 概率限制的数学模型( c h a n c ec o n s t r a i n e dm o d e l s ) ；第二类是考虑重新装货的整数 规划模型；第三类为，线性规划模型。 i 代表客户的需求，t 。表示可行解的集合。第 一类的模型为： m i n z = 。i , j c i , j 啄 s t ： p ( 考r 嘞芏q ) 芑1 一a ( 七= h 肌) x = ( ) l 第二类模型为： r a i n z = 。u 勺x o k + 。九阳 约束条件：x l e 1 - 表示在路线k 上，客户需求超过车辆容量的数量期望。第三类模型，目标函数 大多以r a i n “+ 0 的形式出现，约束条件为每个客户需求和决策变量的整数约束条件 等。 t i l l m a n f 1 9 ，首次提出了v r p s d 的解法，此解法是以c l a r k e w r i g h t 的解法为 基础的。m d r o rp t r u d e a u 2 2 ，考虑车辆路线失败( 车辆所装货物已配送完了，但 路线上还有客户还没有满足需求) ，对路线的总路程期望的影响，其处理方法是假定 路线失败后车辆就不再继续发送，但会受到与未满足的需求成正比的费用惩罚。 w e n h u e iy a n gk m a t h u rr h b a l l o u 2 3 中，假设客户需求是随机的和客户的 实际需求只有在车辆到达客户时才知道，此文第一次设计车辆预定路线时，考虑重新 装货，即在车上所剩的货物不为零的情况下车辆可回到配送中心装货，而且在设定车 辆路线时，车辆在哪一客户处回到配送中心也设计进车辆路线，还提出了先安排线路 后分组和先分组后安排线路两种启发式算法。在此文中，量表示客户的需求，其是随 机变量， ，= 1 ， 2 ， ) ，如果预定的车辆路线为t = ( 1 ，2 ，i i ，1 ) ，假设车辆到 达j 客户并完成对j 的配送任务后，车辆还剩余货载q 。，令占表示经过部分客户的最 优路线，f 表示车辆从j 客户处完成配送任务路线( 经过没有满足需求的客户路线) 的路程期望。斧 表示车辆到达客户j 处时所行路线的路程期望。s ，表示在j 处完成 发送后货载的所有可能情况。在用动态规划求解最优路时，有： 1 2 2 = ：【 。( 皤) + 五6 ( 吼) h ( 碍f ) 。 磊 在此文中还给出了在没有约束条件限制的情况下单车辆的车辆路线要优于多车辆路 线的结论，但没有约束条件的车辆路线在实践中有很多限制。 m d r o rg l a p o r t ep t r u d e a u 2 4 ，对以往的v r p s d 研究进行了回顾，通过比较 已有的数学规划模型，构建了一个新的模型，并推荐了一种新的求解方法一一 m a r k o v i a nd e c i s i o np r i c e s s e s 。d j b e r t i s i m a s 2 5 ，导出需求随机下设定车辆路 线期望的上下界限。j r b i r g e 2 6 ，对多阶段的