0107112物流系统优化中的定位运输路线安排问题

1、管理科学与系统科学研究新进展第6届全国青年管理科学与系统科学学术会议论文集 2001年大连物流系统优化中的定位运输路线安排问题（）研究评述* 国家自然科学基金重点项目(70031020)林岩 胡祥培* 林岩, 硕士研究生, 1972年出生, 主要研究方向: 电子商务, 信息系统工程。 胡祥培, 1962年出生, 教授,博导, 主要研究方向: 电子商务, 智能运筹学, 信息系统集成。 *（大连理工大学系统工程研究所, 116023）摘要 本文概述了物流优化问题中的定位运输路线安排问题（location-routing problems, lrp）的发展历程，并对lrp的分类和解决方法加以评述，最

2、后就这一问题的发展方向进行简单地探讨。关键词 lrp 物流 系统优化 运筹学1 引言新技术的迅速发展，特别是电子商务的风起云涌，为我国经济的快速发展提供了契机。目前我国电子商务得到政府和民众的支持，发展势头强劲，但是，由于它是一套全新的技术，同时还是一种全新的管理理念，所以其发展过程中必然存在一些难题。在电子商务“三流”（信息流、物流、资金流）中，随着网络基础设施建设的成熟、电子商务网站的蓬勃发展以及有效利用网络资源观念的普及，信息流的发展已经比较成熟了；而随着各大银行纷纷开展网上业务，以及支付网关的建立和加密技术的成熟，网上支付已经在许多网站上成为现实；然而，我国传统的物流体系是在计划经济环

3、境下建立、发展起来的，与目前的电子商务环境已经无法相容。现今物流体系的落后现状已经成为我国社会经济快速发展的重要制约因素之一。所以对物流系统优化的研究将会具有很大的现实意义。国外许多学者在电子商务出现之前就已经研究物流系统优化的问题了，为各类实际问题构建了优化模型，并形成了许多解决问题的算法。依据实际问题的不同，可以对物流系统优化问题进行分类，比如，运输车辆路线安排问题（vrp）、定位配给问题（la）、定位运输路线安排问题（lrp）等等，其中lrp更贴近目前的物流系统复杂的实际特征，所以对它的研究是十分有意义的。本文先从vrp和la的集成来探讨lrp的由来，然后讨论lrp的分类，同时探讨lrp

4、的研究现状，并对lrp的解决方法进行概述，最后就lrp的未来发展方向作简要的讨论。2 从vrp、la到lrp物流系统的集成依据实际问题的不同，可以对物流系统优化问题进行分类，比如确定设施（指的是物品流动的出发点和终到点，如配送中心、仓库、生产工厂、垃圾回收中心等）位置、运输路线安排、库存控制等，国内外许多学者就各类问题的特征进行了分析，并提出了各类问题的数学模型和解决方法。2.1 运输车辆路线安排问题（vehicle routing problems vrp）该问题可定义为：运输车辆从一个或多个设施到多个地理上分散的客户点，优化设计一套货物流动的运输路线，同时要满足一系列的约束条件。该问题的前

5、提条件是设施位置、客户点位置和道路情况已知，由此确定一套车辆运输路线，以满足目标函数（通常，vrp的目标函数是总费用最小）。如图1所示。图中，表示设施；表示客户；表示运输路线图1 vrp的图示实际上，vrp是按如下假设定义的最小费用问题1：（1） 所有车辆路线均起始并终止于设施点。（2） 每个客户只接受一个设施的货物。（3） 满足其他一些约束条件，如： 容量限制：每个客户点上都有一个非负的货物需求量，但每条车辆路线上的货物量总和不超过车辆装载量。如果此约束不满足，则引入惩罚函数。 总时间限制：每条路线总的长度或总耗时不超过一个事先定下的数值。这项限制旨在满足客户对供货时间的要求，以及对货物品质

6、的保证。 具体时间限制：对某个客户点，车辆到达时间限制在某一时间段内。此约束在于满足客户对供应/回收的特殊要求。 车辆到达顺序要求：如在到达i点之前要求先到达j点。以上列出的约束只是该问题一部分，具体操作时要视具体情况而定。对vrp的求解算法可分为精确算法和启发式算法两种。其中精确算法包括树状寻优算法、动态规划和整数规划。vrp的启发式算法多是来源于对tsp问题的求解算法。比如局部优先算法、插值法等可以不用修改地用于一些vrp。2.2 定位配给问题（location-allocation problems, la）定位一配给问题可定义为：依据客户点的地理分布与货物分配关系，确定出某一地理范围内

