1. 从一道赛题看旅游路线设计的数学内核如果你参加过数学建模竞赛或者对运筹优化感兴趣那么“最佳旅游路线设计”这个题目一定不陌生。它听起来像是一个旅游攻略问题但其内核是一个经典的组合优化难题——旅行商问题及其变种。Mathorcup第四届的这道C题正是将TSP问题置于一个更贴近现实的场景中要求参赛者不仅要找到最短路径还要综合考虑时间、成本、景点评分等多重约束最终设计出“最佳”而非“最短”的路线。这其中的“最佳”就是数学建模的魅力所在也是这道题区分于教科书例题的关键。今天我就以这道赛题为引子抛开竞赛的紧张氛围和大家深入聊聊当我们用数学工具去规划一次旅行时到底在解决哪些问题以及如何用LINGO这样的优化软件将想法落地。无论你是数学建模的新手还是对优化算法感兴趣的开发者相信这篇从实战出发的拆解都能给你带来一些新的启发。这道题通常会给出一组城市或景点以及它们之间的交通距离或时间、费用同时每个景点可能有各自的游览时间、门票费用、满意度评分等属性。参赛者的任务是在满足总时间或总预算限制的前提下规划一条从起点出发、游览所有或部分指定景点、最后返回起点的环路使得某个目标如总满意度最高、总成本最低、或综合效用最大达到最优。这立刻将问题从单纯的“最短路径”提升到了“多目标决策”的层面。我们面对的不再是一个静态的网络而是一个充满权衡的动态系统。选择绕远路去一个高分景点是否值得在有限的时间里是追求广度去更多景点还是深度在少数精品景点花费更多时间这些旅行中真实存在的纠结正是数学模型需要量化并求解的核心。2. 问题拆解从旅行需求到数学模型框架面对这样一个多因素交织的问题直接上手编程或调包是行不通的。第一步也是最重要的一步是进行严谨的问题分析和模型构建。我们需要把模糊的“最佳”转化为数学语言中清晰的“目标函数”和“约束条件”。2.1 定义核心要素与决策变量首先要明确问题的基本要素。假设我们有N个需要决策是否游览的景点节点编号为1, 2, ..., N。通常节点1被设定为起点和终点例如酒店所在地。我们需要定义最关键的决策变量。最常用的是0-1决策变量 x_{ij}如果路线中包含从景点i直接前往景点j的路径则 x_{ij} 1否则为 0。同时为了消除子回路即形成多个不包含起点的小环路往往需要引入辅助变量 u_i它可以理解为景点i在路线中的访问次序。接下来是参数也就是题目给出的已知数据距离矩阵 DD[i][j]表示从景点i到景点j的交通距离或时间、成本。景点属性游览时间t_i门票费用c_i满意度评分s_i。全局约束总可用时间T_max总预算B_max。2.2 构建目标函数什么是“最佳”“最佳”是一个主观词在模型中必须客观化。常见的目标函数有以下几种有时也需要组合使用最小化总成本这是最直观的目标之一。总成本通常包括交通成本和景点门票成本。目标函数可以写为Minimize Z Σ_i Σ_j (D[i][j] * x_{ij}) Σ_i (c_i * y_i)其中 y_i 是0-1变量表示是否访问景点i。最大化总满意度如果景点评分代表满意度那么目标就是最大化所游览景点的总评分Maximize Z Σ_i (s_i * y_i)。最大化性价比单位成本的满意度这是一个比率目标处理起来更复杂有时可以转化为在成本约束下最大化满意度。多目标优化例如同时希望“满意度尽量高”且“成本尽量低”。这类问题通常没有唯一的最优解而是一组“帕累托最优”解。竞赛中常用的处理方法是线性加权法将多目标转化为单目标。例如定义综合效用 U α * (总满意度) - β * (总成本)其中α和β是权重系数反映了决策者对满意度和成本的重视程度。权重的设定需要结合题目背景或通过灵敏度分析来讨论。在Mathorcup这道题中很可能需要采用第三种或第四种思路即综合考虑花费和体验这也是实际旅行规划的常态。2.3 确立约束条件现实的枷锁目标函数定义了方向约束条件则划定了可行的范围。除了经典的TSP约束每个景点只能离开一次、到达一次、消除子回路还需要加入资源限制流量平衡约束对于每个景点i进入的路径数等于离开的路径数。Σ_j x_{ji} Σ_j x_{ij} y_i (对于起点可能等于1或2取决于模型设定)。起点终点约束通常要求从节点1出发并最终回到节点1。子回路消除约束这是TSP建模的难点。最常用的是MTZ约束u_i - u_j N * x_{ij} ≤ N-1, 对于所有 i, j ≥ 2 且 i ≠ j。这个约束保证了路径的连续性不会形成多个圈。时间约束总时间 交通时间 游览时间 ≤ T_max。即 Σ_i Σ_j (D[i][j] * x_{ij]) Σ_i (t_i * y_i) ≤ T_max。预算约束总费用 交通费 门票费 ≤ B_max。即 Σ_i Σ_j (D[i][j] * x_{ij]) Σ_i (c_i * y_i) ≤ B_max。可选景点约束如果景点不是必须全部访问那么还需要决策 y_i。并且访问一个景点y_i1的前提是有一条路径进入它Σ_j x_{ji} 1。将以上所有要素整合起来我们就得到了一个完整的混合整数线性规划模型。它可能看起来复杂但结构清晰为后续的求解奠定了坚实的基础。3. LINGO求解实战将模型转化为代码模型建立后下一步就是求解。对于中小规模的问题节点数在20-30左右使用专业的优化软件LINGO是非常高效的选择。LINGO的语法接近数学表达可以直观地描述模型。下面我将基于一个简化场景展示如何将上述模型转化为LINGO代码并附上关键环节的解读。假设我们有5个景点节点1为酒店数据如下距离矩阵D单位小时假设速度恒定故距离即时间节点: 1 2 3 4 5 1: 0 2 9 3 6 2: 2 0 7 4 8 3: 9 7 0 5 2 4: 3 4 5 0 1 5: 6 8 2 1 0景点属性节点游览时间t_i(h)门票费c_i(元)评分s_i23100832150941.580752.51206全局限制总时间T_max12小时总预算B_max400元。目标最大化综合效用 U 总评分 - 0.01 * 总成本这里权重系数将成本单位“元”的影响缩小与评分无量纲量匹配。对应的LINGO程序代码如下MODEL: ! 定义集合 SETS: city /1..5/: u, t, c, s, y; ! city: 景点集合u为MTZ辅助变量t游览时间c门票费s评分y是否访问 link(city, city): d, x; ! link: 城市间的连接d为距离/交通时间x为0-1决策变量 ENDSETS ! 输入数据 DATA: d 0, 2, 9, 3, 6, 2, 0, 7, 4, 8, 9, 7, 0, 5, 2, 3, 4, 5, 0, 1, 6, 8, 2, 1, 0; t 0, 3, 2, 1.5, 2.5; ! 节点1酒店游览时间为0 c 0, 100, 150, 80, 120; s 0, 8, 9, 7, 6; T_max 12; B_max 400; ENDDATA ! 定义目标函数最大化综合效用 MAX SUM(city(i): s(i)*y(i)) - 0.01 * ( SUM(link(i,j): d(i,j)*x(i,j)) SUM(city(i): c(i)*y(i)) ); ! 约束条件部分 ! 1. 流量平衡约束对于每个城市i如果被访问则进入和离开各一次 FOR(city(i): SUM(city(j) | j #NE# i: x(j,i)) y(i); SUM(city(j) | j #NE# i: x(i,j)) y(i); ); ! 2. 必须从节点1出发并回到节点1且必须访问节点1作为起点/终点 y(1) 1; SUM(city(j) | j #GT# 1: x(1,j)) 1; SUM(city(j) | j #GT# 1: x(j,1)) 1; ! 3. 子回路消除约束MTZ约束 FOR(link(i,j) | i #GT# 1 #AND# j #GT# 1 #AND# i #NE# j: u(i) - u(j) 5 * x(i,j) 4; ); ! 设置u变量的边界对于非起点城市 FOR(city(i) | i #GT# 1: u(i) 2; u(i) 5; ); ! 4. 时间约束交通时间 游览时间 T_max SUM(link(i,j): d(i,j)*x(i,j)) SUM(city(i): t(i)*y(i)) T_max; ! 5. 预算约束交通费此处假设单位距离费用为1 门票费 B_max ! 注意此处d(i,j)同时代表距离和时间假设费用与距离成正比系数为1。 若题目单独给出交通费用矩阵需替换d(i,j)为对应费用。 SUM(link(i,j): d(i,j)*x(i,j)) SUM(city(i): c(i)*y(i)) B_max; ! 本例为简化使用与时间相同的矩阵代表费用 SUM(link(i,j): d(i,j)*x(i,j)) SUM(city(i): c(i)*y(i)) B_max; ! 6. 定义变量类型 FOR(link(i,j): BIN(x(i,j))); ! x(i,j)为0-1变量 FOR(city(i): BIN(y(i))); ! y(i)为0-1变量 FOR(city(i): GIN(u(i))); ! u(i)为一般整数变量MTZ约束需要 END代码关键点解读与实操心得集合定义是根基LINGO基于集合编程SETS部分定义了city和link两个集合并声明了附着其上的属性变量和参数。这种定义方式使得后续的约束可以简洁地用FOR和SUM对整个集合进行操作避免了冗长的循环语句是LINGO高效性的体现。MTZ约束的细节子回路消除约束u(i) - u(j) N * x(i,j) N-1是核心。其中N是城市总数本例为5。这个约束确保了如果x(i,j)1即走了i到j的路径则必须有u(j) u(i) 1从而给每个访问的城市赋予一个递增的序号防止形成回路。约束条件中的| i #GT# 1 #AND# j #GT# 1 #AND# i #NE# j表示该约束仅对非起点i1且j1且i不等于j的节点对生效这是标准的写法可以避免不必要的约束和起点处理冲突。起点处理的技巧我们强制y(1)1并约束从节点1出发和进入的路径各为1条。对于u变量起点通常不参与MTZ约束而非起点城市的u值被限定在[2, N]之间这有助于求解器更快地找到可行解。目标函数权重的设定本例中目标函数是总评分 - 0.01 * 总成本。为什么是0.01这是一个尺度统一的过程。评分s_i的量级是个位数6-9而总成本交通门票的量级是数百。如果不加调整成本项将完全主导目标函数导致模型退化为纯粹的成本最小化。乘以0.01或除以100相当于将成本单位从“元”转换为“百分之一元”使其数值量与评分接近从而让两个目标都能对结果产生影响。在实际竞赛中这个权重的选取需要说明理由或者进行灵敏度分析展示不同权重下最优解的变化。求解与结果查看在LINGO中编写完上述代码后点击“Solve”按钮。求解完成后在“Solution Report”窗口中可以查看最优目标函数值以及所有变量的值。重点关注x(i,j)和y(i)的取值。例如x(1,2)1表示最优路线中从1酒店直接去了2号景点。根据这些为1的x变量就能拼接出完整的旅行路线。4. 模型对比与拓展不同场景下的建模思路上述模型是一个基础而完整的框架。但在实际竞赛或应用中题目条件会变化需要我们调整模型。这里对比几种常见变体并讨论其建模思路。4.1 经典TSP vs. 带约束的TSP本题基础经典TSP目标唯一即最小化总旅行距离。约束只有每个城市访问一次、形成单个回路。它不考虑时间、预算、景点选择。求解方法关注于算法效率如动态规划、启发式算法。带约束的TSP本题在TSP基础上增加了资源约束时间、预算和节点选择变量y_i。目标可能变为综合效用最大化。建模核心在于引入0-1决策变量y_i来灵活选择景点并将资源消耗表示为Σ d*x Σ t*y的形式。求解时整数规划的特征更明显依赖于LINGO、CPLEX等求解器的分支定界/割平面能力。4.2 团队旅行与多车辆路径问题VRP如果题目涉及一个团队分乘多辆车游览问题就演变为车辆路径问题。核心变化是决策变量需要引入表示车辆k是否从i行驶到j的变量 x_{ijk}。约束每辆车都有容量载客量约束每条路线都必须从共同的起点车场出发并返回。目标可能是最小化总行驶距离或最小化使用车辆数或均衡各车路线时长。建模复杂度急剧上升。通常需要更强的子回路消除约束如流平衡约束的扩展并且求解难度更大对于稍大规模的问题往往需要设计启发式算法如节约算法、扫描算法来获得满意解。4.3 动态与随机情境下的考量更进一步的挑战是引入不确定性例如交通时间随机两点间的行驶时间不是一个定值d_{ij}而是一个随机变量如服从某种分布。此时严格的时间约束Σ (时间)*x T_max可能变得不现实。建模思路可以采用鲁棒优化或随机规划。例如将时间约束改为概率约束P(总时间 ≤ T_max) ≥ 0.95即要求总时间不超过T_max的概率至少为95%。这需要知道时间随机变量的分布并将该概率约束转化为确定的等价类进行求解难度较高常出现在研究生阶段的赛题中。景点开放时间窗每个景点只能在特定时间段内访问如9:00-17:00。这需要引入时间累计变量并添加复杂的时序约束确保到达每个景点的时间在其时间窗内。这类问题称为带时间窗的车辆路径问题是运筹学的研究热点。5. 竞赛实现中的常见“坑”与应对策略即便模型建得再漂亮代码写得再规范在实际求解和结果分析中还是会遇到各种问题。结合我多次参赛和辅导的经验以下几个“坑”值得特别注意。5.1 求解规模与时间瓶颈LINGO在求解整数规划时采用分支定界法。问题规模节点数N稍大求解时间就会指数级增长。对于N30的问题很可能在规定赛时内无法得到最优解。应对策略初始解启发给LINGO提供一个好的初始解可以大幅加速求解。例如先用最近邻法、插入法等简单启发式算法快速生成一条可行路线然后将这条路线对应的x_{ij}和y_i的值作为初始值赋给LINGO的变量。在LINGO中可以用FOR循环和INIT部分来实现。松弛与分解如果问题可以分解为几个相对独立的子问题例如将景点按区域聚类可以先分别求解子问题再考虑连接。设置求解器参数在LINGO的Options菜单中可以调整整数求解器的相关参数如“最优性容差”适当放宽可以加快求解速度但会损失一点解的质量。转向启发式算法对于大规模问题应果断放弃求精确最优解在论文中明确说明并采用模拟退火、遗传算法、蚁群算法等元启发式算法寻找高质量近似解。这往往是更现实的竞赛策略。5.2 模型无可行解检查约束冲突运行LINGO后有时会直接报告“No feasible solution found”。这意味着在给定的约束条件下不存在任何一条路线能满足所有要求。排查步骤检查数据输入首先核对所有参数D, t, c, T_max, B_max是否输入正确单位是否一致。一个错误的数据可能导致约束过紧。放松约束逐步放松约束找到“卡脖子”的环节。例如先注释掉预算约束看是否有解再注释掉时间约束。如果去掉某个约束后模型有解说明该约束可能过于严格。分析约束紧度计算一个“理论下限”。例如即使马不停蹄地跑访问所有景点的最小总时间 最短哈密顿回路的交通时间 所有景点的游览时间。如果这个值已经大于T_max那么问题显然无解。这时就需要修改问题本身比如允许不访问某些景点y_i变量正是为此设计或者向评委说明在当前资源下无法完成全部游览并给出一个访问最多景点的方案此时目标函数需调整。5.3 结果分析与灵敏度检验得到最优解后工作只完成了一半。深入的结果分析能为论文增色不少。路线可视化用MATLAB、Python的Matplotlib或在线工具将最优路线画在地图上一目了然。图中可以标注景点编号、路径方向、各段距离/时间。资源利用分析计算最优解下的总时间利用率和预算利用率。例如总用时11.5小时/12小时95.8%。这能说明你的方案对资源的利用是否充分。灵敏度分析这是体现建模深度的关键。研究关键参数变动对最优解的影响。权重灵敏度改变目标函数中评分与成本的权重如前文中的0.01观察最优路线和景点选择如何变化。可以绘制帕累托前沿图展示不同权重下的“最佳”权衡。资源灵敏度分析总时间T_max或总预算B_max增加或减少10%会对最优目标值产生多大影响。这能回答“如果预算增加100元我们的综合体验能提升多少”这类实际问题。参数灵敏度如果某个景点的评分s_i或时间t_i存在不确定性可以分析其变化在什么范围内当前的最优路线结构即哪些x_{ij}1保持不变。这称为“最优基不变”的灵敏度分析在线性规划中可以直接从单纯形法的最终表中读取对于整数规划则需要做参数规划。5.4 论文写作中的表达要点数学建模竞赛评阅时模型和求解固然重要但清晰的表达同样关键。避免“黑箱”描述不要只写“我们用LINGO求解”而要详细说明你建立的模型具体是什么列出目标函数和所有约束的数学公式以及你是如何将这个模型“翻译”成LINGO代码的可以像本文第三节那样对关键代码段进行解释。突出创新与调整如果对经典模型做了改进例如设计了新的子回路消除约束、提出了分段加权目标函数一定要重点说明动机和优势。结果呈现要直观除了文字多用表格和图表。例如用一张表清晰列出最优路线的访问顺序、各段耗时、各景点花费用另一张表展示灵敏度分析的结果。讨论模型的优缺点没有完美的模型。在论文结尾客观地讨论你所建模型的局限性例如假设交通时间是固定的未考虑拥堵假设满意度是线性可加的未考虑边际效应递减等并提出可能的改进方向这能展示你的批判性思维。规划一条旅行路线从数学上看是在一个充满约束的网络中寻找最优路径。Mathorcup的这道题巧妙地将经典的运筹学问题包装在一个生活化的场景里。通过它我们实践了从问题分析、模型构建、到软件求解、结果分析的全过程。其中如何定义“最佳”如何用0-1变量表达选择如何用MTZ约束破除子回路以及如何用LINGO实现求解是贯穿始终的技术主线。更重要的是我们看到了数学模型如何将主观的“体验”和客观的“成本”统一到一个框架下进行量化权衡。在实际操作中我最大的体会是数据的尺度预处理和约束的可行性检验是保证模型能顺利求解的两个基石。前者决定了目标函数是否真正反映了你的意图后者避免了在错误的方向上浪费时间。下次当你再规划旅行时或许可以下意识地想想这背后的优化问题是不是也有一个优雅的数学解呢 从数学建模到LINGO实战：旅行商问题与多目标优化在路线规划中的应用
1. 从一道赛题看旅游路线设计的数学内核如果你参加过数学建模竞赛或者对运筹优化感兴趣那么“最佳旅游路线设计”这个题目一定不陌生。它听起来像是一个旅游攻略问题但其内核是一个经典的组合优化难题——旅行商问题及其变种。Mathorcup第四届的这道C题正是将TSP问题置于一个更贴近现实的场景中要求参赛者不仅要找到最短路径还要综合考虑时间、成本、景点评分等多重约束最终设计出“最佳”而非“最短”的路线。这其中的“最佳”就是数学建模的魅力所在也是这道题区分于教科书例题的关键。今天我就以这道赛题为引子抛开竞赛的紧张氛围和大家深入聊聊当我们用数学工具去规划一次旅行时到底在解决哪些问题以及如何用LINGO这样的优化软件将想法落地。无论你是数学建模的新手还是对优化算法感兴趣的开发者相信这篇从实战出发的拆解都能给你带来一些新的启发。这道题通常会给出一组城市或景点以及它们之间的交通距离或时间、费用同时每个景点可能有各自的游览时间、门票费用、满意度评分等属性。参赛者的任务是在满足总时间或总预算限制的前提下规划一条从起点出发、游览所有或部分指定景点、最后返回起点的环路使得某个目标如总满意度最高、总成本最低、或综合效用最大达到最优。这立刻将问题从单纯的“最短路径”提升到了“多目标决策”的层面。我们面对的不再是一个静态的网络而是一个充满权衡的动态系统。选择绕远路去一个高分景点是否值得在有限的时间里是追求广度去更多景点还是深度在少数精品景点花费更多时间这些旅行中真实存在的纠结正是数学模型需要量化并求解的核心。2. 问题拆解从旅行需求到数学模型框架面对这样一个多因素交织的问题直接上手编程或调包是行不通的。第一步也是最重要的一步是进行严谨的问题分析和模型构建。我们需要把模糊的“最佳”转化为数学语言中清晰的“目标函数”和“约束条件”。2.1 定义核心要素与决策变量首先要明确问题的基本要素。假设我们有N个需要决策是否游览的景点节点编号为1, 2, ..., N。通常节点1被设定为起点和终点例如酒店所在地。我们需要定义最关键的决策变量。最常用的是0-1决策变量 x_{ij}如果路线中包含从景点i直接前往景点j的路径则 x_{ij} 1否则为 0。同时为了消除子回路即形成多个不包含起点的小环路往往需要引入辅助变量 u_i它可以理解为景点i在路线中的访问次序。接下来是参数也就是题目给出的已知数据距离矩阵 DD[i][j]表示从景点i到景点j的交通距离或时间、成本。景点属性游览时间t_i门票费用c_i满意度评分s_i。全局约束总可用时间T_max总预算B_max。2.2 构建目标函数什么是“最佳”“最佳”是一个主观词在模型中必须客观化。常见的目标函数有以下几种有时也需要组合使用最小化总成本这是最直观的目标之一。总成本通常包括交通成本和景点门票成本。目标函数可以写为Minimize Z Σ_i Σ_j (D[i][j] * x_{ij}) Σ_i (c_i * y_i)其中 y_i 是0-1变量表示是否访问景点i。最大化总满意度如果景点评分代表满意度那么目标就是最大化所游览景点的总评分Maximize Z Σ_i (s_i * y_i)。最大化性价比单位成本的满意度这是一个比率目标处理起来更复杂有时可以转化为在成本约束下最大化满意度。多目标优化例如同时希望“满意度尽量高”且“成本尽量低”。这类问题通常没有唯一的最优解而是一组“帕累托最优”解。竞赛中常用的处理方法是线性加权法将多目标转化为单目标。例如定义综合效用 U α * (总满意度) - β * (总成本)其中α和β是权重系数反映了决策者对满意度和成本的重视程度。权重的设定需要结合题目背景或通过灵敏度分析来讨论。在Mathorcup这道题中很可能需要采用第三种或第四种思路即综合考虑花费和体验这也是实际旅行规划的常态。2.3 确立约束条件现实的枷锁目标函数定义了方向约束条件则划定了可行的范围。除了经典的TSP约束每个景点只能离开一次、到达一次、消除子回路还需要加入资源限制流量平衡约束对于每个景点i进入的路径数等于离开的路径数。Σ_j x_{ji} Σ_j x_{ij} y_i (对于起点可能等于1或2取决于模型设定)。起点终点约束通常要求从节点1出发并最终回到节点1。子回路消除约束这是TSP建模的难点。最常用的是MTZ约束u_i - u_j N * x_{ij} ≤ N-1, 对于所有 i, j ≥ 2 且 i ≠ j。这个约束保证了路径的连续性不会形成多个圈。时间约束总时间 交通时间 游览时间 ≤ T_max。即 Σ_i Σ_j (D[i][j] * x_{ij]) Σ_i (t_i * y_i) ≤ T_max。预算约束总费用 交通费 门票费 ≤ B_max。即 Σ_i Σ_j (D[i][j] * x_{ij]) Σ_i (c_i * y_i) ≤ B_max。可选景点约束如果景点不是必须全部访问那么还需要决策 y_i。并且访问一个景点y_i1的前提是有一条路径进入它Σ_j x_{ji} 1。将以上所有要素整合起来我们就得到了一个完整的混合整数线性规划模型。它可能看起来复杂但结构清晰为后续的求解奠定了坚实的基础。3. LINGO求解实战将模型转化为代码模型建立后下一步就是求解。对于中小规模的问题节点数在20-30左右使用专业的优化软件LINGO是非常高效的选择。LINGO的语法接近数学表达可以直观地描述模型。下面我将基于一个简化场景展示如何将上述模型转化为LINGO代码并附上关键环节的解读。假设我们有5个景点节点1为酒店数据如下距离矩阵D单位小时假设速度恒定故距离即时间节点: 1 2 3 4 5 1: 0 2 9 3 6 2: 2 0 7 4 8 3: 9 7 0 5 2 4: 3 4 5 0 1 5: 6 8 2 1 0景点属性节点游览时间t_i(h)门票费c_i(元)评分s_i23100832150941.580752.51206全局限制总时间T_max12小时总预算B_max400元。目标最大化综合效用 U 总评分 - 0.01 * 总成本这里权重系数将成本单位“元”的影响缩小与评分无量纲量匹配。对应的LINGO程序代码如下MODEL: ! 定义集合 SETS: city /1..5/: u, t, c, s, y; ! city: 景点集合u为MTZ辅助变量t游览时间c门票费s评分y是否访问 link(city, city): d, x; ! link: 城市间的连接d为距离/交通时间x为0-1决策变量 ENDSETS ! 输入数据 DATA: d 0, 2, 9, 3, 6, 2, 0, 7, 4, 8, 9, 7, 0, 5, 2, 3, 4, 5, 0, 1, 6, 8, 2, 1, 0; t 0, 3, 2, 1.5, 2.5; ! 节点1酒店游览时间为0 c 0, 100, 150, 80, 120; s 0, 8, 9, 7, 6; T_max 12; B_max 400; ENDDATA ! 定义目标函数最大化综合效用 MAX SUM(city(i): s(i)*y(i)) - 0.01 * ( SUM(link(i,j): d(i,j)*x(i,j)) SUM(city(i): c(i)*y(i)) ); ! 约束条件部分 ! 1. 流量平衡约束对于每个城市i如果被访问则进入和离开各一次 FOR(city(i): SUM(city(j) | j #NE# i: x(j,i)) y(i); SUM(city(j) | j #NE# i: x(i,j)) y(i); ); ! 2. 必须从节点1出发并回到节点1且必须访问节点1作为起点/终点 y(1) 1; SUM(city(j) | j #GT# 1: x(1,j)) 1; SUM(city(j) | j #GT# 1: x(j,1)) 1; ! 3. 子回路消除约束MTZ约束 FOR(link(i,j) | i #GT# 1 #AND# j #GT# 1 #AND# i #NE# j: u(i) - u(j) 5 * x(i,j) 4; ); ! 设置u变量的边界对于非起点城市 FOR(city(i) | i #GT# 1: u(i) 2; u(i) 5; ); ! 4. 时间约束交通时间 游览时间 T_max SUM(link(i,j): d(i,j)*x(i,j)) SUM(city(i): t(i)*y(i)) T_max; ! 5. 预算约束交通费此处假设单位距离费用为1 门票费 B_max ! 注意此处d(i,j)同时代表距离和时间假设费用与距离成正比系数为1。 若题目单独给出交通费用矩阵需替换d(i,j)为对应费用。 SUM(link(i,j): d(i,j)*x(i,j)) SUM(city(i): c(i)*y(i)) B_max; ! 本例为简化使用与时间相同的矩阵代表费用 SUM(link(i,j): d(i,j)*x(i,j)) SUM(city(i): c(i)*y(i)) B_max; ! 6. 定义变量类型 FOR(link(i,j): BIN(x(i,j))); ! x(i,j)为0-1变量 FOR(city(i): BIN(y(i))); ! y(i)为0-1变量 FOR(city(i): GIN(u(i))); ! u(i)为一般整数变量MTZ约束需要 END代码关键点解读与实操心得集合定义是根基LINGO基于集合编程SETS部分定义了city和link两个集合并声明了附着其上的属性变量和参数。这种定义方式使得后续的约束可以简洁地用FOR和SUM对整个集合进行操作避免了冗长的循环语句是LINGO高效性的体现。MTZ约束的细节子回路消除约束u(i) - u(j) N * x(i,j) N-1是核心。其中N是城市总数本例为5。这个约束确保了如果x(i,j)1即走了i到j的路径则必须有u(j) u(i) 1从而给每个访问的城市赋予一个递增的序号防止形成回路。约束条件中的| i #GT# 1 #AND# j #GT# 1 #AND# i #NE# j表示该约束仅对非起点i1且j1且i不等于j的节点对生效这是标准的写法可以避免不必要的约束和起点处理冲突。起点处理的技巧我们强制y(1)1并约束从节点1出发和进入的路径各为1条。对于u变量起点通常不参与MTZ约束而非起点城市的u值被限定在[2, N]之间这有助于求解器更快地找到可行解。目标函数权重的设定本例中目标函数是总评分 - 0.01 * 总成本。为什么是0.01这是一个尺度统一的过程。评分s_i的量级是个位数6-9而总成本交通门票的量级是数百。如果不加调整成本项将完全主导目标函数导致模型退化为纯粹的成本最小化。乘以0.01或除以100相当于将成本单位从“元”转换为“百分之一元”使其数值量与评分接近从而让两个目标都能对结果产生影响。在实际竞赛中这个权重的选取需要说明理由或者进行灵敏度分析展示不同权重下最优解的变化。求解与结果查看在LINGO中编写完上述代码后点击“Solve”按钮。求解完成后在“Solution Report”窗口中可以查看最优目标函数值以及所有变量的值。重点关注x(i,j)和y(i)的取值。例如x(1,2)1表示最优路线中从1酒店直接去了2号景点。根据这些为1的x变量就能拼接出完整的旅行路线。4. 模型对比与拓展不同场景下的建模思路上述模型是一个基础而完整的框架。但在实际竞赛或应用中题目条件会变化需要我们调整模型。这里对比几种常见变体并讨论其建模思路。4.1 经典TSP vs. 带约束的TSP本题基础经典TSP目标唯一即最小化总旅行距离。约束只有每个城市访问一次、形成单个回路。它不考虑时间、预算、景点选择。求解方法关注于算法效率如动态规划、启发式算法。带约束的TSP本题在TSP基础上增加了资源约束时间、预算和节点选择变量y_i。目标可能变为综合效用最大化。建模核心在于引入0-1决策变量y_i来灵活选择景点并将资源消耗表示为Σ d*x Σ t*y的形式。求解时整数规划的特征更明显依赖于LINGO、CPLEX等求解器的分支定界/割平面能力。4.2 团队旅行与多车辆路径问题VRP如果题目涉及一个团队分乘多辆车游览问题就演变为车辆路径问题。核心变化是决策变量需要引入表示车辆k是否从i行驶到j的变量 x_{ijk}。约束每辆车都有容量载客量约束每条路线都必须从共同的起点车场出发并返回。目标可能是最小化总行驶距离或最小化使用车辆数或均衡各车路线时长。建模复杂度急剧上升。通常需要更强的子回路消除约束如流平衡约束的扩展并且求解难度更大对于稍大规模的问题往往需要设计启发式算法如节约算法、扫描算法来获得满意解。4.3 动态与随机情境下的考量更进一步的挑战是引入不确定性例如交通时间随机两点间的行驶时间不是一个定值d_{ij}而是一个随机变量如服从某种分布。此时严格的时间约束Σ (时间)*x T_max可能变得不现实。建模思路可以采用鲁棒优化或随机规划。例如将时间约束改为概率约束P(总时间 ≤ T_max) ≥ 0.95即要求总时间不超过T_max的概率至少为95%。这需要知道时间随机变量的分布并将该概率约束转化为确定的等价类进行求解难度较高常出现在研究生阶段的赛题中。景点开放时间窗每个景点只能在特定时间段内访问如9:00-17:00。这需要引入时间累计变量并添加复杂的时序约束确保到达每个景点的时间在其时间窗内。这类问题称为带时间窗的车辆路径问题是运筹学的研究热点。5. 竞赛实现中的常见“坑”与应对策略即便模型建得再漂亮代码写得再规范在实际求解和结果分析中还是会遇到各种问题。结合我多次参赛和辅导的经验以下几个“坑”值得特别注意。5.1 求解规模与时间瓶颈LINGO在求解整数规划时采用分支定界法。问题规模节点数N稍大求解时间就会指数级增长。对于N30的问题很可能在规定赛时内无法得到最优解。应对策略初始解启发给LINGO提供一个好的初始解可以大幅加速求解。例如先用最近邻法、插入法等简单启发式算法快速生成一条可行路线然后将这条路线对应的x_{ij}和y_i的值作为初始值赋给LINGO的变量。在LINGO中可以用FOR循环和INIT部分来实现。松弛与分解如果问题可以分解为几个相对独立的子问题例如将景点按区域聚类可以先分别求解子问题再考虑连接。设置求解器参数在LINGO的Options菜单中可以调整整数求解器的相关参数如“最优性容差”适当放宽可以加快求解速度但会损失一点解的质量。转向启发式算法对于大规模问题应果断放弃求精确最优解在论文中明确说明并采用模拟退火、遗传算法、蚁群算法等元启发式算法寻找高质量近似解。这往往是更现实的竞赛策略。5.2 模型无可行解检查约束冲突运行LINGO后有时会直接报告“No feasible solution found”。这意味着在给定的约束条件下不存在任何一条路线能满足所有要求。排查步骤检查数据输入首先核对所有参数D, t, c, T_max, B_max是否输入正确单位是否一致。一个错误的数据可能导致约束过紧。放松约束逐步放松约束找到“卡脖子”的环节。例如先注释掉预算约束看是否有解再注释掉时间约束。如果去掉某个约束后模型有解说明该约束可能过于严格。分析约束紧度计算一个“理论下限”。例如即使马不停蹄地跑访问所有景点的最小总时间 最短哈密顿回路的交通时间 所有景点的游览时间。如果这个值已经大于T_max那么问题显然无解。这时就需要修改问题本身比如允许不访问某些景点y_i变量正是为此设计或者向评委说明在当前资源下无法完成全部游览并给出一个访问最多景点的方案此时目标函数需调整。5.3 结果分析与灵敏度检验得到最优解后工作只完成了一半。深入的结果分析能为论文增色不少。路线可视化用MATLAB、Python的Matplotlib或在线工具将最优路线画在地图上一目了然。图中可以标注景点编号、路径方向、各段距离/时间。资源利用分析计算最优解下的总时间利用率和预算利用率。例如总用时11.5小时/12小时95.8%。这能说明你的方案对资源的利用是否充分。灵敏度分析这是体现建模深度的关键。研究关键参数变动对最优解的影响。权重灵敏度改变目标函数中评分与成本的权重如前文中的0.01观察最优路线和景点选择如何变化。可以绘制帕累托前沿图展示不同权重下的“最佳”权衡。资源灵敏度分析总时间T_max或总预算B_max增加或减少10%会对最优目标值产生多大影响。这能回答“如果预算增加100元我们的综合体验能提升多少”这类实际问题。参数灵敏度如果某个景点的评分s_i或时间t_i存在不确定性可以分析其变化在什么范围内当前的最优路线结构即哪些x_{ij}1保持不变。这称为“最优基不变”的灵敏度分析在线性规划中可以直接从单纯形法的最终表中读取对于整数规划则需要做参数规划。5.4 论文写作中的表达要点数学建模竞赛评阅时模型和求解固然重要但清晰的表达同样关键。避免“黑箱”描述不要只写“我们用LINGO求解”而要详细说明你建立的模型具体是什么列出目标函数和所有约束的数学公式以及你是如何将这个模型“翻译”成LINGO代码的可以像本文第三节那样对关键代码段进行解释。突出创新与调整如果对经典模型做了改进例如设计了新的子回路消除约束、提出了分段加权目标函数一定要重点说明动机和优势。结果呈现要直观除了文字多用表格和图表。例如用一张表清晰列出最优路线的访问顺序、各段耗时、各景点花费用另一张表展示灵敏度分析的结果。讨论模型的优缺点没有完美的模型。在论文结尾客观地讨论你所建模型的局限性例如假设交通时间是固定的未考虑拥堵假设满意度是线性可加的未考虑边际效应递减等并提出可能的改进方向这能展示你的批判性思维。规划一条旅行路线从数学上看是在一个充满约束的网络中寻找最优路径。Mathorcup的这道题巧妙地将经典的运筹学问题包装在一个生活化的场景里。通过它我们实践了从问题分析、模型构建、到软件求解、结果分析的全过程。其中如何定义“最佳”如何用0-1变量表达选择如何用MTZ约束破除子回路以及如何用LINGO实现求解是贯穿始终的技术主线。更重要的是我们看到了数学模型如何将主观的“体验”和客观的“成本”统一到一个框架下进行量化权衡。在实际操作中我最大的体会是数据的尺度预处理和约束的可行性检验是保证模型能顺利求解的两个基石。前者决定了目标函数是否真正反映了你的意图后者避免了在错误的方向上浪费时间。下次当你再规划旅行时或许可以下意识地想想这背后的优化问题是不是也有一个优雅的数学解呢