物流系统优化管理方案样本.doc

物流系统优化中定位—运输路线安排问题
（ＬＲＰ）研究评述* 国家自然科学基金关键项目(70031020)

摘要 本文概述了物流优化问题中定位—运输路线安排问题（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年代，Cooper[9, 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分类标准

分类标准
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) 动态计划[1][17]；
(3) 整数计划[18][19]；
(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 汪寿阳, 赵秋红, 夏国平. 集成物流管理系统中定位——运输线路安排问题研究. 管理科学学报, , 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 comparative 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. Combined 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. Computers & 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 胡祥培, 杨德礼. 智能运筹学和动态系统实时优化控制. 经济管理和社会科学前沿研究—中国博士后学术大会经济管理和人文社会分会暨全国博士后第四届经济学管理学学术会议论文集, 中国金融出版社, 10月出版:137-148
27 Hu Xiangpei. 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 Location—Routing Problems (LRP) in Systematic Optimization of Logistics

Lin Yan Hu Xiangpei
(Institute of System Engineering, Dalian University of Technology)

Abstract This paper reviews the development of the Location–Routing 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