7、设施的数量和位置。如图2所示。图中，表示设施；表示客户；表示运输路线图2 la的图示la实质上是一个依据优化路径的原则来确定在什么地方设置设施的过程2。例如，在一个城镇中设立一个急救中心，这个问题就是一个典型的la问题。它的目标就是使得全镇的居民到医疗中心的路径（时间）总体上最短。根据john current等学者对此问题的综述研究3，把la问题进行了分类。current的方法是根据问题的目标函数来分类的，作为分类依据的目标函数共分四种： (1) 费用最小化； (2) 客户需求导向； (3) 利润最大化； (4) 其他相关考虑。2.3 定位一运输路线安排问题（location-routing

8、problems,lrp）当今物流系统的环境日趋复杂，而且物流地理分布也不断扩大。物流系统优化问题的各个子系统（比如设施定位问题、物品配送问题、运输车辆路线安排问题等）之间的相互影响也越来越大。对许多实际问题，要综合考虑以上问题，这就形成了定位一路线安排问题（lrp）。lrp可以表述为：给定与实际问题相符的一系列客户点和一系列潜在的设施点，在这些潜在的点中确定出一系列的设施位置，同时要确定出一套从各个设施到各个客户点的运输路线，确定的依据是满足问题的目标（通常是总的费用最小）。客户点的位置和客户的需求量是已知的或可估算的，货物有一个或多个设施供应，每个客户只接收来自一个设施的货物，潜在设施点位

9、置已知，问题的目标是把哪些潜在的设施建立起来，以使的总的费用最小。lrp可图示为图3。可以说lrp是la与vrp的集成4，但比后两者更复杂。la在定位时考虑的是运输车辆从设施点到一个客户点后，随即返回设施点，所以它不考虑路线安排问题5。la在确定出设施点后的图形是从设施点到客户点的射线族。而lrp则在定位时同时确定运输路线。lrp与vrp的不同之处是：vrp的前提条件是设施点和客户点在空间上的分布是已知的；lrp所研究的问题只知道潜在的设施点，在确定运输路线的同时要确定设施的位置。图中，表示设施；表示未被选中的设施；表示客户点；表示运输路线图3 lrp的图示在实际物流系统的集成的特征日益突出之

10、前，就已经有人研究lrp了。最早的研究可以追溯到20世纪60年代，当时有些学者已经提出一些类似的概念了6-8。到了70年代，cooper9, 10把定位问题与运输问题结合起来，提出了运输一定位问题（transportation-location problem）。在这个阶段，学者们对lrp的研究还是相当肤浅的，还没有真正涉及运输路线安排问题。到了70年代中期，一些学者在研究运输一定位问题时，开始加入vrp的多点运输的特征，watson-gandy和dohrn11是最早进行这方面工作的学者。直到70年代末，80年代初，才开始有了真正意义的lrp12-14。这些研究成果是伴随着集成物流系统概念的出

11、现而出现的。3 lrp的分类hokey min等学者对lrp进行了详细的分类15，其分类标准十分详尽，几乎包含了lrp的各个方面。表1 lrp的分类标准分类标准ab1物品流向单向双向2供/需特征确定随机3设施数量单个设施多设施4运输车辆数量单个车辆多车辆5车辆装载能力不确定确定6设施容量不确定确定7设施分级单级多级8计划期间单期多期9时间限制无时间限制有时间限制10目标数单目标多目标11模型数据类型假设值实际值hokey的分类是依据问题的特征进行的，具体如表1。表1中，各分类标准解释如下：（1） 物品流向，单向物品流向问题指的是所有设施只进行输入（供应）或只进行输出（回收）的操作；而双向物品流

12、向问题涉及的设施中有一部分既要输入又要输出。（2） 供/需特征，确定型的是指物品供应/需求量是已知的并在一定时期内相对稳定；随机型的是指供应/需求量是不确定的。（3） 设施数量，指所研究问题要求设置设施的数量，分为单一设施和多设施两种。（4） 运输工具数量，是指有多少车辆为一个设施服务的标准，同时也确定了一个从设施出发的路线数。分为单一车辆和多车辆两种。（5） 车辆装载能力，是指是否要考虑车辆装载能力的限制。不确定定型是指对这个问题所涉及的每条路线上的货物总量很小，不会超出车辆的装载量，所以不用考虑车辆的装载能力的限制；确定型是指每条路线上的货物总量有可能超出车辆的装载能力，所以要把车辆的装载

