（管理科学与工程专业论文）物流配送环节中车辆路径问题（vrp）的研究.pdf

山东师范大学硕士学位论文 物流配送环节中车辆路径问题( v r p ) 的研究 摘要 随着人类社会的发展，对问题的求解要求已经不仅仅停留在可行性的角度上，而是朝 着简洁、高效、快速的方向前进，不仅要求满足人们的生活学习的一般需求，而且在时间、 空间等资源消耗上也要求达到最少，以最小的代价实现最好的结果。现代的物流管理学便 是其中一个例子。 随着物流业向全球化、信息化及一体化发展，配送在整个物流系统中的作用变得越来 越重要。运输系统是配送系统中最重要的一个子系统，运输费用占整体物流费用的5 0 左 右，所以降低物流成本首先要从降低物流配送的运输成本开始。其中，运输线路是否合理 直接影响到配送速度、成本和效益，特别是多用户配送线路的确定是一项复杂的系统工程。 高节奏高效率的社会，人们对于物品的配送，不仅要满足正常的物品配送要求，而且还在 物质资源、人力资源、时间资源等的消耗上也提出了要求。 在物流配送业务中，配送车辆调度问题的涉及面较广，需要考虑的因素较多，对配送 企业提高服务质量、降低物流成本、增加经济效益的影响也较大。而且，随着市场经济条 件下对配送服务水平要求的提高，时间因素在配送过程中越发显得重要。鉴于此，本文将 着重研究带时问窗约束的物流配送车辆路径问题。 运输问题是物流决策中的关键问题。一般来说，除去产品中的采购成本外，运输成本 比任何其他物流活动的成本所占的比例都要高。尽管运输的形式有很多种，但其中最重要 的不外乎运输方式的选择、车辆调度与规划等内容。 选取恰当的车辆路径，可以加快对客户需求的响应速度，提高服务质量，增强客户对 物流环节的满意度，降低服务商运作成本。正是有这种迫切的需求，所以在计算机高度发 展的今天，如何让计算机模拟物流的配送过程，并最终给出最简洁最高效的配送方案，一 直以来是众多计算机学者研究的焦点，并由此衍生出了一个新的研究课题车辆路径阔 胚( v e h i c l er o u t i f l gp r o b l e m v i p ) 。 通过世界各国广大研究人员的共同努力，现己提出了许多用于求解不同类型的v r p 的最优解和近优解的模型及其精确和启发式算法，以及相应的软件包。与国际上相比，国 内对v r p 的研究相对较少，有关车辆路径问题的研究是在2 0 世纪9 0 年代以后才逐渐兴起 的。比国外相对落后3 0 余年。目前，国内对于复杂的车辆路径问题的研究尚处于起步状 态。 基于对目前v r p 研究中存在的问题进行详细的分析，本文首先将物流配送问题及物流 配送环节中的v r p 问题进行系统详细的阐述，包括对该问题提出的研究背景、国内外的研 究现状，以及研究的理论依据及存在的问题均作出深刻剖析和总结，并将在v r p 问题中需 要考虑的目标及约束进行综合，列出一个统一的数学模型。这个模型可以根据不同单位对 各目标的重视程度给每个目标辅以不同的权重值，或者可以将五个目标按优先权合理安排 山东师丽犬擘硕士譬位论文 目标模型。本文还根据研究该问题的发展过程，把国内外出现的解决v r p 问题的各种算法 的原理及执行过程作了详细地说明，并分析各种算法的优缺点，说明其最适用于解决何种 问题。然后根据建立的数学模型，找一个典型的物流配送案例，使用c w 方法解决该问 题。最后，对该研究领域做出总结和展望。 关键词：物流物流配送车辆路径问题启发式算法优化 i l 山东师范大学硕士学位论文 r e s e a r c ho nv e h i c l er o u t i n gp r o b l e m si nl o g i s t i c sd i s t r i b u t i o n a b s t r a c t w i t ht h ed e v e l o p m e n to ft h eh u m a ns o c i e t y , t h es o l u t i o no ft h eq u e s t i o na l r e a d yn o t m e r e l yp a u s e si nt h ef e a s i b l ea n g l e ，b u tf a c e st h ed i r e c t i o nt ob e i n gs u c c i n c t ，h i g h l ye f f e c t i v e a n df a s ta d v a n c e d , n o to n l yr e q u e s t st oh a v et om e e tp e o p l e sg e n e r a ln e e di nl i f ea n ds t u d y , b u t a l s or e q u e s t st oc 4 】n s a m et h el e a s tr e s o u r c e so ft i m ea n ds p a c e , a c h i e v e st h eb e s tr e s u l tb yt h e m i n i n l u l np r i c e t h em o d e mr e s e a r c ho f t h e l o g i c sm a n a g e m e n ti sa l ie x a m p l e a l o n gw i t ht h el o g i s t i c si n d u s t r yd e v e l o p st ot h eg l o b a l i z a t i o n , t h ei n f o r m a t i o na n dt h e i n t e g r a t e d ，t h ef u n c t i o no ft h ed e l i v e r i n gi nt h ee n t i r el o g i s t i cs y s t e mb e c o m em o r ea n dm o r e i m p o r t a m , t h et r a n s p o r t i n gs y s t e mi st h em o s ti m p o r t a n ts u b - s y s t e mi nt h ed e l i v e r i n gs y s t e m , t h et r a n s p o r t i n ge x p e n s eo c c u p i e sa b o u t5 0 i nt h ew h o l ee x p e n s e ，a n dt h e r e f o r ei f w ew a n tt o r e d u c et h el o g i s t i c s c o s t ，w es h o u l df i r s tt or e d u c et h et r a n s p o r t a t i o nc o s t a m o n gt h e m ， w h e t h e rt h et r a n s p o r t s l i n er e a s o n a b l ed i r e c t l yi n f l u e n c e st h es p e e d ，t h ec o s ta n dt h eb e n e f i t ， e s p e c i a l l yt h ed e t e r m i n a t i o no f t h em u l t i u s e r s d e l i v e r i n gl i n ei sac o m p l e xe n g i n e e r i n gs y s t e m i nh i g h ；yr h y t h ma n de f f i c i e n c ys o c i e t y , t h eg o o d sd e l i v e r i n gn o to n l ym u s ts a r i s r yt h er e q u e s t o ft h en o r m a lg o o d sd e l i v e f i n g b u ta l s on e e dt o0 0 u s l l m et h el e a s tm a t e r i a lr e s o u r c e s t h e h u m a ni f e s o u r c e s ，t h et i m er e s o u r c e sa n ds oo i l i nt h el o g i s t i c sd e l i v e r i n g ，t h ev e h i c l em u t i n gp r o b l e ma f f e c t sb r o a d l ya r e a , a n dn e e d st o c o n s i d e ral o to ff a c t o r s ，t h ei n f l u e n c et ot h ee n t e r p r i s et oi m p r o v et h eg r a d eo fs e r v i c e , t o r e d u c et h ec o s to ft h el o g i s t i c s ，t oi n c r e a s ee c o n o m i c s e f f i c i e n c yi sb i g b e c a u s et h e e n h a n c e m e n to f t h em q u e s to f d e l i v e r i n gs e r v i c ei nt h em a r k e te c o n o m y 。t h et i m ef a c t o ri nt h e d e l i v e r i n gp r o c e s sb e c o m em o r ea n dm o r ei m p o r t a n t i nv i e wo ft h i s ，t h i sa r t i c l ew i l l e m p h a t i c a l l ys t u d yt h ev e h i c l em u t i n gp r o b l e mw i t ht i m ew i n d o w s t h ed e l i v e r i n gp r o b l e mi st h ek e yi nt h el o g i s t i c s p o l i c y - m a k i n g ，g e n e r a l l ys p e a k i n g ， e x c e p to u t s i d et h ep r o d u c t sc o s ti np u r c h a s e ，t h et r a n s p o r t a t i o nc o s to c c u p i e sh i g h e rp r o p o r t i o n t h a na n yo t h e rt h i n g s a l t h o u g ht h e r e a r em a n yk i n d so ft r a n s p o r t a t i o nf o r m s ，t h em o s t i m p o r t a n tt h i n g sa t et r a n s p o r t a t i o n sm o d ec h o o s i n g 、v e h i c l e sd i s p a t c h i n ga n dp l - m i n ga n d o n s e l e c t i n gt h ea p p r o p r i a t ev e h i c l er o u t i n gm a ys p e e du pt h er e s p o n s et ot h ec u s t o m e r s d e m a n d i m p r o v et h eg r a d eo fs e r v i c e , e n h a n c et h ed e g r e eo fc u s t o m e rs s a t i s f a c t i o n , r e d u c e t h es e r v i c eb u s i n e s so p e r a t i o n sc o s t a c c o r d i n gt os u c hak i n do fu r g e n td e m a n d ，i nt h e c o m p u t e r s h i g h l yd e v e l o p i n gd a y ，h o wt o l e tt h ec o m p u t e rs i m u l a t et h ep r o c e s so fl o g i s t i c s d e l i v t , n s n g , a n df i n a l l yp r o d u c e st h em o s ts u c c i n c t l ya n dh i g h l ye f f e c t i v ed e l i v e r i n gp l 札h a s i 山东师范大学硕士学位论义 s i n c ea l w a y sb e e naf o c a lp o i n tw h i c ht h em u l t i t u d i n o u sc o m p u t e rs c h o l a rs t u d y ，a n df r o mt h i s g r o w s an e wr e s e a r c ht 叩i c - 一v e h i c l er o u t i n gp r o b l e m s ，v r b t h r o u g ht h ev a r i o u sc o u n t r i e sg e n e r a lr e s e a r c h e r sj o i n te f f o r t , a l r e a d yh a v ep r o p o s e d m a n yt y p eo fo p t i m a ls o l m i o na n dt h en e a rs u p e r i o rs o l u t i o nm o d e la n di t si m p r e c i s ea n dt h e h e u r i s t i ca l g o r i t h mt os o l v et h ed i f f e r e n tt y p eo ft h ev r p a sw e l la sc o r r e s p o n d i n gs o f t w a r e p a c k a g e c o m p a r e dw i t l lt h ei n t e r n a t i o n a l , d o m e s t i c sv r pr e s e a r c hi sl a t e r , o n l yg r a d u a l l y e m e r g e si nt h e l 9 9 0 s , c o m p a r e dt oo v e r s e a sr e l a t i v e l yf a l lb e h i n df o rm o r et h a n3 0y e a r s a t p r e s e n ld o m e s t i c sc o m p l e xv e h i c l em u t i n gp r o b l e mr e s e a r c hi so n l ys t a r t e d b a s e do i lt h ea n a l y z e st ot h eq u e s t i o nw h i c he x i s t si nt h ep r e s e n tv r pr e s e a r c hi nd e t a i l , t h i sa r t i c l ef i r s te l a b o r a t e st h el o g i s t i c sd e l i v e r i n gp r o b l e ma n dt h ev e h i c l er o u t i n gp r o b l e mi n t h el i n ko ft h el o g i s t i e sd e l i v e r i n gp r o b l e mi nd e t a i l ，i n c l u d i n gr e s e a r c h i n gh a e k g r o u n d , d o m e s t i c sa n di n t e r n a t i o n a l sp r e s e n tr e s e a r c h i n gs i t u a t i o nw h i c hp r o p o s e st ot h i sq u e s t i o n , w e l la st h er e s e m e ht h e o r y sb a s i sa n dt h ee x i s t e n c eq u e s t i o nw i l lm a k et h ep r o f o u n da n a l y s i s a n dt h es m a r n a l y a n dl i s tau n i f i c dm a t h e m a t i c a lm o d e la c c o r d i n gt ot h eg o a la n dt h er e s t r a i n t w h i c hw i l ln e e dt oc o n s i d e ri nt h e 冲，t l l i sm o d e lm a ya c ta c c o r d i n gt ov a r i o u sg o a l sv a l u e d e g r e e ，w h i c ht h ed i f f e r e n tu n i tt og i v ee a c hg o a la u x i l i a r yb yt h ed i f f e r e n tw e i g h tv a l u e ，o r a r r a n g et h et a r g e ta c c o r d i n gt ot h ep d o r i t y a c c o r d i n gt ot h es t u d yo f t h i sq u e s t i o n , t h i sa r t i c l e h a se x p l a i n e dt h ed e v e l o p i n gp r o c e s se a c ha l g o r i t h mp r i n c i p l ea n dt h ei m p l e m e n t a t i o nw h i c h d o m e s t i ca n df o r e i g na p p e a r si nd e t a i l ，a n da n a l y z e se a c ha l g o r i t h mt h eg o o da n db a dp o i n t s ， e x p l a i n e di t sm o s ts u i t a b l et o s o l v e sw h a tk i n do fp r o b l e m a c c o r d i n gt ot h ee s t a b l i s h c d m a t h e m a t i c a lm o d e l ，t h i sa r t i c l el o o k sf o rat y p i c a ll o g i cd e l i v e r i n gc a s e ，u e e sc - wm e t h o dt o s o l v et h i sp r o b l e m f i n a l l y ，t h i sa r t i c l em a k e st h es m n m a r ya n dt h ef o r e c a s tt ot h i sr e s e a r c h a r e 乱 k e y w a r d ：l o g i s t i c s l o l ；i s t i e sd e l i v e r i n g v e h i c l er o u t i n gp r o b l e m h e u r i s t i ca l g o r i t h m o p t i m i z i n g 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研 究成果。据我所知，除了文中特别加以标注和致谢的地方外。论文中不包含其他人 已经发表或撰写过的研究成果也不包含为获得( 注：如没有其他 需要特别声明的，本栏可空) 或其他教育机构的学位或证书使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名；艾王冱是 导师签字： 学位论文版权使用授权书 五幺4 i - ， 本学位论文作者完全了解堂撞有关保留使用学位论文的规定，有权保留并向 国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权 学校q 以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在解密后适用本授权 书) 学位论文作者签名：史乏巍是 导师签字： 拟年 签字胤2 。7 年5 月影日 签字日期册a 7 年产月甲日 山东师范大学硕士学位论文 1 1 课题研究的背景及意义 第一章绪论 随着网络技术的高速发展，电子商务作为一门新兴行业在我国逐步发展起来。电子 商务具有商品信息量大、透明度高、购买不受时间制约、省时、方便、快捷、产品生产商 和终端用户直接面对、交易环节和交易费用少等优点，是一种崭新的商业模式。电子商务 主要分为b t o b 和b t o c 两种形式，b t o b 的电子商务实际上是i n t e n t e t 、e d i 等网络信息 技术应用于传统企业之问的交易，使交易更加快捷；而b t o c 的电子商务能否成功，面临 着网上资金能否安全、便利地支付和物流配送能否快速、准确地送达两大难题。网上资金 支付可以通过技术解决，但物流配送却不能，因为网上购物的消费者地点分散、购物数量 少。其配送费用无疑与快速送达相矛盾，如何低成本、高速度、准确无误地将商品送达成 为物流配送所要研究的对象。 物流在电子商务中具有不可替代的作用，它的成功与否直接关系到电子商务的成败， 它的实施与运作效率将直接影响网络所带来的经济价值。物流( 1 0 9 i s t i c s ) 是供应链中 晟重要的组成部分，是商品从生产者经过诸流通环节最终到达消费者手中的过程。物流业 则是专门从事物流活动的行业，从企业销售成本和商品价格组成角度考察，物流业蕴藏着 巨大的商机。现代物流业已被公认是企业在降低物资消耗、提高劳动生产率以外的“第三 利润源泉”，也是企业降低经营成本，提高产品竞争力的重要途径，因而受到国内外各行 业的极大重视，并得到较快发展。大量经营规模较大的制造企业和商业企业纷纷建立起配 送中心，向商品流通效率化发起挑战，与此同时，相当部分的大型运输、仓储和航运企业 开始转向第三方物流经营。 配送是指企业或物流代理企业在确认顾客的订购信息之后，将商品从各配送中心( 或 零售点) 送到消费者( 顾客) 手中的过程。从概念范畴上讲，物流包含配送。配送是物流 系统中的一个重要环节，由于它直接与消费者相连，是在集货，配货的基础上，完全按照 用户的要求，包括种类搭配、数量、时间等方面的要求进行的运送，是“配”和。送”的 有机结合形式，因而地位十分突出。配送的一般流程如图i - i 、1 - 2 所示1 1 ： 葫：；同兰同：；同；同三r 弓 供应均氍l 生产物巍 一i 墒售钧蠢 一 c = = 骑漉信息藏 图l l 供应链物流过程图 山东师范人学硕士学位论文 物流配送是物流活动中直接与消费者相连的环节。在物流的各项成本中，配送成本占 了相当高的比例。物流配送车辆调度优化，是物流配送优化中关键的一环，也是电子商务 活动不可缺少的内容。配送车辆调度的合理与否对配送速度、成本、效益影响很大，特别 是多用户配送车辆调度的确定更为复杂。采用科学、合理的方法来进行配送车辆调度，是 物流配送中非常重要的一项活动。对货运车辆进行调度优化，可以提高物流经济效益、实 现物流科学化。对货运车辆调度优化理论与方法进行系统研究是物流集约化发展、建立现 代调度指挥系统、发展智能交通运输系统和开展电子商务的基础。目前问题的形式已有 很大发展，该问题已不仅仅局限于汽车运输领域，在水运、航空、通讯、电力、工业管理、 计算机应用等领域也有一定的应用，其算法已用于航空乘务员轮班安排、轮船公司运送货 物经过港口与货物安排的优化设计、交通车线路安排、生产系统中的计划与控制等多种组 合优化问题。 运输问题是物流决策中的关键问题。一般来说，除去产品中的采购成本外，运输成本 比任何其他物流活动的成本所占的比例都要高。尽管运输的形式有很多种，但其中最重要 的不外乎运输方式的选择、车辆路径的选择与规划等内容。本文将针对其中的车辆路径问 题作较深入地探讨。 选取恰当的车辆路径，可以加快对客户需求的响应速度，提高服务质量，增强客户对物 流环节的满意度，降低服务商运作成本。正是有这种迫切的需求，所以在计算机高度发展 的今天，如何让计算机模拟物流的配送过程，并最终给出最简洁最高效的配送方案，一直 以来是众多计算机学者研究的焦点，并由此衍生出了一个新的研究课题车辆路径问题 ( r o u t i n gv e h i c l ep r o b l e m s ，v r p ) 。 车辆路径问题是一个典型的组合优化问题是一个冲难题。问题的目标是：如何利 用有限数量的车辆实现客户对物品的配送需求，每个客户被且只能被访问一次，每次车辆 的运输距离总长度不超过其最大行驶距离，同时车辆所运送物品的重量不能超过其最大的 载重量的限制，目标是使配送成本最小。车辆从配送中心出发，最后要回到配送中心，每 辆车的配送路径形成一个回路，如图i - 3 所示。如果客户对物品的配送有一定的时间限制， 即要在一定的时间窗内来完成运输配送，则问题被称之为有时间窗的车辆路径问题 ( v e h i c l er o u t i n gp r o b l e m sw i t ht i m ew i n d o w ，v r p t w ) 。本文所研究的就是有时问窗 的车辆路径问题。在下文中，在没有特指的情况下，车辆路径问题的研究都是针对有时间 窗约束条件下的车辆路径问题。 2 山东师范大学顾士学位论文 图1 - 3v r p 问题的示意图 长期以来，研究者对车辆路径问题的研究集中在寻求最优解的方向上，这时所采用的 方法有；运筹学方法、线性规划方法、非线性规划方法、动态规划方法、组合优化方法、 拉格朗日乘子法、分支定界法、爬山法、贪婪法等，并取得了不错的效果。不过这种情况 没有持续多久，在随后出现的大规模问厨上，这些方法都存在“组合爆炸”的问题，求解 时间随着问题规模成指数级增长。直到1 9 8 5 年s a v e l s b e r g h 。1 证明了车辆路径问题是n p 完全问题以后，研究的重点才转向寻求问题的近似最优解上。这时所采用的方法有：智能 规划方法、仿真调度方法、模拟退火算法、禁忌搜索算法、人工神经元网络法等，它们在 解决“组合爆炸”的问题上，能够在一个可以接受的时间内求得问题的近似最优解。 1 2 。国内外研究现状 1 2 1 国内外物流配送研究现状 物流配送在发达国家已有几十年的历史，随着现代经济的持续高涨，物流产业在市场 经济的激烈竞争中运作质量越来越高，规模也越来越大。1 9 9 9 年，美国物流产业规模为 9 0 0 0 亿美元，其中以配送为核心业务的第三方物流合同金额也非常高。美国、日本等工 业发达国家，对物流工程、物流管理等的研究已达到很高的水平，形成了比较成熟的物流 管理理念、先进的物流技术和高效的物流运营系统。在物流配送方面，日本十分重视现代 物流配送业的发展，实行统筹规划，建设有良好的物流配送基础设施。物流配送的社会化、 组织化、网络化程度比较高，生产企业、商业流通企业不是“大而全”、“小而全”地都自 各仓库等流通设施，而是一般都将物流业务交给专业物流企业做，咀达到减少非生产投资、 降低成本的目的。欧盟各国政府对物流配送的发展同样给予高度重视，许多国家认为物流 是其经济发展的加速器。 可以这么说，如果电子商务能成为2 l 世纪的商务工具，而且能像杠杆一样撬起传统 产业和新兴产业，那么，在这一过程中，现代物流产业将成为这个杠丰t 的支点。物流在电 子商务中具有不可代替的作用，它的成功与否直接关系到电子商务的成败，它的实施与运 作效率将直接影响网络所带来的经济价值。因此，近年来，物流作为“第三利润的源泉” 3 些查堑墨查兰堡主兰堡堡苎 受到国内各行业人士的重视并得到较快发展。大量经营规模较大的制造企业和商业企业纷 纷建立起配送中心，向商品流通效率化发起挑战，与此侧时，相当部分的大型运输、仓储 和航运氽业开始转向第三方物流经营。另外，我国具有强大物流配送资源优势的邮政业更 是在递送包裹的基础上为企业、商家和电子商务网站积极开展配送业务。物流配送开始在 我国迅速兴起发展起来，对物流配送的研究也引起了国内物流专家学者的广泛关注。 国内城市的物流和配送服务已有较快的发展，物流配送己经成为许多企业降低成本， 提高竞争能力的重要手段。例如，相当多的连锁企业建立了自己的配送中心，为企业内部 的连锁网点提供物流配送服务。在社会化物流配送方面，一些国有商业批发企业和大型零 售企业正在积极探索和尝试开展社会化物流配送服务。 据中国物流与采购联合会、中国物流信息中心统计，1 9 9 1 - 2 0 0 4 年，反应物流需求规 模的全社会物流总值从3 万亿元上升到3 8 4 万亿元，增长了1 2 8 倍，年均增长2 1 7 ， 太大高于同期6 d p 的年均增速。物流总值的高速增长，表明经济增长对物流的需求越来越 大，经济发展对物流的依赖程度也越来越高。同期，我国全社会物流总成本从5 1 8 2 亿元 扩张到2 9 1 1 4 万亿元，增长了5 6 倍，年均递增1 4 ，高于经济年均递增4 个百分点左右。 但这种增长势头趋于减缓，1 9 9 1 2 0 0 4 年，物流总成本占g d p 总值的比例从2 4 下降到 2 1 3 。其中，运输成本占社会物流总成本的比重为5 7 ，保管成本占社会物流总成本的 比重为2 9 ，管理成本占社会物流总成本的比重为1 4 。这说明我国物流总效益在提高， 但物流成本总体水平仍然偏高，与美国、日本、欧盟国家比要高出8 1 0 个百分点。在这 种形势下，研究如何通过实施科学的物流管理，以提高物流效率、降低物流成本、提高服 务质量是十分必要的。2 0 0 6 年，现代物流的产业地位在国家规划中得以确立，中国物流 业获得稳定快速发展，社会物流总额预计同比增长1 7 1 ，物流业增加值占服务业增加值 的比重超过1 7 ，社会物流总费j j j 与g d p 的比率稳定在1 8 5 左右。随着2 0 0 5 年底物流业 全面开放，中国物流领域正在成为国外资本投资的热点，国内物流企业加速重组整合，加 快做大做强；企业物流转移外包，与社会物流融合与渗透；物流管理与技术持续创新，向 集约化和信息化发展；物流行业各项基础工作扎实推进，物流发展的体制和政策环境进一 步改善，我国物流业进入一个新的发展阶段。1 随着我国生产力水平的提高，以整合交通运输、仓储、配送等环节而成一体，实现企 业与社会成本最低、效益最大的物流业与互联网经济一起被人们当成”新经济”的重要内 容，被广泛地称作第三利润源泉。2 0 0 6 至2 0 1 0 年，中国南方国际现代物流中心的基本框 架和主要功能将形成，物流成本占g d p 的比重再下降3 ，第三方物流占物流市场的比重 达到2 3 。到2 0 1 0 年，全球8 0 的海运出口市场，都将集中在大陆。“ 物流配送不仅在企业界受到高度重视，在理论界也引起了极大的关注。目前，对物流 配送的研究文献相当多，其中对物流配送线路的研究，主要是类似于“推销员问题”或“邮 递员问题”。对于邮递员问题主要是采取奇偶点图上作业法进行求解，且较成熟：对于推销 员问题则主要是采取启发式方法，它分为线路构造法和综合法。在线路构造法中主要是节 约算法、最邻近法和最小生成树法等，其中以节约算法最具代表性；而综合法则是依据问 题的具体情况，将几种方法综合起来应用，通常是先用线路构造法得到初始解，再用线路 改进法对初始解进行改进。在物流配送计划的研究方面，主要是研究配送中心根据客户订 4 山东师范人擘顾士学位论文 单的需求制定一个货物运装、车辆选择与路线选择的具体方案。当前。配送中心的配送计 划主要是由有经验的配送员制定，计划的优劣很大程度上取决于配送人员的经验，也有使 用信息系统来辅助制定的，但是由于配送计划的复杂性和涉及范围的广泛性，因此，对配 送计划的制定，要获得一个全方位的解决方案，还有一定的难度。如节约法仅从路线考虑， 并没有考虑到不同货物、配送时间的需求、运输资源的利用与限制等，对于考虑如满载车 辆优化调度、基于时间窗的车辆优化调度等问题的研究较少，目前主要是采用遗传算法， 但将这种方法直接应用于货运组织的日常调度作业还有一段距离，目前的实际应用较少， 主要停留在理论研究阶段。 1 2 2 国内外车辆路径问题( v r p ) 问题的研究现状 近年来，随着高性能计算机的迅速发展，国外应用计算机及现代数学方法调度车辆以 优化运输管理效果的研究工作，正在较大范围内展开。在车辆调度的形式、构造、分析以 及求解方法的实现上都有了许多突破，某些常用且较成熟的算法己被人彳j 运用于实际配送 调度系统。据资料显示。美国利用最短路算法、启发式算法开发出计算机配送调度系统， 用来解决货运汽车作业计划中路线选择和车辆分配( 如选择车型、确定车数和货运点停靠 顺序) 等问题，使汽车里程利用率提高5 - 1 5 ，运输成本和运输时间也有了明显下降；另 外美国还采用扫描法开发出车辆调度系统；日本采用节约法开发出配送运输调度系统。 但是，国内在这方面的研究大多数停留在理论层次上，实际应用系统的开发才刚刚起 步。随着物流配送业的兴起，对货运车辆运输调度提出了经济性、准时性、灵活性的综合 要求。虽然理论界和物流企业界早在数年静就提出建立配送中心车辆调度系统，但时至今 日，在开发实用的计算机车辆配送优化调度系统上还是一片空白。主要原因在于：配送 运输在我国还未真正开展，企业对优化调度认识还不够，车辆调度数学模型本身与配送 应用结合上也存在一些问题，大多数算法设置了许多假设，且仅考虑了车辆优化调度问题 的某些约束，而实际配送时，用户对运输的要求较高，调度约束条件多，这样就限制了算 法的应用范围。 在现实生产和生活中，邮政投递问题、飞机、铁路车辆、水运船舶及公共汽车的调度 问题、电力调度问题、管道铺设问题、计算机网络拓扑设计问题等都可以抽象为物流配送 中车辆调度问题，它是对一系列发货点和( 或) 收货点，构造适当的行车路经，使车辆有 序的通过他们，在满足一定约束条件的情况下，达到一定的目标。 v r p 最早是由d a n t z i g 和i c a m s e r “1 于1 9 5 9 年提出的，提出后很快引起运筹学、应用 数学、组合数学、图论和网络分析、物流科技、计算机应用学科专家与运输计划制定者和 管理者的极大重视，成为运筹学与组合优化领域的前沿和研究热点问题，备学科的专家对 该问题进行了大量的理论研究及试验分析，取得了很大进展。 自1 9 5 9 年d a n t z i g 和r a m s e r 对v r p 进行了研究，他们描述了一个将汽油送往各加油 站的实际问题，并首次提出了相应的数学规划模型及其求解算法。几年后，即1 9 6 4 年， c l a r k e 和w r i g h t 提出一种对d a n t z i g r a m s e r 方法进行改进的较有效的启发式算法 _ c l a r k e w r i g h t 节约算法。在这两篇开创性的论文发表后，v r p 很快成为运筹学和组 当查堑至查兰堡主兰堡丝兰 台优化领域的前沿与研究热点问题。早在1 9 8 3 年。b o d i n ”等在他们的长达1 4 0 多页的对 v r p 的研究进展进行综述的文章中，就列举了6 9 9 篇相关的参考文献。在1 9 9 5 年出版的 运筹学与管理科学手册中，第八卷就是专门讨论车辆路径问题的”。2 0 0 2 年，p a o l o t o t h 和d a n i e l ev i g o ”。在其出版的著作中，对v r p 的最新研究进展和发展趋势进行了全 面的分析。 m l f i s h e r 于1 9 9 5 年对车辆路径问题作了总结，他把车辆路径问题的研究方法归结 为三个阶段。2 0 世纪6 0 年代到7 0 年代是第一个阶段，这个阶段主要是应用一些简单的 启发式方法来研究车辆路径问题，研究的重点主要局限于局部搜索和交换技术；第二个阶 段是2 0 世纪7 0 年代到8 0 年代基于启发式方法的设计阶段，这个阶段主要是利用不同于 一般启发式方法的近似优化算法来求解车辆路径问题。从实验的结果分析，这个阶段的求 解效果明显优于第一阶段的简单启发式方法。到了第三阶段，即2 0 世纪8 0 年代至今，研 究的重点主要放在精确的优化算法和新兴的人工智能算法，包括模拟退火算法、禁忌搜索 算法、遗传算法和人工神经元网络方法、蚁群算法、粒子群算法等。 与国际上相比，国内对v r p 的研究相对较少，有关车辆路径问题的研究是在2 0 世纪 9 0 年代以后才逐渐兴起的，比国外相对落后3 0 余年。目前，国内对于复杂的车辆路径问 题的研究尚处于起步状态，最近几年才陆续有一些相关的研究成果发表：李军和郭耀煌” 等用传统启发式算法解决了一些相对简单的v l t p 问题，如送货点比较少的容量约束、时间 窗约束v r p ；蔡延光用遗传算法、模拟退货算法等“”1 研究重载v r p ，取得了一些成绩； 张涛等通过遗传算法来保证搜索的全局性，用3 - o p t 算法米加强局部搜索能力，得到针对 v r p 的混合算法“”；谢秉磊、郎茂祥等用遗传算法在容量约束和时间窗约束的v r p 上做 了一些工作“”“。在综述方面：汪寿阳等对寻址路径问题的研究进行了分析；祝崇隽较 全面的回顾了v r p 领域的最新进展“”；谢秉磊、郭耀煌等对动态v r p 的最新发展作了评述 “”。随着顾客需求的变化运输车辆的调度显得日益重要，近年来，我国理论界逐渐开始关 注车辆路径问题的研究，并已取得初步成果。总体来说，目前我国对车辆路径问题的理论 仍需要进一步研究。 总之，通过世界各国广大研究人员的共同努力，现已提出了许多用于求解不同类型的 v r p 的最优解和近优解的模型及其精确和启发式算法，以及相应的软件包。 在刚刚闭幕的两会上，国家提出了“十一五规划”的宏伟蓝图，提出了经济建设的新 的目标和要求。相信在未来的五年中，我国的经济增长会上个新的台阶。我国目前的商品 经济比较发达，但物流配送明显滞后，实践证明，市场经济需要更高程度的组织化、规模 化和系统化，迫切需要尽快加强建设具有信息功能的物流配送中心。美国、日本等发达国 家的物流配送业发展起步早、经验成熟，尤其是信息化管理程度高，对我国物流发展有很 大的借鉴意义。目前我国还小可能达到发达国家物流配送中心的现代化程度，只能从国情、 地区情况、企业情况出发，发展有中国特色的新型物流配送中心。 1 2 3 v r p 问题的分类 6 车辆路径问题可按照其构成要素划分不同的种类： 山东师范大学硕士学位论文 1 、按物流中心的数目分：有单物流中心问题( 配送系统中仅有个物流中心) 和多物 流中心问题( 配送系统中存在多个物流中心) 。 2 、按车辆载货状况分；有满载问题( 由于客户需求和供应的货物数量大于或等于车辆 的载重量，所以完成一项配送任务需要一辆或更多的配送车辆，配送车辆需要满载运行) ； 非满载问题( 由于客户需求或供应的货物数量小于车辆载重量，所以多项配送任务可以共 用一辆配送车辆，车辆在配送过程中经常处于不满载状态) ；以及满载和非满载混合问题 ( 由于一部分客户需求和供应的货物数量大于或等于车辆的载重量，而另一部分客户需求 或供应的货物数量小于车辆的载重量，这样就造成一些配送车辆需要满载运行，而另一些 车辆则经常处于不满载状态) 。 3 、按配送任务特征分：有纯送货问题( 仅仅考虑从物流中心向客户送货，也称为纯卸 问题) ，纯取货问题( 仅考虑把各客户供应的货物取到配送中心，也称为纯装问题) 、以及 取送混合问题( 即考虑将客户需求的货物从物流中心送到各个客户，同时考虑将客户供应 的货物从客户取到物流中心，也称为装卸混合问题或者集、送货一体化问题) 。 4 、按客户对货物取( 送) 肘问的要求分：有无时问约束问题( 客户对货物的取走和送到 的时间无具体要求) 和有时间约束问题( 客户要求将需求的货物在规定的时问窗内送到，将 供应的货物在规定的时间窗内取走，也称为有时间窗的问题) 。有时间约束问题又分为硬 时间窗问题( 客户要求货物必须在规定的时间窗内送到或取走，不能提前或拖后) 和软时问 窗问题( 尽量在规定的时间窗内送到或取走客户的货物，但可以提前或拖后，发生提前或 拖后的情况时要对配送企业实施一定的惩罚) 。 5 、按车辆类型分：有单车型闯题( 所有配送车辆的载重量相同) 和多