7物流系统优化中的定位运输路线安排问题386 .docx
( 4.5 )《7物流系统优化中的定位运输路线安排问题386 .docx》由会员分享，可在线阅读，更多相关《7物流系统优化中的定位运输路线安排问题386 .docx（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、精品名师归纳总结物流系统优化中的定位运输路线支配问题）争论评述林岩胡祥培大连理工高校系统工程争论所, 116023）摘要 本文概述了物流优化问题中的定位运输路线支配问题Location- Routing Problems, LRP ）的进展历程，并对LRP 的分类和解决方法加以评述，最终就这一问题的进展方向进行简洁的探讨。关键词 LRP 物流系统优化运筹学1 引言新技术的快速进展，特殊是电子商务的风起云涌，为我国经济的快速进展供应了契 机。目前我国电子商务得到政府和民众的支持，进展势头强劲，但是，由于它是一套全新 的技术，同时仍是一种全新的治理理念，所以其进展过程中必定存在一些难题。在电子商
2、务“三流” 信息流、物流、资金流）中，随着网络基础设施建设的成熟、电子商务网站的蓬勃进展以及有效利用网络资源观念的普及，信息流的进展已经比较成熟了。而随着各大 银行纷纷开展网上业务，以及支付网关的建立和加密技术的成熟，网上支付已经在很多网 站上成为现实。然而，我国传统的物流体系是在方案经济环境下建立、进展起来的，与目 前的电子商务环境已经无法相容。现今物流体系的落后现状已经成为我国社会经济快速发 展的重要制约因素之一。所以对物流系统优化的争论将会具有很大的现实意义。国外很多学者在电子商务显现之前就已经争论物流系统优化的问题了，为各类实际问题构建了优化模型，并形成了很多解决问题的算法。依据实际问
3、题的不同，可以对物流系统优化问题进行分类，比如，运输车辆路线支配问题VRP）、定位 配给问题 LA）、定位运输路线支配问题 LRP）等等，其中LRP 更贴近目前的物流系统复杂的实际特点，所以对它的争论是非常有意义的。本文先从 VRP和 LA 的集成来探讨 LRP 的由来，然后争论LRP 的分类，同时探讨LRP的争论现状，并对LRP的解决方法进行概述，最终就LRP 的将来进展方向作简要的争论。2 从 VRP 、LA 到 LRP 物流系统的集成依据实际问题的不同，可以对物流系统优化问题进行分类，比如确定设施指的是物品流淌的动身点和终到点，如配送中心、仓库、生产工厂、垃圾回收中心等）位置、运输路线支
4、配、库存掌握等，国内外很多学者就各类问题的特点进行了分析，并提出了各类问题的数学模型和解决方法。2.1 运输车辆路线支配问题Vehicle Routing Problems VRP ）该问题可定义为：运输车辆从一个或多个设施到多个的理上分散的客户点，优化设计一套货物流淌的运输路线，同时要满意一系列的约束条件。该问题的前提条件是设施位置、客户点位置和道路情形已知，由此确定一套车辆运输路线，以满意目标函数林岩, 硕士争论生 , 1972 年诞生 , 主要争论方向 : 电子商务 , 信息系统工程。胡祥培 , 1962 年诞生 , 教授,博导, 主要争论方向 : 电子商务 , 智能运筹学 , 信息系统
5、集成。可编辑资料 - - - 欢迎下载精品名师归纳总结VRP 的目标函数是总费用最小）。如图1 所示。图中，表示设施。表示客户。表示运输路线图 1 VRP 的图示实际上， VRP 是按如下假设定义的最小费用问题1 ：1）全部车辆路线均起始并终止于设施点。2）每个客户只接受一个设施的货物。3）满意其他一些约束条件，如： 容量限制：每个客户点上都有一个非负的货物需求量，但每条车辆路线上的货物量总和不超过车辆装载量。假如此约束不满意，就引入惩处函数。 总时间限制：每条路线总的长度或总耗时不超过一个事先定下的数值。这项限制旨在满意客户对供货时间的要求，以及对货物品质的保证。 具体时间限制：对某个客户点
6、，车辆到达时间限制在某一时间段内。此约束在于满意客户对供应 /回收的特殊要求。 车辆到达次序要求：如在到达i 点之前要求先到达j 点。以上列出的约束只是该问题一部分，具体操作时要视具体情形而定。对 VRP 的求解算法可分为精确算法和启示式算法两种。其中精确算法包括树状寻优算法、动态规划和整数规划。VRP 的启示式算法多是来源于对TSP 问题的求解算法。比如局部优先算法、插值法等可以不用修改的用于一些VRP 。2.2 定位配给问题 Location-Allocation Problems, LA ）定位一配给问题可定义为：依据客户点的的理分布与货物安排关系，确定出某一的理范畴内设施的数量和位置。
7、如图2 所示。图中，表示设施。表示客户。表示运输路线可编辑资料 - - - 欢迎下载精品名师归纳总结图 2 LA 的图示LA实质上是一个依据优化路径的原就来确定在什么的方设置设施的过程2 。例如，在一个城镇中设立一个急救中心，这个问题就是一个典型的LA问题。它的目标就是使得全 镇的居民到医疗中心的路径 费用最小化。2 客户需求导向。3 利润最大化。4 其他相关考虑。2.3 定位一运输路线支配问题Location-Routing problems,LRP ）当今物流系统的环境日趋复杂，而且物流的理分布也不断扩大。物流系统优化问题的各个子系统 比如设施定位问题、物品配送问题、运输车辆路线支配问题等
8、）之间的相互影响也越来越大。对很多实际问题，要综合考虑以上问题，这就形成了定位一路线支配问题LRP ）。LRP 可以表述为：给定与实际问题相符的一系列客户点和一系列潜在的设施点，在这些潜在的点中确定出一系列的设施位置，同时要确定出一套从各个设施到各个客户点的运输路线，确定的依据是满意问题的目标 通常是总的费用最小）。客户点的位置和客户的需求量是已知的或可估算的，货物有一个或多个设施供应，每个客户只接收来自一个设施的货物，潜在设施点位置已知，问题的目标是把哪些潜在的设施建立起来，以使的总的费用最小。 LRP 可图示为图 3。可以说 LRP 是 LA 与 VRP 的集成 4 ，但比后两者更复杂。L
9、A 在定位时考虑的是运输车辆从设施点到一个客户点后，立即返回设施点，所以它不考虑路线支配问题5 。LA在确定出设施点后的图形是从设施点到客户点的射线族。而LRP 就在定位时同时确定运输路线。 LRP 与 VRP 的不同之处是： VRP 的前提条件是设施点和客户点在空间上的分布是已知的。 LRP 所争论的问题只知道潜在的设施点，在确定运输路线的同时要确定设施的位置。图中，表示设施。表示未被选中的设施。表示客户点。表示运输路线图 3 LRP 的图示在实际物流系统的集成的特点日益突出之前，就已经有人争论LRP 了。最早的争论可以追溯到 20 世纪 60 岁月，当时有些学者已经提出一些类似的概念了6-
10、8 。到了 70 岁月， Cooper9, 10 把定位问题与运输问题结合起来，提出了运输肯定位问题Transportation-可编辑资料 - - - 欢迎下载精品名师归纳总结Location problem ）。在这个阶段，学者们对LRP 的争论仍是相当肤浅的，仍没有真正涉及运输路线支配问题。到了70 岁月中期，一些学者在争论运输肯定位问题时，开头加入VRP 的多点运输的特点， Watson-Gandy 和 Dohrn 11 是最早进行这方面工作的学者。直到70岁月末， 80 岁月初，才开头有了真正意义的LRP 12-14 。这些争论成果是相伴着集成物流系统概念的显现而显现的。3 LRP
11、的分类Hokey Min等学者对 LRP 进行了具体的分类15 ，其分类标准非常详尽，几乎包含了LRP 的各个方面。表 1 LRP 的分类标准分类标准AB1物品流向单向双向2供/需特点确定随机3设施数量单个设施多设施4运输车辆数量单个车辆多车辆5车辆装载才能不确定确定6设施容量不确定确定7设施分级单级多级8方案期间单期多期9时间限制无时间限制有时间限制10目标数单目标多目标11模型数据类型假设值实际值Hokey 的分类是依据问题的特点进行的，具体如表1。表 1 中，各分类标准说明如下：1）物品流向，单向物品流向问题指的是全部设施只进行输入供应）或只进行输出 回收）的操作。而双向物品流向问题涉及
12、的设施中有一部分既要输入又要输出。2）供 /需特点，确定型的是指物品供应/需求量是已知的并在肯定时期内相对稳固。 随机型的是指供应 /需求量是不确定的。3）设施数量，指所争论问题要求设置设施的数量，分为单一设施和多设施两种。4）运输工具数量，是指有多少车辆为一个设施服务的标准，同时也确定了一个从设施动身的路线数。分为单一车辆和多车辆两种。5）车辆装载才能，是指是否要考虑车辆装载才能的限制。不确定定型是指对这个问题所涉及的每条路线上的货物总量很小，不会超出车辆的装载量，所以不用考虑车辆的装载才能的限制。确定型是指每条路线上的货物总量有可能超出车辆的装载才能，所以要把车辆的装载限制作为一个参数引入
13、问题。6）设施容量，是指是否考虑各个设施容量的限制。分为不确定型和确定型两种。7）设施分级，可以把设施分为两种：总站型和中间转运站型。总站型设施是指那些车辆路线的动身点或终点。中间转运站型设施是指物品的中间站，货物运入后仍要运出。有了中间转运站，就产生了设施分级的问题，货物从总站型设施运入中间转运站型设施， 经过简洁处理后运到客户点。单级设施问题是指不考虑设施的分级，全部设施均为同级。 而多级中心设施问题就要考虑设施的分级。8）方案期间，单期间问题把整个期间作为一个时间段，是静态问题。多期间问题把整个时间段按问题要求分为多个期间，是动态问题。9）时间限制，主要是指满意客户要求或货物品质要求，而
14、对LRP 的从设施点到客户点的时间约束。分为无时间约束和有时间约束两种。10）目标数量， LRP 的目标通常是总的费用包括建设设施费用和车辆运输费用等）可编辑资料 - - - 欢迎下载精品名师归纳总结最小，但有时也需要考虑其他目标，比如满意顾客的特殊需要、总体利润量大化等等。假如是多目标问题，常常会显现各目标之间的冲突。11）模型数据类型，在有些情形下，模型中的数据 直接树状搜寻 1 。2 动态规划 117 。3 整数规划 1819 。4 非线性规划 20 。在以上算法中，最为常用的是整数规划 问题，所以，在大多数情形下，要用精确算法来解决LRP 是非常困难的。例如，在一个物流系统中，有3 个
15、潜在的中心点，8 个分布的客户点， 3 条行车路线，假如用整数规划来解决，要涉及的变量会达到333 个16 。实际上，以上的物流系统是非常小的，在实践中遇到的系统规模往往会远超过它。很多情形下要引入启示式算法。LRP 往往是非常复杂的，需要采纳多级分解方法对其简化。目前解决LRP 的启示式算法多采纳以下四种方法或是它们的组合：1）先解打算位一配给问题，然后解决运输路线支配问题15, 21 。2）先解决运输路线支配问题，然后解打算位一配给问题22 。3）费用降低 /插入算法 23, 24 。4）路线扩展交换算法。很多情形下精确的优化算法仅仅是作为一种参照的基准，在争论LRP 时比较各种启示式算法
16、的优劣。而在解决实际规模问题时一般要采纳启示式算法。5 LRP 的将来争论方向实际物流系统集成的程度越来越高，物流决策者面临的问题也就越来越复杂。用目前LRP 的争论成果来解决特殊复杂的物流系统优化问题仍存在很多局限。将来对LRP 的争论将会集中于以下难点：5.1 动态性很多 LRP 的参数是随时间变化的，如库存费用会随员工的人数、员工的工资水公平因可编辑资料 - - - 欢迎下载精品名师归纳总结素的变化而变化。运输费用也会因车辆装载情形、油料费用等的转变而转变。所以LRP 具有动态性，对动态 LRP 的争论是有现实意义的。25, 26运筹学理论被认为是解决优化问题非常有效的工具。但是假如实际
- 配套讲稿：
如PPT文件的首页显示word图标，表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制：
部分文档作品中含有的国旗、国徽等图片，仅作为作品整体效果示例展示，禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词：
- 7物流系统优化中的定位运输路线安排问题386 物流 系统 优化 中的 定位 运输 路线 安排 问题 386
淘文阁 - 分享文档赚钱的网站所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
限制150内