1. 项目概述：从数学建模到真实路线规划
刚接触数学建模那会儿，总觉得那些题目离现实很远，直到自己真正参与了一次旅游规划，才发现“合理路线选择”这个看似简单的问题，背后全是数学。Mathorcup第四届C题“合理旅游路线的选择与优化”，就是一个典型的将抽象数学模型落地到具体生活场景的绝佳案例。它要求参赛者为一个旅行团设计从北京出发，游览多个城市后返回北京的最经济路线，并考虑游览时间、城市间交通方式与成本等约束。这本质上是一个带约束的旅行商问题（TSP）的变体，但比经典的TSP更“接地气”，因为它引入了多种交通方式、时间窗口和固定成本，更贴近真实的旅游团操作。
对于刚入门数学建模的同学，或者是对运筹学、路径优化感兴趣的朋友来说，这道题是一个完美的练手项目。它不像一些纯理论题目那样让人望而生畏，其目标非常直观：怎么走最省钱？同时，它又涵盖了线性规划、整数规划、图论等核心建模思想。题目附带的Lingo代码，更是提供了从模型构建到软件求解的完整闭环，让你不仅能理解理论，还能亲手实现并看到结果。本文将带你深度拆解这道赛题，我会结合自己多次带队参赛和实际项目中的经验，不仅还原标准解法，更会分享那些论文里不会写的建模思路、Lingo调试技巧和常见避坑指南，让你真正掌握从问题分析到代码实现的完整技能链。
2. 问题核心与建模思路拆解
2.1 问题重述与关键约束识别
拿到题目，第一步不是急着写公式，而是像侦探一样，把题目中的所有条件和要求“翻译”成数学语言。原题的核心要素可以提炼如下：
- 节点与路径：有若干个需要游览的城市（包括起点北京），城市之间的移动构成路径。
- 决策变量：核心决策是“旅行团是否选择从城市i直接前往城市j”，这通常是一个0-1变量。
- 目标函数：最小化总旅行成本。成本包括两部分：城市间的交通费（与是否选择该路径有关），以及每个城市的固定游览费用（只要到达该城市就产生）。
- 核心约束：
- 每个城市只访问一次（除起点外）：这是TSP问题的经典约束，保证路线是一个环游。
- 从北京出发并返回北京：这定义了路径的起点和终点。
- 时间约束：总旅行时间（交通时间+游览时间）不能超过一个上限。这里交通时间取决于选择的交通方式（如高铁、飞机，不同方式耗时不同）。
- 交通方式选择：城市间可能存在多种交通方式，需要从中选择一种，这引入了额外的选择变量。
- 子回路消除约束：这是解决TSP问题的关键，防止模型产生多个不连通的循环，而不是一个完整的大环。
很多新手在建模时，会试图用一个变量同时表示“是否从i到j”和“选择什么交通方式”，这会使模型变得非常复杂。更清晰的思路是进行分层建模：首先，将“城市i到城市j”的这段路程，抽象成一个“边”。然后，对于每一条边，它可能有多种“属性”，比如乘坐高铁的成本和时间，乘坐飞机的成本和时间。我们的决策其实是二维的：第一，选不选这条边；第二，如果选了，用哪种属性（交通方式）。
2.2 模型选择：为什么是混合整数线性规划（MILP）？
面对这样一个包含0-1决策（是否访问、选择何种交通方式）和连续变量（时间累计），且目标函数和约束条件都是线性关系的问题，混合整数线性规划（Mixed-Integer Linear Programming, MILP）几乎是唯一的选择。
- 整数变量（Integer）：用来表示“是否”这类逻辑选择。例如，定义二元变量 ( x_{ij} = 1 ) 表示从城市i直接前往城市j，否则为0。定义二元变量 ( y_{ij}^k = 1 ) 表示在从i到j的行程中选择第k种交通方式。
- 连续变量（Continuous）：用来表示时间等可以取任意实数的量。例如，定义变量 ( t_i ) 表示到达城市i的时刻。
- 线性（Linear）：目标函数（总成本）是这些变量的线性组合，约束条件（如时间总和、每个城市只离开一次）也都是线性等式或不等式。
选择MILP模型的好处是，它有成熟的理论和强大的求解器（如Lingo、CPLEX、Gurobi）支持，能够高效地找到全局最优解或优质可行解。相比之下，动态规划或启发式算法（如遗传算法、模拟退火）虽然也能处理，但对于这道题给定的规模，MILP借助求解器更能保证解的最优性和精确性，也更符合数学建模竞赛对模型严谨性的要求。
注意：在正式比赛中，清晰地区分变量类型并说明选择MILP的理由，是论文获得高分的关键。评委希望看到你理解不同模型范式的适用场景，而不是简单地套用公式。
2.3 模型构建详解：从变量定义到约束书写
我们来一步步构建这个MILP模型。假设有N个城市，编号1到N，其中城市1是北京（起点兼终点）。城市i到城市j有 ( K_{ij} ) 种交通方式可选。
1. 定义集合：
- ( V = {1, 2, ..., N} )：所有城市的集合。
- ( A = {(i, j) | i, j \in V, i \neq j} )：所有可能弧段（有向边）的集合。
- ( K_{ij} )：从城市i到城市j可选的交通方式集合。
2. 定义参数（已知数据）：
- ( c_{ij}^k )：采用第k种交通方式从城市i到城市j的票价。
- ( d_{ij}^k )：采用第k种交通方式从城市i到城市j所需的时间。
- ( f_i )：在城市i游览所需的固定时间（如参观景点时间）。
- ( g_i )：到达城市i所需支付的固定费用（如门票、住宿套餐费）。
- ( T_{max} )：允许的最大总旅行时间。
- ( M )：一个足够大的正数，在子回路消除约束中常用，通常可取所有城市间最大旅行时间的若干倍，或总时间上限 ( T_{max} )。
3. 定义决策变量：
- ( x_{ij} \in {0, 1} )：二元变量，1表示旅行路线中包含从i到j的直接移动，0表示不含。
- ( y_{ij}^k \in {0, 1} )：二元变量，1表示在从i到j的行程中采用第k种交通方式，0表示不采用。
- ( t_i \ge 0 )：连续变量，表示到达城市i的时刻（可以定义从出发开始计算的小时数）。
4. 目标函数：最小化总成本总成本由交通成本和城市固定费用组成。由于固定费用 ( g_i ) 只要到达城市i就产生，而到达意味着至少有一条入边 ( x_{ji} = 1 )（对于起点北京，我们默认已“到达”）。因此，目标函数为： [ \min \sum_{(i,j) \in A} \sum_{k \in K_{ij}} c_{ij}^k y_{ij}^k + \sum_{i \in V \setminus {1}} g_i \cdot ( \sum_{j \in V, j \neq i} x_{ji} ) ] 第二项保证了只要有任何一条路线进入城市i（非起点），就需要支付 ( g_i )。对于起点北京，其固定费用 ( g_1 ) 可以单独考虑，通常包含在初始成本中或视为0。
5. 约束条件：
流量平衡约束（每个城市访问一次）：对于每个城市i，必须有一条边进入，一条边离开。 [ \sum_{j \in V, j \neq i} x_{ij} = 1, \quad \forall i \in V ] [ \sum_{j \in V, j \neq i} x_{ji} = 1, \quad \forall i \in V ] 这两个约束保证了路线形成一个“环”，每个城市都是环上的一个节点。
交通方式选择耦合约束：如果选择了从i到j的弧（( x_{ij}=1 )），那么必须且只能选择一种交通方式；如果没有选择（( x_{ij}=0 )），则不能选择任何交通方式。 [ \sum_{k \in K_{ij}} y_{ij}^k = x_{ij}, \quad \forall (i,j) \in A ] 这个约束是连接路径选择和方式选择的关键，确保了逻辑一致性。
时间计算与累积约束：定义到达时间变量 ( t_i )。当从i到j，采用第k种方式时，到达j的时间至少是 ( t_i + f_i + d_{ij}^k )（即从i出发的时间 ( t_i )，加上在i的游览时间 ( f_i )，再加上旅途时间 ( d_{ij}^k )）。这需要用“大M法”来线性化这个逻辑关系。 [ t_j \ge t_i + f_i + d_{ij}^k - M(1 - y_{ij}^k), \quad \forall (i,j) \in A, k \in K_{ij} ] 这个约束是理解时间窗问题的核心。解释一下：如果 ( y_{ij}^k = 1 )（即选择了此方式和路径），那么不等式右边变为 ( t_i + f_i + d_{ij}^k - M*0 )，约束生效，强制 ( t_j \ge t_i + f_i + d_{ij}^k )。如果 ( y_{ij}^k = 0 )，右边变为一个很小的值（因为减去一个大M），约束自动满足，不起作用。
总时间限制：最终返回北京的时间不能超过上限。假设 ( t_1 ) 是离开北京的时间（可设为0），那么返回北京（城市1）的时间 ( t_1^{return} ) 需要满足： [ t_1^{return} \le T_{max} ] 注意，在模型中，返回北京意味着存在一条边进入城市1，其到达时间由对应的约束计算得出。我们需要为“返回北京”这个事件也定义一个到达时间变量，或者直接约束所有可能进入北京的路径计算出的时间。
子回路消除约束（Subtour Elimination Constraints, SEC）：这是TSP建模的精华与难点。仅有流量平衡约束，模型可能会产生多个互不相连的小圈（子回路），而不是一个包含所有城市的大圈。最常用的是MTZ约束（Miller-Tucker-Zemlin），它通过引入辅助变量 ( u_i ) 来记录访问顺序。 [ u_i - u_j + N \cdot x_{ij} \le N-1, \quad \forall i, j \in V \setminus {1}, i \neq j ] [ 1 \le u_i \le N-1, \quad \forall i \in V \setminus {1} ] 其中 ( u_i ) 是连续变量，表示城市i在路线中的访问次序。这个约束保证了路径中不会形成不包含起点1的回路。MTZ约束的优点是约束数量相对较少（( O(N^2) ) 级），易于实现。缺点是它可能产生相对较弱的线性规划松弛，对于大规模问题求解效率可能不是最高，但对于本题规模完全足够。
起点设置：可以设定 ( t_1 = 0 )，表示从北京出发的时刻为0。
3. Lingo代码实现与核心技巧
有了数学模型，用Lingo实现就是将上述公式“翻译”成Lingo语法。Lingo的语法相对直观，但有些细节处理不好，会导致模型无解或求解效率低下。
3.1 数据组织与初始化
在Lingo中，数据通常定义在DATA部分。对于本题，我们需要定义城市集合、成本矩阵、时间矩阵等。清晰的数据组织是成功的第一步。
MODEL: SETS: CITY /1..5/: f, g, t, u; ! 假设有5个城市，f游览时间，g固定费，t到达时间，uMTZ次序; LINK(CITY, CITY): x, c, d; ! x是0-1决策变量，c是成本，d是时间; ! 注意：这里为了简化，假设每对城市间只有一种交通方式。多种方式需要扩展集合。 ENDSETS DATA: ! 城市间交通成本矩阵 c(i,j) (单位：元) ; c = 0 300 500 400 600 300 0 200 350 450 500 200 0 250 300 400 350 250 0 280 600 450 300 280 0; ! 城市间交通时间矩阵 d(i,j) (单位：小时) ; d = 0 4.5 6.0 5.0 7.0 4.5 0 2.5 3.5 4.0 6.0 2.5 0 2.0 3.0 5.0 3.5 2.0 0 2.5 7.0 4.0 3.0 2.5 0; ! 每个城市的游览时间 f(i) (小时) ; f = 0 8 6 10 7; ! 城市1（北京）游览时间设为0，或根据题意设定; ! 每个城市的固定费用 g(i) (元) ; g = 0 200 150 300 180; ! 城市1（北京）固定费用可能为0或已包含; ! 最大允许总时间 Tmax (小时) ; Tmax = 120; ! 大M值，通常取一个足够大的数，如总时间上限的2倍 ; BigM = 240; ! 城市数量 N ; N = 5; ENDDATA实操心得：在Lingo中直接写矩阵数据时，务必注意格式对齐。更稳妥的做法是将数据保存在文本文件中，使用
@FILE函数导入，便于修改和调试。例如：c = @FILE('cost_data.txt');。
3.2 模型部分代码编写
接下来是核心的模型部分，对应我们之前推导的公式。
! 目标函数：最小化总成本（交通成本 + 城市固定费用）; MIN = @SUM(LINK(i,j): c(i,j) * x(i,j)) + @SUM(CITY(i) | i #GT# 1: g(i) * @SUM(CITY(j) | j #NE# i: x(j,i)) ); ! 解释：第二部分对每个非起点城市i，如果存在从某个j到i的路径(x(j,i)=1)，则加上其固定费用g(i)。 ! 约束条件部分; ! 1. 每个城市必须离开一次; @FOR(CITY(i): @SUM(CITY(j) | j #NE# i: x(i,j)) = 1; ); ! 2. 每个城市必须到达一次; @FOR(CITY(i): @SUM(CITY(j) | j #NE# i: x(j,i)) = 1; ); ! 3. 时间累积约束 (使用大M法); @FOR(LINK(i,j) | i #NE# j: t(j) >= t(i) + f(i) + d(i,j) - BigM * (1 - x(i,j)); ); ! 注意：这个写法是简化版，假设x(i,j)=1时路径必然存在。更严格的写法需要将d(i,j)与x(i,j)关联，但此处d已包含在条件中。 ! 4. 总时间约束：返回起点的时间不超过Tmax; ! 我们需要找到返回北京（城市1）的那条边。约束可以写为：对于所有进入城市1的边，其计算出的到达时间需满足。 ! 一种方法是添加一个虚拟的“返回时间”变量，更简单的方式是约束所有可能使t(1)增加的情况。 ! 这里采用一个技巧：约束离开北京后，再次“到达”北京的时间。由于t(1)初始为0，我们约束由任何城市j返回北京1所计算出的新时间。 ! 实际上，大M法约束已经包含了所有边的时间关系。我们只需额外约束最终时间。 ! 可以添加：t(1) <= Tmax; 但注意t(1)在离开时被设为0，返回时会被更新。 ! 更准确的做法是，复制一个返回时间变量t_return，并约束它。这里为简化，我们约束所有城市的到达时间不超过Tmax（因为最终要返回，总时间肯定大于任一城市的到达时间）。 @FOR(CITY(i): t(i) <= Tmax); ! 5. 子回路消除约束 (MTZ公式); @FOR(CITY(i) | i #GT# 1: u(i) >= 1; u(i) <= N - 1; ); @FOR(LINK(i,j) | i #NE# j #AND# i #GT# 1 #AND# j #GT# 1: u(i) - u(j) + N * x(i,j) <= N - 1; ); ! 6. 定义变量类型; @FOR(LINK(i,j): @BIN(x(i,j))); ! x是0-1变量; @FOR(CITY(i): @FREE(t(i))); ! 到达时间可以是任意非负实数; @FOR(CITY(i) | i #GT# 1: @GIN(u(i))); ! MTZ次序变量可以是整数，但用连续变量松弛也可行，这里设为整数; ! 7. 起点北京的时间设为0; t(1) = 0; END3.3 Lingo求解与结果解读
编写完代码后，点击Solve按钮运行。Lingo会尝试寻找最优解。
- 状态窗口解读：求解结束后，关注状态窗口。“Global optimal solution found”表示找到了全局最优解，这是最理想的情况。“Local optimal solution found”表示找到了局部最优，可能还有更好的解，但对于线性规划问题，如果模型是凸的，局部最优就是全局最优。对于MILP，Lingo会进行分支定界搜索，最终状态应为全局最优。
- 解的报告：在
Solution Report中，找到变量x(i,j)的值。值为1的x(i,j)就构成了最优路径。例如，x(1,3)=1, x(3,4)=1, x(4,2)=1, x(2,5)=1, x(5,1)=1表示路径为 北京(1) -> 城市3 -> 城市4 -> 城市2 -> 城市5 -> 返回北京(1)。 - 目标函数值：报告中最上方给出的目标函数值就是最小总成本。
- 敏感性分析（可选）：对于线性规划部分，可以查看约束的松弛/剩余变量和对偶价格，分析哪些资源（如时间）是瓶颈。但对于整数规划，敏感性分析意义有限。
踩坑记录：我第一次运行时，模型总是“无可行解”。排查后发现是时间约束过紧。某个城市间的旅行时间
d(i,j)加上游览时间f(i)再累加后，很容易就超过了Tmax。特别是当Tmax设置不合理时。调试技巧：可以先注释掉时间约束，让模型只求解最短路径（不考虑时间），看是否能得到解。然后再逐步加入时间约束，并检查BigM的值是否设置合理。BigM不能太小，否则可能割掉可行解；也不能太大，否则会影响模型数值稳定性，通常取一个比可能最大时间累加值稍大的数即可。
4. 模型扩展与优化思路
原题是一个经典的框架，但在实际应用或更高级的比赛中，我们可以从多个角度进行扩展，让模型更强大、更实用。
4.1 处理多种交通方式
前述简化模型假设城市间只有一种交通方式。要处理多种方式，需要引入新的集合和变量。
SETS: CITY /1..N/: ...; MODE /1..M/: ; ! 定义交通方式集合，如1-高铁，2-飞机，3-汽车; LINK_MODE(CITY, CITY, MODE): y, c_mode, d_mode; ! y是选择该方式的0-1变量，c_mode和d_mode是对应的成本和时间; ENDSETS目标函数变为：MIN = @SUM(LINK_MODE(i,j,m): c_mode(i,j,m)*y(i,j,m)) + ...约束需要增加耦合关系：@FOR(LINK(i,j): @SUM(MODE(m): y(i,j,m)) = x(i,j);)以及时间约束中d(i,j)替换为@SUM(MODE(m): d_mode(i,j,m)*y(i,j,m))。这增加了变量数量，但模型结构依然清晰。
4.2 引入时间窗约束
现实中的旅游团可能需要在特定时间到达某城市（如观看演出），或某景点只在特定时间段开放。这需要引入硬时间窗或软时间窗。
- 硬时间窗：到达时间 ( t_i ) 必须在 ([a_i, b_i]) 区间内。在模型中添加约束：
a_i <= t_i <= b_i。 - 软时间窗：允许提前或延误，但需要支付惩罚成本。这需要在目标函数中增加惩罚项，例如
+ @SUM(CITY(i): p_early * max(a_i - t_i, 0) + p_late * max(t_i - b_i, 0))，其中p_early和p_late是单位惩罚系数。Lingo中处理max函数可能需要引入辅助变量和额外约束将其线性化。
4.3 多旅行团或车辆路径问题（VRP）变体
如果不止一个旅行团，或者一辆车需要服务多个点后返回仓库，问题就演变为车辆路径问题（VRP）。核心变化是：
- 需要引入车辆集合
VEHICLE /1..K/。 - 决策变量变为
x(i,j,k)，表示车辆k是否从i行驶到j。 - 每个城市必须被恰好一辆车访问一次。
- 每辆车都有容量约束（如载客量）或时间约束。
- 目标可能是最小化总成本、车辆使用数或总行驶距离。
VRP的建模复杂度和求解难度远大于TSP，通常需要更高级的算法（如列生成、分支定价）或强大的启发式算法。
4.4 求解效率优化技巧
当城市数量N增大时，MTZ约束的数量以 (O(N^2)) 增长，可能导致求解变慢。可以尝试以下方法：
- 使用更强的子回路消除约束：如DFJ约束（Dantzig-Fulkerson-Johnson），它通过枚举所有可能的子集S来添加约束：
@SUM(i in S, j not in S: x(i,j)) >= 1。这能提供更紧的松弛，但约束数量是指数级的（(2^N)），不能全部添加。通常采用割平面法：先求解不带DFJ约束的松弛问题，检查解中是否有子回路，如果有，则生成对应的DFJ约束加入模型，重新求解，迭代进行。Lingo支持用户通过回调函数添加割平面，但实现较复杂。 - 提供初始可行解：如果你能通过简单启发式（如最近邻法）快速得到一个可行路线，可以将这个路线对应的
x(i,j)值作为初始解提供给Lingo，能显著加快分支定界过程。在Lingo中使用@POINTER函数或直接在数据段初始化变量值。 - 调整Lingo选项：在
LINGO -> Options -> General Solver中，可以调整整数规划的参数，如Branching Direction（分支方向）、Solver（求解器选择）。对于MILP，Branch-and-Bound（分支定界）是默认且主要的算法。
5. 常见问题排查与实战心得
在实际建模和编程过程中，你会遇到各种各样的问题。这里汇总了一些典型问题及其解决方法。
5.1 模型无可行解（Infeasible）
这是最常见的问题。意味着没有任何变量赋值能同时满足所有约束。
- 排查步骤：
- 逐条注释约束：从最严格的约束（如时间窗）开始，逐一注释掉，每注释一条就求解一次。当某条约束被注释后模型变得可行，那么问题就出在这条约束上。
- 检查数据一致性：仔细核对所有输入数据。例如，
Tmax是否设置得过小？城市间的旅行时间d(i,j)加上最小必要游览时间是否已经超过了Tmax？固定费用g_i是否导致无论如何选择成本都过高（虽然这通常不会导致无解，但可能使目标函数异常）？ - 检查约束逻辑：特别是“大M法”约束。确保
BigM的值足够大。一个检查方法是：计算理论上可能的最大时间累加值（比如所有城市游览时间加上最长的旅行时间之和），然后取一个比它大的数作为BigM。 - 检查子回路消除约束：MTZ约束对于起点城市1的处理很关键。确保约束
@FOR(CITY(i) | i #GT# 1: ...)正确排除了起点。错误的约束可能禁止了任何包含起点的合法路径。
5.2 求解时间过长或内存不足
对于规模稍大（如城市数>20）的问题，MILP求解可能会很慢。
- 应对策略：
- 简化模型：如果问题允许，是否可以减少交通方式的选择？是否可以聚合一些相邻的城市？
- 设置时间/迭代限制：在Lingo选项中可以设置最大求解时间（
Time Limit）或最大迭代次数（Iteration Limit）。到达限制后，Lingo会返回当前找到的最优解（可能是可行解，不一定是全局最优）。 - 调整求解器参数：尝试调整分支定界中的“优先方向”（
Branching Direction），有时选择“最接近边界”或“最大不可行性”能更快找到好解。 - 使用启发式算法求初始解：如前所述，提供一个好的初始解能极大提升速度。
- 考虑使用专业求解器：对于大规模问题，可以考虑将模型导出为
.lp或.mps格式，在更专业的商业求解器如Gurobi、CPLEX中求解，它们的求解效率通常更高。
5.3 结果不符合常识或存在子回路
有时求解器会返回一个解，但仔细一看，路径是不连通的，或者形成了两个独立的环。
- 原因与解决：
- 子回路消除约束失效：这是最可能的原因。检查MTZ约束是否编写正确，特别是城市索引的范围。确保
u(i)变量对于起点城市1没有定义约束（或者将其固定为0）。 - 模型存在对称性：如果所有城市和路径成本完全对称，可能存在多个等价最优解，求解器可能返回其中一个包含子回路的解（如果约束不够强）。可以通过添加微小的随机扰动到成本参数上，打破对称性。
- 查看详细解：在Solution Report中，仔细查看所有
x(i,j)=1的边，手动画出路径图，这是发现子回路最直接的方法。
- 子回路消除约束失效：这是最可能的原因。检查MTZ约束是否编写正确，特别是城市索引的范围。确保
5.4 Lingo语法错误与调试
@SUM和@FOR函数是Lingo建模的核心，务必掌握其用法。@SUM(集合[条件]: 表达式)和@FOR(集合[条件]: 约束表达式)。- 注意集合的命名和引用要一致。在
LINK(i,j)上定义变量x，那么在约束中引用时也要用x(i,j)。 - 使用条件过滤时，
#NE#表示不等于，#GT#表示大于，#AND#表示逻辑与。 - 遇到语法错误，Lingo通常会高亮错误行附近。仔细阅读错误信息，常见的错误有：未定义的集合成员、缺少括号、运算符错误等。
我个人最深刻的体会是：数学建模竞赛中，一个清晰、正确的模型描述比复杂的算法更重要。这道C题的价值在于，它完整地展示了一个实际优化问题如何被一步步抽象、建模、转化为Lingo代码并求解的全过程。很多同学沉迷于寻找“高级算法”，却忽略了把基础模型写对、写清楚。先把这道题吃透，理解每一个约束的物理意义和数学表达，未来遇到更复杂的路径规划、排产调度、资源分配问题时，你才能举一反三，知道从哪里入手。最后，一定要动手去写、去调、去试错。Lingo报错时别慌，那正是你理解模型底层逻辑的最好时机。
)
