（企业管理专业论文）基于Trans+CAD的物流设施选址与配送路线优化研究.pdf

摘要 如何实现资源节约型物流，是当前物流业发展的热点话题。通过对配送方案的规划， 实现合理选址、优化路径，是降低物流成本的有效途径。随着物流环境的复杂化，物流 区域的扩大化，设施定位问题和运输车辆路线安排问题之间的相互影响也越来越大。现 今许多实际问题，需要综合考虑上述两种问题，这就形成了定位路线问题( l r p ) 。 传统的解决l r p 的方法是建立数学模型，然后再利用相应的算法通过计算机编程 计算出结果。传统方法解决的是基于放射状的虚拟路网的l r p ，输出结果仅为数据形式， 无法让决策者直观地看出解决方案，并且无法进行数据库管理，所以这种方法的推广有 极大的局限性。 t r a n sc a d 软件系统具有高级数据库管理功能以及用来操作地理信息数据的便于 用户使用的地图界面，能更高效地处理物流设施选址与配送路线的优化问题。t r a n sc a d 具有很强的空间分析能力，可以更有效地分析具有空间特征物流系统，特别适宜于对物 流系统信息的分析处理，是推进物流系统管理现代化的重要工具之一。 本文主要根据物流设施选址与配送路线的特点并结合t r a n sc a d 物流模块，构建适 合t r a n sc a d 软件进行网络分析的l r p 数据结构，探讨基于t r a n sc a d 的车辆路线调 整技术，旨在说明新的信息技术能更高效、直观地对物流系统进行规划。 本文针对基于t r a n sc a d 软件系统的物流设施选址与配送路线的优化进行了深入、 具体的研究，得出如下研究成果： ( 1 ) 构建了基于t r a n sc a d 软件系统的物流系统l r p 基础数据系统。 ( 2 ) 在t r a n sc a d 中创建了l r p 地理图层。 ( 3 ) 创建了l r p 网络，并利用t r a n sc a d 系统工具输出了多路径的最短路径矩阵 和车辆路线矩阵。 ( 4 ) 运用t r a n sc a d 软件系统的物流模块分别解决了设施定位问题和车辆路线安 排问题，并分别以数据窗和路线系统的形式输出了设施定位和车辆路线的解决方案。 ( 5 ) 解决了多设施、多车辆的基于现实路网的l r p 问题。 ( 6 ) 对设施定位和车辆路线问题的解决方案进行分析，运用车辆路线编辑工具对 配送路线进行了调整，得出基于t r a n sc a d 的物流设施选址与配送路线问题解决方案。 关键词：定位路线问题、设施选址问题、车辆路线问题、 r r a n sc a d a b s t r a c t t h eh o tt o p i ci nt h e d e v e l o p m e n to ft h e c u r r e n tl o g i s t i c si n d u s t r yi sh o wt or e a l i z et h e r e s o u r c e - s a v i n gl o g i s t i c s t h ee f f e c t i v ew a yt or e d u c el o g i s t i c sc o s t si st or e a l i z et h er e a s o n a b l el o c a t i o n a n dt h eo p t i m a lr o u t e st h r o u g ht h ep l a n n i n gs c h e m eo fd i s t r i b u t i o n 、i t ht h ec o m p l i c a t e dl o g i s t i c s e n v i r o n m e n ta n de n l a r g e m e n to fl o g i s t i c sa r e a , t h ei n t e r a c t i o nb e t w e e nl o c a t i o na l l o c a t i o np r o b l e m sa n d v e h i c l er o u t i n gp r o b l e m sg r o wl a r g e r n o w a d a y sm a n yp r a c t i c a lp r o b l e m st a k eb o t hp r o b l e m si n t oa c c o u n l i th a sf o r m e dl o c a t i o nr o u t i n gp r o b l e m s ( l r p ) t h et r a d i t i o n a lm e t h o do fs o l v i n gl r pi st oe s t a b l i s ht h em a t h e m a t i c a lm o d e l ，a n dc a l c u l a t er e s u l t s t h r o u g ht h ec o r r e s p o n d i n ga l g o r i t h mb yc o m p u t e rp r o g r a m m i n g t h et r a d i t i o n a lm e t h o do fs o l v i n gt h e p r o b l e mi sb a s e do nt h er a d i a lv i r t u a ln e t w o r kl r p , a n do n l yo u t p u td a t af o r m ，n e i t h e rt om a k ed e c i s i o n m a k e r si n t u i t i v e l ys e et h es o l u t i o n s ，n o rm a n a g et h ed a t a b a s e ，s ot h ep r o m o t i o nt h em e t h o dh a sg r e a t l i m i t a t i o n s t r a n sc a ds o f t w a r es y s t e mw i t hs e n i o rd a t a b a s em a n a g e m e n tf u n c t i o na n dg e o g r a p h i c a ld a t au s e dt o o p e r a t et h eu s a b l em a pi n t e r f a c ec a nb em o r ee f f i c i e n th a n d l i n gl o g i s t i c sl o c a t i o na l l o c a t i o na n dv e h i c l e r o u t i n go p t i m i z a t i o np r o b l e m w i t hs t r o n gs p a t i a la n a l y s i sa b i l i t y , t r a n sc a dc a na n a l y z el o g i s t i c s d i s t r i b u t i o ns y s t e mw i t hs p a t i a lc h a r a c t e r i s t i c sm o r ee f f e c t i v e l y , e s p e c i a l l ys u i t a b l ef o rt h ea n a l y s i so f l o g i s t i c si n f o r m a t i o np r o c e s s i n g ，a n di s o n eo ft h ei m p o r t a n tt o o lo ft h em o d e r n i z a t i o no fl o g i s t i c s m a n a g e m e n t a c c o r d i n gt ot h ec h a r a c t e r i s t i c so fl o g i s t i c sl o c a t i o na l l o c a t i o na n dv e h i c l er o u t i n ga n dt h el o g i s t i c s m o d u l e so ft r a n sc a d ，t h i sp a p e rc o n s t r u c t st h el r pd a t as t r u c t u r ew h i c hi sa p p r o p r i a t ef o rn e t w o r k a n a l y s i so f t r a n sc a ds o f t w a r e ，a n dd i s c u s s e st h ea d j u s t m e n tt e c h n o l o g yo f v e h i c l er o u t i n gb a s e do nt r a n s c a d ，a i m st os h o wt h a tn e wi n f o r m a t i o nt e c h n o l o g yc a nb em o r ee f f i c i e n t ，i n t u i t i v e l yf o rl o g i s t i c s d i s t r i b u t i o ns y s t e m t h i sp a p e rd o e saf u r t h e ra n ds p e c i f i cr e s e a r c hf o rt h eo p t i m i z a t i o no fl o g i s t i c sl o c a t i o na l l o c a t i o na n d v e h i c l er o u t i n gb a s e do nt r a n sc a ds o f t w a r es y s t e m ，a n dg e t st h ec o n c l u s i o n sa sf o l l o w s ： ( 1 ) t h i st h e s i sc o n s t r u c t st h eb a s i cl o g i s t i c sd i s t r i b u t i o nl r pd a t as y s t e mb a s e do nt r a n sc a d s o f t w a r es y s t e m ( 2 ) t h i st h e s i sc r e a t e sl r pg e o g r a p h i cl a y e r si nt r a n sc a d ( 3 ) t h i sp a p e rc r e a t e st h el r pn e t w o r k ，a n do u t p u t st h em u i t i p a t hs h o r t e s tp a t hm a t r i xa n dv e h i c l e r o u t i n gm a t r i xu s i n gt r a n sc a ds y s t e mt o o l s ( 4 ) t h i sp a p e rs o l v e st h el o c a t i o na l l o c a t i o np r o b l e m sa n dv e h i c l er o u t i n gp r o b l e m su s i n gt h e l o g i s t i c sm o d u l e so ft r a n sc a ds o f t w a r es y s t e m ，a n do u t p u t st h es o l u t i o n so fl o c a t i o na l l o c a t i o na n d v e h i c l er o u t i n gw i t ht h ef o r m o fd a t aw i n d o wa n dr o u t es y s t e m ( 5 ) t h i st h e s i ss o l v e st h em u t i - f a c i l i t i e s a n dm u t i - v e h i c l e s l r pb a s e do nr e a l i s t i cn e t w o r k ( 6 ) i nt h i st h e s i st h es o l u t i o n so fl o c a t i o na l l o c a t i o np r o b l e m sa n dv e h i c l er o u t i n gp r o b l e m sa l e a n a l y z e d ，a n dd e l i v e r yr o u t e sh a v eb e e na d j u s t e du s i n gt h ev e h i c l er o u t e se d i t i n gt o o l s i nt h ee n d ，i td r a w s o nt h es o l u t i o n so fl o g i s t i c sl o c a t i o na l l o c a t i o np r o b l e m sa n dv e h i c l er o u t i n gp r o b l e m sb a s e do nt r a n s c a d k e y w o r d s ：l o c a t i o nr o u t i n gp r o b l e m s ；l o c a t i o na l l o c a t i o np r o b l e m s ；v e h i c l er o u t i n g p r o b l e m s ；t r a n sc a d i i i 长安大学硕士学位论文 1 1 前言 第一章概述 进入2 1 世纪以来，我国物流业总体规模快速增长。2 0 0 8 年，我国社会物流总额达 8 9 9 万亿元，比2 0 0 0 年增长4 2 倍，年均增长2 3 ；物流业实现增加值2 0 万亿元，比 2 0 0 0 年增长1 9 倍，年均增长1 4 ；物流业增加值占全部服务业增加值的比重为1 6 5 ， 占g d p 的比重为6 6 ；全社会物流总费用与g d p 的比率，由2 0 0 0 年的1 9 4 下降到 2 0 0 8 年的1 8 3 ，物流费用成本呈下降趋势，促进了经济运行质量的提高；截至2 0 0 8 年底，全国铁路营业里程8 0 万公里，高速公路通车里程6 0 3 万公里，港口泊位3 6 4 万个，其中沿海万吨级以上泊位1 1 6 7 个，拥有民用机场1 6 0 个【i 】。 物流业是服务和支撑其他产业的基础，近年来我国相继出台了一些支持物流业发展 的相关政策。国家“十一五”规划纲要明确提出“大力发展现代物流业 ，为我国物流 业的发展提供了良好的环境。另外，国务院加大力度对物流业进行扶持，并向各地区、 各部门印发了物流业调整和振兴规划，以促进物流业在国际金融危机的冲击下恢复 快速发展。 物流作为“第三利润源 近年来一直备受我国企业的关注。随着市场竞争的不断加 剧，市场竞争渐趋透明化使得企业降低制造成本和增加销售额的利润空问越来越小，此 时物流作为新的利润源又能使企业在竞争中盈利更多。 虽然近年来我国物流业发展势头迅猛，但我国物流业的总体水平仍然偏低。具体表 现为【l 】： ( 1 ) 全社会物流效率偏低。目前，发达国家的物流成本占g d p 约为8 - - 9 5 ，中 等发达国家约为1 6 左右。依据我国物流与采购联合会公布的信息得知2 0 0 8 年我国物 流成本占g d p 比重约为1 8 3 ，几乎高出发达国家一倍左右，比中等发达国家还高出 2 4 个百分点左右。 ( 2 ) 社会化物流需求不足和专业化物流供给能力不足同时存在。目前，我国物流企 业的规模普遍偏小、管理水平不高、设备落后、缺乏核心竞争力，许多企业仓储、运输 等设施不能适应现代物流集约化高效运营的需要，难以提供一体化的供应链服务，导致 制造企业寻求不到合适的物流服务供应商。同时，制造企业的物流活动主要依靠企业内 部物流，特别是大型国有企业，这样导致社会化物流需求和专业化物流供给能力不足同 第一章概述 时存在。 ( 3 ) 物流基础设施服务能力不足，尚未建立布局合理、衔接顺畅、能力充分、高效 便捷的综合交通运输体系，物流园区、物流技术装备等能力有待加强。 ( 4 ) 多数物流系统未进行合理规划，造成配送效率低下，资源浪费严重，很难满足 电子商务环境下的客户要求。 优化物流系统，对物流企业意义重大。企业可以从整体上优化配送系统，使得配送 成本最小，达到降低企业总成本、创造“第三利润 的目的。现代物流系统不仅需要有 高水平的配送设施、设备和技术，更需要在先进的信息技术支持下对配送系统进行规划。 由于我国多数企业尚未对物流系统进行科学规划，导致物流系统效率低下，严重制 约企业发展。因此，科学规划物流系统，对整合物流资源，对物流系统进行整体规划， 对促进我国物流业的良性发展十分必要。随着信息技术的飞速发展，我们要借鉴、吸收 国外物流业先进的信息技术和管理经验来打造我国高水准的物流系统，这将成为我国民 族物流业发展的助推器。 1 2 研究背景及意义 1 2 1 研究背景 在国家“十一五规划纲要明确提出“大力发展现代物流业”的同时，也提出了要 建设资源节约型社会的基本方针。2 1 世纪是全球物流业高速发展的时代，其中信息在 物流中发挥重要的作用。全社会掀起物流信息化建设的热潮，构建资源节约型物流系统 要抓住这一有利时机，充分利用有利信息来发展物流业，实现经济的转型，从而保证经 济的持续、健康、稳定的发展。 如何实现资源节约型物流，实现最小费用最大流，成为当前物流业发展的热点话题。 运输是物流系统的关键环节，降低物流成本首先就要降低运输成本，而通过对配送方案 的规划，合理地进行设施定位及车辆路线安排，实现合理选址、优化路径，是降低运输 成本的有效途径。因而在物流过程中如何优化系统成为现代物流活动的一项关键技术。 物流信息化的应用将推动资源节约型物流的实现： ( 1 ) 对物流资源的集约利用是实现资源节约型物流的前提。和物质资源和能量资 源一样，信息资源也是社会发展的资源。信息资源是人们借以对其他资源进行有效管理 的工具。在物流活动中，通过物流信息化对物流信息资源进行科学地开发，来实现对各 种资源的有效获取、分配和使用。因此，实现物流信息化，发挥物流信息资源的重要作 2 长安大学硕_ 上学位论文 用，可以推动资源节约型物流的实现。 ( 2 ) 实现资源节约型物流需要提高物流系统效率、降低物流成本。现代物流运用 信息网络技术来满足人们对物流服务的及时性要求，并且最大限度地将运输、仓储、包 装、装卸、加工、配送及信息等整合在一起，以有效地满足社会对物流的需求。通过物 流信息化，对物流系统进行科学规划，将大大提高物流系统的运作效率、降低物流总成 本。 ( 3 ) 实现资源节约型物流还需要考虑到对环境的保护。保护环境是世界各国的共 同目标，也是实现资源节约型物流的目标。目前，我国物流业的高速发展虽然促进了经 济的发展，但同时也会给环境带来不利的影响，如运输工具的噪声、废气排放、交通阻 塞等。通过物流信息化，对物流系统进行科学规划，可以有效地避开高峰路段，选择配 送最优路线，可以快捷及时地将货物送达客户点，又可以减少对环境造成的污染。 综上所述，物流信息化的发展将推动资源节约型社会向可持续方向发展，用基于信 息化平台的t r a n sc a d 软件系统来解决物流系统优化问题将加速资源节约型物流的实 现。 传统的物流决策模型对定位配给问题( l o c a t i o na l l o c a t i o np r o b l e m ，l a p ) 和车辆运 输路线安排问题( v e h i c l er o u t i n gp r o b l e m ，v r p ) 的研究较多。l a p 考虑物流设施的定 位与货物配给之间的相互关系，旨在对物流设施的数量、位置进行决策，使设施的运作 成本及车辆的运输成本最低，但l a p 忽视了对车辆路线的考虑，这就有可能使物流成 本增长。v r p 是指在设施位置己知的前提下，确定车辆在各个客户间的行程路线，使 得运输路线最短或运输成本最低1 3 j 。但v r p 未解决设施的选址问题，这将会使得物流 总体成本不能达到最低。 企业管理者希望能协调物流系统中的各个环节，以最低的价格、最好的服务来满足 顾客的需求。在物流系统优化问题的各个子问题( 如设施定位问题、物品分配问题、运 输车辆路线安排问题等) 的基础之上，产生了旨在提高物流系统效率的集成化物流。随 着集成化物流的发展，现今许多实际问题，需要综合考虑设施定位问题及车辆路线安排 问题来提高分销效率，这就形成了定位路线问题( l i 冲) 。 为了更系统地优化物流系统定位路线，自2 0 世纪7 0 年代以来，国内外学者为各类 实际问题构建了优化模型，并形成了许多解决问题的算法。这些算法主要分为两大类： 精确算法和启发式算法。在精确算法中，最常用的是整数规划的分支一定界法，能快速解 决最多8 0 个节点的定位路线问题，但必须在模型中限制设施数量。实际中遇到的系统规 第一章概述 模一般较大，很多情况下需要引入启发式算法。 精确算法和启发式算法通常只是由专业人员进行编程来实现，对于非编程人员，运 用一款内嵌物流模块的信息软件将能更高效地优化物流系统。t r a n sc a d 软件系统拥有 丰富的路径和物流模型，为物流信息化管理与决策提供了良好的基础平台【2 1 。t r a n sc a d 将数字化地图、地理数据库管理、图形表达和运筹学及统计学模型、网络分析模型、路 径选择及物流模型结合起来，可用于解决多种物流系统优化问题，并可以方便地对物流 系统及相关数据进行存储、输出、分析和可视化。 1 2 2 研究意义 在发达的国家和地区，物流业之所以能够实现低成本高效率，关键在于运用大量先 进的信息化平台。随着全球经济的发展和信息技术的突飞猛进，先进的物流信息管理平 台，必将在我国的物流业中得到广泛的应用前景。此时，引进、吸收国外先进的信息技 术，必将促进我国现代物流信息化的发展。 基于地理信息系统( g i s ) 的t r a n sc a d 软件系统具有高级数据库管理功能以及用来 操作地理信息数据的便于用户使用的地图界面，能更高效地处理物流系统优化问题。 t r a n sc a d 能可视化具有空间特征的地理信息，为用户提供了更加直观、清晰的表达形 式，这可以大大提高工作效率。t r a n sc a d 具有很强的空间分析能力，可以更有效地分 析具有空间特征物流系统，特别适宜于对物流信息的分析处理，是推进物流管理现代化 的重要工具之一。 t r a n sc a d 拥有一套车辆路径和物流程序模块，提供一系列工具来解决各种选址、 取货送货的车辆路径选择问题。这些工具可用来输入数据，求解设施选址及车辆路线问 题，并以表格和地图的形式输出t r a n sc a d 软件系统计算出的最优选址、最优路径和车 辆调度时刻表。t r a n sc a d 的这些程序可以解决诸多复杂的物流问题。例如，它可以解 决带时间窗约束的多设施、多类型车辆调度问题。t r a n sc a d 车辆路径和物流程序也能 够解决混合取货送货的问题。最终的解决方案用地图及数据窗显示，用户可以在路线系 统上增减站点来再次优化路径，以便把违反时间窗约束的情况降至最低。 本文使用t r a n sc a d 软件系统解决物流系统l r p ，目的是为了说明采用先进的信 息技术能更高效、直观地为现代物流规划提供最优解决方案。 4 长安人学硕上学位论文 1 3 国内外研究现状 自上世纪以来，国内外许多学者对物流系统定位路线优化问题进行了大量研究，构 建了解决实际问题的优化模型，并提出了一些求解方法。 国外关于物流系统定位路线问题( l r p ) 的研究始于2 0 世纪6 0 年代。v o n b o v e n t e r 4 】( 1 9 6 1 ) 研究了运输问题中的运输成本和定位成本的相互关系； m a r a n z a n a 【5 】( 1 9 6 5 ) 研究了供应点选址的最小运输成本求解问题；w 曲b 【6 】( 1 9 6 8 ) 进行了 关于多阶段仓库选址的成本函数分析；l a w r e n c e 和p e n g i l l y l 7 j ( 1 9 6 9 ) 研究了英国东南部 零售店配送仓库的选址和数量问题；c h r i s t o f i d e s 和e i l o n 8 】( 1 9 6 9 ) 提出了一种车辆分 派方法。到了7 0 年代，h i g g i n s l 9 1 ( 1 9 7 2 ) 提出了配送计划的一种简单模型；c o o p e r 1 0 】【1 1 】 ( 1 9 7 2 ，1 9 7 6 ) 把选址问题与运输问题结合起来，提出了运输一选址问题( t l p ) 。在这 个阶段，学者们对l r p 的研究没有真正涉及运输路线安排问题。w a t s o n - g a n d y 和 d o h r n 1 2 】( 1 9 7 3 ) 在研究运输一选址问题时，开始加入v r p 的多点运输的特征。到2 0 世 纪7 0 年代末、8 0 年代初，p i e r s k a l l a 1 3 】( 1 9 7 9 ) ，j a c o b s e n 和m a d s e n 1 4 1 ( 1 9 8 0 ) ，l a r p o r t e 和n o b e r t ”】( 1 9 8 1 ) 等学者做了进一步的研究工作。1 9 8 6 年l a p o r t e 关于l r p 精确解 法的描述使得l r p 的研究有了真正意义上的发展。l a p o r t ee ta l 1 7 1 ( 1 9 8 9 ) 介绍了一 种适用于较小规模随机l r p 模型并求得优化解。s r i v a s t a v a 和b e n t o n 1 8 】( 1 9 9 0 ) 研究了 可能影响配送系统设计的一些环境影响因素。c h i e n 1 9 j ( 1 9 9 3 ) 介绍了一种求解l r p 问题 的优化方法，他在计算路线成本的过程中应用了对两个不同的估计值预测路线的长度， 从而估计路线的运输成本。h a n s e n 【2 0 】( 1 9 9 4 ) 等介绍了一种更为有效的求解变形w l r p 的方法。s a l h i 和f r a s e r 2 1 l ( 1 9 9 6 ) 介绍了一种不同车辆容量的l r p 问题，并提出了一 种迭代方法，这种迭代在定位阶段和路线阶段之间不断交换，直到遇到一个合适的停止 准则。n a g y 和s a l h i t 2 2 ，2 3 1 ( 1 9 9 6 ) 应用了嵌套算法的概念来求解l r p 问题，思路是将路 线问题看作一个较大规模定位问题的子问题来处理。t a i h i sw u ，c h i n y a ol o w 和 j i u n n w e ib a i l 2 4 j ( 2 0 0 2 ) 将l r p 分解为l a p 和v r p 两个子问题分别进行求解。l i us c 和l i nc c 1 2 5 l ( 2 0 0 4 ) 研究了求解定位路线和库存控制组合优化问题的启发式算法。 m 撕a 【2 6 】( 2 0 0 5 ) 对一种简单的l r p 模型给出了严格的解界限。w a n gx u e f e n g ， s u n x i a o m i n g ，f a n gy a n g 【2 7 】( 2 0 0 5 ) 运用两阶段混合启发式搜索方法对l r p 进行了求解。 b o u h a f sl y a m i n e 等【2 8 1 ( 2 0 0 6 ) 用模拟退火和蚁群组合算法求解了带容量约束的定位路 线问题。m a r i aa l b a r e d a ，e l e n af e r n a n d e z ，g i l b e r tl a p o r t e l 2 9 】( 2 0 0 7 ) 研究了随机l r p 第一章概述 问题，并建立了两阶段模型，提出了两阶段启发式算法和下界求法。b a r r e t os e r g i o 等p o j ( 2 0 0 7 ) 用聚类分析法解决了带容量约束的定位路线问题。r o b e r tr u s s e l l ，w e n c h y u a n c h i a n g ，d a v i dz e p e d a t 3 l 】( 2 0 0 8 ) 采用禁忌搜索算法针对l r p 中涉及大量多品种印刷品 且有时间窗约束的配送问题进行了有效求解。 国内对于l r p 的研究起步较晚，目前只有少数几位学者对该类问题进行了研究。 汪寿阳、赵秋红( 2 0 0 0 ) 是在国内最早开始l r p 研究的学者，他们在文献【3 2 】中研究了 国外对于集成化物流管理系统中l r p 的研究进展情况，对l r p 求解算法进行分类，并 对该问题今后的研究方向提出了几点建议。张潜、高立群等【3 3 】( 2 0 0 3 ) 从算法优化的角 度出发，对l r p 中的定位配给、运输车辆路线安排、定位一运输路线安排三类问题的具 体优化方法进行了分析和比较，并在此基础之上提出两阶段启发式算法来求解l r p 。黄 春雨等【3 4 】( 2 0 0 4 ) 建立以缩短物流多阶响应周期为目标的l r p ，将随机需求分为期望 的需求和扰动的需求，在决策过程分阶段处理，使模型能够对需求提前预测，达到系统 整体最优。张长星【3 5 】( 2 0 0 4 ) 等用遗传算法求解了定位一运输路线问题。张潜、高立群 等【3 6 】( 2 0 0 4 ) 提出了基于最小包络聚类分析及带有控制开关的遗传算法的两阶段启发式 算法来解决l r p 。邱晗光、张旭梅【3 7 】( 2 0 0 6 ) 运用基于遗传算法、模拟退火算法的改 进粒子群算法，对一个开放式定位一运输路线问题进行了求解。张潜掣3 8 】( 2 0 0 6 ) 使用 嵌入混沌搜索的遗传算法和嵌入模糊规则的遗传算法来解决多目标l r p 。胡大伟等 例( 2 0 0 7 ) 运用遗传和禁忌搜索组合算法对l r p 小规模问题实现了有效求解。 随着信息技术的发展，c a l i p e r 公司开发出带有一套解决物流系统定位路线问题的 程序的t r a n sc a d 软件系统，可解决多种物流问题，并以表格和地图的形式向用户输出 最优选址、路线和车辆调度时刻表。 目前国内外运用t r a n sc a d 来解决物流设施选址和车辆路线问题的研究尚为空白， 国内有少数学者对运用t r a n sc a d 解决物流配送车辆路线问题进行了研究。刘敬清l 2 j ( 2 0 0 6 ) 运用t r a n sc a d 软件系统对物流配送的车辆路径问题( v i 冲) 解决方案进行了 研究；杨宁等【4 0 】( 2 0 0 7 ) 对t r a n sc a d 解决带时间窗的车辆路径问题进行了探索。 1 4 研究内容 本文在简要阐述物流系统l r p 问题的基础上，介绍了t r a n sc a d 中l r p 数据系统， 重点分析了支持物流系统l r p 的t r a n sc a d 方案设计，最后对输出结果进行分析，并 用t r a n sc a d 提供的车辆路线编辑工具对物流设施选址与配送路线方案进行了调整。 6 长安人学硕士学位论文 本文共分为5 章，主要内容如下： 第一章阐述了我国物流业发展的现状，提出了对物流设施选址与配送路线进行整体 优化是降低物流成本的重要因素，并对国内外关于物流系统定位路线问题的研究进行回 顾，从而提出了用新的信息技术解决定位路线问题的重要性。 第二章论述了物流系统定位路线问题的理论基础。物流系统优化的研究从定位配给 问题( l a p ) 、车辆路线问题( v r p ) 走向定位路线问题( l r p ) ，实现了物流系统的集 成优化。总结了目前定位路线问题( l l 冲) 的解决方法和研究动向。 第三章首先对t r a n sc a d 数据系统进行了介绍，论述了t r a n sc a d 中物流系统l r p 数据系统的结构。本章最后介绍了t r a n sc a d 中数据显示和编辑的方法。 第四章首先简要介绍了t r a n sc a d 中的物流模块的功能，然后就本文重点详细说明 了如何在t r a n sc a d 中创建地图、构建网络和输出矩阵，最后给出物流系统定位路线问 题的t r a n sc a d 解决方案。 第五章首先介绍了t r a n sc a d 中用以显示车辆路线安排的路线系统，然后对第四章 输出的定位路线问题解决方案进行分析，利用t r a n sc a d 车辆路线编辑工具对第四章解 决方案进行调整，最后给出a 市物流系统l r p 解决方案。 论文最后总结了本文的主要工作及研究成果，并对简要说明了需要进行进一步研究 的问题。 7 第二章物流系统定位路线问题( l i 冲) 第二章物流系统定位路线问题( l r p ) 2 1 集成化物流中的定位路线问题( l r p ) 物流系统优化问题可分为定位配给问题( l a p ) 、车辆路线问题( v r p ) 、定位一路线 问题( l r p ) 等等。其中l r p 更符合复杂物流系统的实际情况，所以对它的研究是现实 意义。随着国际贸易的发展和集成化物流理念的深入，对于集成化l r p 的研究更为普 遍了。w a t s o n - g a n d y 和d o h m ( 1 9 7 3 ) 最早将车辆多点停留特性与定位一运输路线结合起 来进行研究。 定位路线问题( l r p ) 是物流规划中定位配给问题( l a p ) 和车辆路线问题( v l 冲) 的集成，是物流系统优化的难题。 一、定位配给问题( l o c a t i o na ii o c a t i o np r o b i e m s ，l a p ) 定位配给问题( l a p ) 一般定义为：考虑设施选址与货物配送之间的相互关系，为 配送中心、制造业工厂、仓库、医院、零售商场、以及其他类型的设施确定某一范围内 设施的最优数量和位置，目的是为了提供高水平的服务、降低营运费用或使利润最大化。 在定位配给问题的研究中，一般认为设施到客户的运输路线是放射线状的，即车辆每次 访问一个客户后，就返回原设施，如图2 1 所示。 露选中设施 一未选中设施囝客户 夕路线 图2 1l a p 示意图 定位配给问题的目标有两种：一是确定设施的数量，从而确保能够满足预定的服务 水平。例如在某城市内确定消防设施的数量，使得该市内消防设施到任一幢建筑离最近 的消防中心距离不超过5 分钟车程。二是从一个可能的位置集中选择一个或多个设施的 最佳位置。例如从一个备选位置集中选择某城市新警察局的最佳位置，以便使巡逻车从 警察局到该局所管片区内任一居民家的距离最短。 j o h nc u r r e n t 等学者对l a p 进行了综述研究【4 l 】，并根据问题的四种目标函数来进行 囤 长安大学硕： ：学位论文 分类，这些函数有：( 1 ) 费用最小化函数；( 2 ) 客户需求导向函数；( 3 ) 利润最大化函数； ( 4 ) 其他相关函数。 二、车辆路线问题( v e h i c i er o u t i n gp r o b i e m s ，v r p ) 车辆路线问题( l i 冲) 可描述为：给定一个车辆集合、设施集合和客户集合，在满 足所有限制条件( 时间窗口、车辆容量、路线总长度等) 的基础上，在访问所有客户的 前提下，安排最少的车辆行驶最短的距离( 或花费最少的时间) 。该问题的前提条件是 己知设施位置、客户位置、路线和车辆情况，由此确定一套车辆运输路线，以满足目标 函数，如图2 2 所示。 躁设施客户夕路线 图2 2v r p 的示意图 车辆路线问题( v r p ) 通常需要满足如下约束条件【4 2 】： 1 每个客户只接受一个设施点的一个车辆送来的货物。 2 所有车辆的配送路线均起始并终止于同一设施点。 3 满足一些其他约束条件，如： ( 1 ) 车辆容量约束：每个客户点的货物需求量非负，且每条配送路线上的客户需求量总 和不超过车辆装载量。如果不满足此约束条件，则引入惩罚函数。 ( 2 ) 总时间约束：每条路线的总长或车辆运行总耗时不超过预定值。此约束保证客户对 供货时间的要求，以及对货物品质的要求。 ( 3 ) 具体时间约束：客户点要求车辆某一时间段内到达。此约束可满足客户对供应回 收的特殊时间要求。 ( 4 ) 行车顺序约束：如要求车辆在到达b 点之前先要到达a 点。 上述约束条件只是该问题的一些常见约束，实际操作时要视情况而定。 车辆路径问题( v r p ) 的求解算法有精确算法和启发式算法两种。精确算法包括整 9 第二章物流系统定位路线问题( l i 冲) 数规划、树状寻优算法和动态规划。启发式算法大多来源于对旅行商问题( t s p ) 的求 解算法，如插值法、局部优先算法等可以直接用于求解一些车辆路径问题。 三、定位路线问题( k o c a tio nr o u tin gp r o bio m s l r p ) 进入新世纪以来，物流系统环境日益复杂，而且物流区域也在不断扩大，物流系统 优化的子问题之间的影响也在加大。随着集成化物流管理的概念的普及和全球贸易的快 速增长，提高配送效率成了企业生存与发展必须面临的难题。当前所面临的诸多实际问 题中，都需要综合考虑定位配给问题和车辆路线问题，这样定位路线问题( l r p ) 就产生 了。 定位路线问题( l o c a t i o nr o u t i n gp r o b l e m ，l r p ) 是物流规划中定位配给问题( l a p ) 和车辆路线( v r p ) 问题的集成，是物流系统优化的难题。l r p 可描述为：给定一组符 合实际情况的客户点集合和备选设施点集合，从这些备选设施点中选出一组新的设施位 置集合作为规划设施点，同时还要确定出一套从各个设施到其服务客户点的运输路线， 解决该问题的目的是使总费用最小。l r p 通常作如下假定：( 1 ) 客户位置和客户需求量 已知；( 2 ) 备选设施点位置已知；( 3 ) 货物由一个或多个设施供应；( 4 ) 每个客户只接 收来自一个设施的一个车辆送来的货物。图2 3 为l r p 示意图。 l r p 是l a p 与v r p 的集成，但比二者更为复杂。l a p 在设施定位过程中，只考虑 运输车辆从设施点到一个客户点完成配送任务后，随即返回同一设施点，没有考虑车辆 路线安排问题。而l r p 则在进行设施定位的同时，还要确定出最优车辆运输路线。v r p 的前提条件是己知设施点和客户点位置，而l r p 只是己知所有备选设施点位置，在确 定车辆最佳运输路线的同时还需要确定设施点的最佳位置。 叠选中设施豳未选中设施客户 夕路线 图2 3l r p 示意图 l o 长安大学硕上学位论文 2 2l r p 分类 h o k e ym i n ( 1 9 9 8 ) 等学者对l r p 进行了详尽的分类【4 3 1 ，几乎包含了l r p 的各个方 面。h o k e y 的分类标准具体如表2 1 所示。 表2 1l r p 的分类标准 分类标准 a b 1物品流向单向双向 2 供需特征 确定随机 3 设施数量单一设施多设施 4 运输车辆数量单一车辆多车辆 5 车辆装载能力不确定确定 6 设施容量不确定确定 7 设施分级单级多级 8 计划期间单期多期 9 时间限制无时间限制有时间限制 l o 目标数单目标多目标 1 l 模型数据类型假设值实际值 上表中各分类标准说明如下： ( 1 ) 物品流向。单向物品流向问题指的是所有设施只进行输入( 供应) 或只进行输出 ( 回收) 的操作；而双向物品流向问题涉及的设施中有一部分既要输入又要输出。 ( 2 ) 供需特征。确定型供需特征是指物品供应需求量是已知的，并在一定时期内 相对稳定；随机型供需特征的是指供应需求量是不确定的。 ( 3 ) 设施数量，分为单一设施和多设施两种。 ( 4 ) 运输工具数量是指一个设施有多少服务车辆，同时也确定了一个以设施为起始 点的路线数量，可分为单一车辆和多车辆两种。 ( 5 ) 车辆装载能力指是否考虑车辆装载能力的限制。不确定型车辆装载能力是指每 条路线上的货物总量很少，不会超出车辆的装载量，所以不用考虑车辆的装载能力的限 制；确定型车辆装载能力是指每条路线上的货物总量有可能超出车辆的装载能力，所以 要把车辆的装载限制作为一个参数引入。 ( 6 ) 设施容量是指是否考虑各个设施容量的限制，可分为不确定型设施容量和确定 型设施容量两种。 ( 7 ) 设施分级把设施分为两种：总站型和中间转运站型。总站型设施是指车辆路线 的始发点或终点；中间转运站型设施是指物品的中间站，货物运入后还要运出。货物从 总站型设施运入中间转运站型设施，经过简单处理后再运到客户点。单级设施问题不考 】 第二章物流系统定位路线问题( l r p ) 虑设施的分级，所有设施均为同级；而多级设施问题则要考虑设施的分级。 ( 8 ) 计划期间。单期间问题把整个期问作为一个时问段，属于静态问题；多期间问 题把整个时间期间按要求分为多个时间段，属于动态问题。 ( 9 ) 时间限制主要是指满足客户要求或货物品质要求，