物流系统优化中的定位

1、（物流管理）物流系统优化中的定位20XX年XX月多年的企业咨询豉问经验.经过实战验证可以落地机行的卓越管理方案，值得您下载拥有物流系统优化中的定位一运输路线安排问题（LRP）研究评述摘要本文概述了物流优化问题中的定位一运输路线安排问题（Location-RoutingProblems,LRP）的发展历程，且对LRP的分类和解决方法加以评述，最后就这壹问题的发展方向进行简单地探讨。关键词LRP物流系统优化运筹学1引言新技术的迅速发展，特别是电子商务的风起云涌，为我国经济的快速发展提供了契机。目前我国电子商务得到政府和民众的支持，发展势头强劲，可是，由于它是壹套全新的技术，同时仍是壹种全新的管理理

2、念，所以其发展过程中必然存于壹些难题。于电子商务“三流”（信息流、物流、资金流）中，随着网络基础设施建设的成熟、电子商务网站的蓬勃发展以及有效利用网络资源观念的普及，信息流的发展已经比较成熟了；而随着各大银行纷纷开展网上业务，以及支付网关的建立和加密技术的成熟，网上支付已经于许多网站上成为现实；然而，我国传统的物流体系是于计划经济环境下建立、发展起来的，和目前的电子商务环境已经无法相容。现今物流体系的落后现状已经成为我国社会经济快速发展的重要制约因素之壹。所以对物流系统优化的研究将会具有很大的现实意义。国外许多学者于电子商务出现之前就已经研究物流系统优化的问题了，为各类实际问题构建了优化模型，

3、且形成了许多解决问题的算法。依据实际问题的不同，能够对物流系统优化问题进行分类，比如，运输车辆路线安排问题（VRP）、定位一配给问题（LA）、定位一运输路线安排问题（LRP）等等，其中LRP更贴近目前的物流系统复杂的实际特征，所以对它的研究是十分有意义的。本文先从VRP和LA的集成来探讨LRP的由来，然后讨论LRP的分类，同时探讨LRP的研究现状，且对LRP的解决方法进行概述，最后就LRP的未来发展方向作简要的讨论。2从VRP、LA到LRP物流系统的集成依据实际问题的不同，能够对物流系统优化问题进行分类，比如确定设施（指的是物品流动的出发点和终到点，如配送中心、仓库、生产工厂、垃圾回收中心等）

4、位置、运输路线安排、库存控制等，国内外许多学者就各类问题的特征进行了分析，且提出了各类问题的数学模型和解决方法。2.1运输车辆路线安排问题（VehicleRoutingProblemsVRP）该问题可定义为：运输车辆从壹个或多个设施到多个地理上分散的客户点，优化设计壹套货物流动的运输路线，同时要满足壹系列的约束条件。该问题的前提条件是设施位置、客户点位置和道路情况已知，由此确定壹套车辆运输路线，以满足目标函数（通常，VRP的目标函数是总费用最小）。如图1所示。图1VRP的图示实际上，VRP是按如下假设定义的最小费用问题1:(1)所有车辆路线均起始且终止于设施点(2)每个客户只接受壹个设施的货物

5、。(3)满足其他壹些约束条件，如：容量限制：每个客户点上均有壹个非负的货物需求量，但每条车辆路线上的货物量总和不超过车辆装载量。如果此约束不满足，则引入惩罚函数。,总时间限制：每条路线总的长度或总耗时不超过壹个事先定下的数值。这项限制旨于满足客户对供货时间的要求，以及对货物品质的保证。具体时间限制：对某个客户点，车辆到达时间限制于某壹时间段内。此约束于于满足客户又共应/回收的特殊要求。4辆到达顺序要求：如于到达i点之前要求先到达j点。之上列出的约束只是该问题壹部分，具体操作时要视具体情况而定。对VRP的求解算法可分为精确算法和启发式算法俩种。其中精确算法包括树状寻优算法、动态规划和整数规划。V

6、RP的启发式算法多是来源于对TSP问题的求解算法。比如局部优先算法、插值法等能够不用修改地用于壹些VRP。2.2 定位一配给问题(Location-AllocationProblems,LA)定位壹配给问题可定义为：依据客户点的地理分布和货物分配关系，确定出某壹地理范围内设施的数量和位置。如图2所示。OOO图中，口表示设施；。表示客户；/表示运输路线2LA的图示LA实质上是壹个依据优化路径的原则来确定于什么地方设置设施的过程2。例如，于壹个城镇中设立壹个急救中心，这个问题就是壹个典型的LA问题。它的目标就是使得全镇的居民到医疗中心的路径(时间)总体上最短。根据JohnCurrent等学者对此问

