7物流系统优化中的定位运输路线安排问题386 .docx
精品名师归纳总结物流系统优化中的定位运输路线支配问题<)争论评述林岩胡祥培<大连理工高校系统工程争论所, 116023)摘要 本文概述了物流优化问题中的定位运输路线支配问题<Location- Routing Problems, LRP )的进展历程,并对LRP 的分类和解决方法加以评述,最终就这一问题的进展方向进行简洁的探讨。关键词 LRP 物流系统优化运筹学1 引言新技术的快速进展,特殊是电子商务的风起云涌,为我国经济的快速进展供应了契 机。目前我国电子商务得到政府和民众的支持,进展势头强劲,但是,由于它是一套全新 的技术,同时仍是一种全新的治理理念,所以其进展过程中必定存在一些难题。在电子商 务“三流” <信息流、物流、资金流)中,随着网络基础设施建设的成熟、电子商务网站的蓬勃进展以及有效利用网络资源观念的普及,信息流的进展已经比较成熟了。而随着各大 银行纷纷开展网上业务,以及支付网关的建立和加密技术的成熟,网上支付已经在很多网 站上成为现实。然而,我国传统的物流体系是在方案经济环境下建立、进展起来的,与目 前的电子商务环境已经无法相容。现今物流体系的落后现状已经成为我国社会经济快速发 展的重要制约因素之一。所以对物流系统优化的争论将会具有很大的现实意义。国外很多学者在电子商务显现之前就已经争论物流系统优化的问题了,为各类实际问题构建了优化模型,并形成了很多解决问题的算法。依据实际问题的不同,可以对物流系统优化问题进行分类,比如,运输车辆路线支配问题<VRP)、定位 配给问题 <LA)、定位运输路线支配问题 <LRP)等等,其中LRP 更贴近目前的物流系统复杂的实际特点,所以对它的争论是非常有意义的。本文先从 VRP和 LA 的集成来探讨 LRP 的由来,然后争论LRP 的分类,同时探讨LRP的争论现状,并对LRP的解决方法进行概述,最终就LRP 的将来进展方向作简要的争论。2 从 VRP 、LA 到 LRP 物流系统的集成依据实际问题的不同,可以对物流系统优化问题进行分类,比如确定设施<指的是物品流淌的动身点和终到点,如配送中心、仓库、生产工厂、垃圾回收中心等)位置、运输路线支配、库存掌握等,国内外很多学者就各类问题的特点进行了分析,并提出了各类问题的数学模型和解决方法。2.1 运输车辆路线支配问题<Vehicle Routing Problems VRP )该问题可定义为:运输车辆从一个或多个设施到多个的理上分散的客户点,优化设计一套货物流淌的运输路线,同时要满意一系列的约束条件。该问题的前提条件是设施位置、客户点位置和道路情形已知,由此确定一套车辆运输路线,以满意目标函数<通常,国家自然科学基金重点工程70031020>林岩, 硕士争论生 , 1972 年诞生 , 主要争论方向 : 电子商务 , 信息系统工程。胡祥培 , 1962 年诞生 , 教授,博导, 主要争论方向 : 电子商务 , 智能运筹学 , 信息系统集成。可编辑资料 - - - 欢迎下载精品名师归纳总结VRP 的目标函数是总费用最小)。如图1 所示。图中,表示设施。表示客户。表示运输路线图 1 VRP 的图示实际上, VRP 是按如下假设定义的最小费用问题1 :<1)全部车辆路线均起始并终止于设施点。<2)每个客户只接受一个设施的货物。<3)满意其他一些约束条件,如: 容量限制:每个客户点上都有一个非负的货物需求量,但每条车辆路线上的货物量总和不超过车辆装载量。假如此约束不满意,就引入惩处函数。 总时间限制:每条路线总的长度或总耗时不超过一个事先定下的数值。这项限制旨在满意客户对供货时间的要求,以及对货物品质的保证。 具体时间限制:对某个客户点,车辆到达时间限制在某一时间段内。此约束在于满意客户对供应 /回收的特殊要求。 车辆到达次序要求:如在到达i 点之前要求先到达j 点。以上列出的约束只是该问题一部分,具体操作时要视具体情形而定。对 VRP 的求解算法可分为精确算法和启示式算法两种。其中精确算法包括树状寻优算法、动态规划和整数规划。VRP 的启示式算法多是来源于对TSP 问题的求解算法。比如局部优先算法、插值法等可以不用修改的用于一些VRP 。2.2 定位配给问题 <Location-Allocation Problems, LA )定位一配给问题可定义为:依据客户点的的理分布与货物安排关系,确定出某一的理范畴内设施的数量和位置。如图2 所示。图中,表示设施。表示客户。表示运输路线可编辑资料 - - - 欢迎下载精品名师归纳总结图 2 LA 的图示LA实质上是一个依据优化路径的原就来确定在什么的方设置设施的过程2 。例如,在一个城镇中设立一个急救中心,这个问题就是一个典型的LA问题。它的目标就是使得全 镇的居民到医疗中心的路径<时间)总体上最短。依据 John Current 等学者对此问题的综述争论3 ,把 LA 问题进行了分类。 Current 的方法是依据问题的目标函数来分类的,作为分类依据的目标函数共分四种:1> 费用最小化。2> 客户需求导向。3> 利润最大化。4> 其他相关考虑。2.3 定位一运输路线支配问题<Location-Routing problems,LRP )当今物流系统的环境日趋复杂,而且物流的理分布也不断扩大。物流系统优化问题的各个子系统 <比如设施定位问题、物品配送问题、运输车辆路线支配问题等)之间的相互影响也越来越大。对很多实际问题,要综合考虑以上问题,这就形成了定位一路线支配问题<LRP )。LRP 可以表述为:给定与实际问题相符的一系列客户点和一系列潜在的设施点,在这些潜在的点中确定出一系列的设施位置,同时要确定出一套从各个设施到各个客户点的运输路线,确定的依据是满意问题的目标< 通常是总的费用最小)。客户点的位置和客户的需求量是已知的或可估算的,货物有一个或多个设施供应,每个客户只接收来自一个设施的货物,潜在设施点位置已知,问题的目标是把哪些潜在的设施建立起来,以使的总的费用最小。 LRP 可图示为图 3。可以说 LRP 是 LA 与 VRP 的集成 4 ,但比后两者更复杂。LA 在定位时考虑的是运输车辆从设施点到一个客户点后,立即返回设施点,所以它不考虑路线支配问题5 。LA在确定出设施点后的图形是从设施点到客户点的射线族。而LRP 就在定位时同时确定运输路线。 LRP 与 VRP 的不同之处是: VRP 的前提条件是设施点和客户点在空间上的分布是已知的。 LRP 所争论的问题只知道潜在的设施点,在确定运输路线的同时要确定设施的位置。图中,表示设施。表示未被选中的设施。表示客户点。表示运输路线图 3 LRP 的图示在实际物流系统的集成的特点日益突出之前,就已经有人争论LRP 了。最早的争论可以追溯到 20 世纪 60 岁月,当时有些学者已经提出一些类似的概念了6-8 。到了 70 岁月, Cooper9, 10 把定位问题与运输问题结合起来,提出了运输肯定位问题<Transportation-可编辑资料 - - - 欢迎下载精品名师归纳总结Location problem )。在这个阶段,学者们对LRP 的争论仍是相当肤浅的,仍没有真正涉及运输路线支配问题。到了70 岁月中期,一些学者在争论运输肯定位问题时,开头加入VRP 的多点运输的特点, Watson-Gandy 和 Dohrn 11 是最早进行这方面工作的学者。直到70岁月末, 80 岁月初,才开头有了真正意义的LRP 12-14 。这些争论成果是相伴着集成物流系统概念的显现而显现的。3 LRP 的分类Hokey Min等学者对 LRP 进行了具体的分类15 ,其分类标准非常详尽,几乎包含了LRP 的各个方面。表 1 LRP 的分类标准分类标准AB1物品流向单向双向2供/需特点确定随机3设施数量单个设施多设施4运输车辆数量单个车辆多车辆5车辆装载才能不确定确定6设施容量不确定确定7设施分级单级多级8方案期间单期多期9时间限制无时间限制有时间限制10目标数单目标多目标11模型数据类型假设值实际值Hokey 的分类是依据问题的特点进行的,具体如表1。表 1 中,各分类标准说明如下:<1)物品流向,单向物品流向问题指的是全部设施只进行输入<供应)或只进行输出 <回收)的操作。而双向物品流向问题涉及的设施中有一部分既要输入又要输出。<2)供 /需特点,确定型的是指物品供应/需求量是已知的并在肯定时期内相对稳固。 随机型的是指供应 /需求量是不确定的。<3)设施数量,指所争论问题要求设置设施的数量,分为单一设施和多设施两种。<4)运输工具数量,是指有多少车辆为一个设施服务的标准,同时也确定了一个从设施动身的路线数。分为单一车辆和多车辆两种。<5)车辆装载才能,是指是否要考虑车辆装载才能的限制。不确定定型是指对这个问题所涉及的每条路线上的货物总量很小,不会超出车辆的装载量,所以不用考虑车辆的装载才能的限制。确定型是指每条路线上的货物总量有可能超出车辆的装载才能,所以要把车辆的装载限制作为一个参数引入问题。<6)设施容量,是指是否考虑各个设施容量的限制。分为不确定型和确定型两种。<7)设施分级,可以把设施分为两种:总站型和中间转运站型。总站型设施是指那些车辆路线的动身点或终点。中间转运站型设施是指物品的中间站,货物运入后仍要运出。有了中间转运站,就产生了设施分级的问题,货物从总站型设施运入中间转运站型设施, 经过简洁处理后运到客户点。单级设施问题是指不考虑设施的分级,全部设施均为同级。 而多级中心设施问题就要考虑设施的分级。<8)方案期间,单期间问题把整个期间作为一个时间段,是静态问题。多期间问题把整个时间段按问题要求分为多个期间,是动态问题。<9)时间限制,主要是指满意客户要求或货物品质要求,而对LRP 的从设施点到客户点的时间约束。分为无时间约束和有时间约束两种。<10)目标数量, LRP 的目标通常是总的费用<包括建设设施费用和车辆运输费用等)可编辑资料 - - - 欢迎下载精品名师归纳总结最小,但有时也需要考虑其他目标,比如满意顾客的特殊需要、总体利润量大化等等。假如是多目标问题,常常会显现各目标之间的冲突。<11)模型数据类型,在有些情形下,模型中的数据<如物品供 /需量等)是来源于实际的。而有些情形下,这些数据是在实际中不行得的,需要对其进行假设。依据模型数据类型的不同,把LRP 分成假设型和实际型两类。4 LRP 的解决方法国外很多学者对LRP 的解决方法进行了有益的探讨,所采纳的方法可以分为两种:精确算法和启示式算法。4.1 解决 LRP的精确算法基于运筹学的优化算法,解决LRP 的精确算法可以分为以下四种:1> 直接树状搜寻 1 。2> 动态规划 117 。3> 整数规划 1819 。4> 非线性规划 20 。在以上算法中,最为常用的是整数规划<包括混合整数规划),而具体解决时效率最高的方法是分支 定界法。它可以在不很长的运算时间内解决多至80 个节点的 LRP ,但是采纳分支 定界法的 LRP 必需在其模型中限制设施的数量。一旦所涉及的LRP 的规模扩大,精确算法就不有用了。4.2 解决 LRP的启示式算法由于 LRP 结合了LA问题和VRP ,而后两者都是NP-HardNon deterministicPolynomial hard> 问题,所以,在大多数情形下,要用精确算法来解决LRP 是非常困难的。例如,在一个物流系统中,有3 个潜在的中心点,8 个分布的客户点, 3 条行车路线,假如用整数规划来解决,要涉及的变量会达到333 个16 。实际上,以上的物流系统是非常小的,在实践中遇到的系统规模往往会远超过它。很多情形下要引入启示式算法。LRP 往往是非常复杂的,需要采纳多级分解方法对其简化。目前解决LRP 的启示式算法多采纳以下四种方法或是它们的组合:<1)先解打算位一配给问题,然后解决运输路线支配问题15, 21 。<2)先解决运输路线支配问题,然后解打算位一配给问题22 。<3)费用降低 /插入算法 23, 24 。<4)路线扩展交换算法。很多情形下精确的优化算法仅仅是作为一种参照的基准,在争论LRP 时比较各种启示式算法的优劣。而在解决实际规模问题时一般要采纳启示式算法。5 LRP 的将来争论方向实际物流系统集成的程度越来越高,物流决策者面临的问题也就越来越复杂。用目前LRP 的争论成果来解决特殊复杂的物流系统优化问题仍存在很多局限。将来对LRP 的争论将会集中于以下难点:5.1 动态性很多 LRP 的参数是随时间变化的,如库存费用会随员工的人数、员工的工资水公平因可编辑资料 - - - 欢迎下载精品名师归纳总结素的变化而变化。运输费用也会因车辆装载情形、油料费用等的转变而转变。所以LRP 具有动态性,对动态 LRP 的争论是有现实意义的。25, 26运筹学理论被认为是解决优化问题非常有效的工具。但是假如实际问题发生变化,就会引起数学模型转变和模型求解程序的转变。对于动态问题,这种连锁反应是时时刻刻都在发生的。因而用传统的运筹学理论解决动态的优化问题会力不从心。其缘由是传统的运筹学理论缺乏基于学问的推理机制和处理动态问题的自适应才能。为了克服这一缺陷,八十岁月以来国内外学者将人工智能和学问工程理论引入运筹学 , 开创了智能运筹学 这一新的争论方向。使运筹学由过去的仅能解决静态问题变为可以解决动态问题,它必将有助于动态 LRP 的求解5.2 实时调控在实际情形下,特殊是在如今被广泛重视的电子商务物流的实施过程中,商品供货点、运输工具、运输路径和送货时间等需要实时作出决择。这就涉及到实时调控的问题。近年来, Agent 技术进展快速, Agent 具有的自主性、主动性、反应性和智能性为改进基于运筹学学问表示理论的动态问题的实时优化掌握系统制造了条件。将Agent 技术与运筹学理论有机结合和交叉渗透,必将对最终解决实际规模LRP 有打算性的意义。5.3 随机性在实践中,物品的供应/ 需求量、客户点位置、车辆行驶时间等等在很多情形下是不能事先确定的,这些参数就带有随机性。把随机性引入LRP ,更有利于解决实际问题。已经有很多学者对随机性LRP 进行了争论,如Laporte 等人 29 对供应 /需求量不确定的LRP 作了探讨。他们提出了一种两阶段算法:第一阶段,在供应/需求量未知的情形下,确定中心位置、运输路线、车队数量。其次阶段,由于一条路线上的供应/需求量有可能超出车辆的装载才能,车辆在某点装满时要返回中心点装货/卸货,然后回到返回点复原运输, 以上的车辆操作产生了惩处项。为明白决这类问题,引入两种方法:<1)在保证显现车辆返回的概率不小于某一预定值的情形下,确定第一阶段值。<2)在保证由于车辆返回而产生的费用不超过某一预定费用的情形下,确定第一阶段值。这类问题就可以采纳整数规划来解决了。5.4 时间限制实际的物流系统中,很多情形下,客户对车辆的到达时间是有限制的。这种时间的限制又可以分为硬限制和软限制两种,硬限制要求时间的一点,软限制指定一段时间。但 是,到目前为止,对LRP 的争论很少考虑对时间的限制。这方面的争论将会是有益的。5.5 多目标性物流系统中的各个目标之间会产生冲突,如依据总费用最小目标确定的方案,在满意客户对时间要求的目标时,可能会不合要求。然而,实际物流系统均有多目标的特点。所以以后对 LRP 的争论中会注意多目标之间优化。6 结论本文对物流系统中的LRP的由来、分类、解决方法作了简要的评述,并对LRP 的未来争论方向作了分析。对LRP的争论仍存在很多没有很好解决的方面。对LRP 的争论将会越来越向符合实际情形的方向进展。可编辑资料 - - - 欢迎下载精品名师归纳总结参考文献1 Gilbert Laporte. The vehicle routing problem : An overview of exact and approximate algorthms.European Journal of Operational Research,1992,59 : 345-3582 Alant Murray, Ross A. Gerrard. Capacitated service and regional constraints in location-allocation modeling. Location Science, 1997, 52> : 103-1183 John Current, H. Min, D.A. Schilling. Multiobjective analysis of facility location decisions. European Journalof Operational Research, 1990, 49 : 295-3074 汪寿阳 , 赵秋红 , 夏国平 . 集成物流治理系统中的定位运输线路支配问题的争论. 治理科学学报 , 2000, 32> : 69-755 S. Salhi, G.K. Rand. The effect of ignoring routes when locating deports. European Journal of Operational Research, 1989, 39 : 150-1566 Maranzana F.E. On the locationof supplypoints tominimizetransport cost. Operational Research Quarterly,1965,15> : 261-2707 M.H.J. Webb. Cost functions in the location of deports for multiple-delivery journeys. Operational ResearchQuarterly, 1968, 19> : 311-3208 N.Christofides, S.Eilton. An algorithm for the vehicle dispatching problem. Operational Research Quarterly, 1969, 20> : 309-3189 Leon Cooper. The Transportation-Location Problem. Operations Research, 1972, 20 : 94-10810 Leon Cooper. An efficient heuristic algorithm for the transportationlocation problem. Journal of Regional Science, 1976, 163> : 309-31511 C.Watson-Gandy, P.Dohrn. Depot location with van salesmanA practical approach. Omega, 1973, 13> : 321-32912 I.Or,W.P.Pierskalla. A transportation,location allocationmodel forregionalbloodbanking. AIIE Transactions, 1979, 112> : 86-9513 Jacobson.S.k., Madsen. O.B.G.A comparative study of heuristics for a tow-level routing location problem. European Journal of Operational Research, 1980, 5 : 378-38714 Laporte G.,Nobert Y. A exact algorithm for minimizingrouting and operating costs in depot location . European Journal of Operational Research,1981,6:224-22615 Hokey Min, Vaidyanathan Jayaraman, Rajesh Srivastava. Combined location - routing problems : A synthesis and future research direction. European Journal of Operational Research, 1998, 108:1-1516 Rajesh Srivastava, W.C.Benton. The location-routing problem : considerations in physical distribution system design. Computers & Operations Research, 1990, 17 : 427-43517 I.Averbakh, O.Berman. Routing and location routing p-delivery man problems on a path. TransportationScience, 1994, 282> : 162-16618 C.ReVelle, J.Cohon, D.Shobrys. Simultaneous sitingand routing in the disposal of hazardous wastes. Transportation Science, 1991, 252> : 138-14519 G.Laporte, Y. Nobert, D.Arpin.An exact algorithmfor solving a capacitated location routing problem.Annals of Operations Research, 1986, 6, : 293-31020 C.L.Stowers, U.S.Paleker. Location models with routing considerations for a single obnoxious facility. Transportation Science, 1993, 274> : 350-36221 J.H.Bookbinder, K.E.Reece. Vehicle routing considerations in distribution system design. European Journal of Operational Research, 1988, 37 : 204-213可编辑资料 - - - 欢迎下载精品名师归纳总结22 J.Perl, M.S.Daskin. A warehouse location routing problem. TransportationResearch, 1985, 19B5> : 381-39623 T.W.Chien. Heurristic procedures for practicalsized uncapacitated location capacitated routing problems. Decision Sciences, 1993, 245> : 995-102124 P.H.Hansen, B.Hegedah1, S.Hjortk, B.Obel. A heuristic solution to the warehouse location - routing problem. European Journal of Operational Research, 1994, 76 : 111-12725 R.I.phelps. ArtificialIntelligence - An overview of Similaritieswith O.R. Journal of Operational ResearchSociety, 1986, 371> : 13-2026 胡祥培 , 杨德礼 . 智能运筹学与动态系统实时优化掌握 . 经济治理与社会科学前沿争论 2000 年中国博士后学术大会经济治理与人文社会分会暨全国博士后第四届经济学治理学学术会谈论文集 , 中国金融出版社 , 2000 年 10 月出版 :137-14827 Hu Xiangpei. A New Method on Knowledge Representation for Programming ModelofOperationalResearchStructuredState-space Representation.ProceedingsoftheSecondRussian-Chinese International Symposium On Management Science, Economic Education Press, Moscow, Russia, Oct. 199428 胡祥培 , 钱国明 , 胡运权 . 离散型动态规划模型的学问表示及其IBFS 算法争论 .哈尔滨工业高校学报,1996,3:119-12629 Gilbert Laporte, Francois Louveaux, He lene Mercure. Modles and exact solutions for a class of stochastic location-routing problems. European Journal of Operational Research, 1989, 39 : 71-78Review on LocationRouting Problems LRP> in Systematic Optimization of LogisticsLin YanHu XiangpeiInstitute of System Engineering, Dalian University of Technology>AbstractThispaper reviews the developmentofthe Location RoutingProblems LRP>. Whereafter,types,algorithmsandsolutionsofLRP, whichhad been researched bysome specialists, will be discussed, then the intending cruxes of LRP will be summarized.KeywordsLRP Logistics Systematic Optimization Operations Research可编辑资料 - - - 欢迎下载