谈选址路径问题及其优化算法综述

论文关键词：选址路径　算法论文摘要：本文叙述了物流系统中选址运输路径安排问题(lrp)的含义、发展历程，重点阐述了求解lrp优化算法的机制，并对lrp的未来研究方向作了分析。1　选址路径问题(lrp)概述选址路径问题(locationroutingproblems,lrp)的研究开始于70年代，watsongandy和dohrn将运输车辆行程安排的多点停留特性与定位运输网络结合起来开展研究。通过增加定位运输网络中巡回路线的建立决策，lrp问题比传统的运输定位模型更难解决。虽然存在求解及模型构建方面的许多困难，真正意义上的lrp研究还是在20世纪70年代末和80年代初得到发展。这些研究工作包括or和pierskalla(1979)，jacobsen和madsen(1978)，harrison(1979)，jacobsen和madsen(1980)，nambiar(1981)，laporte和nobert(1981)，madsen(1983)。到80年代后期，由于实际应用的迫切需要，lrp的研究才得到了学术界的广泛重视。据不完全统计，迄今为止，在英文出版物中，有关lrp的模型、算法的研究及综述文章和论著已有数百篇。国内学术界对lrp的起步虽然较晚，但也取得一些成就，如汪寿阳(2000)《集成物流管理系统中定位运输路线安排问题的研究》，东北大学张潜的博士论文介绍了集成化物流中lrp问题的模型，并对其优化算法进行研究。2　lrp问题的求解算法一般而言，lrp的算法可以分为两类，一类是精确算法，一类是启发式算法。2.1.精确算法由于lrp是nphard的，因而用精确算法求解lrp是十分困难的，求解规模也十分小，用精确算法求解lrp的文献十分的少，随着实际问题越来越复杂，最近几年很少有人研究精确算法求解，精确算法的研究一般是在早期的文献里。主要有：整数规划（integerprogramming）。在解决lrp的精确算法中，整数规划占很大的比例。主要有：laprote和nobert(1981)用公式描述了整数规划并采用放宽约束条件的方法解决不受旅行长度限制的lrp，laporteetal(1983,1986)使用类似的方法去解决非满载或满载的多设施的lrp问题。用整数规划解决lrp问题还有revelleetal(1991)，min(1996)等。动态规划(dynamicprogramming)。averbankh和berman(1994)用动态规划解决多分发人员的lrp。分枝定界(branchandbound)。laportetal.(1988)用修改了的分枝定界法解决带时间窗的非对称的多中心的lrp；laportetal.(1989)用此法解决固定车队大小的随机lrp。此外还有daskin(1987)用此法解决了救护车的lrp。非线性规划(nonlinearprogramming。stowers和pelekar(1993)用非线性规划解决连续的、易损lrp。averbankh和berman(1995)使用非线形规划解决带不具体时间窗的商品分发员的lrp。此外还有ghoshetai(1981)等。除以上几种算法外，还有bookbinder和reece(1988)定义了三层多商品配送体系，建立了非线性混合整数规划模型等。2.2启发式算法目前，多采用启发式方法来解决lrp问题，应用启发式算法可提高解题的效率，适于处理实际中较大规模的问题，并有利于对问题进行灵敏度分析。lrp的启发式算法一般将问题分解为若干个子问题，将这些子问题依次采用启发式方法或精确方法来加以解决，各子问题之间存在相互依赖的关系。采用多阶段分解步骤可使复杂的问题简单化，避免产生局部最小化的结果。lrp的启发式算法主要有：先解决定位配给问题(locationallocationfirst)，然后解决车辆路线安排问题(routesecond)，即先选址，后路径。jacobsen和madsen(1978)用这种方法解决两层报纸分发系统的交换点的带时间窗的lrp，这两人在(1980)用此方法与节约法解决了报纸分发的带时间窗的lrp，harrison(1979)用同样的方法解决了多仓库多车辆的随机lrp。还有用此方法与插入法解决了多级、多设施、多车辆血库的lrp。此外还有nambiaretal(1981),bookbinder和reece(1988)等。先解决车辆路线安排问题(routefirst)，然后解决定位配给问题(locationallocationsecond)，即先路径，后选址。perl和daskin(1984,1985)用这种方法解决了有车辆容量约束的和设施无容量约束的多设施多车辆的仓库的lrp等。节约成本/插入。一般来说节约成本/插入算法不单独使用，总是和其他的混合起来使用，且此算法一般用于生成路线，它是以clarke和wright及rosenkrantzetal所提出的算法为基础。clarke和wright(1964)提出的节约算法其核心思想就是将运输问题中存在的两个回路合并成一个回路。改进路线/交换。最初由lin(1965)提出的“路线的改进/交换”启发式算法，也用于设计运输工具的行程路线，采用的方法是：可行的路线连续地改变，以便产生降低总成本的另一条可行路线，直至成本不可能再降低。因此，不同于降低成本/插入方法，这种启发式算法在整个解题步骤中都要保持可行性。常见的交换算法有：koptechange,oroptechange,?姿interchange,relocateechange。其中：koptechange表示的是k边交换，用的比较多的是2optechange和3optechange。用的比较多的是2opt.echange，它不会改变路的方向。relocateechange表示的是不同线路点的交换。如图：实际上是的扩展，即一条线路上的小于等于个客户与另一条线路的小于等于个客户交换。参考文献汪寿阳,赵秋红,夏国平.集成物流管理系统中定位运输路线安排问题的研究.管理科学学报,2000,6(3):6975.张长星,党延忠.定位一运输路线安排问题的遗传算法研究.计算机工程与应用,2004,12,6568.laporte,g,nobert,y.aneactalgorithmforminimizingroutingandoperatingcostsindepotlocation.europeanjournalofoperationalresearch.1981,6:224226.林岩,胡祥培,王旭茵.物流系统优化中的定位运输路线安排问题(lrp)研究评述.管理工程学报,2004,4(18):4549.