物流系统优化管理方案样本.doc
《物流系统优化管理方案样本.doc》由会员分享,可在线阅读,更多相关《物流系统优化管理方案样本.doc(24页珍藏版)》请在咨信网上搜索。
1、物流系统优化中定位运输路线安排问题()研究评述* 国家自然科学基金关键项目(70031020)摘要 本文概述了物流优化问题中定位运输路线安排问题(Location-Routing Problems, LRP)发展历程,并对LRP分类和处理方法加以评述,最终就这一问题发展方向进行简单地探讨。关键词 LRP 物流 系统优化 运筹学1 引言新技术快速发展,尤其是电子商务风起云涌,为中国经济快速发展提供了契机。现在中国电子商务得到政府和民众支持,发展势头强劲,不过,因为它是一套全新技术,同时还是一个全新管理理念,所以其发展过程中肯定存在部分难题。在电子商务“三流”(信息流、物流、资金流)中,伴随网络基
2、础设施建设成熟、电子商务网站蓬勃发展和有效利用网络资源观念普及,信息流发展已经比较成熟了;而伴随各大银行纷纷开展网上业务,和支付网关建立和加密技术成熟,网上支付已经在很多网站上成为现实;然而,中国传统物流体系是在计划经济环境下建立、发展起来,和现在电子商务环境已经无法相容。现今物流体系落后现实状况已经成为中国社会经济快速发展关键制约原因之一。所以对物流系统优化研究将会含有很大现实意义。国外很多学者在电子商务出现之前就已经研究物流系统优化问题了,为各类实际问题构建了优化模型,并形成了很多处理问题算法。依据实际问题不一样,能够对物流系统优化问题进行分类,比如,运输车辆路线安排问题(VRP)、定位配
3、给问题(LA)、定位运输路线安排问题(LRP)等等,其中LRP更贴近现在物流系统复杂实际特征,所以对它研究是十分有意义。本文先从VRP和LA集成来探讨LRP由来,然后讨论LRP分类,同时探讨LRP研究现实状况,并对LRP处理方法进行概述,最终就LRP未来发展方向作简明讨论。2 从VRP、LA到LRP物流系统集成依据实际问题不一样,能够对物流系统优化问题进行分类,比如确定设施(指是物品流动出发点和终到点,如配送中心、仓库、生产工厂、垃圾回收中心等)位置、运输路线安排、库存控制等,中国外很多学者就各类问题特征进行了分析,并提出了各类问题数学模型和处理方法。2.1 运输车辆路线安排问题(Vehicl
4、e Routing Problems VRP)该问题可定义为:运输车辆从一个或多个设施到多个地理上分散用户点,优化设计一套货物流动运输路线,同时要满足一系列约束条件。该问题前提条件是设施位置、用户点位置和道路情况已知,由此确定一套车辆运输路线,以满足目标函数(通常,VRP目标函数是总费用最小)。图1所表示。图中,表示设施;表示用户;表示运输路线图1 VRP图示实际上,VRP是按以下假设定义最小费用问题1:(1) 全部车辆路线均起始并终止于设施点。(2) 每个用户只接收一个设施货物。(3) 满足其它部分约束条件,如: 容量限制:每个用户点上全部有一个非负货物需求量,但每条车辆路线上货物量总和不超
5、出车辆装载量。假如此约束不满足,则引入处罚函数。 总时间限制:每条路线总长度或总耗时不超出一个事先定下数值。这项限制意在满足用户对供货时间要求,和对货物品质确保。 具体时间限制:对某个用户点,车辆抵达时间限制在某一时间段内。此约束在于满足用户对供给/回收特殊要求。 车辆抵达次序要求:如在抵达i点之前要求先抵达j点。以上列出约束只是该问题一部分,具体操作时要视具体情况而定。对VRP求解算法可分为正确算法和启发式算法两种。其中正确算法包含树状寻优算法、动态计划和整数计划。VRP启发式算法多是起源于对TSP问题求解算法。比如局部优先算法、插值法等能够不用修改地用于部分VRP。2.2 定位配给问题(L
6、ocation-Allocation Problems, LA)定位一配给问题可定义为:依据用户点地理分布和货物分配关系,确定出某一地理范围内设施数量和位置。图2所表示。图中,表示设施;表示用户;表示运输路线图2 LA图示LA实质上是一个依据优化路径标准来确定在什么地方设置设施过程2。比如,在一个城镇中设置一个抢救中心,这个问题就是一个经典LA问题。它目标就是使得全镇居民到医疗中心路径(时间)总体上最短。依据John Current等学者对此问题综述研究3,把LA问题进行了分类。Current方法是依据问题目标函数来分类,作为分类依据目标函数共分四种: (1) 费用最小化; (2) 用户需求导
7、向; (3) 利润最大化; (4) 其它相关考虑。2.3 定位一运输路线安排问题(Location-Routing problems,LRP)当今物流系统环境日趋复杂,而且物流地理分布也不停扩大。物流系统优化问题各个子系统(比如设施定位问题、物品配送问题、运输车辆路线安排问题等)之间相互影响也越来越大。对很多实际问题,要综合考虑以上问题,这就形成了定位一路线安排问题(LRP)。LRP能够表述为:给定和实际问题相符一系列用户点和一系列潜在设施点,在这些潜在点中确定出一系列设施位置,同时要确定出一套从各个设施到各个用户点运输路线,确定依据是满足问题目标(通常是总费用最小)。用户点位置和用户需求量是
8、已知或可估算,货物有一个或多个设施供给,每个用户只接收来自一个设施货物,潜在设施点位置已知,问题目标是把哪些潜在设施建立起来,以使总费用最小。LRP可图示为图3。能够说LRP是LA和VRP集成4,但比后二者更复杂。LA在定位时考虑是运输车辆从设施点到一个用户点后,随即返回设施点,所以它不考虑路线安排问题5。LA在确定出设施点后图形是从设施点到用户点射线族。而LRP则在定位时同时确定运输路线。LRP和VRP不一样之处是:VRP前提条件是设施点和用户点在空间上分布是已知;LRP所研究问题只知道潜在设施点,在确定运输路线同时要确定设施位置。图中,表示设施;表示未被选中设施;表示用户点;表示运输路线图
9、3 LRP图示在实际物流系统集成特征日益突出之前,就已经有些人研究LRP了。最早研究能够追溯到20世纪60年代,当初有些学者已经提出部分类似概念了6-8。到了70年代,Cooper9, 10把定位问题和运输问题结合起来,提出了运输一定位问题(Transportation-Location problem)。在这个阶段,学者们对LRP研究还是相当肤浅,还没有真正包含运输路线安排问题。到了70年代中期,部分学者在研究运输一定位问题时,开始加入VRP多点运输特征,Watson-Gandy和Dohrn11是最早进行这方面工作学者。直到70年代末,80年代初,才开始有了真正意义LRP12-14。这些研究
10、结果是伴伴随集成物流系统概念出现而出现。3 LRP分类Hokey Min等学者对LRP进行了具体分类15,其分类标准十分详尽,几乎包含了LRP各个方面。表1 LRP分类标准分类标准AB1物品流向单向双向2供/需特征确定随机3设施数量单个设施多设施4运输车辆数量单个车辆多车辆5车辆装载能力不确定确定6设施容量不确定确定7设施分级单级多级8计划期间单期多期9时间限制无时间限制有时间限制10目标数单目标多目标11模型数据类型假设值实际值Hokey分类是依据问题特征进行,具体如表1。表1中,各分类标准解释以下:(1) 物品流向,单向物品流向问题指是全部设施只进行输入(供给)或只进行输出(回收)操作;而
11、双向物品流向问题包含设施中有一部分既要输入又要输出。(2) 供/需特征,确定型是指物品供给/需求量是已知并在一定时期内相对稳定;随机型是指供给/需求量是不确定。(3) 设施数量,指所研究问题要求设置设施数量,分为单一设施和多设施两种。(4) 运输工具数量,是指有多少车辆为一个设施服务标准,同时也确定了一个从设施出发路线数。分为单一车辆和多车辆两种。(5) 车辆装载能力,是指是否要考虑车辆装载能力限制。不确定定型是指对这个问题所包含每条路线上货物总量很小,不会超出车辆装载量,所以不用考虑车辆装载能力限制;确定型是指每条路线上货物总量有可能超出车辆装载能力,所以要把车辆装载限制作为一个参数引入问题
12、。(6) 设施容量,是指是否考虑各个设施容量限制。分为不确定型和确定型两种。(7) 设施分级,能够把设施分为两种:总站型和中间转运站型。总站型设施是指那些车辆路线出发点或终点;中间转运站型设施是指物品中间站,货物运入后还要运出。有了中间转运站,就产生了设施分级问题,货物从总站型设施运入中间转运站型设施,经过简单处理后运到用户点。单级设施问题是指不考虑设施分级,全部设施均为同级;而多级中心设施问题则要考虑设施分级。(8) 计划期间,单期间问题把整个期间作为一个时间段,是静态问题;多期间问题把整个时间段按问题要求分为多个期间,是动态问题。(9) 时间限制,关键是指满足用户要求或货物品质要求,而对L
13、RP从设施点到用户点时间约束。分为无时间约束和有时间约束两种。(10) 目标数量,LRP目标通常是总费用(包含建设设施费用和车辆运输费用等)最小,但有时也需要考虑其它目标,比如满足用户特殊需要、总体利润量大化等等。假如是多目标问题,常常会出现各目标之间冲突。(11) 模型数据类型,在有些情况下,模型中数据(如物品供/需量等)是起源于实际;而有些情况下,这些数据是在实际中不可得,需要对其进行假设。依据模型数据类型不一样,把LRP分成假设型和实际型两类。4 LRP处理方法国外很多学者对LRP处理方法进行了有益探讨,所采取方法能够分为两种:正确算法和启发式算法。4.1 处理LRP正确算法 基于运筹学
14、优化算法,处理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是十
15、分困难。比如,在一个物流系统中,有3个潜在中心点,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研究是有现实意义。运筹学理论被认为是处理优化问题十分有效工具。不过假如实际问题发生改变,就会引发数学模型改变和模型求解程序改变。对于动态问题,这种连锁反应是时时刻刻全部在发生。
17、所以用传统运筹学理论处理动态优化问题会力不从心。其原因是传统运筹学理论缺乏基于知识推理机制和处理动态问题自适应能力。为了克服这一缺点,八十年代以来中国外学者将人工智能和知识工程理论引入运筹学,开辟了智能运筹学25, 26这一新研究方向。使运筹学由过去仅能处理静态问题变为能够处理动态问题,它必将有利于动态LRP求解5.2 实时调控在实际情况下,尤其是在现在被广泛重视电子商务物流实施过程中,商品供货点、运输工具、运输路径和送货时间等需要实时作出决择。这就包含到实时调控问题。多年来,Agent技术发展快速,Agent含有自主性、主动性、反应性和智能性为改善基于运筹学知识表示理论动态问题实时优化控制系
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 物流 系统 优化 管理 方案 样本
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【精***】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【精***】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。