（产业经济学专业论文）确定信息条件下的车辆调度问题研究.pdf

摘要 随着物流业的迅猛发展，车辆路径问题( v e h i c l er o u t i n gp r o b l e m ，简称v r p ) 在物流研究领域备受关注，己成为该领域的热门问题。合理的路径安排方案不仅 可以降低企业的配送成本，还可以提高企业服务的质量，增强企业的综合竞争能 力。 本文旨在研究更加贴近现实的确定信息条件下的v r p 问题。首先，从考虑 了顾客受时间约束的v r p 变化形式一一带时间窗的车辆路径问题( v e h i c l e r o u t i n gp r o b l e mw i t ht i m ew i n d o w s ，简称v r p t w ) 入手，再在传统v r p t w 的基础上，结合考虑实际生活中由于资金等诸多原因而不能无限制购置车辆的问 题，对由l a u 等人于2 0 0 3 年提出的新模型限定车辆数的m v r p t w 进行研 究，提出并用c + + 语言实现一种解m - v r p t w 的新型两阶段启发式算法，然后运 用经典的s o l o m o n 算例验证其适用范围，最终通过分析对比得出该算法对于有效 地求解现实生活中一类物流配送问题的可行性。 本文的研究过程将先对其他学者的研究成果进行总结和归纳，通过对比分析 的手段，总结出各种算法的优势与不足，然后，经过对v r p t v v 和m - v r p t w 的 进一步研究，针对v r p t w 问题提出了改进的遗传算法，而对于m - v r p t w 问题 提出了新型的两阶段启发式算法，并将有效的解法运用到实际问题的解决中，最 终将算法推广到解决一类物流配送问题。 本文的重点工作在于：给出针对v r p t w 问题的改进遗传算法，并用c + + 语言实现了该算法，通过算例验证算法的有效性；针对m v r p t w 问题给出新 型两阶段启发式算法，并通过经典算例验证算法的有效性，然后用该算法解决一 类实际配送问题。该算法针对第一阶段最大化服务顾客数的目标，运用一种基于 优化的k - 均值聚类算法的优化算法；第二阶段则是在第一阶段的基础上，采用 改进的a m p 算法( a d a p t i v em e m o r yp r o c e d u r e ) 来改进第一阶段的某些解，使 它们能进一步逼近最优解。通过实验的比较分析，也证实了该算法的有效性。 关键词：确定信息条件下的车辆调度问题，v r p t w ，m v r p t w ，改进的遗传算 法，新型两阶段启发式算法 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to ft h el o g i s t i c si n d u s t r y , v e h i c l er o u t i n gp r o b l e m ( v r p ) i saf a m o u sc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e mi nl o g i s t i c s ，w h i c hh a sb e e n a t t r a c t e d , s om u c ha t t e n t i o ni nr e c e n ty e a r s i t sn o td o u b tt h a tas u i t a b l er o u t i n gp l a n c a r ln o to n l yr e d u c et h ec o s to fac o m p a n y , b u ta l s op r o m o t et h eq u a l i t yo f b u s i n e s s s e r v i c e ，a n de n h a n c et h ec o m p r e h e n s i v ec o m p e t i t i v e n e s so fe n t e r p r i s e s t h i sp a p e ra i m st os t u d yt h e 冲p r o b l e mu n d e rt h ec o n d i t i o no fi d e n t i f y i n g i n f o r m a t i o nw h i c hi sm u c hc l o s e rt ot h er e a l i t y f i r s t l y , is t a r tw i t ht h ev e h i c l e r o u t i n gp r o b l e mw i t ht i m ew i n d o w s ( v r p n 聊，w h i c hi so n eo f v a r i a n to f 冲t h a t p r a c t i c a l l yt a k e sa c c o u n to ft i m ec o n s t r a i n t s t h e n , o nt h eb a s eo ft h et r a d i t i o n a l v r p t w jit a k em a n yl i m i t si nr e a l i t yi n t oa c c o u n t ，s u c h 勰al i m i t e df l e e td u et ot h e l a c ko fc a p i t a l s o ，t h i sp a p e rs t u d i e so na n o t h e rn e wm o d e l v r p t ww i t ha l i m i t e dn u m b e r ( m v r p n 聊，w h i c hi sav a r i a n to f v r p t wa n dw a sp u tf o r w a r d b y l a ui n2 0 0 3 a n dib r i n gf o r w a r da n du s ec + + l a n g u a g ep r o g r a man e w t w o - s t a g e h e u r i s t i ca l g o r i t h m ，w h i c ha i m st o 也em - v r p t w t h e n , t h r o u g ha n a l y s i sa n d c o m p a r i s o nt h er e s u l t so fs o l o m o n sc l a s s i ce x a m p l e s ，1w o r k o u tac l a s so fr e a l - l i f e v r p p r o b l e m st h a ta r es u i t a b l et ot h i sn e wa l g o r i t h m t h i ss t u d yp r o c e s sw i l ls t a r tw i ms u m m a r i z i n gt h er e s u l t so f o t h e rs c h o l a r s r e s e a r c hr e s u l t s a n ds u n l su pt h es t r e n g t h sa n dw e a k n e s s e so fv a r i o u sa l g o r i t h m sb y w a yo fc o n t r a s t i n ga n da n a l y s i s t h e nt h r o u g hf u r t h e rs t u d i e so nt h ev r p t w a n dt h e m - v r p t wa n du s e se f f e c t i v em e t h o d st os o l v ep r a c t i c a lp r o b l e m s f o rv r p t wi g i v ei m p r o v e dg e n e t i ca l g o r i t h m ，a n df o rm v r p t wig i v ean e wt w o - s t a g e h e u r i s t i ca l g o r i t h m ，a n da p p l yt h et w oe f f e c t i v em e t h o d st os o l v ep r a c t i c a lp r o b l e m s t h e ne x t e n d st h en e wt w o s t a g eh e u r i s t i ca l g o r i t h mt os o l v eac l a s so fl o g i 【s t i c sa n d d i s t r i b u t i o np r o b l e m i nt h i sp a p e r , t h em a i n w o r ki su s i n gai m p r o v e dg e n e t i ca l g o r i t h mt os o l v e v r p t w p r o b l e m a l s ou s i n gc + + l a n g u a g ec o m p l yt h ea l g o r i t h m t h r o u g h n u m e r i c a le x a m p l e sv m f yt h ee f f e c t i v e n e s so ft h ea l g o r i t h m ；f o rm - v r p t 眦i 嫩a n e wt w o s t a g eh e u r i s t i ca l g o r i t h mt os o l v er e a l i t yp r o b l e m s g i v e nma n dav r p t w i n s t a n c e ，t h ef i r s to b j e c to fm - v r p t w i st om a x i m i z et h en u m b e ro fs e r v e d c u s t o m e r sw i mmv e h i c l e sa sm a n ya sp o s s i b l e ，a n dt h es e c o n do b j e c to ft h i sp r o b l e m i st om i n i m i z et o t a ld i s t a n c e s ip r o p o s e da l g o r i t h mb a s e do nk - m e a n st os o l v et h e i l f i r s to b j e c t w h i l er e s o r t e dt oi m p r o v e da m p a l g o r i t h mi sa ne f f e c t i v em e t h o dt od e a l 、历t l lt h es e c o n do n e t h ee x p e r i m e n t a lr e s u l t ss h o wt h et w o s t a g eh e u r i s t i ca l g o r i t h m i s 锄e f f e c t i v em e t h o dt os o l v et h em v r p t w ： k e y w o r d s ：v e h i c l es c h e d u l i n gp r o b l e mu n d e rf i x e di n f o r m a t i o n ，v r p t w ， m - v r p ”，i m p r o v e dg e n e t i ca l g o r i t h m s ，an e wt w o s t a g eh e u r i s t i ca l g o r i t h m i i i 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容 外，本论文不含任何其他个人或集体已经发表或撰写过的作品成 果。对本文所涉及的研究工作做出重要贡献的个人和集体，均已 在文中以明确方式标明。本人完全意识到本声明的法律责任由本 人承担。 特此声明 学位论文作者虢白1 苹 卿年相知日 学位论文版权使用授权书 本人完全了解对外经济贸易大学关于收集、保存、使用学位 论文的规定，同意如下各项内容：按照学校要求提交学位论文的 印刷本和电子版本；学校有权保存学位论文的印刷本和电子版， 并采用影印、缩印、扫描、数字化或其它手段保存论文；学校有 权提供目录检索以及提供本学位论文全文或部分的阅览服务；学 校有权按照有关规定向国家有关部门或者机构送交论文；在以不 以赢利为目的的前提下，学校可以适当复制论文的部分或全部内 容用于学术活动。保密的学位论文在解密后遵守此规定。 a 四年4 - 月知e l 7 年。月；。日 午 考芝 名 签球乃多撇参 作 ： 文 名 论 签 位 师 学 引 1 1 课题背景及研究意义 第1 章引言 物流与商流、信息流并称为现代经济的三大支柱，由于物流对国民经济的重 大影响，物流系统化、合理化能创造巨大经济利益，因此物流被认为是继劳动力、 资源之后的“第三利润源泉 。 传统的物流配送系统中，由于商品的需求量及种类较少，零售商可凭借较多 的存货及较长的订货周期来减少供货商的配送频率，以降低运输成本。但是，现 代物流系统中，物流配送将朝着少批量、多品种、多批次的即时配送方向发展， 物流企业应根据客户的个性化需求，提供“量体裁衣式的优质、灵活的物流配 送服务。因此在如何满足客户需求的前提下，进一步降低物流成本已经成为国内 外许多理论、应用学者们关注的焦点。 随着物流业向全球化、信息化及一体化发展，配送在整个物流系统中的作用 变得越来越重要。运输系统是配送系统中最重要的一个子系统，运输费用占整体 物流费用的5 0 n 1 左右，所以降低物流成本首先要从降低物流配送的运输成本开 始。其中，运输线路是否合理直接影响到配送速度、成本和效益，特别是多用户 配送线路的确定是一项复杂的系统工程。选取恰当的车辆路径，可以加快对客户 需求的响应速度，提高服务质量，增强客户对物流环节的满意度，降低服务商 运作成本。优化运输物流，降低运输成本，是企业尤其是物流配送企业提高企业 竞争力的有效途径之一。 本课题之所以将现实生活中最常见、最普遍的类型确定信息下的v r p 定 为研究背景，是由于在当今电子商务发展的带动下，物流企业的经营模式也发生 了变化，而以往国内外的同类研究往往只注重算法的研究，尤其是对核心经典模 型的算法研究，验证的算例也只是构造的简单的或者经典的算例，这些理论性强 的算法也难以在实际中真正应用。所以，本文从现实背景出发，以这一类型的物 流企业配送为实例，运用前人的算法设计路径规划方案，这对于众多中小型物流 配送企业及公司内部涉及物流配送的企业均有现实指导意义。 本文研究的重点在于对v r f r i w 和m - v r p i w 分别进行建模啪，并针对v r p t w 给出 改进的遗传算法，针对r v r p l w 给出新型两阶段启发式算法，对于我国中小企业 在城市配送中心营运的实际情况，选取一类中的典型实例，考虑在时间窗以及有 限车辆的约束条件下，建立以总成本最小化( 总路程最小) 为目标的车辆调度模 【1 】祝崇俊等供应链中车辆路径问题的研究进展及前景计算机集成制造系统_ c 埘s j ，2 0 0 1 7 ( 1 1 ) ：卜6 f 2 】李军，郭耀煌车辆优化调度理论与方法 m 北京：中国物资出版社，2 0 0 1 6 ，2 - 3 1 型，并运用新型的两阶段启发式算法为基础，规划求解出配送车辆各自的合理路 线，然后推广至出适合使用该解法的一类企业。本文的研究意义主要体现在以下 几点： ( 1 ) 从研究的目标上，本文的研究的内容可在很大程度上降低物流配送成本、 提高物流服务水平以及在一定程度上减缓城市交通压力，因而本文的研究具有重 要的现实意义。 ( 2 ) 从研究的内容上，本文将通过对个例进行系统的分析，从而推广至某一 类的物流企业，指导这类企业进行车辆调度，从而提高配送效率，降低配送成本。 ( 3 ) 从研究的方法上，本文尽可能地减少各种假设约束，建立了具有针对性 的模型。同时在对模型进行求解时，对于不同的模型提出了不同的算法( 运用改 进的遗传算法求解v r p t w 问题，运用新型的两阶段启发式算法求解m - v r p t w 问题) ， 并用c + + 语言实现了算法，且验证了算法的有效性，最后对实际案例给出求解结 果并推广至适合该算法的一类配送企业。 因此，本文研究的确定信息条件下车辆调度问题的模型建立及求解为当前我 国的中小物流企业及涉及物流配送的企业优化调度配送车辆提供了有价值的理 论参考，具有一定的实际指导意义。 1 2 国内外研究现状概况 1 2 1 国外的研究现状 v p , p t w 问题是v r p 问题的推广。有关v r p 问题的研究文献，在1 9 8 3 年b o d i n 就统计了约有7 0 0 余篇口1 。可是，带时间约束的车辆路线问题只在2 0 世纪8 0 年代 才开始受到重视：第一个v r p t w 最优化算法是k o l e n 等在1 9 8 7 年提出的动态规划 算法n 们。k o l e na ta 1 曾利用分枝定界法求解含时间窗约束的车辆巡回问题，其实 验的节点数范围为6 1 5 嘲1 。h e l d 和k a r p 指出分枝定界法的求解效率与其界限设定 的宽紧有极大的关系。节约算法最早由c l a r k e 等于1 9 6 4 年提出该方法并用于求解 车辆巡回问题。s o l o m o n 于1 9 8 3 年将其用于求解有时间窗约束的车辆巡回问题， 此方法的优点是可提高车辆的利用率啪3 。邻接算法是s o l o m o n 于1 9 8 3 年所提出的 求解v r p t w 的方法，它是一种序列构造路线法。插入法原本是m o l e 和j a m e s o n 于1 9 7 6 年所提出，用于求解v r p 问题的方法，其结合邻接算法与节约算法的观念， 【3 】刘云忠，宣慧玉车辆路径问题的模型及算法研究综述管理工程学报。2 0 0 5 ，1 9 ( i ) ：1 2 4 1 2 8 【1 6 】钟石泉物流配送车辆调度智能优化方法研究天津大学硕士学位论文2 0 0 4 年1 2 月：卜1 9 ”m d c s r o c h e r s ，j d e s r o s i e r s ，e t a l an e wo p t i m i z a t i o na l g o r i t h mf o rv e h i c l er o u t i n gp r o b l e mw i t ht i m e w i n d o w s j o p e r a t i o t i sr e s e a r c h ，1 9 9 2 ，( 4 0 ) ：3 4 2 - 3 5 4 1 3 0 lh w a n gh s a ni m p r o v e dm o d e lf o rv e h i c l er o u t i n gp r o b l e mw i t h t i m ec o n s t r a i n tb a s e d0 1 1g e n e t i ca l g o r i t h m 明c o m p u t c a sa n di n d u s t r i a le n g i n e e r i n g , 2 0 0 2 ( 4 2 ) ：3 6 1 - 3 6 9 2 依序将顾客点插入路径中以构建配送路线。s o l o m o n 于1 9 8 3 年将此方法应用于求 解v r p t w 问题，因为时间因素的加入，而使原问题的顾客等待时间缩短。扫除 算法最早由g i l l e t t 和m i l l e r 毛e 1 9 7 4 年提出，是一种“先分组后路线”的算法。1 9 8 7 年，s o l o m o n 将其推广应用于v m t w 问题的路线构造口幻。1 9 9 4 年，g a r c i a 等首先将 禁忌算法应用于心t 、7 l ，问题。利。遗传算法是借用适者生存规律进行局部搜索改 进的一类算法。最早是i 扫h o l l a n d 在1 9 7 5 年提出，并首先被d ej o n g 用来解决复杂问 题。1 9 9 1 年，t h a n g i a h 首先将遗传算法用于求解姆t w 问题。1 9 9 6 年，c h i a n g 和 r u s s e l l 提出v r p t w 问题的模拟退火算法。2 0 0 0 年，t a n 等基于2 i n t e r c h a n g e 法和 单调降的降温表提出一种快速模拟退火算法。19 9 9 年，g a m b a r d e l l ae ta 1 应用蚁 群算法对v r p t w 进行路线改进口鲥。 从研究的层面上看，国外同类研究往往只注重算法的研究，尤其是对核心经 典模型的算法研究，验证的算例也只是构造的简单的或经典的算例，这些理论性 强的算法也难以真正应用。另外，国外的研究对模型的构造研究相对较少，经典 的调度模型与实际物流企业的现实状况相差较大。 1 2 2 国内的研究现状 与国际上相比，国内对v r p 的研究相对较少，主要研究对象是t s p 、c p p 、 d c p p 等，系统性研究还尚未见到。有关车辆路径问题的研究是在2 0 世纪9 0 年代 以后才逐渐兴起的，比国外相对落后3 0 余年。目前，国内对于复杂的车辆路径问 题的研究尚处于起步状态，通过中国期刊数据库检索，1 9 9 4 至1 j 2 0 0 8 年1 5 年的时间 内，在中国正式期刊上己经发表该领域的文章仅一百多篇，就这方面研究的深度 和广度来说，远不能适应当前我国配送业以及物流业迅速发展的需要。最近几年 才陆续有一些相关的研究成果发表：李军和郭耀煌侧等用传统启发式算法解决了 一些相对简单的v r p 问题，如送货点比较少的容量约束、时间窗约束v r p ；蔡延 光用遗传算法、模拟退货算法等研究重载v r p ，取得了一些成绩啪1 ；李大卫等 ( 1 9 9 8 ) 以v r p 的最近距离启发式为基础，通过设置评价函数来处理时间窗约束， 求解了简单v r p 瞳。张震( 1 9 9 5 ) 针对单车场满载问题，提出了考虑运输行程约束 的优化方法。遗传算法和神经网络方法对简单v r p 的求解取得了一定成果( 靳番 l i j b k a l l e h a u g e , j l a r s e n e t a l l a g r a n g i a nd u a l i t ya p p l i e dt ot h ev e h i c l er o u t i n gp r o b l e mw i t ht i m e w i n d o w s j c o m p u l e r s & o p e r a t i o n sr e s e a r c h ，2 0 0 6 ，3 3 ：1 4 6 4 1 4 8 7 1 3 2 1a l i m , x w z h a n g at w o - s t a g e h e u r i s t i cf o rt h ev e h i c l er o u t i n gp r o b l e m 讹t u n ew i n d o w sa n dal i m i t e d n u m b e ro f v e h i c l e s j i n t e r n a t i o n a lc o n f e r e n c eo ns y s t e ms d 锄c e , 2 0 0 5 d 3 f o s t e rb 八r y a ndm a ni n t e g e rp r o g r a m m i n ga p p r o a c ht ot h ev e h i c l es c h e d u l i n gp r o b l e m t j 0 p d s r e s e a r c h ，2 0 0 32 7 ( 2 ) ：3 6 7 - 3 8 4 1 2 4 1 孙两君有时间窗的车辆路径规划模型知识表示研究 d 大连：大连理工大学，2 0 0 6 1 2 【刎朗茂祥，胡思继用混和遗传算法求解物流配送路径优化问题的研究中国管理科学，2 0 0 2 1 0 【2 1 1 李大卫等遗传算法在有时间窗车辆路径问题上的应用系统工程理论与实践，t 9 9 9 ( 8 ) ：6 5 - 6 9 3 等，1 9 9 6 ；赵赫等，1 9 9 8 ；) 。蔡延光等( 1 9 9 8 ) 应用并行表搜索算法和模拟退火 算法对满载问题进行了求解，但只针对简单情形。 国内在车辆路径问题上的研究基本上着重于车辆路径问题的启发式算法研 究，特别是针对仿生算法中的遗传算法。关于m v r p t w 的其他方面算法，包括 组合优化理论算法和变化启发式算法的研究还较少，缺乏创新性。在这方面，我 们国内的研究远落后于国外的研究。同时也存在着与国外研究中相似的问题，即 对模型的构造研究相对较少，经典的调度模型与我国实际物流企业的现实状况相 差较大。 1 3 本文主要研究的问题 1 3 1 研究内容 本文的研究对象侧重于确定信息条件下的车辆调度问题研究，主要包括两个 问题，且p v r p t w 和m - v r p t w 问题。目前，大多数研究还是集中在上冲t w ， 对于m v r p t w 的研究还相对较少，关于m - v r p t w 问题的参考文献也相对较少。 由于m - v r p t w 是v r p t w 的一种变形，所以本文先从t p t w 研究起，再进一步 研究m - v r p t w 。详述如下： 归纳总结解决v r p 问题的各种算法，并分析对比其性能及优缺点。因为，不 论是v r p t w 还是m - v r p t w ，都是v r p 问题的变形情况，所以，在学习和了解了 传统问题的解法后，为进一步研究其特殊形式问题的解法提供了理论基础。 分析研究v r p t w 问题，并给出实例进行算法验证。首先描述v r p t w 问题， 分析其影响因素，进一步建立问题的模型、提出解决问题的算法，并用c + + 实现 算法，通过例子验证算法。 分析研究m 强t w 问题，并给出实例进行算法验证。首先描述珈- _ l p t w 问题，分析其影响因素，进一步建立问题的模型，提出针对该问题的新型两阶段 启发式算法。 对本文给出的新型两阶段启发式算法的全局寻优性能进行验证，并选出一类 m v r p t w 问题中有代表性的实际企业案例进行求解，最后推广出适合使用该算 法的企业类型特征。 综上所述，本课题的研究过程将先对其他学者的研究成果进行总结和归纳， 通过对比分析的手段，总结出各种算法的优势与不足，再经过对v r p t w 和 m - v r p t w 的进一步研究，提出对这两类问题的求解算法，并用实例进行求解验 证算法的正确性，最后推广出本文算法所适用的企业类型特征 本课题属于应用研究，对于刚提出不久的m - v r p t w 问题也进行了探讨，旨 4 在对一类有代表性的物流企业的车辆调度问题的解决方案进行研究。针对本文的 研究的主要内容，本文分为五个部分进行系统地研究： 第1 章引言，介绍了本文在研究我国中小企业急需提高物流配送效率的现实 背景下，提出采用车辆调度优化的方法来解决当前的问题。在研究了国内外关于 对车辆优化调度研究现状的基础上，结合当前我国的实际情况，提出本文研究的 内容及重点。 第2 章车辆调度问题概述，系统地介绍了车辆调度优化的理论知识。首先介 绍了v r p 的分类标准，基本数学模型，然后对现有的主要算法进行了详细地说明， 并对比分析出各种算法的优劣性及适用条件，为下文的研究做好铺垫。 第3 章确定信息条件下的车辆调度问题，引出本文研究的重点内容。首先通 过对v r p t w 和m v r p t w 进行细致地分析，对其所表示的一类问题进行描述，指 出所涉及的影响因素，然后建立模型，提出合适的解决算法并用c + + 编程实现， 最后通过算例进行验证。 第4 章案例验证。本章通过引入一个具有代表性的实际案例，对该案例进行 详细地分析，并将案例的信息表述成适合建模的数据形式，然后对本文解决此案 例的算法适用性进行分析，其中引入了s o l o m o n 提出的六类测算集中的r c 2 类， 经过对r c 2 类的测算及结果的分析，得出使用新型两阶段启发式算法可以有效地 解决本案例。最终给出本案例的优化结果，并推而广之，给出适合使用该算法的 一类物流配送的特点。 第5 章总结与展望。 文章的整体组织结构如下图所示： 图1 论文结构图 5 1 3 2 创新点 由于国内外对于v r p 问题的解决算法已经相当成熟，因此本课题研究前期将 充分总结、分析、对比现有研究成果，如果没有对现有成果充分理解的研究，也 就谈不上创新。 本文之所以选择确定信息条件下的车辆调度问题中的v r p t w 和m v r p t w 问题进行研究，是因为这类问题更加贴近现实企业的需求：该类问题不仅考虑了 路径的优化和最小的行驶路线，而且考虑了顾客对服务时间的限制，以及公司对 车辆数目的限制等因素。这样建立起来的模型才更具有实用价值。 本文对于v r p t w 的解决提出了改进的遗传算法，采用了整数编码构造可行 线路的染色体，对适应度函数加入了惩罚项解决约束问题、对类p m x 方法中交 叉算子和逆转变异算子进行了改进，并用c + + 编写程序实现了该改进的遗传算 法，实证分析了该算法的可行性。 本文对于m v r p t w 的解决提出了新型的两阶段启发式算法，该算法的主要 解决思路是根据m v r p t w 的特点即给定了车辆数m ，这样就可以先把所有顾客 聚成m 类，即m 辆车或m 条路径，然后通过算子或其他近似算法最大化m 条路径中 的被服务的顾客数，最后再来最小化总路程。 本文将m v r p t w 问题算法的理论运用到实际中，指导企业物流配送中的路 径规划。首先利用了经典的侧算集进行了算法适用性的分析评估，然后对于一个 具有代表性的实际例证，给出优化方案，最后对结果进行推广，给出适合该算法 的一类企业特征，从而指导该类型的物流配送企业进行路径规划，降低物流成本， 提高企业综合竞争力。 6 第2 章车辆调度问题概述 随着市场竞争的日益激烈，物流成本对经济活动的影响已经越来越受到人们 的重视，成为了重要的竞争领域。车辆调度问题是物流配送的核心问题，实现配 送车辆的优化调度对物流企业增加利润起着关键作用。只有解决了调度问题才能 使配送有效合理。因此许多专家学者将着眼点放在如何更好的解决车辆优化调度 的问题上。那么接下去本文针对车辆调度问题的一些相关理论进行介绍。 2 1 车辆调度问题( v r p ) 的分类 i 刍v r p 问题被提出后，l h m s ( 1 9 8 1 ) ，b o d i n 和g o l d e n ( 1 9 8 1 ) ，b o d i n ( 1 9 8 3 ) ， a s s a d ( 1 9 8 8 ) ，d e s r o c h e t s ，l e x i s t r a 和s a v e l s b e t g h ( 1 9 9 0 ) 等许多学者对v i 冲问题从 不同角度，按不同的标准进行了多种分类口3 。 按任务特征分，有纯装问题或纯卸问题( p u r ep i c ku po rp u r ed e l i v e r y ，车辆 在所有任务点装货或卸货，即集货或送货问题) 及装卸混合问题( c o m b i n e dp i c k u pa n dd e l i v e r y ，每项任务有不同的装货点和卸货点，即集货、送货一体化问题) 。 按任务性质分，有对弧服务问题( 如中国邮递员问题) 和对点服务问题( 如旅 行商问题) 以及混合服务问题( 如交通车线路安排问题) 。 按车辆载货状况分，有满载问题( 货运量不小于车辆容量，完成一项任务需 要不只一辆车) 和非满载问题( 货运量小于车辆容量，多项任务用一辆车) 。 按车场( 或货场、配送中心等) 数目分，有单车场问题和多车场问题。 按车辆类型数分，有单车型问题( 所有车辆容量相同) 和多车型问题( 执行 任务的车辆的容量不全相同) 。 按车辆对车场的所属关系分，有车辆开放问题( 车辆可以不返回其发出车场) 和车辆封闭问题( 车辆必须返回其发出车场) 。 按优化目标数来分，有单目标问题和多目标问题。 由于情况的不同，车辆调度问题的模型构造及算法有很大差别。到目前为止 大多数对v r p 问题的研究主要集中于某一类v r p 问题，考虑问题较为单一，目标 的设定也只是针对运输路经最短或总运费最小进行讨论，而事实上在物流配送的 业务中，车辆调度的优化目标多种多样，常见的有： 1 、运输路经最短； 2 、总运费最少； 3 、总运输时间最短； 【9 l 刘兴，贺国光等一种有时间约束的多车辆协作路径模型及算法 j 系统工程，2 0 0 5 2 3 ( 4 ) ：1 0 5 - 1 0 9 7 4 、空载车总运行时间最少； 5 、完成任务所需的车辆最少。 综合考虑这五个目标时，总运费就不应单单是距离的函数，而要考虑到即时 配送、车辆成本、人员成本的问题。实际中配送中心对这五个目标都作了一定的 规定，只有五个目标同时满足才能称得上是一个完整的物流配送。不同单位对这 五个目标的重视程度不同，这就构成了一个多目标问题。 2 2 车辆调度问题( v r p ) 的基本数学模型 正如前面所指出，根据实际问题的不同，v r p 可以分为不i 司的类型，其主要 区别在于所考虑的某些因素的不同，这些因素包括：配送中心的数目，车辆的种 类和数目，顾客的需求特征，顾客对服务时间的需求，对车辆工作时间的限制， 等等。在以下部分只考虑一类典型的强问题，用数学语言可以将其描述为：存 在网络g = ( v ，a ) ，其中，y = ( v o ，v 1 ，v 2 ，) 是一系列顶点集合， a = ( ( 1 ，1 ，) u ，v ，v ，i ，) 是一系列边的集合，点顶点代表配送中心，在该 处有数量不受限制的、拥有同样容量q 的配送车辆，其他的顶点均代表客户。 任意两个顶点o ；，y j ) 间的运输距离为勺，并且有勺= c 月。盔表示点，处的客户 的需求量，在美国决策期间，每个客户要求只被访问一次并且其需求被满足。该 v r p 问题的目标是，确定从配送中心出发并最后回到配送中心的车辆数量及其行 驶路线，使得在满足客户需求的前提下，车辆的总运输距离最短。可将该v r p 问题用以下数学规划模型进行描述n 舶。 r a i n e c 妒 ( 2 一1 ) j e y 佧yv e 工 s t = 1 ，夥矿，j 0 ( 2 2 ) l e g 忙y x ；= l ，v f y ，f so( 2 3 ) i e y 扣p 一= 0 , v p y ，v v k( 2 4 ) i e y e y d ，( ) g ，v ，足 ( 2 5 ) 彳e y j e y 确s 1 ，v v k ( 2 6 ) 扛y 碥1 ，v v k( 2 7 ) x ；z ，v i ，_ ，矿，v v k ( 2 8 ) 【3 】陈火根，丁红钢，程耀东物流配送中心车辆调度模型与遗传算法设计浙江大学学报( 工学 版) ，2 0 0 3 3 7 ( 5 ) ：5 1 2 5 1 6 8 在这个模型中，决策变量x ：是二进制变量，l 表示路径( 1 ，v ，) 由车辆v 完成运输，否则为0 。式( 2 - i ) 为目标函数，表示运输的总距离最短；约束条件 ( 2 - 2 ) 和( 2 - 3 ) 表明，每个需求点仅由一个车辆提供配送服务；式( 2 - 4 ) 保 证一个车辆应离开已经进入过的顶点；对车辆承载能力的限制有式( 2 - 5 ) 给出； 式( 2 - 6 ) 和( 2 - 7 ) 表示每个车辆最多只能用一次；对不经由配送中心的子路 径的限制由约束( 2 - 8 ) 给出z 可被定义为 r ，、1 z = k ) ：蚓一l 扣培y o ) ；例2 ( 2 9 ) l l e bj e b j v r p 的特点是解空间随着变量的增多呈指数增长的趋势。因此，当需要配送 的顾客数量增多时，求解上有很大难度。所以，精确算法( 即能够寻找到最优解 的算法，如分支定界法、割平面法、动态规划方法等) 只适合于求解客户数量很 小的问题，如当停车卸货点的数目超过2 0 个小时，采用一般的精确算法求解最短 运输路径的时间在几个小时以上。而各种近似算法( 主要是各种启发式算法) 由 于能够在一定的时间内得到满意解，因而得到了广泛的研究与应用。 启发式方法一般都是首先产生一个初始解，然后根据算法所规定的聚类方 法，对初始解进行不断的优化，同时满足可行性条件，最终得到问题所需的满意 解。启发式方法通常在有些得时间内能够得到满意解，但不能保证时最优解，此 外，该方法通常只适用于求解某一类特定的问题，并且解的性能难以保证。因此， 通用性、稳定性以及较快的收敛性是衡量启发式方法性能的主要标准。 2 3 车辆调度问题( v r p ) 的算法评价 2 3 1 算法分类 货运车辆优化调度问题的求解方法非常丰富，n a g n a n t j ( 1 9 8 1 ) ，b o d i n 和 g o l d e n ( 1 9 8 3 ) ，g o l d e n ( 1 9 8 4 ) ，l a p o r t e ( 1 9 9 2 ) ，l a p o x t e 和o s m a n ( 1 9 9 5 ) 等许多学 者对v r p 求解方法的分类进行了研究，认为究其实质，基本上可以分为精确算法 和启发式算法两大类。 ( 一) 精确算法 精确算法指可求出其最优解的算法，精确算法主要有： 分枝定界法( b 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 ga p p r o a c h ) 9 精确算法的计算量一般随问题规模的增大呈指数增长，因此在实际中其应用 范围很有限。 ( 二) 启发式算法 启发式方法能够比较快地得到满意解，这对解决n p 问题有不可估量的作用。 因此，该方法在求解v r p 中得到了广泛的研究与应用。按照寻求模型的最优解( 满 意解) 的搜索方式的不同，可以将求解v r p 的启发式算法分为两大类。n 1 1 l 、传统启发式算法( c l a s s i ch e u r i s t i c s ) 传统启发式算法实际上是一种局部搜索方法，该算法通常从某个初始可行解 开始，按照某种规则，搜寻其领域范围内性能更优的可行解，并以搜索到的新的 可行解为出发点，不断重复上述过程，直到满足算法的终止条件为止。求解v r p 的传统启发式算法主要包括： ( 1 ) c w 节约法( s a v i n g sa l g o r i t h m ) 节约算法是由c l a r k e 和w r i s t 于1 9 6 4 年提出的，它是目前在求解v r p 问题中 应用较为官方的一种启发式算法，有许多解决v r p 问题的商业软件均是基于此算 法而开发设计的。节约算法的核心思想就是试着将目前的可行解中的两个回路 ( 0 ，i ，0 ) 和( 0 ，j ，o ) 合并为一个回路( 0 ，i ，j ，o ) 如 果在上述的合并操作中，整个运输过程的总运输距离下降，则称节约了运输距离， 相应的变化值叫做节约值。同时，若合并后的路径满足约束条件的限制( 如车辆 承载能力的限制) ，则完成此合并。到算法结束时，节约法分析并判断所有可以 产生节约值的合并。 ( 2 ) 扫描算法( s w e e p ) 该算法是有w r e n ，g a l l e t t 等人提出的。该算法首先计算要访问的顾客位置 的极坐标，并按极坐标角度大小排序，然后在未分配到任何路径中的顾客中，从 角度最小的顾客开始，依次将顾客归并到相应的路径中，直到车辆的能力约束被 满足为止；再重新选择新的车辆，重复上述过程，直到所有的顾客均分配完毕； 最后用t s p 的优化算法对各子路径进行优化。 ( 3 ) c l u s t e ra n dr o u t e 算法 该算法包括两种：先聚类后排序方法( c f r s ) 和先排序后聚类方法( 1 强c s ) 。 c f r s 是早由g i l l e t t 等人提出，它是先用启发式方法将节点( 客户) 分成若干路径， 任何对路径中的点进行排序；r f c s f l j b e s l e y 提出，它先对所有节点按照t s p 算法 进行排序，然后考虑车辆运载能力的约束，将大的路径分成若干个小的路径。 2 、现代启发式算法( m