物流系统优化管理方案样本.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年代，Cooper9, 10把定位问题和运输问题结合起来，提出了运输一定位问题（Transportation-Location problem）。在这个阶段，学者们对LRP研究还是相当肤浅，还没有真正包含运输路线安排问题。到了70年代中期，部分学者在研究运输一定位问题时，开始加入VRP多点运输特征，Watson-Gandy和Dohrn11是最早进行这方面工作学者。直到70年代末，80年代初，才开始有了真正意义LRP12-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-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-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 analysis of facility location decisions. European Journal of Operational Research, 1990, 49 : 295-3074 汪寿阳, 赵秋红, 夏国平. 集成物流管理系统中定位运输线路安排问题研究. 管理科学学报, , 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-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. 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 Regional 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., 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 minimizing routing 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. Transportation Science, 1994, 28(2) : 162-16618 C.ReVelle, J.Cohon, D.Shobrys. Simultaneous siting and routing in the disposal of hazardous 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 obnoxious 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, 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 胡祥培, 杨德礼. 智能运筹学和动态系统实时优化控制. 经济管理和社会科学前沿研究中国博士后学术大会经济管理和人文社会分会暨全国博士后第四届经济学管理学学术会议论文集, 中国金融出版社, 10月出版:137-14827 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. 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 Yan Hu Xiangpei (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