集成化物流中的定位—运输路线安排问题(lrp)优化算法评述

《集成化物流中的定位—运输路线安排问题(lrp)优化算法评述》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第24卷第1期东北大学学报（自然科学版）Vol.24，No.12003年1月JournalofNortheasternUniversity（Naturalscience）Jan.2003!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!文章编号：1005-3026（2003）01-0031-04集成化物流中的定位-运输路线安排问题（LRP）优化算法评述张潜1，高立群1，胡祥培2（1.东北大学信息科学与工程学院，辽宁沈阳110004；2.大

2、连理工大学系统工程研究所，辽宁大连116023）摘要：总结定位-运输路线安排问题（Location-RoutingProblem，LRP）的发展历程，重点评述LRP优化算法的研究进展，并对比分析了常用的两类求解LRP问题的方法精确算法和启发式算法·并对LRP中的定位配给、运输车辆路线安排、定位-运输路线安排三类问题的具体优化方法进行了分析、比较，指出在求解LRP问题时应综合利用各种技术的优势，建立一种新的搜索方法，实现准确、高效的搜索，改进遗传算法用于求解LRP问题是解决这类NP-hard问题的一条途径·关键

3、词：集成化物流；定位-运输路线安排问题（LRP）；运输路线安排问题（VRP）；定位配给问题（LA）；优化算法；遗传算法中图分类号：TP1S；0232文献标识码：A近年来，国外许多学者对物流系统优化问题1定位-运输路线安排问题（LRP）的进行了一定的研究，构建了解决实际问题的优化含义及发展历程模型，并找到了一些求解算法·关于LRP的研究开始于20世纪70年代，Watson-gandy和1.1LRP的含义［1］定位-运输路线安排问题（Location-RoutingDohrn将运输车辆多点停留特性与定位-运输网P

4、roblemLRP）可以表示为给定与实际问题相符络结合起来开展了研究·但由于LRP问题的难度的一系列潜在的设施点，在这些潜在的点中确定很大，对该类问题的研究进展缓慢·20世纪90年出一系列的设施位置，同时要确定出一套以各个代以来，国外的学者对物流系统优化中的运输车设施到各个客户点的运输路线，确定的依据是满辆路线安排问题（VRP）和定位-配给问题（LA）的足问题的目标（通常是总的费用最小）·客户点的研究取得了一定的进展·随着集成化物流管理的位置和客户的需求量是已知的或可估算的，货物概念被越来越多的企业所接受和全

5、球贸易的快速有一个或多个设施点位置已知，问题的目标是把增长，提高分销效率成为了企业生存与发展的必那些潜在的设施建立起来，以使总的费用最小·由之路·LRP更贴近目前的物流系统的实际特1.2定位-运输路线安排问题（LRP）发展历程征，所以对其研究有现实的意义·（1）定位-运输路线问题（LRP）概念的发展本文参考了有关LRP优化求解算法的资料，关于LRP概念的研究追溯到1961年Von评述了定位—运输路线安排问题（LRP）问题研究［2］关于运输问题中的运输成本和定位成本Boventer的发展历程·结合常用的最优化方

6、法，阐述了解决的相互关系；1965年Maranzana［3］研究了供应点的LRP优化问题的基本思想；同时结合国内外研究定位的最小运输成本求解问题；196S年Webb［4］进现状，分析、比较解决LRP三类问题的优化算法，行了关于多阶段的仓库选址的成本函数分析；从而为解决物流系统优化问题中定位-运输路线［5］研究了英国东南部1969年Lawrence和Pengilly问题（LRP）的研究提供思路和参考·零售店配送时，仓库的选址和数量问题；1969年收稿日期：2002-06-21基金项目：国家自然科学基金资助项目（

7、70171040，70031020）·作者简介：张潜（1971-），女，辽宁沈阳人，东北大学博士研究生；高立群（1949-），男，辽宁沈阳人，东北大学教授，博士生导师；胡祥培（1962-），男，安徽黄山人，大连理工大学教授，博士生导师·32东北大学学报（自然科学版）第24卷［6］提出了一种车辆分派方法；Christofides和Eilon［7］提出了配送计划的一种简单模1972年~iggins型·早期研究集中在LRP的复杂性上，后来人们开始意识到定位和运输决策间的协调性·Cooper（1972，1976）［8

8、］概括了运输—定位问题，目的是图1定位（Location）、分配（Allocation）、路线（Routin9）三者的相互关系为了优化供货位置，降低运输成本·TapieroFi9.1TherelationshiPamon9location，［9］allocationandroutin9（1971）改善了Cooper的研究工作，把时间的复杂性引入普通运输定位模型·所有这些工作，主要2定位-运输路线问题