《物流系统优化中的定位运输路线安排问题》由会员分享，可在线阅读，更多相关《物流系统优化中的定位运输路线安排问题（22页珍藏版）》请在金锄头文库上搜索。
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的以后进展方向作简要的讨
4、论。2 从VRP、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
7、的图示LA实质上是一个依据优化路径的原则来确定在什么地点设置设施的过程2。例如，在一个城镇中设立一个急救中心，那个问题确实是一个典型的LA问题。它的目标确实是使得全镇的居民到医疗中心的路径（时刻）总体上最短。依照John Current等学者对此问题的综述研究3，把LA问题进行了分类。Current的方法是依照问题的目标函数来分类的，作为分类依据的目标函数共分四种： (1) 费用最小化； (2) 客户需求导向； (3) 利润最大化； (4) 其他相关考虑。2.3 定位一运输路线安排问题（Location-Routing problems,LRP）当今物流系统的环境日趋复杂，而且物流地理分布也不
8、断扩大。物流系统优化问题的各个子系统（比如设施定位问题、物品配送问题、运输车辆路线安排问题等）之间的相互阻碍也越来越大。对许多实际问题，要综合考虑以上问题，这就形成了定位一路线安排问题（LRP）。LRP能够表述为：给定与实际问题相符的一系列客户点和一系列潜在的设施点，在这些潜在的点中确定出一系列的设施位置，同时要确定出一套从各个设施到各个客户点的运输路线，确定的依据是满足问题的目标（通常是总的费用最小）。客户点的位置和客户的需求量是已知的或可估算的，物资有一个或多个设施供应，每个客户只接收来自一个设施的物资，潜在设施点位置已知，问题的目标是把哪些潜在的设施建立起来，以使的总的费用最小。LRP可
9、图示为图3。能够讲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进行了详细
11、的分类15，其分类标准十分详尽，几乎包含了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的精确算法 基于运筹学的
15、优化算法，解决LRP的精确算法能够分为以下四种：(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。实际上，以上的物
