摘要：定位——运输路线安排问题(Location-Routing Problem——LRP)是物流系统规划和设计中涉及到的一类复杂的组合优化问题，是NP-hard问题，只能用启发式(heuristic)或超启发式(metaheuristic)算法求解。根据对LRP问题的分析和所建立的数学模型，提出了一种用于求解该类问题的metaheuristic算法：禁忌搜索——蚁群混合算法。该算法在禁忌搜索算法的框架中嵌入蚁群算法，用禁忌搜索的方式搜索配送中心的定位方案，对于给定的定位方案通过蚁群算法求出优化的运输路线，运输路线安排优化的结果用于指导禁忌搜索的进一步搜索。
禁忌搜索——蚁群混合算法在求解LRP问题的过程中整体考虑了定位和运输路线优化两方面的决策，能够充分搜索问题的解空间，有效地避免陷入“局部最优”。仿真实验证明了所提出算法的有效性。
关键词：定位——运输路线安排问题(LRP) 组合优化 禁忌搜索算法 蚁群算法
前言
随着经济全球化和信息时代的发展，被誉为继自然资源和劳动力之后的“第三利润源泉”——物流发挥着越来越重要的作用。物流系统在规划和设计中应当根据客户的分布情况合理选择设立配送中心的位置，以尽量减少货物运输费用和降低运营成本，这类问题称为定位——分派问题(Location-Allocation Problem-LAP)。通常在LAP的研究中假设从配送中心出发的车辆服务完一个客户以后就返回配送中心，并没有考虑一台车辆服务多个客户时如何安排路线的车辆路径问题(Vehicle Routing Problem——VRP)。把LAP和VRP结合起来考虑的选址——路线安排问题(Location-Routing Problem——LRP)研究的是在给定的候选地址集合中选择设立配送中心的数量和地点并安排从每个配送中心到客户的车辆运输路线，是物流系统规划与设计中的难题。
VRP是组合优化中的经典问题，是NP-hard问题[1]，LRP比VRP更为复杂，精确算法只能应用于问题规模比较小的情况下，问题规模稍大，就只能采用启发式算法求解。近年来对LRP问题的研究逐渐受到了重视，特别是随着超启发式算法(Metaheuristic)在优化领域的成功，越来越多的学者致力于应用Metaheuristic求解LRP。文[2]采用了一种两阶段的禁忌搜索(Tabu Search)算法求解LRP问题，该方法把LRP分为两个阶段求解：LAP阶段和VRP阶段，每个阶段都使用一个禁忌搜索算法求解，并且在求解过程中采取了一系列简化算法的措施，这种方法的优点是效率比较好，但是由于在求解过程中LRP的两个阶段之间基本上是相互独立的，造成算法对解空间的搜索很可能不充分。文[3]求解LRP使用了一种基于两层树编码的免疫遗传算法，该算法没有按照通常的思路将LRP分为两个阶段求解，而是直接将LRP的解作为一个整体看待，该算法比较复杂，实现起来有一定难度。文[4]研究了一类特殊的LRP问题，也是将其分为两个阶段求解，第一阶段采用了基于最小包络法的启发式算法，第二阶段采用带有控制开关的遗传算法求解。
本文设计了一种用于求解LRP的禁忌搜索——蚁群混合算法，该算法将蚁群算法嵌入禁忌搜索算法的框架中，用禁忌搜索方法确定设立配送中心的数目和地点，在配送中心的定位方案确定后用蚁群算法求解运输路线安排问题，运输路线安排的结果又用来指导进一步的禁忌搜索。这种混合算法整体考虑了LRP问题中的定位和运输路线优化两方面的决策，充分利用了蚁群算法在路径搜索上的优越性能。