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

管理科学和系统科学研究的新进展第6届全国青少年管理科学系统科学学术会议论文集2001大连物流系统优化的定位运输路线布局问题(LRP)研究回顾*国家自然科学基金重点项目()林岩胡尚菲* *林岩，硕士，1972年出生，主要研究方向：电子商务，信息系统工程。胡相培，1962年出生，教授，指导，主要研究方向：电子商务，智能运营研究，信息系统集成。(大连理工大学系统工程研究所)摘要本文简要介绍了物流优化问题的定位-定位-路由方案(LRP)的发展过程，探讨了LRP的分类和解决方法，然后简要回顾了该问题的发展方向。关键词LRP物流系统优化运行研究引言1新技术的快速发展，特别是电子商务的兴起，为我国经济的快速发展提供了契机。目前，我们的电子商务得到政府和国民的支持，呈现出强大的增长势头，但这是一种全新的技术，同时也是一种全新的经营哲学，因此发展过程中必然会出现一些难题。在电子商务“三流”(信息流、物流、资金流)中，随着网络基础设施建设的成熟、电子商务网站的快速发展、网络资源概念的有效利用的普及，信息流的发展更加成熟。随着大型银行开展在线业务，结算网关的构建和加密技术成熟，在线支付在很多网站上成为现实。但是我国传统的物流系统是在计划经济环境下建立和发展的，与当前的电子商务环境已经不相容了。当今物流体系的落后现状成为我国社会经济快速发展的重要制约因素之一。因此对物流系统优化的研究将具有现实意义。很多外国学者在出现电子商务之前就研究了物流系统优化问题，建立了各种实际问题的优化模型，形成了解决问题的很多算法。根据实际问题分类物流系统优化问题，例如运输工具路由问题(VRP)、定位-分配问题(LA)、定位-运输路线布局问题(LRP)等。在这里，LRP更接近于当前物流系统的复杂实际特征，因此对此的研究非常重要。本文首先讨论了LRP在VRP与LA集成中的起源，然后讨论了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定位-分配问题(LA)定位问题可以定义为根据客户地点的地理分布和商品分配关系确定特定地区的设施数量和位置。如图2所示。在图中表示设施。表示客户。表示运输路线图2 LA中的图标LA本质上是根据路径优化原则决定在何处安装设施的过程2。例如，在一个城市建立紧急中心是典型的洛杉矶问题。其目标是使把村民送到医疗中心的途径(时间)总体上最短。根据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研究的问题只知道潜在的设施地点，在确定运输路线的同时确定设施的位置。在图中表示设施。表示未选定的设施。122950表示客户地点。表示运输路线图3 LRP图标在实际物流系统的集成特性出现之前，对LRP进行了研究。早期研究可以追溯到20世纪60年代，当时一些学者已经提出了类似的概念6-8。到了70年代，Cooper9，10将定位问题与运输问题结合起来，提出了运输定位问题。现阶段学者对LRP的研究仍然相当肤浅，还没有真正涉及运输路线布局问题。到了20世纪70年代中期，有些学者开始研究运输定位问题，加入VRP，沃森-甘迪和多恩11是第一个完成这类工作的学者。直到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)设施等级可以将设施分为终点站和中间转运站两种。终点站设施意味着该车辆路线的起点或终点。中间转站型设备是指货物的中间站，货物必须在运输后发运。中间转运站出现了设施分类问题，货物从终点站型设施转移到中间转运站型设施，经过简单处理，运输到客户地点。单层设施问题意味着不考虑设施的等级，所有设施都处于同一级别；多层次中心设施问题需要考虑设施的等级。(八)计划期间，单个期间问题是整个期间，静态问题；多期间问题根据问题要求将整个期间划分为多个期间是动态问题。(9)主要满足客户要求或商品质量要求，而对LRP的设施到客户地点的时间限制。时间限制和时间限制。(10)目标数、LRP的目标通常是建设设施成本和车辆运输成本等总成本最低的情况，但有时还需要考虑其他目标，例如满足客户的特殊要求、最大化整体利益等。如果是多目标问题，则目标之间经常发生冲突。(11)在某些情况下，模型中的数据(例如物料供应/需求等)是从实际值导出的模型数据类型。在某些情况下，这些数据实际上是不可能的，需要对此进行假设。LRP根据模型数据类型分为假定类型和实际类型。4 LRP解决方案国外很多学者对LRP的解决方法进行了有益的讨论，使用的方法可以分为精确算法和启发式算法两种。解决4.1 LRP的精确算法基于运营研究优化算法求解LRP的精确算法可以分为以下四种：(1)直接树搜索1；(2)动态计划117；(3)整数编程1819；(4)非线性程式设计20。上述算法中最常用的是整数编程，包括混合整数编程，特别是最有效的解决方法是分支-边界方法。使用分割-边界方法的LRP需要限制模型中的设施数，因此计算时间不会太长。随着相关LRP的规模扩大，精确的算法不实用。求解4.2 LRP的启发式算法LRP是LA问题与VRP相结合后的非分布式多用途hard(NP-hard)问题，因此在大多数情况下，很难用精确的算法解决LRP。例如，在一个物流系统中，有3个潜在的中心点、8个分散的客户地点和3个行车路径，在整数计划解决的情况下，要处理的变量为333 16。实际上，上述物流系统非常小，实际发生的系统规模往往比它大得多。经常引入启发式算法。LRP经常非常复杂，必须使用多阶段分解方法进行简化。解决LRP的启发式方法使用以下四种方法或其组合：(1)先解决1分配问题，然后运输路线分配问题15，21；(2)先解决运输路线布局问题，然后解决一线布局问题22；(3)成本节约/插入算法23，24；(4)路径扩展切换算法。在很多情况下，精确的优化算法只是一种参考标准，在研究LRP时比较了各种启发式算法的优缺点。在解决实际规模问题时，通常使用启发式算法。5 LRP的未来研究方向随着实际物流系统集成水平的日益提高物流决策者面临的问题也越来越复杂使用当前的LRP研究结果解决特别复杂的物流系统优化问题仍然存在很多局限性。今后对LRP的研究将侧重于以下困难：5.1动态许多LRP的参数会随时间而变化。例如，库存成本可能取决于员工数、员工薪金水平等因素。运输费用也取决于车辆装载情况、燃料费等。所以LRP是动态的，对动态LRP的研究是现实的。运营研究理论被认为是解决优化问题的非常有效的工具。但是，当实际问题发生变化时，数学模型的变化和模型求解器的变化也会发生。对于动态问题，这种连锁反应时时刻刻都在发生。因此，用传统的运营研究理论解决动态优化问题可能是远远不够的。传统的运营研究理论是因为缺乏处理基于知识的推理机制和动态问题的适应性。为了克服这一缺陷，80年代以来国内外学者将人工智能和知识工程理论引入运营研究，开创了