物流系统优化中的定位-运输路线安排问题,(2).doc

物流系统优化中的定位-运输路线安排问题,(2)物流系统优化中的定位运输路线安排问题 （）研究评述_ 国家自然科学基金重点项目(70031020) 林岩 胡祥培_ 林岩, 硕士研究生, 1972年出生, 主要研究方向: 电子商务, 信息系统工程。 胡祥培, 1962年出生, 教授,博导, 主要研究方向: 电子商务, 智能运筹学, 信息系统集成。 _ （大连理工大学系统工程研究所, 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） 该问题可定义为：运输车辆从一个或多个设施到多个地理上分散的客户点优化设计一套货物流动的运输路线同时要满足一系列的约束条件。该问题的前提条件是设施位置、客户点位置和道路情况已知由此确定一套车辆运输路线以满足目标函数（通常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和Dohrn11是最早进行这方面工作的学者。直到70年代末80年代初才开始有了真正意义的LRP12-14。这些研究成果是伴随着集成物流系统概念的出现而出现的。 3 LRP的分类 Hokey Min等学者对LRP进行了详细的分类15其分类标准十分详尽几乎包含了LRP的各个方面。 表1 LRP的分类标准 分类标准 A B 1 物品流向 单向 双向 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-Hard (Non deterministic Polynomial 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-358 2 Alant Murray, Ross A. Gerrard. Capacitated service and regional constraints in location-allocation modeling. Location Science, 1997, 5(2) : 103-118 3 John Current, H. Min, D.A. Schilling. Multiobjective analysis of facility location decisions. European Journal of Operational Research, 1990, 49 : 295-307 4 汪寿阳, 赵秋红, 夏国平. 集成物流管理系统中的定位运输线路安排问题的研究. 管理科学学报, 2000, 3(2) : 69-75 5 S. Salhi, G.K. Rand. The effect of ignoring routes when locating deports. European Journal of Operational Research, 1989, 39 : 150-156 6 Maranzana F.E. On the location of supply points to minimize transport cost. Operational Research Quarterly,1965,(15) : 261-270 7 M.H.J. Webb. Cost functions in the location of deports for multiple-delivery journeys. Operational Research Quarterly, 1968, (19) : 311-320 8 N.Christofides, S.Eilton. An algorithm for the vehicle dispatching problem. Operational Research Quarterly, 1969, (20) : 309-318 9 Leon Cooper. The Transportation-Location Problem. Operations Research, 1972, 20 : 94-108 10 Leon Cooper. An efficient heuristic algorithm for the transportation location problem. Journal of Regional Science, 1976, 16(3) : 309-315 11 C.Watson-Gandy, P.Dohrn. Depot location with van salesman A practical approach. Omega, 1973, 1(3) : 321-329 12 I.Or, W.P.Pierskalla. A transportation, location allocation model for regional blood banking. AIIE Transactions, 1979, 11(2) : 86-95 13 Jacobson.S.k., Madsen. O.B.G.A parative study of heuristics for a tow-level routing location problem. European Journal of Operational Research, 1980, 5 : 378-387 14 Laporte G.,Nobert Y. A exact algorithm for minimizing routing and operating costs in depot location . European Journal of Operational Research,1981,6:224-226 15 Hokey Min, Vaidyanathan Jayaraman, Rajesh Srivastava. bined location - routing problems : A synthesis and future research direction. European Journal of Operational Research, 1998, 108:1-15 16 Rajesh Srivastava, W.C.Benton. The location-routing problem : considerations in physical distribution system design. puters & Operations Research, 1990, 17 : 427-435 17 I.Averbakh, O.Berman. Routing and location routing p-delivery man problems on a path. Transportation Science, 1994, 28(2) : 162-166 18 C.ReVelle, J.Cohon, D.Shobrys. Simultaneous siting and routing in the disposal of hazardous wastes. Transportation Science, 1991, 25(2) : 138-145 19 G.Laporte, Y. Nobert, D.Arpin. An exact algorithm for solving a capacitated location routing problem. Annals of Operations Research, 1986, 6, : 293-310 20 C.L.Stowers, U.S.Paleker. Location models with routing considerations for a single obnoxious facility. Transportation Science, 1993, 27(4) : 350-362 21 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. Transportation Research, 1985, 19B(5) : 381-396 23 T.W.Chien. Heurristic procedures for practical sized uncapacitated location capacitated routing problems. Decision Sciences, 1993, 24(5) : 995-1021 24 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-127 25 R.I.phelps. Artificial Intelligence - An overview of Similarities with O.R. Journal of Operational Research Society, 1986, 37(1) : 13-20 26 胡祥培, 杨德礼. 智能运筹学与动态系统实时优化控制. 经济管理与社会科学前沿研究2000年中国博士后学术大会经济管理与人文社会分会暨全国博士后第四届经济学管理学学术会议论文集, 中国金融出版社, 2000年10月出版:137-148 27 Hu _iangpei. A New Method on Knowledge Representation for Programming Model of Operational ResearchStructured State-space Representation. Proceedings of the Second Russian-Chinese International Symposium On Management Science, Economic Education Press, Moscow, Russia, Oct. 1994 28 胡祥培,钱国明,胡运权.离散型动态规划模型的知识表示及其IBFS算法研究. 哈尔滨工业大学学报,1996,3:119-126 29 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-78 Review on LocationRouting Problems (LRP) in Systematic Optimization of Logistics Lin Yan Hu _iangpei (Institute of System Engineering, Dalian University of Technology) Abstract This paper reviews the development of the LocationRouting Problems (LRP). Whereafter, types, algorithms and solutions of LRP, which had been researched by some specialists, will be discussed, then the intending cruxes of LRP will be summarized. Keywords LRP Logistics Systematic Optimization Operations Research 第 19 页 共 19 页