1. 项目概述从数学建模到旅游路线的实战跨越刚接触数学建模那会儿总觉得那些抽象的模型和现实生活隔着一层纱。直到后来自己带队参加了几次竞赛尤其是像Mathorcup妈妈杯这种强调应用性的比赛才真正体会到把数学模型“砸”进具体场景里的快感。第四届C题这个“最佳旅游路线设计与对比”就是一个绝佳的案例。它看起来是个经典的旅行商问题TSP变种但题目里埋的“坑”和现实中的考量远比教科书上的例子复杂得多。简单说这道题的核心就是给你一堆旅游城市城市之间有交通方式比如飞机、火车每种方式有不同的票价、时间和碳排放量。游客有总预算、总时间限制还可能对碳排放有要求。你的任务就是设计一条或多条旅游路线在满足这些约束的前提下优化某个或多个目标比如总花费最少、总时间最短或者总碳排放最低。最后还要对不同优化目标下的路线进行对比分析。这完全就是一个简化版的智能旅行规划引擎要解决的问题。为什么说它有意思呢因为它完美地体现了数学建模从“理想模型”到“带枷锁跳舞”的转变。纯TSP只关心最短路径但现实中我们永远是在金钱、时间、体验、甚至环保理念之间做权衡。这道题把多目标优化、线性/整数规划、图论这些知识打包在一起逼着你去思考怎么用数学语言描述这些权衡再用合适的工具比如题目要求的Lingo去求解。这不仅是考数学更是考你对问题的理解和转化能力。接下来我就以这道题为蓝本拆解一下从题目分析、模型构建、到Lingo求解和结果分析的全过程。我会尽量还原我们当时解题时的思考路径包括那些试错的环节和最终沉淀下来的技巧。无论你是正在备战数学建模竞赛的学生还是对路径优化算法感兴趣的开发者相信这些从实战中摔打出来的经验都能给你一些直接的参考。2. 问题拆解与核心思路设计面对这样一个多约束、多目标的旅游路线设计问题直接上手建模型很容易思路混乱。我们的做法是像剥洋葱一样把复杂问题一层层拆解成可处理的子问题。2.1 关键要素提取与抽象首先得把题目里的“人话”翻译成数学语言。我们梳理出以下几个核心要素节点与网络所有旅游城市构成节点集合。任何两个城市之间构成一条边。但这里的关键是一条边上可能有多种交通方式如飞机、火车每种方式对应不同的属性。这实际上构成了一个“多属性图”。决策变量这是模型的核心。我们需要决定两件事一是路线顺序先访问哪个城市再访问哪个城市二是每两个城市之间选择哪种交通方式。这通常需要用0-1变量来表示。例如X(i,j,m)1表示从城市i到城市j选择了第m种交通方式。约束条件这是模型的“枷锁”。流量平衡每个城市只能被进入一次、离开一次起点和终点除外。这保证了路线是一条连贯的环线或指定起终点的路径。预算约束所有交通费用的总和不能超过总预算。时间约束所有交通时间与在每个城市的停留时间总和不能超过总时间。碳排放约束所有交通碳排放总和不能超过上限如果题目给出。子回路消除这是TSP类问题的经典约束防止模型解出几个互不连通的小圈必须保证是一条完整的大环线。目标函数这是优化的方向。题目通常要求单目标优化如最小化费用或多目标优化。对于多目标处理方式有① 分层序列法先优化最主要目标将其结果作为约束再优化次要目标② 加权求和法给费用、时间、碳排放分配权重合并为单一目标③ 帕累托前沿法求出一组非劣解。竞赛中前两种方法更常见也更容易实现。注意在抽象问题时一定要明确题目是否要求“返回起点”。经典的TSP是返回起点的环游但很多旅游场景是给定起点和终点如从家出发最后从另一个城市飞回家。这一点对模型构建有根本性影响必须首先确认。2.2 模型选型与思路确定基于以上要素我们决定采用混合整数线性规划MILP模型。原因如下贴合问题我们的决策变量是0-1变量是否选择某条边、某种方式目标函数和约束条件在参数确定后都是线性的这正是MILP的典型应用场景。工具匹配题目指定或建议使用Lingo。Lingo在求解中小规模的线性、非线性规划以及整数规划问题上非常高效其建模语言描述这类问题也很直观。可扩展性MILP框架清晰便于后续增加新的约束如“必须游览某城市”、“城市A必须在城市B之前访问”等或调整目标。我们的核心思路流程图概念上如下数据准备整理城市列表、城市间距离或交通方式具体参数、各种交通方式的单价、耗时、碳排放系数。模型构建定义集合城市、交通方式、参数费用、时间、碳排、预算等、决策变量、目标函数、约束条件。模型求解使用Lingo进行求解。根据目标不同可能需要运行多次如单目标分别求或多目标加权求。结果提取与对比从Lingo解中提取路线序列和交通方式选择计算各项指标进行可视化对比如绘制路线图、制作对比表格。这个过程中最大的挑战往往不是建模本身而是如何将现实中的“软性”要求转化为严格的数学约束以及如何让模型在可接受的时间内求解。接下来我们就深入每个环节的细节。3. 模型构建的详细步骤与Lingo实现这里我们假设一个相对完整的赛题场景有N个城市城市间有两种交通方式飞机-代号1火车-代号2。我们需要规划一条从指定城市1出发最后回到城市1的环游路线。目标是在不超过总预算和总时间的前提下最小化总碳排放。这是一个典型的带约束的单目标优化问题。3.1 定义集合与参数在Lingo中我们首先需要定义模型的基本元素。这部分代码通常放在SETS:和DATA:段。MODEL: SETS: CITY / 1..N / : ; ! 定义N个城市的集合这里N是具体数字例如6; MODE / 1..2 / : ; ! 定义交通方式集合1-飞机2-火车; LINK(CITY, CITY, MODE) : DISTANCE, COST, TIME, CARBON, X; ! 定义“链接”集合表示从城市i到城市j采用方式m。 ! DISTANCE: 距离 (km) COST: 费用 (元) TIME: 时间 (小时) ! CARBON: 碳排放 (kg) X: 决策变量(0或1); ENDSETS DATA: ! 以下参数需要根据实际题目数据填写这里用注释说明格式; ! 距离矩阵 (对于方式1和方式2可能不同例如飞机是直线距离火车是铁路距离); DISTANCE ... ; ! 一个N*N*2的三维数组; ! 费用矩阵计算方式可能是基础票价 单价 * 距离; COST ... ; ! 时间矩阵计算方式可能是固定时间如候机、检票 距离 / 速度; TIME ... ; ! 碳排放矩阵计算方式可能是距离 * 该交通方式的碳排放系数; CARBON ... ; ! 总预算和总时间上限; TOTAL_BUDGET 5000; TOTAL_TIME 120; ! 每个城市的建议停留时间小时; STAY_TIME 4, 3, 5, 2, 4, 3; ! 假设有6个城市; ENDDATA实操心得在竞赛中数据准备往往是最耗时也最容易出错的一环。建议先用Excel或Python处理好所有矩阵数据确保维度正确。在填入Lingo的DATA段时可以采用OLE()函数直接从Excel读取这样比手动输入更可靠也便于修改。例如COST OLE(‘data.xlsx’, ‘CostMatrix’);。3.2 定义决策变量与目标函数决策变量X(i,j,m)是0-1变量表示是否选择从城市i到城市j采用交通方式m。 目标函数是最小化总碳排放。! 定义决策变量; FOR(LINK(i, j, m): BIN(X(i, j, m))); ! 声明X为0-1变量; ! 目标函数最小化总碳排放; MIN SUM(LINK(i, j, m): CARBON(i, j, m) * X(i, j, m));3.3 构建核心约束条件这是模型最核心的部分约束写对了问题就解决了一大半。! 1. 每个城市必须被离开一次对于所有城市; FOR(CITY(i): SUM(CITY(j) | j #NE# i: SUM(MODE(m): X(i, j, m))) 1 ); ! 解释对于任意城市i求和所有不是i的城市j 所有交通方式mX(i,j,m) 1。意味着从城市i必须出发一次。 ! 2. 每个城市必须被进入一次对于所有城市; FOR(CITY(j): SUM(CITY(i) | i #NE# j: SUM(MODE(m): X(i, j, m))) 1 ); ! 解释对于任意城市j求和所有不是j的城市i 所有交通方式mX(i,j,m) 1。意味着进入城市j必须有一次。 ! 3. 预算约束总费用不能超过预算; SUM(LINK(i, j, m): COST(i, j, m) * X(i, j, m)) TOTAL_BUDGET; ! 4. 时间约束总交通时间 总停留时间 总时间; SUM(LINK(i, j, m): TIME(i, j, m) * X(i, j, m)) SUM(CITY(i): STAY_TIME(i)) TOTAL_TIME; ! 注意这里假设每个城市都停留且停留时间固定。如果停留也是决策则需要更复杂的模型。 ! 5. 防止自己到自己的连接; FOR(CITY(i): FOR(MODE(m): X(i, i, m) 0)); ! 6. 子回路消除约束 - MTZ约束法 (Miller-Tucker-Zemlin); ! 该方法引入辅助变量U(i)表示城市i在路线中的顺序。 FOR(CITY(i): GIN(U(i))); ! U(i)为整数变量; FOR(CITY(i): U(i) 1); ! 顺序从1开始; U(1) 1; ! 设定起点城市顺序为1; ! 关键的MTZ约束对于任意i, j (i≠1, j≠1, i≠j)如果X(i,j,m)1则U(j) U(i) 1; FOR(CITY(i) | i #GT# 1: FOR(CITY(j) | j #GT# 1 #AND# j #NE# i: SUM(MODE(m): X(i, j, m)) (N-1) * (1 - (U(j) - U(i) - 1)/(N-1)) ! 这是一种线性化写法实际中常用以下更标准的格式; ) ); ! 更常见且稳定的MTZ约束写法如下需配合Big M法M取一个足够大的数如N FOR(CITY(i) | i #GT# 1: FOR(CITY(j) | j #GT# 1 #AND# j #NE# i: U(i) - U(j) N * SUM(MODE(m): X(i, j, m)) N - 1 ) ); ! 这个约束保证了不会形成不包含起点1的子回路。踩坑记录子回路消除约束是TSP建模的难点。MTZ约束是最常用的方法但它有一个缺点它会导致模型的线性松弛质量变差可能影响求解速度。对于城市数量较多比如15的情况可以考虑另一种更强的约束DFJ约束Dantzig-Fulkerson-Johnson它通过枚举所有可能的子集来消除子回路约束数量呈指数增长通常用“惰性约束”或“回调函数”在求解过程中动态添加。但在Lingo中对于中小规模问题N20MTZ约束通常够用。务必理解你所用约束的原理这是论文答辩时的关键得分点。3.4 模型求解与结果输出编写完所有代码后在Lingo中点击“Solve”即可求解。求解完成后需要查看并解读结果。! 在模型末尾可以添加一些输出语句便于查看结果; ! 例如只输出被选中的边X1的链接; FOR(LINK(i, j, m) | X(i, j, m) #GT# 0.5: ! 由于浮点计算判断0.5; WRITE(‘从城市 ‘, i, ‘ 到城市 ‘, j, ‘ 乘坐方式 ‘, m, ‘ (费用: ‘, COST(i,j,m), ‘ 时间: ‘, TIME(i,j,m), ‘ 碳排: ‘, CARBON(i,j,m), ‘)\n’); ); ! 计算并输出总费用、总时间、总碳排; TOTAL_C SUM(LINK(i, j, m): COST(i, j, m) * X(i, j, m)); TOTAL_T SUM(LINK(i, j, m): TIME(i, j, m) * X(i, j, m)) SUM(CITY(i): STAY_TIME(i)); TOTAL_CAR SUM(LINK(i, j, m): CARBON(i, j, m) * X(i, j, m)); WRITE(‘\n总费用: ‘, TOTAL_C, ‘\n总时间: ‘, TOTAL_T, ‘\n总碳排放: ‘, TOTAL_CAR); END运行后Lingo会给出全局最优解对于线性模型或找到的最优解。你需要从输出报告中提取出X(i,j,m)1的变量从而拼接出完整的旅游路线。4. 多目标优化与方案对比分析现实中我们很少只追求单一目标。题目中“设计与对比”的要求通常意味着需要进行多目标优化分析。我们以“费用”、“时间”、“碳排放”三个目标为例展示如何操作和对比。4.1 多目标处理方法方法一加权求和法最常用将多个目标按重要程度分配权重合并为一个单一目标。! 假设权重系数需根据题目要求或决策者偏好设定; w_cost 0.5; w_time 0.3; w_carbon 0.2; ! 注意费用、时间、碳排的单位和数量级可能差异巨大直接加权不合理需要先归一化。 ! 归一化方法例如 (当前值 - 理论最小值) / (理论最大值 - 理论最小值) ! 但理论最值通常未知一个实用方法是先分别求解单目标最小值F_min和最大值F_max通过改变目标函数然后归一化。 ! 在竞赛中如果时间紧张可以假设一个合理的范围进行归一化或者说明权重是基于标准化后的数据。 ! 目标函数变为; MIN w_cost * (SUM(LINK: COST * X) / COST_NORM) w_time * ((SUM(LINK: TIME * X) SUM(CITY: STAY_TIME)) / TIME_NORM) w_carbon * (SUM(LINK: CARBON * X) / CARBON_NORM); ! 其中COST_NORM, TIME_NORM, CARBON_NORM是归一化因子。方法二分层序列法先优化最重要的目标将其最优值作为约束再优化次重要目标。! 第一步最小化费用; MIN SUM(LINK: COST * X); ! 求解得到最小费用 Min_Cost; ! 第二步在费用不超过(Min_Cost * (1α))的约束下最小化时间α为一个小的松弛系数如0.05; SUM(LINK: COST * X) Min_Cost * 1.05; MIN SUM(LINK: TIME * X) SUM(CITY: STAY_TIME); ! 可以继续第三步在前两个目标都略有放松的条件下最小化碳排放。4.2 方案对比与可视化求解出不同目标权重下的方案后如何进行有说服力的对比结果汇总表制作一个表格清晰列出不同优化策略下的关键指标。优化策略路线顺序交通方式选择总费用(元)总时间(小时)总碳排放(kg)最小费用1-3-5-2-4-6-1(3,5火车),(5,2飞机),...3200135280最短时间1-4-2-6-3-5-1(1,4飞机),(4,2飞机),...480098420最低碳排1-6-4-3-2-5-1(1,6火车),(6,4火车),...3500150210加权综合(0.5,0.3,0.2)1-3-2-5-4-6-1...3800115250雷达图/柱状图对比将费用、时间、碳排放三个指标进行可视化对比直观展示各方案的优劣。例如用雷达图可以清晰看到“最小费用”方案在费用轴上突出但在时间和碳排轴上凹陷。敏感性分析这是体现建模深度的加分项。分析当权重系数或约束条件如预算、时间上限轻微变动时最优方案是否稳定。例如“当预算增加5%最短时间方案是否会改变”“碳排放权重从0.2提升到0.4最优路线发生了怎样的变化”这可以通过Lingo的参数化求解功能来实现多次运行模型并记录结果。注意事项在论文中呈现对比结果时不要只扔出一个表格或一张图。一定要有文字分析指出每个方案的特点和适用场景。例如“最小费用方案适合预算紧张的背包客但耗时较长最短时间方案适合商务出行者但对费用和环保不敏感加权综合方案在三者间取得了较好的平衡是大多数休闲游客的推荐选择。” 这样的分析能将冰冷的数字与实际问题联系起来。5. Lingo求解中的常见问题与调试技巧即使用对了模型在Lingo求解过程中也可能遇到各种问题。下面是一些我们踩过坑后总结的经验。5.1 常见错误与警告“No feasible solution found” (找不到可行解)原因约束条件太严格互相冲突没有同时满足所有约束的解。排查检查预算TOTAL_BUDGET和时间TOTAL_TIME是否设得太小。尝试先放松这些约束看是否有解。检查子回路消除约束MTZ是否写错特别是城市索引的边界条件。检查STAY_TIME是否被重复计算或数值过大。实用技巧可以先注释掉所有约束只保留流量平衡约束看模型是否能得到一个基本的哈密顿环。然后逐步添加其他约束定位是哪个约束导致不可行。求解时间过长甚至无法在比赛时间内完成原因问题规模城市数N较大整数规划问题本身是NP-Hard的。对策设定求解时间限制在Lingo的Options-General Solver-Time Limitation中设置一个最大时间如300秒。时间到后Lingo会给出当前找到的最优解可能是局部最优。调整求解器选项在Options-Integer Solver中可以调整Relative Optimality Tolerance相对最优容差。默认是0.000001可以适当调大如0.01这样求解器会更快找到一个“足够好”的解而不是执着于寻找那一点点改进。简化模型如果交通方式很多可以考虑先预处理只保留每对城市之间成本最低或时间最短的1-2种方式减少变量数。使用启发式算法获取初始解可以先用手工或简单算法如最近邻法构造一条可行路线将对应的X(i,j,m)变量固定为1作为“初始解”提供给Lingo能大大加快求解速度。在Lingo中可以用POINTER函数或直接在数据段赋值。“Objective value is unbounded” (目标值无界)原因极小化问题中目标函数值可以无限小。这通常是因为模型有错误使得决策变量在满足约束的情况下可以无限降低目标值例如忘记给某些成本参数赋值默认为0。排查仔细检查所有参数COST,TIME,CARBON的DATA输入是否正确是否有缺失或为0的情况。5.2 模型调试与验证技巧从小规模开始不要一开始就用全部城市数据。先用3-4个城市手动计算一个最优解然后用你的模型去求解看结果是否一致。这是验证模型逻辑是否正确的最有效方法。利用WRITE和DEBUG输出中间信息在约束条件中临时插入WRITE语句输出某些求和表达式的值看看是否与预期相符。检查解的逻辑得到解后手动沿着X1的边走一遍看是否构成一条完整的、无子回路的路线并手动计算一下总费用、总时间看是否与Lingo输出的目标函数值一致。理解Lingo报告求解后仔细阅读状态报告Solution Report。关注“Global optimal solution found”找到全局最优还是“Local optimal solution found”局部最优。对于线性MILPLingo通常能找到全局最优。也要看“Objective value”和“Infeasibilities”不可行量应为0。5.3 代码优化与可读性使用FOR和SUM简化代码避免写出冗长且易错的约束列表。Lingo的集合操作功能非常强大。为集合和参数起有意义的名字如CITYMODECOST 而不是简单的C,M,F。这大大提高了代码的可读性和可维护性。将模型与数据分离对于大型数据强烈建议使用OLE()或TEXT()函数从外部文件Excel, txt读取数据。这样修改数据时无需动模型代码。添加大量注释在每一段关键的约束或复杂的求和表达式后面用!添加注释解释其数学含义和实际意图。这在团队协作和后期检查时至关重要。6. 从模型到论文结果呈现与写作要点数学建模竞赛三分靠建模七分靠表达。一个再精巧的模型如果不能在论文中清晰、有说服力地呈现出来也很难取得好成绩。6.1 论文结构梳理针对“旅游路线设计”这类问题论文可以遵循以下结构问题重述与分析不要照抄题目要用自己的话概括问题的背景、目标和约束条件并提炼出问题的特点多目标、多约束、TSP变体等。模型假设列出为了简化问题而做出的合理假设。例如“假设城市间的交通费用只与距离和交通方式有关不考虑动态票价”、“假设在每个城市的停留时间为固定值”、“忽略换乘等候时间”等。假设要合理且需要在模型灵敏度分析或优缺点讨论中提及这些假设的影响。符号说明以表格形式列出模型中用到的主要符号、含义及单位。这是论文的“字典”务必清晰、完整。模型建立这是核心章节。数据预处理说明如何从题目数据计算出COST,TIME,CARBON矩阵。模型构建详细阐述决策变量、目标函数、约束条件。每一行公式最好都配上文字说明解释这个公式在解决实际问题中对应什么。多目标处理说明你采用的方法加权法/分层法以及理由。模型求解算法与工具说明使用Lingo求解并简述Lingo求解MILP的原理分支定界法。求解过程可以简要描述调试过程遇到什么问题如何解决。求解结果以清晰的表格和图形展示不同优化目标下的最优路线、交通方式选择、以及各项指标费用、时间、碳排。路线最好用“1-3-5-2-4-6-1”这样的序列和“1,3:火车3,5:飞机…”这样的方式双重呈现。结果分析与对比对比分析对上一章的结果进行深入分析。为什么最小费用路线长那样它牺牲了什么综合方案是如何权衡的灵敏度分析展示当关键参数如预算上限、时间权重变化时最优方案如何变化。用图表展示这种变化趋势并给出管理启示例如“建议预算至少提高到XX元才能获得时间上大幅优化的方案”。模型评价客观评价模型的优点如考虑全面、求解精确和缺点如假设固定停留时间、忽略拥堵等现实因素并提出可能的改进方向。参考文献与附录附录中应包含完整的、可运行的Lingo程序代码重要以及重要的中间数据表格。6.2 图表制作技巧路线图使用绘图工具如Python的Matplotlib NetworkX 或在线工具将最优路线可视化。用不同颜色或线型区分飞机和火车让评委一目了然。对比表格如前所述表格设计要简洁专业单位统一重要数据可加粗。雷达图/柱状图用于多目标对比时非常直观。可以使用Excel、Python或MATLAB轻松生成。灵敏度分析图用折线图展示目标函数值或路线关键指标随某个参数如预算变化的趋势。6.3 写作避坑指南避免“说明书”式写作不要只罗列“我们做了什么”而要强调“我们为什么这么做”以及“这么做带来了什么结果”。多写分析少写过程。公式与文字结合不要大段堆砌公式也不要只有文字没有公式。每个重要公式前后都应有引导性和解释性文字。强调创新点与工作量在摘要、模型建立和结论部分要点出你模型的亮点。例如“本文创新性地将碳排放约束引入经典TSP模型并采用加权法处理多目标冲突”、“我们通过细致的灵敏度分析为不同偏好的旅行者提供了决策支持”。代码附录要规范附录的代码要有必要的注释变量名与论文中一致。可以只贴核心模型部分数据读取部分可以简化说明。这道“最佳旅游路线设计”题就像一把钥匙打开了一扇门门后是运筹学、优化理论在真实世界中的广阔应用。从车辆路径规划到物流配送从电网调度到生产排程其核心思想都是相通的。通过这次完整的拆解我希望你不只是得到了一份竞赛题的参考答案更重要的是掌握了一种将模糊现实问题转化为清晰数学模型并利用工具求解、分析、呈现的系统方法。在下次遇到新的优化问题时不妨也试着用这个“剥洋葱”的思路去拆解它你会发现很多看似复杂的问题其实都有迹可循。 数学建模实战：基于Lingo的多目标旅游路线优化与TSP问题求解
1. 项目概述从数学建模到旅游路线的实战跨越刚接触数学建模那会儿总觉得那些抽象的模型和现实生活隔着一层纱。直到后来自己带队参加了几次竞赛尤其是像Mathorcup妈妈杯这种强调应用性的比赛才真正体会到把数学模型“砸”进具体场景里的快感。第四届C题这个“最佳旅游路线设计与对比”就是一个绝佳的案例。它看起来是个经典的旅行商问题TSP变种但题目里埋的“坑”和现实中的考量远比教科书上的例子复杂得多。简单说这道题的核心就是给你一堆旅游城市城市之间有交通方式比如飞机、火车每种方式有不同的票价、时间和碳排放量。游客有总预算、总时间限制还可能对碳排放有要求。你的任务就是设计一条或多条旅游路线在满足这些约束的前提下优化某个或多个目标比如总花费最少、总时间最短或者总碳排放最低。最后还要对不同优化目标下的路线进行对比分析。这完全就是一个简化版的智能旅行规划引擎要解决的问题。为什么说它有意思呢因为它完美地体现了数学建模从“理想模型”到“带枷锁跳舞”的转变。纯TSP只关心最短路径但现实中我们永远是在金钱、时间、体验、甚至环保理念之间做权衡。这道题把多目标优化、线性/整数规划、图论这些知识打包在一起逼着你去思考怎么用数学语言描述这些权衡再用合适的工具比如题目要求的Lingo去求解。这不仅是考数学更是考你对问题的理解和转化能力。接下来我就以这道题为蓝本拆解一下从题目分析、模型构建、到Lingo求解和结果分析的全过程。我会尽量还原我们当时解题时的思考路径包括那些试错的环节和最终沉淀下来的技巧。无论你是正在备战数学建模竞赛的学生还是对路径优化算法感兴趣的开发者相信这些从实战中摔打出来的经验都能给你一些直接的参考。2. 问题拆解与核心思路设计面对这样一个多约束、多目标的旅游路线设计问题直接上手建模型很容易思路混乱。我们的做法是像剥洋葱一样把复杂问题一层层拆解成可处理的子问题。2.1 关键要素提取与抽象首先得把题目里的“人话”翻译成数学语言。我们梳理出以下几个核心要素节点与网络所有旅游城市构成节点集合。任何两个城市之间构成一条边。但这里的关键是一条边上可能有多种交通方式如飞机、火车每种方式对应不同的属性。这实际上构成了一个“多属性图”。决策变量这是模型的核心。我们需要决定两件事一是路线顺序先访问哪个城市再访问哪个城市二是每两个城市之间选择哪种交通方式。这通常需要用0-1变量来表示。例如X(i,j,m)1表示从城市i到城市j选择了第m种交通方式。约束条件这是模型的“枷锁”。流量平衡每个城市只能被进入一次、离开一次起点和终点除外。这保证了路线是一条连贯的环线或指定起终点的路径。预算约束所有交通费用的总和不能超过总预算。时间约束所有交通时间与在每个城市的停留时间总和不能超过总时间。碳排放约束所有交通碳排放总和不能超过上限如果题目给出。子回路消除这是TSP类问题的经典约束防止模型解出几个互不连通的小圈必须保证是一条完整的大环线。目标函数这是优化的方向。题目通常要求单目标优化如最小化费用或多目标优化。对于多目标处理方式有① 分层序列法先优化最主要目标将其结果作为约束再优化次要目标② 加权求和法给费用、时间、碳排放分配权重合并为单一目标③ 帕累托前沿法求出一组非劣解。竞赛中前两种方法更常见也更容易实现。注意在抽象问题时一定要明确题目是否要求“返回起点”。经典的TSP是返回起点的环游但很多旅游场景是给定起点和终点如从家出发最后从另一个城市飞回家。这一点对模型构建有根本性影响必须首先确认。2.2 模型选型与思路确定基于以上要素我们决定采用混合整数线性规划MILP模型。原因如下贴合问题我们的决策变量是0-1变量是否选择某条边、某种方式目标函数和约束条件在参数确定后都是线性的这正是MILP的典型应用场景。工具匹配题目指定或建议使用Lingo。Lingo在求解中小规模的线性、非线性规划以及整数规划问题上非常高效其建模语言描述这类问题也很直观。可扩展性MILP框架清晰便于后续增加新的约束如“必须游览某城市”、“城市A必须在城市B之前访问”等或调整目标。我们的核心思路流程图概念上如下数据准备整理城市列表、城市间距离或交通方式具体参数、各种交通方式的单价、耗时、碳排放系数。模型构建定义集合城市、交通方式、参数费用、时间、碳排、预算等、决策变量、目标函数、约束条件。模型求解使用Lingo进行求解。根据目标不同可能需要运行多次如单目标分别求或多目标加权求。结果提取与对比从Lingo解中提取路线序列和交通方式选择计算各项指标进行可视化对比如绘制路线图、制作对比表格。这个过程中最大的挑战往往不是建模本身而是如何将现实中的“软性”要求转化为严格的数学约束以及如何让模型在可接受的时间内求解。接下来我们就深入每个环节的细节。3. 模型构建的详细步骤与Lingo实现这里我们假设一个相对完整的赛题场景有N个城市城市间有两种交通方式飞机-代号1火车-代号2。我们需要规划一条从指定城市1出发最后回到城市1的环游路线。目标是在不超过总预算和总时间的前提下最小化总碳排放。这是一个典型的带约束的单目标优化问题。3.1 定义集合与参数在Lingo中我们首先需要定义模型的基本元素。这部分代码通常放在SETS:和DATA:段。MODEL: SETS: CITY / 1..N / : ; ! 定义N个城市的集合这里N是具体数字例如6; MODE / 1..2 / : ; ! 定义交通方式集合1-飞机2-火车; LINK(CITY, CITY, MODE) : DISTANCE, COST, TIME, CARBON, X; ! 定义“链接”集合表示从城市i到城市j采用方式m。 ! DISTANCE: 距离 (km) COST: 费用 (元) TIME: 时间 (小时) ! CARBON: 碳排放 (kg) X: 决策变量(0或1); ENDSETS DATA: ! 以下参数需要根据实际题目数据填写这里用注释说明格式; ! 距离矩阵 (对于方式1和方式2可能不同例如飞机是直线距离火车是铁路距离); DISTANCE ... ; ! 一个N*N*2的三维数组; ! 费用矩阵计算方式可能是基础票价 单价 * 距离; COST ... ; ! 时间矩阵计算方式可能是固定时间如候机、检票 距离 / 速度; TIME ... ; ! 碳排放矩阵计算方式可能是距离 * 该交通方式的碳排放系数; CARBON ... ; ! 总预算和总时间上限; TOTAL_BUDGET 5000; TOTAL_TIME 120; ! 每个城市的建议停留时间小时; STAY_TIME 4, 3, 5, 2, 4, 3; ! 假设有6个城市; ENDDATA实操心得在竞赛中数据准备往往是最耗时也最容易出错的一环。建议先用Excel或Python处理好所有矩阵数据确保维度正确。在填入Lingo的DATA段时可以采用OLE()函数直接从Excel读取这样比手动输入更可靠也便于修改。例如COST OLE(‘data.xlsx’, ‘CostMatrix’);。3.2 定义决策变量与目标函数决策变量X(i,j,m)是0-1变量表示是否选择从城市i到城市j采用交通方式m。 目标函数是最小化总碳排放。! 定义决策变量; FOR(LINK(i, j, m): BIN(X(i, j, m))); ! 声明X为0-1变量; ! 目标函数最小化总碳排放; MIN SUM(LINK(i, j, m): CARBON(i, j, m) * X(i, j, m));3.3 构建核心约束条件这是模型最核心的部分约束写对了问题就解决了一大半。! 1. 每个城市必须被离开一次对于所有城市; FOR(CITY(i): SUM(CITY(j) | j #NE# i: SUM(MODE(m): X(i, j, m))) 1 ); ! 解释对于任意城市i求和所有不是i的城市j 所有交通方式mX(i,j,m) 1。意味着从城市i必须出发一次。 ! 2. 每个城市必须被进入一次对于所有城市; FOR(CITY(j): SUM(CITY(i) | i #NE# j: SUM(MODE(m): X(i, j, m))) 1 ); ! 解释对于任意城市j求和所有不是j的城市i 所有交通方式mX(i,j,m) 1。意味着进入城市j必须有一次。 ! 3. 预算约束总费用不能超过预算; SUM(LINK(i, j, m): COST(i, j, m) * X(i, j, m)) TOTAL_BUDGET; ! 4. 时间约束总交通时间 总停留时间 总时间; SUM(LINK(i, j, m): TIME(i, j, m) * X(i, j, m)) SUM(CITY(i): STAY_TIME(i)) TOTAL_TIME; ! 注意这里假设每个城市都停留且停留时间固定。如果停留也是决策则需要更复杂的模型。 ! 5. 防止自己到自己的连接; FOR(CITY(i): FOR(MODE(m): X(i, i, m) 0)); ! 6. 子回路消除约束 - MTZ约束法 (Miller-Tucker-Zemlin); ! 该方法引入辅助变量U(i)表示城市i在路线中的顺序。 FOR(CITY(i): GIN(U(i))); ! U(i)为整数变量; FOR(CITY(i): U(i) 1); ! 顺序从1开始; U(1) 1; ! 设定起点城市顺序为1; ! 关键的MTZ约束对于任意i, j (i≠1, j≠1, i≠j)如果X(i,j,m)1则U(j) U(i) 1; FOR(CITY(i) | i #GT# 1: FOR(CITY(j) | j #GT# 1 #AND# j #NE# i: SUM(MODE(m): X(i, j, m)) (N-1) * (1 - (U(j) - U(i) - 1)/(N-1)) ! 这是一种线性化写法实际中常用以下更标准的格式; ) ); ! 更常见且稳定的MTZ约束写法如下需配合Big M法M取一个足够大的数如N FOR(CITY(i) | i #GT# 1: FOR(CITY(j) | j #GT# 1 #AND# j #NE# i: U(i) - U(j) N * SUM(MODE(m): X(i, j, m)) N - 1 ) ); ! 这个约束保证了不会形成不包含起点1的子回路。踩坑记录子回路消除约束是TSP建模的难点。MTZ约束是最常用的方法但它有一个缺点它会导致模型的线性松弛质量变差可能影响求解速度。对于城市数量较多比如15的情况可以考虑另一种更强的约束DFJ约束Dantzig-Fulkerson-Johnson它通过枚举所有可能的子集来消除子回路约束数量呈指数增长通常用“惰性约束”或“回调函数”在求解过程中动态添加。但在Lingo中对于中小规模问题N20MTZ约束通常够用。务必理解你所用约束的原理这是论文答辩时的关键得分点。3.4 模型求解与结果输出编写完所有代码后在Lingo中点击“Solve”即可求解。求解完成后需要查看并解读结果。! 在模型末尾可以添加一些输出语句便于查看结果; ! 例如只输出被选中的边X1的链接; FOR(LINK(i, j, m) | X(i, j, m) #GT# 0.5: ! 由于浮点计算判断0.5; WRITE(‘从城市 ‘, i, ‘ 到城市 ‘, j, ‘ 乘坐方式 ‘, m, ‘ (费用: ‘, COST(i,j,m), ‘ 时间: ‘, TIME(i,j,m), ‘ 碳排: ‘, CARBON(i,j,m), ‘)\n’); ); ! 计算并输出总费用、总时间、总碳排; TOTAL_C SUM(LINK(i, j, m): COST(i, j, m) * X(i, j, m)); TOTAL_T SUM(LINK(i, j, m): TIME(i, j, m) * X(i, j, m)) SUM(CITY(i): STAY_TIME(i)); TOTAL_CAR SUM(LINK(i, j, m): CARBON(i, j, m) * X(i, j, m)); WRITE(‘\n总费用: ‘, TOTAL_C, ‘\n总时间: ‘, TOTAL_T, ‘\n总碳排放: ‘, TOTAL_CAR); END运行后Lingo会给出全局最优解对于线性模型或找到的最优解。你需要从输出报告中提取出X(i,j,m)1的变量从而拼接出完整的旅游路线。4. 多目标优化与方案对比分析现实中我们很少只追求单一目标。题目中“设计与对比”的要求通常意味着需要进行多目标优化分析。我们以“费用”、“时间”、“碳排放”三个目标为例展示如何操作和对比。4.1 多目标处理方法方法一加权求和法最常用将多个目标按重要程度分配权重合并为一个单一目标。! 假设权重系数需根据题目要求或决策者偏好设定; w_cost 0.5; w_time 0.3; w_carbon 0.2; ! 注意费用、时间、碳排的单位和数量级可能差异巨大直接加权不合理需要先归一化。 ! 归一化方法例如 (当前值 - 理论最小值) / (理论最大值 - 理论最小值) ! 但理论最值通常未知一个实用方法是先分别求解单目标最小值F_min和最大值F_max通过改变目标函数然后归一化。 ! 在竞赛中如果时间紧张可以假设一个合理的范围进行归一化或者说明权重是基于标准化后的数据。 ! 目标函数变为; MIN w_cost * (SUM(LINK: COST * X) / COST_NORM) w_time * ((SUM(LINK: TIME * X) SUM(CITY: STAY_TIME)) / TIME_NORM) w_carbon * (SUM(LINK: CARBON * X) / CARBON_NORM); ! 其中COST_NORM, TIME_NORM, CARBON_NORM是归一化因子。方法二分层序列法先优化最重要的目标将其最优值作为约束再优化次重要目标。! 第一步最小化费用; MIN SUM(LINK: COST * X); ! 求解得到最小费用 Min_Cost; ! 第二步在费用不超过(Min_Cost * (1α))的约束下最小化时间α为一个小的松弛系数如0.05; SUM(LINK: COST * X) Min_Cost * 1.05; MIN SUM(LINK: TIME * X) SUM(CITY: STAY_TIME); ! 可以继续第三步在前两个目标都略有放松的条件下最小化碳排放。4.2 方案对比与可视化求解出不同目标权重下的方案后如何进行有说服力的对比结果汇总表制作一个表格清晰列出不同优化策略下的关键指标。优化策略路线顺序交通方式选择总费用(元)总时间(小时)总碳排放(kg)最小费用1-3-5-2-4-6-1(3,5火车),(5,2飞机),...3200135280最短时间1-4-2-6-3-5-1(1,4飞机),(4,2飞机),...480098420最低碳排1-6-4-3-2-5-1(1,6火车),(6,4火车),...3500150210加权综合(0.5,0.3,0.2)1-3-2-5-4-6-1...3800115250雷达图/柱状图对比将费用、时间、碳排放三个指标进行可视化对比直观展示各方案的优劣。例如用雷达图可以清晰看到“最小费用”方案在费用轴上突出但在时间和碳排轴上凹陷。敏感性分析这是体现建模深度的加分项。分析当权重系数或约束条件如预算、时间上限轻微变动时最优方案是否稳定。例如“当预算增加5%最短时间方案是否会改变”“碳排放权重从0.2提升到0.4最优路线发生了怎样的变化”这可以通过Lingo的参数化求解功能来实现多次运行模型并记录结果。注意事项在论文中呈现对比结果时不要只扔出一个表格或一张图。一定要有文字分析指出每个方案的特点和适用场景。例如“最小费用方案适合预算紧张的背包客但耗时较长最短时间方案适合商务出行者但对费用和环保不敏感加权综合方案在三者间取得了较好的平衡是大多数休闲游客的推荐选择。” 这样的分析能将冰冷的数字与实际问题联系起来。5. Lingo求解中的常见问题与调试技巧即使用对了模型在Lingo求解过程中也可能遇到各种问题。下面是一些我们踩过坑后总结的经验。5.1 常见错误与警告“No feasible solution found” (找不到可行解)原因约束条件太严格互相冲突没有同时满足所有约束的解。排查检查预算TOTAL_BUDGET和时间TOTAL_TIME是否设得太小。尝试先放松这些约束看是否有解。检查子回路消除约束MTZ是否写错特别是城市索引的边界条件。检查STAY_TIME是否被重复计算或数值过大。实用技巧可以先注释掉所有约束只保留流量平衡约束看模型是否能得到一个基本的哈密顿环。然后逐步添加其他约束定位是哪个约束导致不可行。求解时间过长甚至无法在比赛时间内完成原因问题规模城市数N较大整数规划问题本身是NP-Hard的。对策设定求解时间限制在Lingo的Options-General Solver-Time Limitation中设置一个最大时间如300秒。时间到后Lingo会给出当前找到的最优解可能是局部最优。调整求解器选项在Options-Integer Solver中可以调整Relative Optimality Tolerance相对最优容差。默认是0.000001可以适当调大如0.01这样求解器会更快找到一个“足够好”的解而不是执着于寻找那一点点改进。简化模型如果交通方式很多可以考虑先预处理只保留每对城市之间成本最低或时间最短的1-2种方式减少变量数。使用启发式算法获取初始解可以先用手工或简单算法如最近邻法构造一条可行路线将对应的X(i,j,m)变量固定为1作为“初始解”提供给Lingo能大大加快求解速度。在Lingo中可以用POINTER函数或直接在数据段赋值。“Objective value is unbounded” (目标值无界)原因极小化问题中目标函数值可以无限小。这通常是因为模型有错误使得决策变量在满足约束的情况下可以无限降低目标值例如忘记给某些成本参数赋值默认为0。排查仔细检查所有参数COST,TIME,CARBON的DATA输入是否正确是否有缺失或为0的情况。5.2 模型调试与验证技巧从小规模开始不要一开始就用全部城市数据。先用3-4个城市手动计算一个最优解然后用你的模型去求解看结果是否一致。这是验证模型逻辑是否正确的最有效方法。利用WRITE和DEBUG输出中间信息在约束条件中临时插入WRITE语句输出某些求和表达式的值看看是否与预期相符。检查解的逻辑得到解后手动沿着X1的边走一遍看是否构成一条完整的、无子回路的路线并手动计算一下总费用、总时间看是否与Lingo输出的目标函数值一致。理解Lingo报告求解后仔细阅读状态报告Solution Report。关注“Global optimal solution found”找到全局最优还是“Local optimal solution found”局部最优。对于线性MILPLingo通常能找到全局最优。也要看“Objective value”和“Infeasibilities”不可行量应为0。5.3 代码优化与可读性使用FOR和SUM简化代码避免写出冗长且易错的约束列表。Lingo的集合操作功能非常强大。为集合和参数起有意义的名字如CITYMODECOST 而不是简单的C,M,F。这大大提高了代码的可读性和可维护性。将模型与数据分离对于大型数据强烈建议使用OLE()或TEXT()函数从外部文件Excel, txt读取数据。这样修改数据时无需动模型代码。添加大量注释在每一段关键的约束或复杂的求和表达式后面用!添加注释解释其数学含义和实际意图。这在团队协作和后期检查时至关重要。6. 从模型到论文结果呈现与写作要点数学建模竞赛三分靠建模七分靠表达。一个再精巧的模型如果不能在论文中清晰、有说服力地呈现出来也很难取得好成绩。6.1 论文结构梳理针对“旅游路线设计”这类问题论文可以遵循以下结构问题重述与分析不要照抄题目要用自己的话概括问题的背景、目标和约束条件并提炼出问题的特点多目标、多约束、TSP变体等。模型假设列出为了简化问题而做出的合理假设。例如“假设城市间的交通费用只与距离和交通方式有关不考虑动态票价”、“假设在每个城市的停留时间为固定值”、“忽略换乘等候时间”等。假设要合理且需要在模型灵敏度分析或优缺点讨论中提及这些假设的影响。符号说明以表格形式列出模型中用到的主要符号、含义及单位。这是论文的“字典”务必清晰、完整。模型建立这是核心章节。数据预处理说明如何从题目数据计算出COST,TIME,CARBON矩阵。模型构建详细阐述决策变量、目标函数、约束条件。每一行公式最好都配上文字说明解释这个公式在解决实际问题中对应什么。多目标处理说明你采用的方法加权法/分层法以及理由。模型求解算法与工具说明使用Lingo求解并简述Lingo求解MILP的原理分支定界法。求解过程可以简要描述调试过程遇到什么问题如何解决。求解结果以清晰的表格和图形展示不同优化目标下的最优路线、交通方式选择、以及各项指标费用、时间、碳排。路线最好用“1-3-5-2-4-6-1”这样的序列和“1,3:火车3,5:飞机…”这样的方式双重呈现。结果分析与对比对比分析对上一章的结果进行深入分析。为什么最小费用路线长那样它牺牲了什么综合方案是如何权衡的灵敏度分析展示当关键参数如预算上限、时间权重变化时最优方案如何变化。用图表展示这种变化趋势并给出管理启示例如“建议预算至少提高到XX元才能获得时间上大幅优化的方案”。模型评价客观评价模型的优点如考虑全面、求解精确和缺点如假设固定停留时间、忽略拥堵等现实因素并提出可能的改进方向。参考文献与附录附录中应包含完整的、可运行的Lingo程序代码重要以及重要的中间数据表格。6.2 图表制作技巧路线图使用绘图工具如Python的Matplotlib NetworkX 或在线工具将最优路线可视化。用不同颜色或线型区分飞机和火车让评委一目了然。对比表格如前所述表格设计要简洁专业单位统一重要数据可加粗。雷达图/柱状图用于多目标对比时非常直观。可以使用Excel、Python或MATLAB轻松生成。灵敏度分析图用折线图展示目标函数值或路线关键指标随某个参数如预算变化的趋势。6.3 写作避坑指南避免“说明书”式写作不要只罗列“我们做了什么”而要强调“我们为什么这么做”以及“这么做带来了什么结果”。多写分析少写过程。公式与文字结合不要大段堆砌公式也不要只有文字没有公式。每个重要公式前后都应有引导性和解释性文字。强调创新点与工作量在摘要、模型建立和结论部分要点出你模型的亮点。例如“本文创新性地将碳排放约束引入经典TSP模型并采用加权法处理多目标冲突”、“我们通过细致的灵敏度分析为不同偏好的旅行者提供了决策支持”。代码附录要规范附录的代码要有必要的注释变量名与论文中一致。可以只贴核心模型部分数据读取部分可以简化说明。这道“最佳旅游路线设计”题就像一把钥匙打开了一扇门门后是运筹学、优化理论在真实世界中的广阔应用。从车辆路径规划到物流配送从电网调度到生产排程其核心思想都是相通的。通过这次完整的拆解我希望你不只是得到了一份竞赛题的参考答案更重要的是掌握了一种将模糊现实问题转化为清晰数学模型并利用工具求解、分析、呈现的系统方法。在下次遇到新的优化问题时不妨也试着用这个“剥洋葱”的思路去拆解它你会发现很多看似复杂的问题其实都有迹可循。