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


    物流系统优化中定位—运输路线安排问题
    (LRP)研究评述* 国家然科学基金重点项目(70031020)



    摘 文概述物流优化问题中定位—运输路线安排问题(LocationRouting Problems LRP)发展历程LRP分类解决方法加评述问题发展方进行简单探讨
    关键词 LRP 物流 系统优化 运筹学

    1 引言
    新技术迅速发展特电子商务风起云涌国济快速发展提供契机目前国电子商务政府民众支持发展势头强劲套全新技术时种全新理理念发展程中必然存难题电子商务三流(信息流物流资金流)中着网络基础设施建设成熟电子商务网站蓬勃发展效利网络资源观念普信息流发展已较成熟着银行纷纷开展网业务支付网关建立加密技术成熟网支付已许网站成现实然国传统物流体系计划济环境建立发展起目前电子商务环境已法相容现物流体系落现状已成国社会济快速发展重制约素物流系统优化研究会具现实意义
    国外许学者电子商务出现前已研究物流系统优化问题类实际问题构建优化模型形成许解决问题算法实际问题物流系统优化问题进行分类运输车辆路线安排问题(VRP)定位—配问题(LA)定位—运输路线安排问题(LRP)等等中LRP更贴目前物流系统复杂实际特征研究十分意义
    文先VRPLA集成探讨LRP然讨LRP分类时探讨LRP研究现状LRP解决方法进行概述LRP未发展方作简讨

    2 VRPLALRP——物流系统集成
    实际问题物流系统优化问题进行分类确定设施(指物品流动出发点终点配送中心仓库生产工厂垃圾回收中心等)位置运输路线安排库存控制等国外许学者类问题特征进行分析提出类问题数学模型解决方法

    21 运输车辆路线安排问题(Vehicle Routing Problems VRP)
    该问题定义:运输车辆设施理分散客户点优化设计套货物流动运输路线时满足系列约束条件该问题前提条件设施位置客户点位置道路情况已知确定套车辆运输路线满足目标函数(通常VRP目标函数总费)图1示










    图中□表示设施〇表示客户↗表示运输路线
    图1 VRP图示

    实际VRP假设定义费问题[1]:
    (1) 车辆路线均起始终止设施点
    (2) 客户接受设施货物
    (3) 满足约束条件:
    ■ 容量限制:客户点非负货物需求量条车辆路线货物量总超车辆装载量果约束满足引入惩罚函数
    ■ 总时间限制:条路线总长度总耗时超事先定数值项限制旨满足客户供货时间求货物品质保证
    ■ 具体时间限制:某客户点车辆达时间限制某时间段约束满足客户供应回收特殊求
    ■ 车辆达序求:达i点前求先达j点
    列出约束该问题部分具体操作时视具体情况定
    VRP求解算法分精确算法启发式算法两种中精确算法包括树状寻优算法动态规划整数规划VRP启发式算法源TSP问题求解算法局部优先算法插值法等修改VRP

    22 定位—配问题(LocationAllocation Problems LA)
    定位配问题定义:客户点理分布货物分配关系确定出某理范围设施数量位置图2示









    图中□表示设施〇表示客户↗表示运输路线
    图2 LA图示

    LA实质优化路径原确定什方设置设施程[2]例城镇中设立急救中心问题典型LA问题目标全镇居民医疗中心路径(时间)总体短
    根John Current等学者问题综述研究[3]LA问题进行分类Current方法根问题目标函数分类作分类目标函数分四种:
    (1) 费化
    (2) 客户需求导
    (3) 利润化
    (4) 相关考虑

    23 定位运输路线安排问题(LocationRouting problemsLRP)
    物流系统环境日趋复杂物流理分布断扩物流系统优化问题子系统(设施定位问题物品配送问题运输车辆路线安排问题等)间相互影响越越许实际问题综合考虑问题形成定位路线安排问题(LRP)
    LRP表述:定实际问题相符系列客户点系列潜设施点潜点中确定出系列设施位置时确定出套设施客户点运输路线确定满足问题目标(通常总费)客户点位置客户需求量已知估算货物设施供应客户接收设施货物潜设施点位置已知问题目标潜设施建立起总费LRP图示图3
    说LRPLAVRP集成[4]两者更复杂LA定位时考虑运输车辆设施点客户点返回设施点考虑路线安排问题[5]LA确定出设施点图形设施点客户点射线族LRP定位时时确定运输路线LRPVRP处:VRP前提条件设施点客户点空间分布已知LRP研究问题知道潜设施点确定运输路线时确定设施位置








    图中□表示设施△表示未选中设施〇表示客户点↗表示运输路线
    图3 LRP图示

    实际物流系统集成特征日益突出前已研究LRP早研究追溯20世纪60年代时学者已提出类似概念[68]70年代Cooper[9 10]定位问题运输问题结合起提出运输定位问题(TransportationLocation problem)阶段学者LRP研究相肤浅没真正涉运输路线安排问题70年代中期学者研究运输定位问题时开始加入VRP点运输特征WatsonGandyDohrn[11]早进行方面工作学者直70年代末80年代初开始真正意义LRP[1214]研究成果伴着集成物流系统概念出现出现

    3 LRP分类
    Hokey Min等学者LRP进行详细分类[15]分类标准十分详包含LRP方面
    表1 LRP分类标准

    分类标准
    A
    B
    1
    物品流


    2
    供需特征
    确定

    3
    设施数量
    单设施
    设施
    4
    运输车辆数量
    单车辆
    车辆
    5
    车辆装载力
    确定
    确定
    6
    设施容量
    确定
    确定
    7
    设施分级
    单级

    8
    计划期间
    单期

    9
    时间限制
    时间限制
    时间限制
    10
    目标数
    单目标
    目标
    11
    模型数类型
    假设值
    实际值
    Hokey分类问题特征进行具体表1
    表1中分类标准解释:
    (1) 物品流单物品流问题指设施进行输入(供应)进行输出(回收)操作双物品流问题涉设施中部分输入输出
    (2) 供需特征确定型指物品供应需求量已知定时期相稳定机型指供应需求量确定
    (3) 设施数量指研究问题求设置设施数量分单设施设施两种
    (4) 运输工具数量指少车辆设施服务标准时确定设施出发路线数分单车辆车辆两种
    (5) 车辆装载力指否考虑车辆装载力限制确定定型指问题涉条路线货物总量会超出车辆装载量考虑车辆装载力限制确定型指条路线货物总量超出车辆装载力车辆装载限制作参数引入问题
    (6) 设施容量指否考虑设施容量限制分确定型确定型两种
    (7) 设施分级设施分两种:总站型中间转运站型总站型设施指车辆路线出发点终点中间转运站型设施指物品中间站货物运入运出中间转运站产生设施分级问题货物总站型设施运入中间转运站型设施简单处理运客户点单级设施问题指考虑设施分级设施均级级中心设施问题考虑设施分级
    (8) 计划期间单期间问题整期间作时间段静态问题期间问题整时间段问题求分期间动态问题
    (9) 时间限制指满足客户求货物品质求LRP设施点客户点时间约束分时间约束时间约束两种
    (10) 目标数量LRP目标通常总费(包括建设设施费车辆运输费等)时需考虑目标满足顾客特殊需总体利润量化等等果目标问题常会出现目标间突
    (11) 模型数类型情况模型中数(物品供需量等)源实际情况数实际中需进行假设根模型数类型LRP分成假设型实际型两类

    4 LRP解决方法
    国外许学者LRP解决方法进行益探讨采方法分两种:精确算法启发式算法

    41 解决LRP精确算法
    基运筹学优化算法解决LRP精确算法分四种:
    (1) 直接树状搜索[1]
    (2) 动态规划[1][17]
    (3) 整数规划[18][19]
    (4) 非线性规划[20]
    算法中常整数规划(包括混合整数规划)具体解决时效率高方法分支—定界法长计算时间解决80节点LRP采分支
    —定界法LRP必须模型中限制设施数量旦涉LRP规模扩精确算法实

    42解决LRP启发式算法
    LRP结合LA问题VRP两者NPHard (Non – deterministic Polynomial hard)问题数情况精确算法解决LRP十分困难例物流系统中3潜中心点8分布客户点3条行车路线果整数规划解决涉变量会达333[16]实际物流系统十分实践中遇系统规模会远超情况引入启发式算法
    LRP十分复杂需采级分解方法简化目前解决LRP启发式算法采四种方法组合:
    (1) 先解决定位配问题然解决运输路线安排问题[15 21]
    (2) 先解决运输路线安排问题然解决定位配问题[22]
    (3) 费降低插入算法[23 24]
    (4) 路线扩展交换算法
    情况精确优化算法仅仅作种参基准研究LRP时较种启发式算法优劣解决实际规模问题时般采启发式算法

    5 LRP未研究方
    实际物流系统集成程度越越高物流决策者面问题越越复杂目前LRP研究成果解决特复杂物流系统优化问题存许局限未LRP研究会集中难点:

    51 动态性
    许LRP参数时间变化库存费会员工数员工工资水等素变化变化运输费会车辆装载情况油料费等改变改变LRP具动态性动态LRP研究现实意义
    运筹学理认解决优化问题十分效工具果实际问题发生变化会引起数学模型改变模型求解程序改变动态问题种连锁反应时时刻刻发生传统运筹学理解决动态优化问题会力心原传统运筹学理缺乏基知识推理机制处理动态问题适应力克服缺陷八十年代国外学者工智知识工程理引入运筹学开辟智运筹学[25 26]新研究方运筹学仅解决静态问题变解决动态问题必助动态LRP求解

    52 实时调控
    实际情况特广泛重视电子商务物流实施程中商品供货点运输工具运输路径送货时间等需实时作出决择涉实时调控问题
    年Agent技术发展迅速Agent具性动性反应性智性改进基运筹学知识表示理动态问题实时优化控制系统创造条件Agent技术运筹学理机结合交叉渗透必终解决实际规模LRP决定性意义

    53 机性
    实践中物品供应需求量客户点位置车辆行驶时间等等情况事先确定参数带机性机性引入LRP更利解决实际问题
    已许学者机性LRP进行研究Laporte等[29]供应需求量确定LRP作探讨提出种两阶段算法:第阶段供应需求量未知情况确定中心位置运输路线车队数量第二阶段条路线供应需求量超出车辆装载力车辆某点装满时返回中心点装货卸货然回返回点恢复运输车辆操作产生惩罚项解决类问题引入两种方法:(1)保证出现车辆返回概率某预定值情况确定第阶段值(2)保证车辆返回产生费超某预定费情况确定第阶段值类问题采整数规划解决

    54 时间限制
    实际物流系统中许情况客户车辆达时间限制种时间限制分硬限制软限制两种硬限制求时间点软限制指定段时间目前止LRP研究少考虑时间限制方面研究会益

    55 目标性
    物流系统中目标间会产生突总费目标确定方案满足客户时间求目标时会合求然实际物流系统均目标特征LRP研究中会注重目标间优化

    6 结
    文物流系统中LRP分类解决方法作简评述LRP未研究方作分析LRP研究存许没解决方面LRP研究会越越符合实际情况方发展

    参考文献
    1 Gilbert Laporte The vehicle routing problem An overview of exact and approximate algorthmsEuropean Journal of Operational Research199259 345358
    2 Alant Murray Ross A Gerrard Capacitated service and regional constraints in locationallocation modeling Location Science 1997 5(2) 103118
    3 John Current H Min DA Schilling Multiobjective analysis of facility location decisions European Journal of Operational Research 1990 49 295307
    4 汪寿阳 赵秋红 夏国 集成物流理系统中定位——运输线路安排问题研究 理科学学报 2000 3(2) 6975
    5 S Salhi GK Rand The effect of ignoring routes when locating deports European Journal of Operational Research 1989 39 150156
    6 Maranzana FE On the location of supply points to minimize transport cost Operational Research Quarterly1965(15) 261270
    7 MHJ Webb Cost functions in the location of deports for multipledelivery journeys Operational Research Quarterly 1968 (19) 311320
    8 NChristofides SEilton An algorithm for the vehicle dispatching problem Operational Research Quarterly 1969 (20) 309318
    9 Leon Cooper The TransportationLocation Problem Operations Research 1972 20 94108
    10 Leon Cooper An efficient heuristic algorithm for the transportation – location problem Journal of Regional Science 1976 16(3) 309315
    11 CWatsonGandy PDohrn Depot location with van salesman – A practical approach Omega 1973 1(3) 321329
    12 IOr WPPierskalla A transportation location – allocation model for regional blood banking AIIE Transactions 1979 11(2) 8695
    13 JacobsonSk Madsen OBGA comparative study of heuristics for a towlevel routing — location problem European Journal of Operational Research 1980 5 378387
    14 Laporte GNobert Y A exact algorithm for minimizing routing and operating costs in depot location European Journal of Operational Research19816224226
    15 Hokey Min Vaidyanathan Jayaraman Rajesh Srivastava Combined location routing problems A synthesis and future research direction European Journal of Operational Research 1998 108115
    16 Rajesh Srivastava WCBenton The locationrouting problem considerations in physical distribution system design Computers & Operations Research 1990 17 427435
    17 IAverbakh OBerman Routing and location – routing pdelivery man problems on a path Transportation Science 1994 28(2) 162166
    18 CReVelle JCohon DShobrys Simultaneous siting and routing in the disposal of hazardous wastes Transportation Science 1991 25(2) 138145
    19 GLaporte Y Nobert DArpin An exact algorithm for solving a capacitated location – routing problem Annals of Operations Research 1986 6 293310
    20 CLStowers USPaleker Location models with routing considerations for a single obnoxious facility Transportation Science 1993 27(4) 350362
    21 JHBookbinder KEReece Vehicle routing considerations in distribution system design European Journal of Operational Research 1988 37 204213
    22 JPerl MSDaskin A warehouse location – routing problem Transportation Research 1985 19B(5) 381396
    23 TWChien Heurristic procedures for practical – sized uncapacitated location – capacitated routing problems Decision Sciences 1993 24(5) 9951021
    24 PHHansen BHegedah1 SHjortk BObel A heuristic solution to the warehouse location routing problem European Journal of Operational Research 1994 76 111127
    25 RIphelps Artificial Intelligence An overview of Similarities with OR Journal of Operational Research Society 1986 37(1) 1320
    26 胡祥培 杨德礼 智运筹学动态系统实时优化控制 济理社会科学前研究—2000年中国博士学术会济理文社会分会暨全国博士第四届济学理学学术会议文集 中国金融出版社 2000年10月出版137148
    27 Hu Xiangpei A New Method on Knowledge Representation for Programming Model of Operational ResearchStructured Statespace Representation Proceedings of the Second RussianChinese International Symposium On Management Science Economic Education Press Moscow Russia Oct 1994
    28 胡祥培钱国明胡运权离散型动态规划模型知识表示IBFS算法研究 哈尔滨工业学学报19963119126
    29 Gilbert Laporte Francois Louveaux He lene Mercure Modles and exact solutions for a class of stochastic locationrouting problems European Journal of Operational Research 1989 39 7178

    Review on Location—Routing Problems (LRP) in Systematic Optimization of Logistics

    Lin Yan Hu Xiangpei
    (Institute of System Engineering Dalian University of Technology)

    Abstract This paper reviews the development of the Location–Routing Problems (LRP) Whereafter types algorithms and solutions of LRP which had been researched by some specialists will be discussed then the intending cruxes of LRP will be summarized
    Keywords LRP Logistics Systematic Optimization Operations Research
    文档香网(httpswwwxiangdangnet)户传

    《香当网》用户分享的内容,不代表《香当网》观点或立场,请自行判断内容的真实性和可靠性!
    该内容是文档的文本内容,更好的格式请下载文档

    下载文档到电脑,查找使用更方便

    文档的实际排版效果,会与网站的显示效果略有不同!!

    需要 2 积分 [ 获取积分 ]

    下载文档

    相关文档

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

    物流系统优化中的定位—运输路线安排问题 (LRP)研究评述* 国家自然科学基金重点项目(70031020) 林岩 胡祥培** 林岩, 硕士研究生, 1972年出生, 主要研究...

    9年前   
    20792    0

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

    物流系统优化中的定位—运输路线安排问题 (LRP)研究评述* 国家自然科学基金重点项目(70031020) 林岩 胡祥培** 林岩, 硕士研究生, 1972年出生, 主要研究...

    13年前   
    4449    0

    零部件物流Milk-Run优化系统实现

    第三章零部件物流Milk-Run优化系统实现3.1基于Arc-GIS软件的milk-run路径可视化1.建立上海路网GIS原始图通过建立上海电子地图信息数据库,将数据库导入到ArcMap软件当...

    2年前   
    449    0

    物流运输线路优化-以狮桥沪成线为例

    随着当前经济的快速发展,市场竞争越来越激烈,许多企业为了提高员工的工作效率的同时,也更加注重企业物流管理,物流管理不仅能提高企业员工的工作效率,也能提高企业的综合竞争能力。

    3年前   
    433    0

    OTN技术在电力通信系统中的应用与优化

    电力系统通信网,作为电力行业的专用通信网,是电力系统不可缺少的组成部分,伴随着电力系统信息化、智能化发展需求的不断提升,电力系统通信网承载的业务逐渐从单一的调度监控业务、安全生产业务、营销业务、...

    3年前   
    702    0

    物流优化研究开题报告

    物流优化研究开 题 报 告指导老师:_________________ 学 生:_________________ 学 号:_________________ 专 ...

    3年前   
    2487    0

    《定位》读后感 定位中的营销

    定位中的营销  《定位》读后感       在得到《定位》伊始,我对作者和他作品几乎一无所知,于是简单地上网找了些资料,竟引起了莫大的兴趣。 首先,本书作者之一的杰克·特劳特非等闲之辈。...

    11年前   
    12113    0

    运输物流实践报告

    运输物流实践报告运输物流实践报告1   (一)实践目的   初步熟悉.,进一步了解货代以及物流运输组织与管理的相关学问,做到学以致用,把从学校学到的理论学问与实际工作中的实践贯穿起来,从...

    2年前   
    439    0

    运输物流公司简介

    运输物流公司简介  寿光鸿运物流有限公司是经国家主管部门批准成立的专业化物流服务商!自成立以来,本着诚信经营,视顾客为伙伴的经营思想,以为客户创造竞争优势的同时创建自身的竞争优势为理念,已在国...

    10年前   
    680    0

    运输物流实践报告

    运输物流实践报告  实习目的:  了解物流运输企业生产工序流程,了解物流运输企业财务会计程序以及财务会计工作人员的工作情况。了解不同岗位工作人员工作环境,生活情况。  实习对象:  江苏南京瀚...

    11年前   
    719    0

    物流运输协议

    根据国家有关运输规定,经过甲乙双方友好协商,本着平等互利的原则,达成如下协议:

    3年前   
    522    0

    基于需求预测的D制造企业物流系统优化研究

    本文选取属于电子器件制造行业的小型制造企业D为代表进行研究。针对D公司存在着需求预测系统不完善、库存量过高等问题,作者对D企业的需求管理系统和库存管理策略做出优化方案。

    3年前   
    531    0

    基于需求预测的D制造企业物流系统优化研究

    本文选取属于电子器件制造行业的小型制造企业D为代表进行研究。针对D公司存在着需求预测系统不完善、库存量过高等问题,作者对D企业的需求管理系统和库存管理策略做出优化方案。

    3年前   
    518    0

    运输方案设计物流系统规划与设计课程设计

    成绩 物流系统规划与设计课程设计报告学院名称 管理学院 专 业 物流工程 班 级 级物流工程班 学生姓名 ...

    3年前   
    685    0

    GPS(RTK)全球定位系统在建筑工程测量中的应用

    GPS(RTK)全球定位系统在建筑工程测量中的应用     【摘要】 RTK技术是GPS实时载波相位差分的简称。这是一种将GPS与数传技术相结合,实时解算并进行处理,在1~2秒时间内得到...

    9年前   
    6344    0

    叉车定位系统流程设计

    叉车定位系统流程设计  叉车在仓库环境内安装若干个Symeo LPR_2D信号发射器,叉车上面安装Symeo LPR_2D定位终端装置,就可以实现2D定位。在叉车上安装一个基站和两个天线就能确...

    2年前   
    465    0

    西部物流资源的优化配置研究

    西部物流资源的优化配置研究    物流资源广义地讲是指物流服务和物流作业所依赖的资金、技术、知识、信息、人员、场地、设备、设施、网络等所有元素,狭义地讲主要指...

    12年前   
    8235    0

    延期安装使用新道路运输车辆卫星定位系统车载终端请示

              关于延期安装使用新道路运输车辆卫星定位系统车载终端的请示 **市运管处客运监管科: 根据交运发[2011]158号文:关于认真贯彻《道路运输车辆卫星定位系统平台技术要求...

    12年前   
    13429    0

    智能物流系统

    2021-2021学年第1学期课程号:IEPA40320T 智能物流系统 课程论文 院系: 信息学院专业: 计算机科学与技术班级: 2021210506姓名: ...

    2年前   
    744    0

    叫号系统优化建议

     叫号系统优化建议 智能化的叫号系统,有效的解决了排队等候或一拥而上争相办理业务的现象,大大改善了工行服务质量和企业形象,而且可以根据客户所需办理业务的不同合理的分配到不同的柜台办理业务,减...

    12年前   
    12920    0