列生成算法在旅行商问题中的应用示例 题目描述 考虑一个旅行商问题（TSP）：一个销售员需要访问n个城市（城市0,1,...,n-1），每个城市恰好访问一次，最后返回起点城市，目标是找到总距离最短的环路。城市之间的距离矩阵已知且对称。这是一个NP难问题，直接求解困难。我们将使用列生成算法，将其建模为集合覆盖模型，通过线性规划松弛来获得下界。 解题过程 第一步：问题建模为集合覆盖模型 将TSP视为选择若干个环路的集合，使得每个城市被恰好覆盖一次（即每个城市在环路中出现一次）。但这样会导致模型包含所有可能的环路，数量是指数级的。因此，我们使用列生成：主问题初始只包含部分变量（环路），然后通过求解子问题（即定价问题）来生成新的、可能改善目标的环路（列）。 主问题（松弛后）： 变量：\( \lambda_ p \) 表示是否选择环路p（连续松弛，0 ≤ \( \lambda_ p \) ≤ 1） 目标：最小化总距离，即 \( \min \sum_ p c_ p \lambda_ p \)，其中 \( c_ p \) 是环路p的长度 约束：每个城市被恰好覆盖一次，即 \( \sum_ p a_ {ip} \lambda_ p = 1, \forall i \)，其中 \( a_ {ip} = 1 \) 如果城市i在环路p中，否则为0。 由于环路数量巨大，我们初始只包含一个简单的环路集合（如每个城市自环），然后通过列生成动态添加环路。 第二步：初始化限制主问题 初始限制主问题（RMP）只包含少量环路，例如n个自环（每个环路只包含一个城市，距离为0）。但自环不满足TSP的访问要求，因此需要添加人工变量或调整。更实际的方法是：初始包含一些简单环路，如通过最近邻法生成的环路。但为简单，我们假设初始RMP包含一组可行解（如多个小环路覆盖所有城市），但可能质量差。 RMP的线性规划形式： 变量：已生成的环路对应的 \( \lambda_ p \) 约束：覆盖约束（等式） 求解RMP得到对偶变量 \( \pi_ i \)（每个城市i对应一个对偶值）。 第三步：定价子问题（生成新列） 子问题是寻找一个环路p，使得其缩减成本 \( \bar{c} p = c_ p - \sum {i} a_ {ip} \pi_ i \) 为负（因为主问题是最小化）。如果存在，则该环路可加入RMP改善目标。 子问题实质是一个最短路径问题，但要求形成环路，且需满足TSP约束（每个城市最多访问一次）。这可以建模为一个资源约束最短路径问题（RCSP），其中： 图节点：城市0到n-1（起点可固定为城市0，但环路需包含所有城市？不，子问题只生成一个环路，它可能只包含部分城市，但最终主问题会组合多个环路覆盖所有城市——这是集合覆盖模型的松弛，允许解分裂为多个子环路）。 目标：找到一条从城市0出发并返回城市0的路径（环路），但路径可访问多个城市，其成本为实际距离减去对偶值 \( \pi_ i \)（访问城市i获得“奖励” \( \pi_ i \)）。 约束：路径不能重复访问城市（即简单环路）。 子问题是NP难的（类似于TSP），但规模小（n城市），可用动态规划（如Held-Karp算法）或启发式求解。例如，用标签算法（labeling algorithm）求解RCSP：状态为（当前城市，已访问城市集合），代价为累积缩减成本。 第四步：迭代过程 求解当前RMP（线性规划），得到对偶变量 \( \pi_ i \)。 求解子问题：寻找缩减成本为负的环路。如果找到，加入RMP；否则，当前解是最优的（线性规划松弛下）。 重复直到无负缩减成本环路。 最终得到TSP的线性规划下界。由于TSP是整数规划，这个下界可能不是整数解（解可能包含多个子环路），需结合分支定界获得精确解（即分支定价）。 第五步：示例说明 假设3个城市（0,1,2），距离矩阵：d(0,1)=2, d(0,2)=3, d(1,2)=1。初始RMP包含环路：0-1-0（距离4）、1-2-1（距离2）、2-0-2（距离6）。覆盖约束：每个城市被覆盖一次。 求解RMP得对偶值。子问题：计算新环路缩减成本，如环路0-1-2-0，成本d=2+1+3=6，减去对偶和。如果缩减成本负，则加入。迭代直到无负成本列，得到下界（此例下界可能为实际最优解6）。 总结 列生成将TSP分解为主问题（选择环路）和子问题（生成环路），通过迭代逼近最优解。这种方法能处理大规模TSP实例，是精确算法的基础。