13、限制作为一个参数引入问题。（6） 设施容量，是指是否考虑各个设施容量的限制。分为不确定型和确定型两种。（7） 设施分级，可以把设施分为两种：总站型和中间转运站型。总站型设施是指那些车辆路线的出发点或终点；中间转运站型设施是指物品的中间站，货物运入后还要运出。有了中间转运站，就产生了设施分级的问题，货物从总站型设施运入中间转运站型设施，经过简单处理后运到客户点。单级设施问题是指不考虑设施的分级，所有设施均为同级；而多级中心设施问题则要考虑设施的分级。（8） 计划期间，单期间问题把整个期间作为一个时间段，是静态问题；多期间问题把整个时间段按问题要求分为多个期间，是动态问题。（9） 时间限制，主要是

14、指满足客户要求或货物品质要求，而对lrp的从设施点到客户点的时间约束。分为无时间约束和有时间约束两种。（10） 目标数量，lrp的目标通常是总的费用（包括建设设施费用和车辆运输费用等）最小，但有时也需要考虑其他目标，比如满足顾客的特殊需要、总体利润量大化等等。如果是多目标问题，经常会出现各目标之间的冲突。（11） 模型数据类型，在有些情况下，模型中的数据（如物品供/需量等）是来源于实际的；而有些情况下，这些数据是在实际中不可得的，需要对其进行假设。根据模型数据类型的不同，把lrp分成假设型和实际型两类。4 lrp的解决方法国外许多学者对lrp的解决方法进行了有益的探讨，所采用的方法可以分为两种

15、：精确算法和启发式算法。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 po

16、lynomial hard)问题，所以，在大多数情况下，要用精确算法来解决lrp是十分困难的。例如，在一个物流系统中，有3个潜在的中心点，8个分布的客户点，3条行车路线，如果用整数规划来解决，要涉及的变量会达到333个16。实际上，以上的物流系统是十分小的，在实践中遇到的系统规模往往会远超过它。很多情况下要引入启发式算法。lrp往往是十分复杂的，需要采用多级分解方法对其简化。目前解决lrp的启发式算法多采用以下四种方法或是它们的组合：（1） 先解决定位一配给问题，然后解决运输路线安排问题15, 21；（2） 先解决运输路线安排问题，然后解决定位一配给问题22；（3） 费用降低/插入算法23,

17、24；（4） 路线扩展交换算法。很多情况下精确的优化算法仅仅是作为一种参照的基准，在研究lrp时比较各种启发式算法的优劣。而在解决实际规模问题时一般要采用启发式算法。5 lrp的未来研究方向实际物流系统集成的程度越来越高，物流决策者面临的问题也就越来越复杂。用目前lrp的研究成果来解决特别复杂的物流系统优化问题还存在许多局限。未来对lrp的研究将会集中于以下难点：5.1 动态性许多lrp的参数是随时间变化的，如库存费用会随员工的人数、员工的工资水平等因素的变化而变化；运输费用也会因车辆装载情况、油料费用等的改变而改变。所以lrp具有动态性，对动态lrp的研究是有现实意义的。运筹学理论被认为是解

18、决优化问题十分有效的工具。但是如果实际问题发生变化，就会引起数学模型改变和模型求解程序的改变。对于动态问题，这种连锁反应是时时刻刻都在发生的。因而用传统的运筹学理论解决动态的优化问题会力不从心。其原因是传统的运筹学理论缺乏基于知识的推理机制和处理动态问题的自适应能力。为了克服这一缺陷，八十年代以来国内外学者将人工智能和知识工程理论引入运筹学,开辟了智能运筹学25, 26这一新的研究方向。使运筹学由过去的仅能解决静态问题变为可以解决动态问题，它必将有助于动态lrp的求解5.2 实时调控在实际情况下，特别是在如今被广泛重视的电子商务物流的实施过程中，商品供货点、运输工具、运输路径和送货时间等需要实

