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

"

论文关键词：选址路径 算法

论文摘要：本文叙述了物流系统中选址运输路径安排问题(LRP)的含义、发展历程，重点阐述了求解LRP优化算法的机制，并对LRP的未来研究方向作了分析。

1 选址路径问题(LRP)概述

2 LRP问题的求解算法

一般而言，LRP的算法可以分为两类，一类是精确算法，一类是启发式算法。

2.1.精确算法

由于LRP是NP-Hard的，因而用精确算法求解LRP是十分困难的，求解规模也十分小，用精确算法求解LRP的文献十分的少，随着实际问题越来越复杂，最近几年很少有人研究精确算法求解，精确算法的研究一般是在早期的文献里。

主要有：

整数规划（Integer Programming）。在解决LRP的精确算法中，整数规划占很大的比例。主要有：Laprote和Nobert(19

8

1)用公式描述了整数规划并采用放宽约束条件的方法解决不受旅行长度限制的LRP，Laporte et al(1983,19

8

6)使用类似的方法去解决非满载或满载的多设施的LRP问题。用整数规划解决LRP问题还有Revelle et al(19

9

1)，Min(19

9

6)等。

动态规划(Dynamic Programming)。Averbankh和Berman(19

9

4)用动态规划解决多分发人员的LRP。

分枝定界(Branch and bound)。Laport et al.(19

8

8)用修改了的分枝定界法解决带时间窗的非对称的多中心的LRP；Laport et al.(19

8

9)用此法解决固定车队大小的随机LRP。此外还有Daskin(19

8

7)用此法解决了救护车的LRP。

非线性规划(Nonlinear programming}。Stowers和Pelekar(19

9

3)用非线性规划解决连续的、易损LRP 。Averbankh和Berman(19

9

5)使用非线形规划解决带不具体时间窗的商品分发员的LRP。此外还有Ghosh et aI(19

8

1)等。

除以上几种算法外，还有Bookbinder和Reece(19

8

8)定义了三层多商品配送体系，建立了非线性混合整数规划模型等。

2.2启发式算法

目前，多采用启发式方法来解决LRP问题，应用启发式算法可提高解题的效率，适于处理实际中较大规模的问题，并有利于对问题进行灵敏度分析。LRP的启发式算法一般将问题分解为若干个子问题，将这些子问题依次采用启发式方法或精确方法来加以解决，各子问题之间存在相互依赖的关系。采用多阶段分解步骤可使复杂的问题简单化，避免产生局部最小化的结果。 "

LRP的启发式算法主要有：

先解决定位-配给问题(Location-allocation first)，然后解决车辆路线安排问题(Route-second)，即先选址，后路径。

Jacobsen和Madsen(19

7

8)用这种方法解决两层报纸分发系统的交换点的带时间窗的LRP，这两人在(19

80)用此方法与节约法解决了报纸分发的带时间窗的LRP，Harrison(19

7

9)用同样的方法解决了多仓库多车辆的随机LRP。还有用此方法与插入法解决了多级、多设施、多车辆血库的LRP。此外还有Nambiar et al (19

8

1), Bookbinder和Reece(19

8

8)等。

先解决车辆路线安排问题(Route-first )，然后解决定位-配给问题( Location-allocation second )，即先路径，后选址。

Perl和Daskin(1984,19

8

5)用这种方法解决了有车辆容量约束的和设施无容量约束的多设施多车辆的仓库的LRP等。

节约成本/插入。一般来说节约成本/插入算法不单独使用，总是和其他的混合起来使用，且此算法一般用于生成路线，它是以Clarke和Wright及Rosenkrantz et al所提出的算法为基础。Clarke和Wright (19

6

4)提出的节约算法其核心思想就是将运输问题中存在的两个回路合并成一个回路。

改进路线/交换。最初由Lin(19

6

5)提出的“路线的改进/交换”启发式算法，也用于设计运输工具的行程路线，采用的方法是：可行的路线连续地改变，以便产生降低总成本的另一条可行路线，直至成本不可能再降低。因此，不同于降低成本/插入方法，这种启发式算法在整个解题步骤中都要保持可行性。常见的交换算法有：

k-opt exchange,or-opt exchange,?姿-interchange,relocate exchange。

其中：k-opt exchange表示的是k边交换，用的比较多的是2-opt exchange和3-opt exchange。

用的比较多的是2-opt.exchange，它不会改变路的方向。relocate exchange表示的是不同线路点的交换。如图：

实际上是的扩展，即一条线路上的小于等于 个客户与另一条线路的小于等于 个客户交换。

参考文献 [2]张长星,党延忠.定位一运输路线安排问题的遗传算法研究[J].计算机工程与应用,2004,12,65-68. [４]林岩,胡祥培,王旭茵.物流系统优化中的定位-运输路线安排问题( LRP)研究评述[J].管理工程学报,2004,4

(1

8):45-49.