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

管理科学与系统科学研究新进展 第 6 届全国青年管理科学与系统科学学术会议论文集 2001 年 大连 437 物流系统优化中的定位物流系统优化中的定位 运输路线安排问题运输路线安排问题 研究评述 研究评述 林岩 胡祥培 大连理工大学系统工程研究所 摘要 本文概述了物流优化问题中的定位 运输路线安排问题 Location Routing Problems LRP 的发展历程 并对 LRP 的分类和解决方法加以评述 最后就这一问题的发展方向进行简单地探讨 关键词 LRP 物流 系统优化 运筹学 1 引言 新技术的迅速发展 特别是电子商务的风起云涌 为我国经济的快速发展提供了契机 目前我国电子商务得到政府和民众的支持 发展势头强劲 但是 由于它是一套全新的技 术 同时还是一种全新的管理理念 所以其发展过程中必然存在一些难题 在电子商务 三流 信息流 物流 资金流 中 随着网络基础设施建设的成熟 电子商务网站的蓬 勃发展以及有效利用网络资源观念的普及 信息流的发展已经比较成熟了 而随着各大银 行纷纷开展网上业务 以及支付网关的建立和加密技术的成熟 网上支付已经在许多网站 上成为现实 然而 我国传统的物流体系是在计划经济环境下建立 发展起来的 与目前 的电子商务环境已经无法相容 现今物流体系的落后现状已经成为我国社会经济快速发展 的重要制约因素之一 所以对物流系统优化的研究将会具有很大的现实意义 国外许多学者在电子商务出现之前就已经研究物流系统优化的问题了 为各类实际问 题构建了优化模型 并形成了许多解决问题的算法 依据实际问题的不同 可以对物流系 统优化问题进行分类 比如 运输车辆路线安排问题 VRP 定位 配给问题 LA 定位 运输路线安排问题 LRP 等等 其中 LRP 更贴近目前的物流系统复杂的实际特征 所以 对它的研究是十分有意义的 本文先从 VRP 和 LA 的集成来探讨 LRP 的由来 然后讨论 LRP 的分类 同时探讨 LRP 的研究现状 并对 LRP 的解决方法进行概述 最后就 LRP 的未来发展方向作简要的讨论 2 从 VRP LA 到 LRP 物流系统的集成 依据实际问题的不同 可以对物流系统优化问题进行分类 比如确定设施 指的是物 品流动的出发点和终到点 如配送中心 仓库 生产工厂 垃圾回收中心等 位置 运输 国家自然科学基金重点项目 林岩 硕士研究生 1972 年出生 主要研究方向 电子商务 信息系统工程 胡祥培 1962 年出生 教授 博导 主要研究方向 电子商务 智能运筹学 信息系统集成 管理科学与系统科学研究新进展 第 6 届全国青年管理科学与系统科学学术会议论文集 2001 年 大连 438 路线安排 库存控制等 国内外许多学者就各类问题的特征进行了分析 并提出了各类问 题的数学模型和解决方法 2 1 运输车辆路线安排问题 Vehicle Routing Problems VRP 该问题可定义为 运输车辆从一个或多个设施到多个地理上分散的客户点 优化设计 一套货物流动的运输路线 同时要满足一系列的约束条件 该问题的前提条件是设施位置 客户点位置和道路情况已知 由此确定一套车辆运输路线 以满足目标函数 通常 VRP 的目标函数是总费用最小 如图 1 所示 图中 表示设施 表示客户 表示运输路线 图 1 VRP 的图示 实际上 VRP 是按如下假设定义的最小费用问题 1 1 所有车辆路线均起始并终止于设施点 2 每个客户只接受一个设施的货物 3 满足其他一些约束条件 如 容量限制 每个客户点上都有一个非负的货物需求量 但每条车辆路线上的货物量 总和不超过车辆装载量 如果此约束不满足 则引入惩罚函数 总时间限制 每条路线总的长度或总耗时不超过一个事先定下的数值 这项限制旨 在满足客户对供货时间的要求 以及对货物品质的保证 具体时间限制 对某个客户点 车辆到达时间限制在某一时间段内 此约束在于满 足客户对供应 回收的特殊要求 车辆到达顺序要求 如在到达 i 点之前要求先到达 j 点 以上列出的约束只是该问题一部分 具体操作时要视具体情况而定 对 VRP 的求解算法可分为精确算法和启发式算法两种 其中精确算法包括树状寻优算 法 动态规划和整数规划 VRP 的启发式算法多是来源于对 TSP 问题的求解算法 比如局 部优先算法 插值法等可以不用修改地用于一些 VRP 管理科学与系统科学研究新进展 第 6 届全国青年管理科学与系统科学学术会议论文集 2001 年 大连 439 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 在定位时考虑的是运输 管理科学与系统科学研究新进展 第 6 届全国青年管理科学与系统科学学术会议论文集 2001 年 大连 440 车辆从设施点到一个客户点后 随即返回设施点 所以它不考虑路线安排问题 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 的分类标准 分类标准AB 1物品流向单向双向 2供 需特征确定随机 3设施数量单个设施多设施 4运输车辆数量单个车辆多车辆 5车辆装载能力不确定确定 6设施容量不确定确定 7设施分级单级多级 8计划期间单期多期 9时间限制无时间限制有时间限制 10目标数单目标多目标 11模型数据类型假设值实际值 管理科学与系统科学研究新进展 第 6 届全国青年管理科学与系统科学学术会议论文集 2001 年 大连 441 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 管理科学与系统科学研究新进展 第 6 届全国青年管理科学与系统科学学术会议论文集 2001 年 大连 442 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 这 管理科学与系统科学研究新进展 第 6 届全国青年管理科学与系统科学学术会议论文集 2001 年 大连 443 一新的研究方向 使运筹学由过去的仅能解决静态问题变为可以解决动态问题 它必将有 助于动态 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 的研究将 会越来越向符合实际情况的方向发展 管理科学与系统科学研究新进展 第 6 届全国青年管理科学与系统科学学术会议论文集 2001 年 大连 444 参考文献 1Gilbert Laporte The vehicle routing problem An overview of exact and approximate algorthms European Journal of Operational Research 1992 59 345 358 2Alant Murray Ross A Gerrard Capacitated service and regional constraints in location allocation modeling Location Science 1997 5 2 103 118 3John Current H Min D A Schilling Multiobjective analysis of facility location decisions European Journal of Operational Research 1990 49 295 307 4汪寿阳 赵秋红 夏国平 集成物流管理系统中的定位 运输线路安排问题的研究 管理科学学报 2000 3 2 69 75 5S Salhi G K Rand The effect of ignoring routes when locating deports European Journal of Operational Research 1989 39 150 156 6Maranzana F E On the location of supply points to minimize transport cost Operational Research Quarterly 1965 15 261 270 7M H J Webb Cost functions in the location of deports for multiple delivery journeys Operational Research Quarterly 1968 19 311 320 8N Christofides S Eilton An algorithm for the vehicle dispatching problem Operational Research Quarterly 1969 20 309 318 9Leon Cooper The Transportation Location Problem Operations Research 1972 20 94 108 10Leon Cooper An efficient heuristic algorithm for the transportation location problem Journal of Regional Science 1976 16 3 309 315 11C Watson Gandy P Dohrn Depot location with van salesman A practical approach Omega 1973 1 3 321 329 12I Or W P Pierskalla A transportation location allocation model for regional blood banking AIIE Transactions 1979 11 2 86 95 13Jacobson 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 14Laporte G Nobert Y A exact algorithm for minimizing routing and operating costs in depot location European Journal of Operational Research 1981 6 224 226 15Hokey Min Vaidyanathan Jayaraman Rajesh Srivastava Combined location routing problems A synthesis and future research direction European Journal of Operational Research 1998 108 1 15 16Rajesh Srivastava W C Benton The location routing problem considerations in physical distribution system design Computers Operations Research 1990 17 427 435 17I Averbakh O Berman Routing and location routing p delivery man problems on a path Transportation Science 1994 28 2 162 166 18C ReVelle J Cohon D Shobrys Simultaneous siting and routing in the disposal of hazardous wastes Transportation Science 1991 25 2 138 145 19G Laporte Y Nobert D Arpin An exact algorithm for solving a capacitated location routing problem 管理科学与系统科学研究新进展 第 6 届全国青年管理科学与系统科学学术会议论文集 2001 年 大连 445 Annals of Operations Research 1986 6 293 310 20C L Stowers U S Paleker Location models with routing considerations for a single obnoxious facility Transportation Science 1993 27 4 350 362 21J H Bookbinder K E Reece Vehicle routing considerations in distribution system design European Journal of Operational Research 1988 37 204 213 22J Perl M S Daskin A warehouse location routing problem Transportation Research 1985 19B 5 381 396 23T W Chien Heurristic procedures for practical sized uncapacitated location capacitated routing problems Decision Sciences 1993 24 5 995 1021 24P 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 25R I phelps Artificial Intelligence An overview of Similarities with O R Journal of Operational Research Society 19