物流系统优化中的定位-运输路线安排问题
物流系统优化中的定位—运输路线安排问题 （ＬＲＰ）研究评述( 林岩 胡祥培(( （大连理工大学系统工程研究所, 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的前提条件是设施点和客户点在空间上的分布是已知的；L RP所研究的问题只知道潜在的设施点，在确定运输路线的同时要确定设施的位置。 图中，□表示设施；△表示未被选中的设施；?表示客户点；↗表示运输路线 图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的研究是有现实意义的。 运筹学理论被认为是解决优化问题十分有效的工具。但是如果实际问题发生变化，就 会引起数学模型改变和模型求解程序的改变。对于动态问题，这种连锁反应是时时刻刻 都在发生...
物流系统优化中的定位-运输路线安排问题