19、时作出决择。这就涉及到实时调控的问题。近年来，agent技术发展迅速，agent具有的自主性、主动性、反应性和智能性为改进基于运筹学知识表示理论的动态问题的实时优化控制系统创造了条件。将agent技术与运筹学理论有机结合和交叉渗透，必将对最终解决实际规模lrp有决定性的意义。 5.3 随机性在实践中，物品的供应/需求量、客户点位置、车辆行驶时间等等在很多情况下是不能事先确定的，这些参数就带有随机性。把随机性引入lrp，更有利于解决实际问题。已经有许多学者对随机性lrp进行了研究，如laporte等人29对供应/需求量不确定的lrp作了探讨。他们提出了一种两阶段算法：第一阶段，在供应/需求量未知

20、的情况下，确定中心位置、运输路线、车队数量；第二阶段，由于一条路线上的供应/需求量有可能超出车辆的装载能力，车辆在某点装满时要返回中心点装货/卸货，然后回到返回点恢复运输，以上的车辆操作产生了惩罚项。为了解决这类问题，引入两种方法：（1）在保证出现车辆返回的概率不小于某一预定值的情况下，确定第一阶段值。（2）在保证由于车辆返回而产生的费用不超过某一预定费用的情况下，确定第一阶段值。这类问题就可以采用整数规划来解决了。5.4 时间限制实际的物流系统中，许多情况下，客户对车辆的到达时间是有限制的。这种时间的限制又可以分为硬限制和软限制两种，硬限制要求时间的一点，软限制指定一段时间。但是，到目前为止

21、，对lrp的研究很少考虑对时间的限制。这方面的研究将会是有益的。5.5 多目标性物流系统中的各个目标之间会产生冲突，如按照总费用最小目标确定的方案，在满足客户对时间要求的目标时，可能会不合要求。然而，实际物流系统均有多目标的特征。所以以后对lrp的研究中会注重多目标之间优化。6 结论本文对物流系统中的lrp的由来、分类、解决方法作了简要的评述，并对lrp的未来研究方向作了分析。对lrp的研究还存在许多没有很好解决的方面。对lrp的研究将会越来越向符合实际情况的方向发展。参考文献1 gilbert laporte. the vehicle routing problem : an overvie

22、w 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, 5(2) : 103-1183 john current, h. min, d.a. schilling. multiobjective a

23、nalysis of facility location decisions. european journal of operational research, 1990, 49 : 295-3074 汪寿阳, 赵秋红, 夏国平. 集成物流管理系统中的定位运输线路安排问题的研究. 管理科学学报, 2000, 3(2) : 69-755 s. salhi, g.k. rand. the effect of ignoring routes when locating deports. european journal of operational research, 1989, 39 : 150

24、-1566 maranzana f.e. on the location of supply points to minimize transport cost. operational research quarterly,1965,(15) : 261-2707 m.h.j. webb. cost functions in the location of deports for multiple-delivery journeys. operational research quarterly, 1968, (19) : 311-3208 n.christofides, s.eilton.

25、 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 transportation location problem. journal of region

26、al science, 1976, 16(3) : 309-31511 c.watson-gandy, p.dohrn. depot location with van salesman a practical approach. omega, 1973, 1(3) : 321-32912 i.or, w.p.pierskalla. a transportation, location allocation model for regional blood banking. aiie transactions, 1979, 11(2) : 86-9513 jacobson.s.k., mads

27、en. 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 minimizing routing and operating costs in depot location . european journal of operational research,1981,6:22

28、4-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 distribu

29、tion system design. computers & operations research, 1990, 17 : 427-43517 i.averbakh, o.berman. routing and location routing p-delivery man problems on a path. transportation science, 1994, 28(2) : 162-16618 c.revelle, j.cohon, d.shobrys. simultaneous siting and routing in the disposal of hazardous

30、wastes. transportation science, 1991, 25(2) : 138-14519 g.laporte, y. nobert, d.arpin. an exact algorithm for 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 obnoxio

31、us facility. transportation science, 1993, 27(4) : 350-36221 j.h.bookbinder, k.e.reece. vehicle routing considerations in distribution system design. european journal of operational research, 1988, 37 : 204-21322 j.perl, m.s.daskin. a warehouse location routing problem. transportation research, 1985

32、, 19b(5) : 381-39623 t.w.chien. heurristic procedures for practical sized uncapacitated location capacitated routing problems. decision sciences, 1993, 24(5) : 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. artificial intelligence - an overview of similarities with o.r. journal of operational research society, 1986, 37(1) : 13-2026 胡祥培, 杨德礼. 智能运筹学与动态系统实时优化控制. 经济管理与社会科学前沿研究2000年中国博士后学术