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

谈选址路径问题及其优化算法综述 ( 作者：贺协腾　　发表时间：2014年11月 ) 　　论文关键词：选址路径　算法 　　论文摘要：本文叙述了物流系统中选址运输路径安排问题(LRP)的含义、发展历程，重点阐述了求解LRP优化算法的机制，并对LRP的未来研究方向作了分析。 　　 　　1　选址路径问题(LRP)概述 　　 　　选址-路径问题(Location-Routing Problems, LRP)的研究开始于70年代，Watson-Gandy和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是NP-Hard的，因而用精确算法求解LRP是十分困难的，求解规模也十分小，用精确算法求解LRP的文献十分的少，随着实际问题越来越复杂，最近几年很少有人研究精确算法求解，精确算法的研究一般是在早期的文献里。 　　主要有： 　　整数规划（Integer Programming）。在解决LRP的精确算法中，整数规划占很大的比例。主要有：Laprote和Nobert(1981)用公式描述了整数规划并采用放宽约束条件的方法解决不受旅行长度限制的LRP，Laporte et al(1983,1986)使用类似的方法去解决非满载或满载的多设施的LRP问题。用整数规划解决LRP问题还有Revelle et al(1991)，Min(1996)等。 　　动态规划(Dynamic Programming)。Averbankh和Berman(1994)用动态规划解决多分发人员的LRP。 　　分枝定界(Branch and bound)。Laport et al.(1988)用修改了的分枝定界法解决带时间窗的非对称的多中心的LRP；Laport et al.(1989)用此法解决固定车队大小的随机LRP。此外还有Daskin(1987)用此法解决了救护车的LRP。 　　非线性规划(Nonlinear programming}。Stowers和Pelekar(1993)用非线性规划解决连续的、易损LRP 。Averbankh和Berman(1995)使用非线形规划解决带不具体时间窗的商品分发员的LRP。此外还有Ghosh et aI(1981)等。 　　除以上几种算法外，还有Bookbinder和Reece(1988)定义了三层多商品配送体系，建立了非线性混合整数规划模型等。 　　2.2启发式算法 　　目前，多采用启发式方法来解决LRP问题，应用启发式算法可提高解题的效率，适于处理实际中较大规模的问题，并有利于对问题进行灵敏度分析。LRP的启发式算法一般将问题分解为若干个子问题，将这些子问题依次采用启发式方法或精确方法来加以解决，各子问题之间存在相互依赖的关系。采用多阶段分解步骤可使复杂的问题简单化，避免产生局部最小化的结果。 ( 作者：贺协腾　　发表时间：2014年11月 ) 　　LRP的启发式算法主要有： 　　先解决定位-配给问题(Location-allocation first)，然后解决车辆路线安排问题(Route-second)，即先选址，后路径。 　　Jacobsen和Madsen(1978)用这种方法解决两层报纸分发系统的交换点的带时间窗的LRP，这两人在(1980)用此方法与节约法解决了报纸分发的带时间窗的