第一节　选址-路径问题

选址问题和路径问题是物流中两个基本的规划任务。LRP问题需要做出以下两种类型的决策：

（1）在有限或无限数量的潜在配送中心中选择合适的配送中心开放；

（2）确定车辆路线问题，即需确定每一个顾客应安排哪个车辆按何种次序访问的问题[29]。其网络结构如图2-1所示。

图2-1　LRP问题的网络结构

Watson-Gandy和Dohrn[30]首次通过非线性的利润函数模型，同时考虑了车辆路径和仓库的选址问题。Salhi和Rand[31]量化了同时考虑选址问题和路径问题带来的好处。对于选址路径问题的求解方法主要有两大类：一类是精确算法，另一类是启发式算法。用精确算法解决选址路径问题在近期一些文章中才出现。Belenguer等人[32]提出了一种分支切割算法，并采用新的有效不等式来提高算法效率。Akca等人[33]提出了列生成方法来解决该问题。Baldacci等人[34]将选址路径问题分解为有限的多车库车辆路径的集合，然后基于动态规划方法求解。Contardo等人[35]则用了分支切割和价格的算法。上述的精确算法都可以有效解决50个顾客和5～10个仓库规模的问题。但对于大规模问题，精确算法没有启发式算法求解方便。关于选址-路径问题的启发式算法研究很丰富，主要有基于邻域的启发式算法、模拟退火算法、变邻域算法、蚁群算法。本节从以下几个方面来介绍现有研究成果：

（1）基于邻域的启发式算法。Prins等人[36]利用贪婪随机启发式构造一个初始解，然后通过局部搜索对该解进行改进来求解LRP问题。Duhamel等人[37]利用扰动和局部搜索在每次迭代中生成多个子解来改进经典局部搜索算法，提高LRP问题求解质量。Duhamel等人[38]则采用了分类算法，改进了算法的运行时间。

（2）模拟退火算法。Yu等人[39]采用了模拟退火启发式算法，并将每个解都编码为一个数列来提高邻域解的多样性。Jokar和Sahraeian[40]采用和Yu等人的模拟退火启发式算法相同的编码解，其初始解是通过贪婪-局部搜索算法生成的，且在路径搜索上改进了该算法。

（3）变邻域算法。Jabal-ameli等人[41]提出一个变邻域下降算法。初始解的计算方法是先解决一个选址分配问题，然后使用节约算法为每个仓库构建路径。

（4）蚁群算法。Ting和Chen[42]提出了一种蚁群优化算法，该算法将选址路径问题分解为三个决策层次：一个容量有限的设施选址问题，一个顾客到仓库的分配问题，以及一个针对每个仓库的车辆路径问题。

（5）禁忌搜索算法。Prins等人[43]用拉格朗日松弛和禁忌搜索算法来求解该问题。Escobar等人[44]则采用了两阶段的禁忌搜索算法，在算法中对顾客的分类采用了不同的方法。

选址-路径问题也随着环境的复杂性而拓展，主要的研究成果可以分为多阶段的LRP问题、多目标LRP问题、多周期LRP问题。

（1）多阶段的LRP问题。物流网络可以由三层构成（工厂、配送中心和顾客）组成，其中第一层、第二层或两者都有选址决策。Lin和Lei[45]研究多阶段LRP问题时考虑了无容量约束的配送中心，并用了遗传算法解决了该问题。而Boccia等人[46]设计了一个禁忌搜索算法解决了两阶段的带容量约束的LRP问题。Nguyen等人[47]同样考虑了有容量约束的配送中心，采用了贪婪随机搜索算法提高了求解效率。Contardo等人[48]提出了分支和切割算法，并用有效不等式提高算法的求解效率。而Schwengere等人[49]则用变邻域搜索算法来求解。

（2）多目标LRP问题。Caballero等人[50]在LRP问题的基础上考虑了回收中心的位置与居民区之间的距离因素。Rath和Gutjahr[51]考虑了灾后LRP问题，因而考虑了服务水平。Sun[52]则研究了带时间窗的LRP问题。

（3）多周期LRP问题。Prodhon和Prins[53]提出了一种进化算法来求解多周期的LRP问题。Prodhon[54]提出了一种进化的局部搜索，通过增加搜索范围改进了经典的进化算法。Albareda-Sambola[55]考虑了与上述两篇文章不同的多周期LRP问题，即在每个周期所开放的配送中心可以是不同的。