的求解算法

LRP是定位—配给问题（LAP）和运输车辆路线安排问题（VRP）的集成，属于NP-hard问题。而且LRP所研究的问题是在已知设施点和客户点的约束条件下，确定设施的位置、数目和运输路线，因此，属于组合优化问题。由于问题的复杂性，对其进行求解存在一定的困难。目前，一般采用启发式算法来求解LRP问题，采用启发式算法可以提高求解的速度，还可以求解规模较大的问题。求解LRP的启发式算法可以分为：禁忌搜索算法、模拟退火算法、遗传算法、蚁群算法等。在5．1．3节中我们已对这些启发式算法做了简单的介绍。目前常用方法是两阶段启发式算法，将LRP问题分解成两个子问题，将这两个问题依次采用启发式算法进行求解。采用两阶段方法可使复杂的问题简单化，避免发生局部最优的后果。

Hokey Min认为求解LRP问题的启发式方法主要有如下四种［77］：

（1）先解决定位—配给问题，然后再解决运输路线安排问题（Location-allocation，Route-second）；

（2）先求解运输路线安排问题，然后再求解定位—配给问题（Route-first，Location-allocation-sencond）；

（3）费用降低／插值算法（Savings／Insert）；

（4）路线改进／交换（the Tour Improvement／Exchange）。

Perl和Daskin［61］将多设施LRP问题分成了三个子问题：（1）多设施车辆调度问题；（2）设施的定位—配给问题；（3）运输路线安排问题；先解决定位—配给问题，然后解决车辆路线安排问题构造一个初始可行解，然后采用一种改进方法求得最优解。此算法解决了考虑配送中心可变费用和有通过能力约束限制的LRP模型。Srisvastava和Beton［4］给出了一个两阶段求解算法，采用“先求解运输路线安排问题，然后求解定位—配给问题”的方法获得初始解，然后通过改进求得最优解。Tuzun和Burke［103］两阶段的禁忌搜索算法；首先采用禁忌搜索算法求解车辆运输路线安排问题，然后再用禁忌搜索算法求解定位—配给问题，得到问题的初始解，最后用领域改进的搜索法进行改进。

在启发式算法中，禁忌搜索算法具有全局寻优能力，而且比较容易实现，自从20世纪90年代就引起了广泛的重视。遗传算法是一种全局优化概率算法，具有以下优点：（1）遗传算法对所求解的优化问题没有太多的数学要求，由于它的进化特性，搜索过程中不需要问题的内在性质，对于任意形式的目标函数和约束，无论是线性的还是非线性的，离散的还是连续的都可处理。（2）进化算子的各态历经性使得遗传算法能够非常有效地进行概率意义的全局搜索。（3）遗传算法对于各种特殊问题可以提供极大的灵活性来混合构造邻域独立的启发式，从而保证算法的有效性。因此，本书在构造了LRP数学模型后，采用禁忌搜索—遗传混合算法对LRP问题进行求解。