7、题的综述研究3，把LA问题进行了分类。Current的方法是根据问题的目标函数来分类的，作为分类依据的目标函数共分四种：(1) 费用最小化；(2) 客户需求导向；(3) 利润最大化；(4) 其他关联考虑。2.3 定位壹运输路线安排问题(Location-Routingproblems,LRP)当今物流系统的环境日趋复杂，而且物流地理分布也不断扩大。物流系统优化问题的各个子系统(比如设施定位问题、物品配送问题、运输车辆路线安排问题等)之间的相互影响也越来越大。对许多实际问题，要综合考虑之上问题，这就形成了定位壹路线安排问题(LRP)。LRP能够表述为：给定和实际问题相符的壹系列客户点和壹系列潜于

8、的设施点，于这些潜于的点中确定出壹系列的设施位置，同时要确定出壹套从各个设施到各个客户点的运输路线，确定的依据是满足问题的目标(通常是总的费用最小)。客户点的位置和客户的需求量是已知的或可估算的，货物有壹个或多个设施供应，每个客户只接收来自壹个设施的货物，潜于设施点位置已知，问题的目标是把哪些潜于的设施建立起来，以使的总的费用最小。LRP可图示为图3。能够说LRP是LA和VRP的集成4，但比后俩者更复杂。LA于定位时考虑的是运输车辆从设施点到壹个客户点后，随即返回设施点，所以它不考虑路线安排问题5。LA于确定出设施点后的图形是从设施点到客户点的射线族。而LRP则于定位时同时确定运输路线。LRP

9、和VRP的不同之处是：VRP的前提条件是设施点和客户点于空间上的分布是已知的；LRP所研究的问题只知道潜于的设施点，于确定运输路线的同时要确定设图中，口表示设施；表示未被选中的设施；0表示客户点；/表示运输路线图3LRP的图示于实际物流系统的集成的特征日益突出之前，就已经有人研究LRP了。最早的研究能够追溯到20世纪60年代，当时有些学者已经提出壹些类似的概念了6-8。到了70年代，Cooper9，10把定位问题和运输问题结合起来，提出了运输壹定位问题(Transportation-Locationproblem)。于这个阶段，学者们对LRP的研究仍是相当肤浅的，仍没有真正涉及运输路线安排问题

10、。到了70年代中期，壹些学者于研究运输壹定位问题时，开始加入VRP的多点运输的特征，Watson-Gandy和Dohrn11是最早进行这方面工作的学者。直到70年代末，80年代初，才开始有了真正意义的LRP12-14。这些研究成果是伴随着集成物流系统概念的出现而出现的。3LRP的分类HokeyMin等学者对LRP进行了详细的分类15,其分类标准十分详尽，几乎包含了LRP的各个方面表1LRP的分类标准分类标准AB1物品流向单向双向2供/需特征确定随机3设施数量单个设施多设施4运输车辆数量单个车辆多车辆5车辆装载能力不确定确定6设施容量不确定确定7设施分级单级多级8计划期间单期多期9时间限制无时间

11、限制有时间限制10目标数单目标多目标11模型数据类型假设值实际值Hokey的分类是依据问题的特征进行的，具体如表1o表1中，各分类标准解释如下：(1)物品流向，单向物品流向问题指的是所有设施只进行输入(供应)或只进行输出(回收)的操作；而双向物品流向问题涉及的设施中有壹部分既要输入又要输出。(2)供/需特征，确定型的是指物品供应/需求量是已知的且于壹定时期内相对稳定;随机型的是指供应/需求量是不确定的。(3)设施数量，指所研究问题要求设置设施的数量，分为单壹设施和多设施俩种（ 4）运输工具数量，是指有多少车辆为壹个设施服务的标准，同时也确定了壹个从设施出发的路线数。分为单壹车辆和多车辆俩种。（

12、 5）车辆装载能力，是指是否要考虑车辆装载能力的限制。不确定定型是指对这个问题所涉及的每条路线上的货物总量很小，不会超出车辆的装载量，所以不用考虑车辆的装载能力的限制；确定型是指每条路线上的货物总量有可能超出车辆的装载能力，所以要把车辆的装载限制作为壹个参数引入问题。（ 6）设施容量，是指是否考虑各个设施容量的限制。分为不确定型和确定型俩种。（ 7）设施分级，能够把设施分为俩种：总站型和中间转运站型。总站型设施是指那些车辆路线的出发点或终点；中间转运站型设施是指物品的中间站，货物运入后仍要运出。有了中间转运站，就产生了设施分级的问题，货物从总站型设施运入中间转运站型设施，经过简单处理后运到客户

