尧图网站开发 
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”表示找到了局部最优可能还有更好的解但对于线性规划问题如果模型是凸的局部最优就是全局最优。对于MILPLingo会进行分支定界搜索最终状态应为全局最优。解的报告在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求解器选择。对于MILPBranch-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的边手动画出路径图这是发现子回路最直接的方法。5.4 Lingo语法错误与调试SUM和FOR函数是Lingo建模的核心务必掌握其用法。SUM(集合[条件]: 表达式)和FOR(集合[条件]: 约束表达式)。注意集合的命名和引用要一致。在LINK(i,j)上定义变量x那么在约束中引用时也要用x(i,j)。使用条件过滤时#NE#表示不等于#GT#表示大于#AND#表示逻辑与。遇到语法错误Lingo通常会高亮错误行附近。仔细阅读错误信息常见的错误有未定义的集合成员、缺少括号、运算符错误等。我个人最深刻的体会是数学建模竞赛中一个清晰、正确的模型描述比复杂的算法更重要。这道C题的价值在于它完整地展示了一个实际优化问题如何被一步步抽象、建模、转化为Lingo代码并求解的全过程。很多同学沉迷于寻找“高级算法”却忽略了把基础模型写对、写清楚。先把这道题吃透理解每一个约束的物理意义和数学表达未来遇到更复杂的路径规划、排产调度、资源分配问题时你才能举一反三知道从哪里入手。最后一定要动手去写、去调、去试错。Lingo报错时别慌那正是你理解模型底层逻辑的最好时机。 
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”表示找到了局部最优可能还有更好的解但对于线性规划问题如果模型是凸的局部最优就是全局最优。对于MILPLingo会进行分支定界搜索最终状态应为全局最优。解的报告在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求解器选择。对于MILPBranch-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的边手动画出路径图这是发现子回路最直接的方法。5.4 Lingo语法错误与调试SUM和FOR函数是Lingo建模的核心务必掌握其用法。SUM(集合[条件]: 表达式)和FOR(集合[条件]: 约束表达式)。注意集合的命名和引用要一致。在LINK(i,j)上定义变量x那么在约束中引用时也要用x(i,j)。使用条件过滤时#NE#表示不等于#GT#表示大于#AND#表示逻辑与。遇到语法错误Lingo通常会高亮错误行附近。仔细阅读错误信息常见的错误有未定义的集合成员、缺少括号、运算符错误等。我个人最深刻的体会是数学建模竞赛中一个清晰、正确的模型描述比复杂的算法更重要。这道C题的价值在于它完整地展示了一个实际优化问题如何被一步步抽象、建模、转化为Lingo代码并求解的全过程。很多同学沉迷于寻找“高级算法”却忽略了把基础模型写对、写清楚。先把这道题吃透理解每一个约束的物理意义和数学表达未来遇到更复杂的路径规划、排产调度、资源分配问题时你才能举一反三知道从哪里入手。最后一定要动手去写、去调、去试错。Lingo报错时别慌那正是你理解模型底层逻辑的最好时机。