《《精编》关于运输路线安排问题研究评述》由会员分享，可在线阅读，更多相关《《精编》关于运输路线安排问题研究评述（8页珍藏版）》请在金锄头文库上搜索。
1、物流系统优化中的定位运输路线安排问题（）研究评述* 国家自然科学基金重点项目(70031020)林岩 胡祥培* 林岩, 硕士研究生, 1972年出生, 主要研究方向: 电子商务, 信息系统工程。 胡祥培, 1962年出生, 教授,博导, 主要研究方向: 电子商务, 智能运筹学, 信息系统集成。 （大连理工大学系统工程研究所, 116023）摘要 本文概述了物流优化问题中的定位运输路线安排问题（Location-Routing Problems, LRP）的发展历程，并对LRP的分类和解决方法加以评述，最后就这一问题的发展方向进行简单地探讨。关键词 LRP 物流 系统优化 运筹学1 引言新技术的
2、迅速发展，特别是电子商务的风起云涌，为我国经济的快速发展提供了契机。目前我国电子商务得到政府和民众的支持，发展势头强劲，但是，由于它是一套全新的技术，同时还是一种全新的管理理念，所以其发展过程中必然存在一些难题。在电子商务“三流”（信息流、物流、资金流）中，随着网络基础设施建设的成熟、电子商务网站的蓬勃发展以及有效利用网络资源观念的普及，信息流的发展已经比较成熟了；而随着各大银行纷纷开展网上业务，以及支付网关的建立和加密技术的成熟，网上支付已经在许多网站上成为现实；然而，我国传统的物流体系是在计划经济环境下建立、发展起来的，与目前的电子商务环境已经无法相容。现今物流体系的落后现状已经成为我国社
3、会经济快速发展的重要制约因素之一。所以对物流系统优化的研究将会具有很大的现实意义。国外许多学者在电子商务出现之前就已经研究物流系统优化的问题了，为各类实际问题构建了优化模型，并形成了许多解决问题的算法。依据实际问题的不同，可以对物流系统优化问题进行分类，比如，运输车辆路线安排问题（VRP）、定位配给问题（LA）、定位运输路线安排问题（LRP）等等，其中LRP更贴近目前的物流系统复杂的实际特征，所以对它的研究是十分有意义的。本文先从VRP和LA的集成来探讨LRP的由来，然后讨论LRP的分类，同时探讨LRP的研究现状，并对LRP的解决方法进行概述，最后就LRP的未来发展方向作简要的讨论。2 从VR
4、P、LA到LRP物流系统的集成依据实际问题的不同，可以对物流系统优化问题进行分类，比如确定设施（指的是物品流动的出发点和终到点，如配送中心、仓库、生产工厂、垃圾回收中心等）位置、运输路线安排、库存控制等，国内外许多学者就各类问题的特征进行了分析，并提出了各类问题的数学模型和解决方法。2.1 运输车辆路线安排问题（Vehicle Routing Problems VRP）该问题可定义为：运输车辆从一个或多个设施到多个地理上分散的客户点，优化设计一套货物流动的运输路线，同时要满足一系列的约束条件。该问题的前提条件是设施位置、客户点位置和道路情况已知，由此确定一套车辆运输路线，以满足目标函数（通常，
5、VRP的目标函数是总费用最小）。如图1所示。图中，表示设施；表示客户；表示运输路线图1 VRP的图示实际上，VRP是按如下假设定义的最小费用问题1：（1） 所有车辆路线均起始并终止于设施点。（2） 每个客户只接受一个设施的货物。（3） 满足其他一些约束条件，如： 容量限制：每个客户点上都有一个非负的货物需求量，但每条车辆路线上的货物量总和不超过车辆装载量。如果此约束不满足，则引入惩罚函数。 总时间限制：每条路线总的长度或总耗时不超过一个事先定下的数值。这项限制旨在满足客户对供货时间的要求，以及对货物品质的保证。 具体时间限制：对某个客户点，车辆到达时间限制在某一时间段内。此约束在于满足客户对供
6、应/回收的特殊要求。 车辆到达顺序要求：如在到达i点之前要求先到达j点。以上列出的约束只是该问题一部分，具体操作时要视具体情况而定。对VRP的求解算法可分为精确算法和启发式算法两种。其中精确算法包括树状寻优算法、动态规划和整数规划。VRP的启发式算法多是来源于对TSP问题的求解算法。比如局部优先算法、插值法等可以不用修改地用于一些VRP。2.2 定位配给问题（Location-Allocation Problems, LA）定位一配给问题可定义为：依据客户点的地理分布与货物分配关系，确定出某一地理范围内设施的数量和位置。如图2所示。图中，表示设施；表示客户；表示运输路线图2 LA的图示LA实质
7、上是一个依据优化路径的原则来确定在什么地方设置设施的过程2。例如，在一个城镇中设立一个急救中心，这个问题就是一个典型的LA问题。它的目标就是使得全镇的居民到医疗中心的路径（时间）总体上最短。根据John Current等学者对此问题的综述研究3，把LA问题进行了分类。Current的方法是根据问题的目标函数来分类的，作为分类依据的目标函数共分四种： (1) 费用最小化； (2) 客户需求导向； (3) 利润最大化； (4) 其他相关考虑。2.3 定位一运输路线安排问题（Location-Routing problems,LRP）当今物流系统的环境日趋复杂，而且物流地理分布也不断扩大。物流系统优
8、化问题的各个子系统（比如设施定位问题、物品配送问题、运输车辆路线安排问题等）之间的相互影响也越来越大。对许多实际问题，要综合考虑以上问题，这就形成了定位一路线安排问题（LRP）。LRP可以表述为：给定与实际问题相符的一系列客户点和一系列潜在的设施点，在这些潜在的点中确定出一系列的设施位置，同时要确定出一套从各个设施到各个客户点的运输路线，确定的依据是满足问题的目标（通常是总的费用最小）。客户点的位置和客户的需求量是已知的或可估算的，货物有一个或多个设施供应，每个客户只接收来自一个设施的货物，潜在设施点位置已知，问题的目标是把哪些潜在的设施建立起来，以使的总的费用最小。LRP可图示为图3。可以说
9、LRP是LA与VRP的集成4，但比后两者更复杂。LA在定位时考虑的是运输车辆从设施点到一个客户点后，随即返回设施点，所以它不考虑路线安排问题5。LA在确定出设施点后的图形是从设施点到客户点的射线族。而LRP则在定位时同时确定运输路线。LRP与VRP的不同之处是：VRP的前提条件是设施点和客户点在空间上的分布是已知的；LRP所研究的问题只知道潜在的设施点，在确定运输路线的同时要确定设施的位置。图中，表示设施；表示未被选中的设施；表示客户点；表示运输路线图3 LRP的图示在实际物流系统的集成的特征日益突出之前，就已经有人研究LRP了。最早的研究可以追溯到20世纪60年代，当时有些学者已经提出一些类
10、似的概念了6-8。到了70年代，Cooper9, 10把定位问题与运输问题结合起来，提出了运输一定位问题（Transportation-Location problem）。在这个阶段，学者们对LRP的研究还是相当肤浅的，还没有真正涉及运输路线安排问题。到了70年代中期，一些学者在研究运输一定位问题时，开始加入VRP的多点运输的特征，Watson-Gandy和Dohrn11是最早进行这方面工作的学者。直到70年代末，80年代初，才开始有了真正意义的LRP12-14。这些研究成果是伴随着集成物流系统概念的出现而出现的。3 LRP的分类Hokey Min等学者对LRP进行了详细的分类15，其分类标准
11、十分详尽，几乎包含了LRP的各个方面。表1 LRP的分类标准分类标准AB1物品流向单向双向2供/需特征确定随机3设施数量单个设施多设施4运输车辆数量单个车辆多车辆5车辆装载能力不确定确定6设施容量不确定确定7设施分级单级多级8计划期间单期多期9时间限制无时间限制有时间限制10目标数单目标多目标11模型数据类型假设值实际值Hokey的分类是依据问题的特征进行的，具体如表1。表1中，各分类标准解释如下：（1） 物品流向，单向物品流向问题指的是所有设施只进行输入（供应）或只进行输出（回收）的操作；而双向物品流向问题涉及的设施中有一部分既要输入又要输出。（2） 供/需特征，确定型的是指物品供应/需求量
12、是已知的并在一定时期内相对稳定；随机型的是指供应/需求量是不确定的。（3） 设施数量，指所研究问题要求设置设施的数量，分为单一设施和多设施两种。（4） 运输工具数量，是指有多少车辆为一个设施服务的标准，同时也确定了一个从设施出发的路线数。分为单一车辆和多车辆两种。（5） 车辆装载能力，是指是否要考虑车辆装载能力的限制。不确定定型是指对这个问题所涉及的每条路线上的货物总量很小，不会超出车辆的装载量，所以不用考虑车辆的装载能力的限制；确定型是指每条路线上的货物总量有可能超出车辆的装载能力，所以要把车辆的装载限制作为一个参数引入问题。（6） 设施容量，是指是否考虑各个设施容量的限制。分为不确定型和确
13、定型两种。（7） 设施分级，可以把设施分为两种：总站型和中间转运站型。总站型设施是指那些车辆路线的出发点或终点；中间转运站型设施是指物品的中间站，货物运入后还要运出。有了中间转运站，就产生了设施分级的问题，货物从总站型设施运入中间转运站型设施，经过简单处理后运到客户点。单级设施问题是指不考虑设施的分级，所有设施均为同级；而多级中心设施问题则要考虑设施的分级。（8） 计划期间，单期间问题把整个期间作为一个时间段，是静态问题；多期间问题把整个时间段按问题要求分为多个期间，是动态问题。（9） 时间限制，主要是指满足客户要求或货物品质要求，而对LRP的从设施点到客户点的时间约束。分为无时间约束和有时间
14、约束两种。（10） 目标数量，LRP的目标通常是总的费用（包括建设设施费用和车辆运输费用等）最小，但有时也需要考虑其他目标，比如满足顾客的特殊需要、总体利润量大化等等。如果是多目标问题，经常会出现各目标之间的冲突。（11） 模型数据类型，在有些情况下，模型中的数据（如物品供/需量等）是来源于实际的；而有些情况下，这些数据是在实际中不可得的，需要对其进行假设。根据模型数据类型的不同，把LRP分成假设型和实际型两类。4 LRP的解决方法国外许多学者对LRP的解决方法进行了有益的探讨，所采用的方法可以分为两种：精确算法和启发式算法。4.1 解决LRP的精确算法 基于运筹学的优化算法，解决LRP的精确
15、算法可以分为以下四种：(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。实际上，以上的物流系统是十分小的，在
