（计算机应用技术专业论文）物流配送中车辆路径生成策略的研究与实现.pdf

江苏大学硕士学位论文 摘要 物流配送是物流活动中直接与消费者相连的环节。在物流的各项成本中，配 送成本占了很大的比例，而车辆路径优化的合理与否直接影响配送成本。凶此， 采用科学、合理的方法解决车辆路径优化问题，是物流配送中非常重要的一个环 节。 本课题以现代物流配送环节中的车辆路径问题为研究对象，结合实际物流配 送中配送中心多、问题规模大、约束条件多、复杂性高等问题，提出一种基于“集 群第一，路线第二”的路径生成策略。该策略首先使j j 改进的k - m e a n s 聚类算法 实现客户的配送区域的自动划分，将大规模的v r p 简化成小规模的v r p ，降低计算 量，提高求解速度；其次使用改进的p f i t i 算法和变邻域搜索( v n s ) 算法相结合 的混合启发式算法求解配送区域内车辆路径优化问题。 基于上述策略，本文的主要工作如下i ( 1 ) 物流配送区域及客户的聚类分析。分析影响配送过程的主要凶素，以减 少求解复杂性为目标，采用改进的k - m e a n s 算法实现客户配送区域的自动划分。 ( 2 ) 带时f h j 窗约束的车辆路径问题数学模型的构建和初始可行车辆配送路线 的求解。在实现对客户点配送区域划分的基础e ，使用一种改进的p f i h 算法求 解配送区域内车辆初始可行路径，得到备选的车辆路径方案集合。 ( 3 ) 路线改进和路线优化。为提高生成的车辆路径的效率和质量，在所得到 的备选车辆路径集合中，基于v o r o n o i 多边形邻域相似信息的性质，使用变邻域 搜索算法的操作对备选方案进行路径改进与路线优化，得到较优解。 ( 4 ) 烟草物流配送原型系统的实现。基于本文提出的车辆路径生成策略，设 计并实现了一个烟草物流配送车辆路径生成原型系统。 实验结果表明，本文的车辆路径生成策略既能获取较优的车辆配送路线，同 时也具有较好的实时性，能满足实际应用需求。 关键词：聚类分析，混合启发式算法，变邻域搜索，v o r o n o i 邻域相似信息 江苏大学硕士学位论文 a bs t r a c t l o g i s t i c sd i s t r i b u t i o ni sa no p e r a t i o nl i n k i n gw i t hc o n s u m e rd i r e c t l y , a n dt a k e s a c c o u n tf o rc o n s i d e r a b l ep r o p o r t i o ni nv a r i a b l ec o s t si nl o g i s t i c s ，a n dt h ep l a n n i n go f v e h i c l er o u t i n gi nd i s t r i b u t i n gw i l lb et a k eg r e a te f f e c t si nc o s ti nl o g i s t i c s d i s t r i b u t i o n as c i e n t i f i ca n dr e a s o n a b l es o l u t i o nt ot h ev e h i c l ep a t hp l a n n i n gp r o b l e m i sa ni m p o r t a n ta c t i v i t yi nt h el o g i s t i c sd i s t r i b u t i o n t h i sr e s e a r c hi sa b o u tv r p ( v e h i c l er o u t i n gp r o b l e m ) i nt h em o d e ml o g i s t i c s d i s t r i b u t i o np r o c e d u r e r e a ll o g i s t i c sd i s t r i b u t i o ni sc h a r a c t e r i z e db ym u l t id i s t r i b u t i o n c e n t e r , l a r g es c a l e ，m a n yr e s t r i c t i o n sa n da d v a n c e dc o m p l e x i t y a n dt h es t r a t e g yo f v e h i c l er o u t i n gg e n e r a t i o nb a s e do nt h es t r a t e g yo f “c l u s t e rf i r s t r o u t es e c o n d i sp u t f o r w a r d f i r s t l y 1 a r g e s c a l ev r p i ss i m p l i f i e di n t os m a l l s c a l ev r p b yu s i n gk m e a n s c l u s t e ra n a l y s i st od i v i d et h ed i s t r i b u t i o ni no r d e rt or e d u c ec o m p u t a t i o nw h i l ei m p r o v e t h ec o m p u t i n gs p e e d ；a n dt h e ni n t r o d u c eah y b r i dh e u r i s t i ca l g o r i t h mw h i c hc o m b i n e s t h ei m p r o v e dp u s hf o r w a r di n s e r t i o nh e u r i s t i ca l g o r i t h ma n dt h ev a r i a b l en e i g h b o r s e a r c ha l g o r i t h mi no r d e rt os o l v et h ev e h i c l er o u t i n go p t i m i z a t i o np r o b l e m si n d e l i v e r yr e g i o n b a s e do nt h ea b o v es t r a t e g y t h em a i nw o r ko ft h i sp a p e ri sa sf o i l o w s ： ( 1 ) m e t h o df o rd i s t r i b u t i o na r e ad i v i s i o na n dc u s t o m e rc l u s t e r i n g t h ep r i n c i p l eo f d i s t r i b u t i o na r e ad i v i s i o na n dc u s t o m e rc l a s s i f i c a t i o ni sf i r s tp r e s e n t e d t h e nw eu s e t h ei m p r o v e dk - m e a n sc l u s t e r i n ga l g o r i t h mt oa u t o m a t i cd i v i d et h ed e l i v e r yr e g i o ni n o r d e rt or e d u c et h ec o m p l e x i t yo fs o l v i n gp r o b l e m s ( 2 ) t h ev r p t wm a t h e m a t i c a lm o d e lc o n s t r u c t i o na n df e a s i b l ev e h i c l er o u t i n g s o l u t i o n i no r d e rt os o l v et h ev e h i c l er o u t i n go p t i m i z a t i o np r o b l e m si nd e l i v e r y r e g i o n ai m p r o v e dp u s hf o r w a r di n s e r t i o nh e u r i s t i ca l g o r i t h mw a su s e di no r d e rt o g e n e r a t ei n i t i a lf e a s i b l ev e h i c l er o u t i n gp r o b l e m si nd e l i v e r yr e g i o n t h e nas e to f f e a s i b l er o u t i n gs c h e m e si sa c h i e v e d ( 3 ) v e h i c l er o u t i n gi m p r o v e m e n ta n do p t i m i z a t i o n i no r d e rt oi m p r o v et h ev e h i c l e r o u t i n gs o l u t i o na n di m p r o v et h ec o m p u t i n ge f f i c i e n c ya n dq u a l i t yo fg e n e r a t e di n i t i a l v e h i c l er o u t i n g ，a l g o r i t h mu s e st h ev o r o n o ip o l y g o na d j a c e n c yi n f o r m a t i o nt od e f i n e t h eo p e r a t i o no fv a r i a b l en e i g h b o r h o o ds e a r c hi no r d e rt oi m p r o v ea n do p t i m i z et h e i n i t i a lf e a s i b l ev e h i c l er o u t i n g ( 4 ) t h ei m p l e m e n t a t i o no ft h et o b a c c od i s t r i b u t i o np r o t o t y p es y s t e m b a s e do nt h e p r o p o s e d v e h i c l er o u t i n gg e n e r a t i o ns t r a t e g y , av e h i c l er o u t i n gg e n e r a t i o nt o b a c c o p r o t o t y p es y s t e mw a sd e s i g n e da n dr e a l i z e d t h i sv e h i c l er o u t i n gg e n e r a t i o ns t r a t e g yc a na c h i e v eab e t t e rs o l u t i o nt ov e h i c l e r o u t eo p t i m i z a t i o np r o b l e m st h r o u g ht h ee x p e r i m e n tr e s u l t sa n dt h ea n a l y s i sa n d v e r if i c a t i o no ft h ea p p l i c a t i o ns y s t e m a tt h es a m et i m e i ta l s oh a sb e t t e rr e a l - t i m e w h i c hc a nm e e tt h en e e d so fp r a c t i c a la p p l i c a t i o n k e y w o r d s ：c l u s t e ra n a l y s i s ；ah y b r i dh e u r i s t i ca l g o r i t h m ；v n s ；v o r o n o ia d j a c e n c y i n f o r m a t i o n i l 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文 的规定，同意学校保留并向国家有关部门或机构送交论文的 复印件和电子版，允许论文被查阅和借阅。本人授权江苏大 学可以将本学位论文的全部内容或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存和汇 编本学位论文。 保密口，在年解密后适用本授权书。 本学位论文属于 不保密口。 独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指 导下，独立进行研究工作所取得的成果。除文中已注明引用 的内容以外，本论文不包含任何其他个人或集体己经发表或 撰写过的作品成果。对本文的研究做出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的 法律结果由本人承担。 学位论文作者签名：劲誊珲 日期：埘，o 年6 月i e t 江苏大学硕士学位论文 1 1 课题背景 第一章绪论 随着经济全球化趋势的加强，科学技术尤其是信息技术的突飞猛进的发展， 产品营销范f j jf 1 益扩大，社会! e 产、物资流通、商品交易及其管理方式j 下在发生 着深刻的变革，与此相适应，被普遍认为企业在降低物资消耗、提高劳动生产率 以外的“第三利润源”的现代物流在全世界范围内广泛兴起l 。在我国工业领域 中，由于长期受计划经济的影响，采购、制造、运输、仓储、代理、配送、销售 等环节彼此分割，造成一方面生产企业的原材料和产成品库存过大，占压资金过 多，产品生产成本上升；另一方面运输、仓储等企业有效货源不足，现有设施能 力未能充分利用，并且运输环节不衔接造成成本上升。近十年来，随着市场经济 的发展和物流产业的必起，我罔不少企业已经开始改变上述状况。比如青岛海尔 集团通过物流改革和突破取得了初步的成功。物流现在被称为在物资资源领域和 人力资源领域之外发生在流通领域的第三利润源。物流的作用主要体现在： ( 1 ) 物流在企业战略中，对企业经营活动的成本和利润发生重大影响。物流 是企业成本的重要的产生点。冈此，必须通过物流合理化、现代化等一系列活动 降低成本，支持保障营销和采购等活动。所以，物流被称为“降低成本的宝库”。 成本和利润足相关的，成本的降低意味管利润空间的扩大。物流作为主体可以为 企业提供大量直接和间接的利润，是企业形成经营利润的主要活动。 ( 2 ) 物流活动最大的作用，并不仅仅在于企业减少了费用，降低了成本或增 加了利润，更重要的是在于提高了企业对用户的服务水平，进而提高了企业的竞 争能力。 可见，丌发物流对于我国企业在压缩资金占用率和加快资金周转具有重大的 现实意义。物流配送1 2 j 就是在产品用户集中的区域，按用户的订货要求和时间计 划，在配送中心配货，并将配好的货物采用车辆巡回运送的方式送交收货人。从 运输成本看，我们还有很大的空问可以去努力。只要我们能够将现有运输成本降 低1 0 左右，我们的国民经济总体水平就能出现一次新的飞跃，一次真正的飞跃。 因此，大力推进现代物流产业，把彼此分割的环节连接起来，优化企业物资供应 江苏大学硕士学位论文 链，是国民经济发展的迫切需要，图卜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 r p 的理论研究，主要集中在一些简单的小规模问题。而在实 际生活中，问题规模往往比较大，如与日常生活息息相关的诸多城市配送车辆路 径优化问题：烟草行业、食盐等国家专卖品、快速生活消费品、家用电气、易腐 坏食品( 乳制品、肉类) 、冷冻食品等。其规模通常包含上千个客户，现有方法和 理论难以有效解决实际问题。车辆路径问题在规模增加的同时，客户对服务时间 的满意度也成为了企业关注的问题。在大规模车辆问题中加入时间窗的限制，便 成为带时间窗车辆路径问题( v r pw i t ht i m ew i n d o w s ，v r p t w ) 。带时间窗车辆路 径问题( v r p t w ) 是在v r p 上加上了客户的被访问的时问窗约束。近年来，先进 的信息技术和经济全球化促使物流业迅猛发展，物流企业的运输设备规模日益扩 大，运输网络也更广泛更复杂，带时间窗的大规模v r p 已成为物流企业迫切要解 决的问题，对该问题的研究可以有效提升企业的物流环节效率以及社会总体物流 水平。因此，对v r p t w 问题的研究具有极其重要的理论和现实意义。 2 江苏大学硕士学位论文 1 2 问题提出 车辆路径问题1 3 l ( v r p ) 最y - 是山d a n t z i g 和r a m s e r 于1 9 5 9 年首次提出，一 直足运筹学与组合优化领域研究的热点和难点问题，该问题作为网络优化的基本 问题之一而一直倍受学者的关注。v r p 可定义为：对于一系列客户点，组织适当 的行车路线，使车辆有序地通过它们，在满足一定的约束条件( 如货物需求量、 发货量、交发货时f l j 、车辆容量限制、行驶里程限制、时问窗限制等) 下，达到 一定的目标( 如路程鼓短、费用最少、时间尽黾少、使用车辆数尽量少等) 1 4 j 。 车辆路径l 、u j 题中具体代表性的几类问题f 5 l ：( 1 ) 带容最约束的车辆路径问题 ( c a p a c i t a t e dv r p ，c v r p ) ；( 2 ) 多供货点车辆路径问题( m u t i p l ed e p o tv r p ， m d v r p ) ；( 3 ) 周期规划车辆路径问题( p e r i o d i cv r p ，p v r p ) ；( 4 ) 分批交货 的车辆路径f u j 题( s t o c h a s t i cv r p ，s v r p ) ；( 6 ) 乜i 程时集货的车辆路径问题( v r p w i t hb a c k h a u l s ，v r p b ) ；( 7 ) 集货供货一一体化车辆路径问题( v r p w i t hp i c k u p a n d d e l i v e r i n g ，v r p p d ) ；( 8 ) 带卫星通讯设备的车辆路径问题( v r pw i t hs a t e l l i t e f a c i l i t i e s ，v r p s f ) ；( 9 ) 带时间窗的车辆路径问题( v r pw i t ht i m ew i n d o w s ， v r p t w ) 。带时问窗约束的车辆路径问题( v r p t w ) 是现实世界最普遍的一类 v r p ，其研究成果最为广泛，也是其他车辆路径问题的基础。 一般而占，在理论上，车辆路径优化的目标是在满足各类约束条件的前提下， 在客户可以接受的演算时间内，给出尽可能优化的路线规划方案。所谓“尽可能 优化的路线规划方案”一般而言，指的足最大限度地降低客户的运营成本( 运营 时f h j ，距离或其他费用) 。算法考虑的约束条件一般会有：车辆的运力情况( 体 积、载重、车辆类型) 、时间窗约束( 客户的收货时问、服务时间、配送点的工 作时问等) 、取、送货点的约束、订单优先级的区别、其他各类客户定义的约束。 在处理实际问题时，优化还必须兼顾路线规划方案的实际可操作性，比如考虑到 各个驾驶员对城市不同区域道路的熟悉程度，所以在路线优化时加入配送区域的 限制。 首先根据客户要求的送货时间、地区位置、车辆型号、配送中心位置、交通 路线和各时间段的交通状况等因素，进行配送车辆分配和配送路径的规划。配送 路径是否合理对配送速度、成本、效益影响很大，因此采用合理的配送策略生成 合理的配送路径是一项非常重要的工作。因此，车辆路径问题( v r p ) 中，单纯 江苏大学硕士学位论文 研究v r p 问题是毫无意义的，很大一部分是指对v r p 及其衍生问题的研列6 。 随着社会经济的不断发展，客户对配送时间提出明确的要求，一般都规定了 一个希望被访问的时问窗。从现实约束来看，时间窗是一类非常重要的约束，因 为配送时间直接影响到对客户的服务水平。带时间窗的车辆路径优化问题，简称 为v r p t w ( v e h i c l e r o u t i n gp r o b l e m sw i t ht i m ew i n d o w s ) 是对v r p 问题的扩展。 v r p t w 是一个非常困难的组合优化问题。此外，问题的大小施加了更多的复杂 问题。为了在合理的时间内应付这个问题的复杂性并提供完整的解决方案，许多 研究人员已经作出了许多深入的研究。近年来，v r p t w 问题的研究比较多，但 也有一定的局限性。从实际角度出发，随着企业规模的扩大和市场经济以及协同 合作的发展，车辆往往来源于不同的配送中心，因此仅仅研究单一配送中心的 v r p 问题就不再适用了。所以，带有时间窗的多配送中心v r p 问题是有待深入 研究的问题，同时也具有十分重要的现实意义。 1 3 国内外研究现状分析 1 3 1 国外研究现状 车辆路径问题随着问题规模的增大，问题求解的状态空| 、日j 急剧膨胀，现己被 证实是n p - h a r d 问题1 7 1 。在过去的几十年中，众多学者在求解算法方面已经取得 了丰富的研究成果【8 】。国外相关领域研究者对车辆路径问题的研究始于5 0 年代 末，在理论研究和实际应用两方面都已取得了非常显著的成果。当时的车辆路径 问题主要集中在静态的车辆调度问题上，描述的是运筹学中的优化问题。随着研 究的深入发展，如何使研究的理论模型更贴近现实中的运输规划问题开始成为研 究者们关注的焦点。b o d i n 等人【9 j 对一般的车辆路线规划问题做了详尽的综述， s o l o m o n 和d e s r o s i e r s 等人1 1 0 i 考虑将时间约束加入到一般的车辆路径问题中，最 早对带时间窗约束的车辆路径问题进行了研究，d e s r o c h e r s 等人l i l j 进一步对用于 求解带时间窗的车辆路径问题的各种优化方法做了简明的概括。由于时间因素在 实际运输规划问题中是很常见，很重要的因素之一，9 0 年代以后带时间窗的车辆 路径问题引起了运筹学、人工智能领域学者的关注。 同简单的车辆路径问题一样，带时间窗的车辆路径问题( v r p t w ) 的求解 也主要是基于精确算法和启发式方法两大类方法。k o l e n 、d e s r o c h e r s 、f i s h e r 、 4 江苏大学硕士学位论文 k o h l 等人l l2 i 将各种精确算法如分支定界法等应用于v r p t w 的求解中，成功的解决 了理论和现实中的一些规模较小的v r p t w 。采用精确算法虽然可以得到最优解， 但是需要消耗大量计算量和计算时间，不适用于现实中大规模的车辆路径问题， 过去的研究结果也证明了这一点。近几年来，国外研究者都致力于设计新的高效 省时的启发式方法来构建或改进v r p t w 问题的解。禁忌搜索法、模拟退火及遗传 算法等启发式方法陆续被引入到v r p t w 的求解中，取得了显著的效果。 1 3 2 国内研究现状 我国对车辆路径问题的研究是在2 0 世纪9 0 年代以后才逐渐兴起，比国外滞 后3 0 余年。目前，幽内对于复杂的车辆路径问题的研究仍处于起步状态，一些 专家和学者也丌始尝试对v r p f w 问题进行研究。1 9 9 8 年，李大卫1 1 3 j 等人对适用于 旅行商| 、u j 题( 7 f s p ) 的最近距离搜索启发式算法进行修j 下，构造出评价函数，并 据此提出一种求解v r i y r w 的启发式算法。2 0 0 0 年，谢秉磊1 1 4 j 等人将货运量约束和 时l 、b j 窗约束转化为目标约束，设计了基于自然数编码的可同时处理软、硬时间窗 约束的遗传算法( g a ) ，实验分析获得了较好的结果。2 0 0 1 年，周贤伟等人i 巧j 根 据车辆装载g p s 设备的特性，建立了v r p t w 的数学模型，设计了相应的g a 。2 0 0 3 年，宋厚冰和繁远利i l6 j 针对v r p t w ，在标准g a 的基础上，将分组信息与每一个染 色体结合，并辅以交换局部搜索技术，构造了一种改进遗传算法( g a ) ，使得求 解结果更接近最优解。丁建立等人l i 7 j 融合了遗传算法与蚁群算法，采用遗传算法 生成信息素分布，利用蚁群算法求精确解，对旅行商问题进行了仿真，取得了非 常好的效果，但存在如计算时问长，容易陷入局部最优等问题。刘小兰【l8 j 等人为 了克服原有大规模邻域搜索算法不能有效求解时间窗较宽v r p 的缺陷，介绍了 v r p t w 的通用数学模型，并通过分析各主要变量之间的关系，构造了一种简单、快 速的确定性初始算法，同时引入“短路径优先策略”构造了改进的大规模邻域搜 索算法，该策略也可嵌入到求解时间窗比较窄的v r p 中，达到加速搜索的目的。 吴憬莉、李陶深【1 9 】等探讨了如何将基于遗传算法和禁忌搜索算法的混合策略。张 涛等用禁忌搜索算法和遗传算法的混合策略求解v r p 问题。李宁等提出了倒时间 窗的粒子群算法，方霞等人利用免疫遗传算法的全局搜索能力和收敛性，用新型 的启发式算法解决v r p 问题【2 0 1 。王素云等【2 1 1 研究了两阶段启发式算法在带时间窗 的车辆路径问题中的应用，论文对带时间窗约束的物流配送中的车辆路径问题， 江苏大学硕士学位论文 构造了一种两阶段启发式算法，第一阶段采用k - m e a n s 算法将客户聚类分群，第 二阶段对每一客户子类采用禁忌搜索算法优化车辆路径，该方法降低了算法的复 杂性。但是当客户点地理位置较分散时，如何将客户点的其他约束信息，如时间 窗等应用到聚类中来，提前处理某些约束，还需进一步探讨。目前，国内对于复 杂的车辆路径优化问题的研究仍处于起步状态，通过对中国期刊网数据库检索， 1 9 9 7 - 2 0 0 7 年这8 年间，在中国期刊网上发表的有关该领域的论文2 2 5 篇【2 列。就 收集的资料看，我国在这个方面的研究具有以下特点1 2 习：( 1 ) 所研究的问题类型 都是确定性问题；( 2 ) 对该领域的专有名称没有统一的提法( 如对v r p 的提法有 车辆问题、车辆路线问题、车辆路线安排问题、路山问题、车辆调度问题、多重 运输调度问题) ；( 3 ) 该领域的研究者群体小，仅有两南交通大学、清华大学、 浙江大学、北京交通大学、东北大学、南京航空航天大学等少数高校的科研工作 者从事这方面的研究工作。因此，在这方面研究的深度和广度来说，还不能适应 我国配送业及物流业迅速发展的需要。 1 4 本文的研究内容与篇章结构 1 4 1 本文的研究内容 本文首先对车辆路径问题中所涉及的实际物流配送路径优化中的不同约束 条件进行分析和总结，确定本文的研究对象为带时问窗的车辆路径问题( v r p t w ) ， 即在不违背车辆容量限制、满足客户时f h j 窗口等约束条件下，合理规划配送的车 辆路径安排，以尽可能小的成本满足客户对货物和配送服务时问区问的要求；然 后从解决方法的角度对求解车辆路径问题的各种算法进行分类和总结，从而奠定 了本文算法的基础；接着根据实际配送要求提出了本文的研究问题一带时问窗 的大规模车辆路径问题。建立以车辆容量和客户时问窗要求为约束条件，以配送 运输成本为目标函数的v r p t w 数学模型。针对由多个配送中心和多个客户点组成 的物流网络中的车辆路径问题，提出了一种基于“集群第一，路线第二”的路径 优化策略，即首先使用聚类分析对客户进行配送区域的划分，该配送区域可作为 规划中的集群处理，能够减小问题的规模，提供更明确的实施方向和更强的可操 作性。然后引入综合改进p f i h 算法和变邻域搜索算法( v n s ) 的混合启发式算法 求解配送区域内车辆路径问题，实现配送区域内的路线规划，可提供更详细的路 6 江苏大学硕士学位论文 线规划方案。最后通过应用系统的实现表明该混合算法既能获取质量较优解，同 时也具有较好的实时性，能较好地满足实际应用需求。 本论文的具体研究内容如图卜2 所示( 实线表示基础理论部分，虚线表示本 文研究部分) 。主要包括：客户的聚类分析对客户物流配送区域的自动划分、配 送区域内带时i 日j 窗的大规模车辆路径问题、路线排序和路线优化、烟草物流配送 原型系统的实现。 图卜2 论文研冗图解模型 ( 1 ) 物流配送区域及客户的聚类分析 分析物流配送区域聚类的影响因素。以缩减解空间为目标，根据主要影响因 素，对配送区域及客户进行初步划分，并使用改进的k - m e a n s 算法对客户点集进 行集群划分，即配送区域的自动划分。 ( 2 ) 求解v r p t w 配送区域内带时间窗的大规模车辆路径问题 在客户聚类及配送区域自动划分基础上，建立了带时间窗车辆路径问题数学 模型，提出一种混合启发式算法求解配送区域内车辆路径问题，提高车辆路径方 案生成的效率和质量，得到备选的车辆路径方案集合。在备选车辆路径方案集合 的基础上，利用v o r o n o i 多边形邻域相似信息性质建立车辆路径改进与优化方案。 ( 3 ) 烟草物流配送原型系统的实现 设计并实现了烟草物流配送原型系统实现客户的配送区域自动划分、车辆优 7 江苏大学硕士学位论文 化路线显示、车辆配送详细信息、车辆服务时间窗显示等几个模块。该原型系统 的一个突出优点就是将划分的结果直接显示在电子地图上，供用户评价和改进。 1 4 2 本文的篇章结构 本论文共分为六章，各章内容具体安排如下： 第一章；绪论部分。主要概述了本课题的研究背景、车辆路径优化问题和带 时i h j 窗的车辆路径问题在国内外的研究现状、论文的主要研究内容及其论文研究 的图解模型。 第二章：路径优化技术综述。首先介绍车辆路径问题( v r p ) 的描述、路径 特性等方面的内容，并在此基础上阐述带时问窗路径问题( v r p t w ) 的数学模型， 为任务分配和路径排序与优化提供一个理论的支持。最后介绍v o r o n o i 多边形的 定义、生成算法及其相关性质的研究与对实际问题的划分。 第三章：基于聚类的配送区域的划分。本章首先介绍聚类定义、主要聚类算 法及其优缺点及其本文所采用的基于“集群第一，路线第二”策略的配送区域划 分的原因。然后根据本文所研究的特定问题，选取传统k - m e a n s 算法进行配送区 域的划分，但就传统k m e a n s 算法所存在的对初始聚类中心的依赖性问题对传统 的k - m e a n s 算法进行改进。改进的算法采用加强集群中心( c c i a ) 算法和基于密 度的快速压缩算法( m e r g e d b m s d c ) 。 第四章：求解v r p t w 的混合启发式算法。在配送区域划分的基础上，实现在 配送区域内对配送路线进行排序与优化，主要分为三个步骤：建立距离矩阵，构 建初始解( 路线) 、对初始可行路线进行路线排序和路线优化。建立距离矩阵为 构建初始可行解，路线排序和路线改进提供最基本的信息；生成初始路径是在不 违反容量等基本约束的条件下，能迅速产生一个初始可行的车辆配送路径。路线 排序和优化是在保持初始解可行的前提下，改进第一个阶段生产的初始解，本文 定义变邻域搜索算法三种操作：单节点插入、单节点移除插入、链式移除插入 对初始可行解进行改进。 第五章：烟草物流配送原型系统的研究和实现。 第六章：对本文的研究工作进行总结，并提出进一步研究方向。 8 江苏大学硕士学位论文 第二章路径优化技术综述 本章主要阐述路径优化技术研究用到的基础理论，首先选取物流配送模型中 两个典型问题：选址问题和车辆路径问题；然后介绍带时间窗车辆路径问题 ( v r p t w ) 概念、约束条件和数学模型；最后介绍v o r o n o i 多边形的概念、d e l a u a y 三角网的生成、v o r o n o i 多边形邻域相似信息的性质及其在路线排序和路线优化中 的应用及其实例分析。 2 1 物流配送模型中的选址问题 选址决策【2 4 j 是实现物流系统高效运营的最重要、最困难的决策，属于长期的 战略决策。选址分配问题可描述为如何为m 个设施( 配送中心) 选址，并将n 个 顾客( 客户点) 分配给设施( 配送中心) ，以使系统总成本最小( 系统的配送效 率最高) 。所有的商业零售都面临选择地址的问题，特别是对客户数量多、密度 大的大规模车辆路径问题，选址的好坏对提高配送效率起了很重要的作用。从选 址的不同角度可分为单级设施选址与多级设施选址问题。所谓单级或者一级设施 选址问题，也就是产品只经过一层的设施( 一般指配送中心) 就流动到了客户点， 这种情况在实际的大多数企业来说是最为常见的情况。但是也有时会涉及到所谓 的多级设施选址问题，特别是对一些跨国公司和一些国内外市场区域很大的企 业。实际问题中用得到的是两层设施选址，比如第一层为中心仓库，第二层为中 转仓库等。在本文所研究的物流配送系统中，针对物流配送客户点数量多、分布 密度大等特点，特将该问题划分为二层设施选址。对二级配送中心的选址，必须 有一个整体规划，也就是要从空问和时间上对配送中心的新建、改建和扩建进行 全面系统的规划。规划的合理与否，对节省投资和运营费用等都会产生深远的影 响。较好的配送中心选址方案是使商品通过配送中的汇集、中转、分发，直至输 送到客户网点的全过程的效益最好。通常配送中心拥有众多建筑物、构筑物以及 固定机械设备，如果选址不当，将产生极大的负面影响并付出长远的代价。因此， 在配送中心选址规划中，对配送中心的选址原则、影响因素等进行综合分析、提 出慎密的决策建议是非常必要的。选址，是关键的一步。 1 配送中心选址方法 9 江苏大学硕士学位论文 配送中心的选址应综合运用定性和定量分析相结合的方法，在全面考虑选址 影响因素的基础上，粗选出若干个可选的地点，进一步借助比较法、专家评价法、 模糊综合评价等数学方法量化比较，最终得出较优的方案。 选址可分为单一配送中心的选址和多个配送中心有机配合使用时多地址选择 两种类型。二者在方法上略有不同。而在制定基本计划时，若尚未确定配送中心 是采用单一设施还是配置多个设施时，可以用单一选址方法和多址选址方法对其 分别计算，进行全部费用比较，选取最优方案。 2 配送中心选址的程序和步骤 在进行中心选址时，其选址流程通常可以按照图2 一l 所示进行【2 川。下面就具 体的选址步骤进行简单的浼明： 图2 - 1 选址流程图 ( 1 ) 选址约束条件分析 选之前要明确建立配送中心的必要性、目的和意义，然后根据物流系统 的现状进行分析，制定物流系统的基本计划，明确所需要了解的基本条件， 以便缩小选址的范围。 l o 江苏大学硕士学位论文 ( 2 ) 收集整理资料 选址地址的方法，一般是通过成本计算，也就是将运输费用、配送费用 及物流设旋费用模犁化，采用约束条件及目标函数建立数学公式，从中寻找 费用最小的方案。但是，采用这种选址方法，寻找最优的选址解时，必须对 产量和生产成本进行正确分析和判断。 ( 3 ) 地址筛选 在对所取得的相关资料进行充分的整理和分析、考虑各种因素可能的影 响并对需求进行预测，然后就可以初步确定选址范围，即确定初始选址点。 ( 4 ) 定量分析 针对不同情况选用不同的模型，进行计算，得出结果。如果是对单一配 送中心进行选址，可采用重心法等，如果对多个配送中心选址时，就可采用 奎汉、哈姆勃兹、鲍摩一瓦尔夫模型、c e l p 法等。 ( 5 ) 结果评价 结合市场的适应性、购置土地条件服务质量等，对计算所得结果进行评 价是看其是否具有现实意义及可行性。 ( 6 ) 复查 分析其他影响因素对计算结果的相对影响程度，分别赋予它们一定的权 重，采用加权法对计算结果进行复查。如果复查通过，则原计算结果即为最 终结果；如果复查发现原计算不适用，则返回第三步继续计算，直至得到最 终结果为止。 ( 7 ) 确定选址结果 在加权法复查通过后，则计算所得的结果即可作为最终的计算结果，但 是得到的解不一定为最优解，可能只是符合条件的满意解。由于选址分派问 题在物流系统规划中占据着相当重要的地位，国内外学者进行了大量的进一 步的建模研究。从研究方法来看，选址分派问题主要采用非线性规划方法、 混合整数规划模型、模糊机会约束规划模型和区l 日j 问规划模型等。从模型解 法来看，主要采用精确法、分解方法和启发式算法。 江苏大学硕士学位论文 2 2 车辆路径问题 车辆路径问题( v r p ) 是从旅行商问题( t s p ) 演化而来，旅行商l 、u j 题是车辆 路径问题的一个特例，它只包括一条路径问题，且没有能力约束。而有时问窗车 辆路径问题时在经典车辆路径问题基础上根据学术研究和实际应用延伸和变化 的一种型态，v r p 问题和v r p t w 问题是一脉相承的、相互联系的。 2 2 1 车辆路径问题的描述 物流配送活动中的配送运输路线规划问题1 26 。，是二十多年以来车辆路径问题 的重点研究对象和应用领域。在配送运输中，由于配送用户多，城市交通路线又 较复杂，如何组成最佳路线、如何使配装和配送路线有效搭配等，是物流配送运 输的特点，也是难度较大的工作。于是采用科学的、合理的方法来确定配送路线， 成为提高物流配送车辆效益、实现物流配送科学化的重要途径。凶此，目前许多 v r p 问题的研究工作都足以物流配送活动为背景描述的。 车辆路径问题一般定义为：对一系列客户，组织适当的行车路线，使车辆有 序地通过它们，在满足一定的约束条件( 如货物需求量、发货量、交货时| u j 、车 辆容量限制、行驶罩程限制、时间限制等) 下，在客户可以接受的演算时问内， 给出尽可能优化的路线规划方案，最大限度的降低客户的运营成本( 运营时问， 距离或其他费用) 。车辆路径问题的描述如图2 2 所示。 图2 - 2v r p 示意图 一般而言，车辆路径问题需要从以下几个方面描述： 1 2 江苏大学硕士学位论文 ( 1 ) 道路网 用来运输物资的道路网通常用一个图来表示，其中，图中的弧用来表示路段， 而点则对应道路交叉点、配送中心和客户。根据其道路是单行线还是双行线，图 中相对应的弧段可分为有向弧和无向弧。每条弧段对应着一个运行费用，通常表 示其距离，或运行时间( 可能与车辆类型和何时通过该路段有关) 。 ( 2 ) 客户 用图上的点表示。客户所需运送或收取的货物，可能有不同的种类。一般要 求提供服务的时l 、h j 段( 时问窗) ，例如由于客户只在特定的时间段内营业，或者因 为交通管制只能在特定的时间段内前往，o 需要估计在客户点交付或提取货物所花 费的时l 、h j ( 分别为卸货或装货时间) 。有时，每个客户的需求不可能全部得到满足。 在这种情况下，运送或收取的货物量可以减少，或者一部分客户得不到服务。为 了处理这类情形，可以根据其客户是部分还是全部得不到服务，引入相应的优先 权或惩罚。 ( 3 ) 配送中心 服务各客户的车辆行驶路径丌始并终止于一个或多个配送中心，也用道路图 中的点来表示。每个配送中心的特征由所配备的车辆种类和数量及所能处理的货 物总量来表示。在某些实际应用中，先按照配送中心划分需配送的客户集合，于 是在每次完成货物的取送任务后，车辆必须返回配送中心。在这种情况下，整个 v r p 就町以分解为几个独立的v r p ，每个问题都对应于一个不同的配送中心。 ( 4 ) 车辆 货物的运输由一组车辆来完成，其典型的特性为：车辆的配送中心，完成任 务后是否要求返回配送中心：车辆的容量，通常以最大的载重量、容积来表示：可 用于进行货物装卸的设备：使用车辆的费用( 单位距离、单位时间、每辆车或每 条路线等) 。 ( 5 ) 驾驶员 给配送车辆驾驶员安排取送货任务时，必须符合工作合同和公司规章制度的 有关规定( 如每天的工作时间、工作期间的短暂休息次数和时间、最大的连续驾 驶时间、加班时间等) 。有关驾驶员的这些限制条件一般都嵌入到相应的车辆限 制条件中。 江苏大学硕士学位论文 ( 6 ) 路径排序中的限制条件 给配送车辆编排行驶路径时，应满足几个取决于所运送的货物性质、服务质 量水平、以及客户和车辆的特点的运营限制条件。比如，每条路线上，相应车辆 的当前装载量不能超过车辆的载重量：只能在客户所要求的时问窗以及相应车辆 驾驶员的工作时间内给客户提供服务等。 ( 7 ) 行驶费用和行驶时问 为了评价一组配送路线的总费用和检查其相应的运营限制，必须知道客户与 客户之间，配送中心与客户之间的行驶费用和行驶时间。为此，原始道路图( 通 常是很稀疏的) 一般被转变为一个完备图，其中的点还足原来道路图中的点，对 应于客户和配送中心。对于完备图中的每一点对，和了，定义一条弧( f ) ，其费 用q 等于原来道路图中从客户点到i 点到j 的距离，而行驶时问，则为原来道路图 中从点f 到点，的最短路径上各条弧的行驶时问之和。在以后的讨论中，大多考虑 其相应的完备图，而不是原始道路图本身，该完备图可