13、点。单级设施问题是指不考虑设施的分级，所有设施均为同级；而多级中心设施问题则要考虑设施的分级。（ 8）计划期间，单期间问题把整个期间作为壹个时间段，是静态问题；多期间问题把整个时间段按问题要求分为多个期间，是动态问题。（ 9）时间限制，主要是指满足客户要求或货物品质要求，而对LRP的从设施点到客户点的时间约束。分为无时间约束和有时间约束俩种。（ 10）目标数量，LRP的目标通常是总的费用（包括建设设施费用和车辆运输费用等）最小，但有时也需要考虑其他目标，比如满足顾客的特殊需要、总体利润量大化等等。如果是多目标问题，经常会出现各目标之间的冲突。（ 11）模型数据类型，于有些情况下，模型中的数据（

14、如物品供/需量等）是来源于实际的；而有些情况下，这些数据是于实际中不可得的，需要对其进行假设。根据模型数据类型的不同，把LRP分成假设型和实际型俩类。4LRP的解决方法国外许多学者对LRP的解决方法进行了有益的探讨，所采用的方法能够分为俩种：精确算法和启发式算法。4.1 解决LRP的精确算法基于运筹学的优化算法，解决LRP的精确算法能够分为以下四种：(1) 直接树状搜索1；(2) 动态规划117；(3) 整数规划1819；(4) 非线性规划20。于之上算法中，最为常用的是整数规划(包括混合整数规划),而具体解决时效率最高的方法是分支定界法。它能够于不很长的计算时间内解决多至80个节点的LRP，

15、可是采用分支定界法的LRP必须于其模型中限制设施的数量。壹旦所涉及的LRP的规模扩大，精确算法就不实用了。4.2 解决LRP的启发式算法由于LRP结合了LA问题和VRP，而后俩者均是NP-Hard(NonFeterministicPolynomialhard)问题，所以，于大多数情况下，要用精确算法来解决LRP是十分困难的。例如，于壹个物流系统中，有3个潜于的中心点，8个分布的客户点，3条行车路线，如果用整数规划来解决，要涉及的变量会达到333个16。实际上，之上的物流系统是十分小的，于实践中遇到的系统规模往往会远超过它。很多情况下要引入启发式算法。LRP往往是十分复杂的，需要采用多级分解方法

16、对其简化。目前解决LRP的启发式算法多采用以下四种方法或是它们的组合：（1）先解决定位壹配给问题，然后解决运输路线安排问题15,21；（2）先解决运输路线安排问题，然后解决定位壹配给问题22；（3）费用降低/插入算法23,24；（4）路线扩展交换算法。很多情况下精确的优化算法仅仅是作为壹种参照的基准，于研究LRP时比较各种启发式算法的优劣。而于解决实际规模问题时壹般要采用启发式算法。5LRP的未来研究方向实际物流系统集成的程度越来越高，物流决策者面临的问题也就越来越复杂。用目前LRP的研究成果来解决特别复杂的物流系统优化问题仍存于许多局限。未来对LRP的研究将会集中于以下难点：5.1 动态性许

17、多LRP的参数是随时间变化的，如库存费用会随员工的人数、员工的工资水平等因素的变化而变化；运输费用也会因车辆装载情况、油料费用等的改变而改变。所以LRP具有动态性，对动态LRP的研究是有现实意义的。运筹学理论被认为是解决优化问题十分有效的工具。可是如果实际问题发生变化，就会引起数学模型改变和模型求解程序的改变。对于动态问题，这种连锁反应是时时刻刻均于发生的。因而用传统的运筹学理论解决动态的优化问题会力不从心。其原因是传统的运筹学理论缺乏基于知识的推理机制和处理动态问题的自适应能力。为了克服这壹缺陷，八十年代以来国内外学者将人工智能和知识工程理论引入运筹学,开辟了智能运筹学25,26这壹新的研究

18、方向。使运筹学由过去的仅能解决静态问题变为能够解决动态问题，它必将有助于动态LRP的求解5.2 实时调控于实际情况下，特别是于如今被广泛重视的电子商务物流的实施过程中，商品供货点、运输工具、运输路径和送货时间等需要实时作出决择。这就涉及到实时调控的问题。近年来，Agent技术发展迅速，Agent具有的自主性、主动性、反应性和智能性为改进基于运筹学知识表示理论的动态问题的实时优化控制系统创造了条件。将Agent技术和运筹学理论有机结合和交叉渗透，必将对最终解决实际规模LRP有决定性的意义。5.3 随机性于实践中，物品的供应/需求量、客户点位置、车辆行驶时间等等于很多情况下是不能事先确定的，这些参数就带有随机性。把随机性引入LRP,更有利于解决实际问题。已经有许多学者对随机