1. 项目概述与赛题背景2021年长三角高校数学建模竞赛的A题“Go!Fun游长三角”是一个典型的、融合了运筹优化与综合评价的复杂现实问题。拿到这个题目第一感觉就是“味儿对了”——它不像一些纯理论推导题那样飘在空中而是把数学模型实实在在地摁在了旅游规划这个接地气的场景里。题目要求参赛者为一家旅游公司设计一条覆盖长三角多个城市的旅游线路这听起来像是经典的旅行商问题但细看之下远不止于此。它不仅要你规划出一条“走遍”的路径还要综合考虑每个城市的“游玩价值”、游客的“满意度”、以及最重要的“成本控制”。换句话说它要求你在有限的预算和时间内拿出一条能让游客玩得爽、公司赚得稳的“黄金线路”。这种多目标、带约束的优化问题正是数学建模从课本走向产业应用的核心体现非常考验参赛者对模型进行拆解、融合与创新的能力。从网络热词的集中度来看“TSP”、“动态规划”、“TOPSIS”、“层次分析法”是大家讨论和求解本题时绕不开的几个核心工具。这很合理因为题目本身的结构就天然分成了几个模块如何量化每个城市的吸引力评价问题如何基于这些吸引力和其他约束生成可行的线路路径优化问题。前者是静态的评价排序适合用综合评价方法后者是动态的序列决策适合用优化算法。所以一个成熟的解题框架应该是先用AHP或熵权TOPSIS对各个候选城市进行打分排序筛选出高价值目的地再将这些城市作为节点构建一个考虑时间、成本、满意度等多重约束的改进型TSP模型进行线路规划。动态规划则可能是求解这个复杂TSP模型的一种有效手段尤其是在节点数经过筛选后规模可控的情况下。接下来我就结合自己多次带队参赛和评审的经验把这个“解题全过程”掰开揉碎了讲清楚从思路构建到程序实现包括那些论文里不会写的“坑”和“技巧”。2. 核心思路拆解与模型选型逻辑面对“Go!Fun游长三角”这种多目标规划题最忌讳的就是一上来就埋头写公式、调代码。我的经验是先花足够的时间把题目“翻译”成数学语言并设计一个清晰的、模块化的求解流水线。整个解题的顶层逻辑可以概括为“评价-筛选-优化-验证”四步走。第一步定义目标与量化指标。题目中隐含了至少三个目标最大化旅游线路的总体吸引力让游客满意最小化总成本让公司盈利以及满足时间约束行程可行。这三个目标往往是相互冲突的便宜的路线可能不好玩好玩的路线可能超预算。因此我们通常不追求同时达到三个最优而是采用“主要目标法”或“约束法”。在本题中更实际的思路是将“最大化吸引力”作为主要目标将“总成本”和“总时间”作为硬性约束。也就是说我们在不超过预算和规定天数的前提下找出一条吸引力最高的线路。第二步城市吸引力综合评价对应TOPSIS/AHP。哪些城市值得去题目通常会提供或暗示一系列评价指标比如城市的旅游资源等级5A/4A景区数量、文化底蕴指数、交通便利度、消费水平、气候舒适度等。我们的任务就是给每个候选城市一个综合得分。这里有两个主流方法层次分析法适合指标间存在层次关系且需要融入一定主观经验如专家打分的情况。通过构建判断矩阵计算权重一致性检验最后得到每个城市的加权得分。它的优势是能处理定性指标逻辑清晰缺点是主观性较强当指标或城市较多时构造判断矩阵的工作量巨大且容易不一致。熵权TOPSIS法这是一种客观赋权法。它根据各指标数据本身的离散程度熵来确定权重信息量越大的指标权重越高。然后通过计算每个城市与正理想解、负理想解的相对接近度来排序。它的优势是完全依赖客观数据避免了人为干扰特别适合本题这种可能给出大量定量数据的情况。从实战角度看在数学建模竞赛中熵权TOPSIS因其客观、可解释性强、编程实现简单正逐渐成为综合评价类问题的首选。我们通常会优先采用它除非题目明确要求考虑专家意见。第三步线路优化建模对应TSP/动态规划。给城市打完分后我们得到的是一个城市的“价值”列表。但旅游不是简单的价值叠加城市之间的连接成本交通费、时间至关重要。这就引入了经典的旅行商问题如何访问一系列城市并返回起点使得总路程或总成本最短。但本题的TSP是“带妆出场”的带权访问每个节点城市有一个吸引力得分价值我们追求的是路径上节点价值之和最大而不是路径本身最短。这变成了一个** Prize-Collecting TSP** 或Orienteering Problem的变体。多约束总花费路径成本节点访问成本和总时间有上限。不一定访问所有节点因为预算和时间有限我们只能选择一部分高价值城市访问。面对这种复杂的组合优化问题精确算法如动态规划在节点数稍多20时就会遭遇“组合爆炸”。因此分层策略是明智的先用综合评价法筛选出得分最高的10-15个城市大幅减少问题规模。然后对于这个中等规模的问题我们可以尝试动态规划DP对于15个城市左右的问题状态压缩DP是可行的。我们可以定义状态dp[S][i]表示已经访问过的城市集合为S当前位于城市i所能获得的最大吸引力值。通过状态转移来求解。DP能得到精确解是论文中体现模型严谨性的亮点。元启发式算法如遗传算法、模拟退火。当节点数更多或约束更复杂时这是更实用的选择。它们能快速给出高质量近似解且编程框架相对固定。在我们的解题方案中为了兼顾解的精确性和模型的完整性采用了“熵权TOPSIS筛选 动态规划精确优化”的双层框架。先用TOPSIS从所有长三角城市中选出核心目的地群再对这个精选的集合运用动态规划求解最优线路。3. 基于熵权TOPSIS的城市吸引力综合评价实战理论说得再多不如一行代码。我们假设组委会提供了长三角20个主要旅游城市的详细数据包括景区质量评分、人均消费、高铁班次、酒店均价、气候指数等5个指标。我们的目标是计算每个城市的综合得分。3.1 数据预处理与标准化首先指标通常有正向越大越好如景区评分和负向越小越好如人均消费。我们需要将所有指标转化为极大型。import pandas as pd import numpy as np # 假设df是包含20个城市、5个指标的数据框 # 假设前两列是城市名和编号后五列是指标 df pd.read_excel(city_data.xlsx) data df.iloc[:, 2:].values # 获取指标数据矩阵 city_names df.iloc[:, 0].values # 定义指标方向假设第0,2,4列是正向指标第1,3列是负向指标 pos_indices [0, 2, 4] neg_indices [1, 3] # 标准化处理 - 极差法 def normalize_matrix(matrix, pos_indices, neg_indices): norm_matrix np.zeros_like(matrix, dtypefloat) for j in range(matrix.shape[1]): col matrix[:, j] max_val, min_val col.max(), col.min() if max_val min_val: # 避免除零 norm_matrix[:, j] 1 else: if j in pos_indices: norm_matrix[:, j] (col - min_val) / (max_val - min_val) elif j in neg_indices: norm_matrix[:, j] (max_val - col) / (max_val - min_val) return norm_matrix norm_data normalize_matrix(data, pos_indices, neg_indices)注意数据标准化方法除了极差法还有Z-score标准化等。在TOPSIS中极差法更常用因为它能将结果严格限定在[0,1]区间便于后续计算相对接近度。务必检查数据中是否存在缺失值或异常值需在预处理阶段处理。3.2 计算熵权熵权法的核心思想是指标的数据越离散差异越大其包含的信息量就越大权重也应越高。# 计算熵权 def calculate_entropy_weight(norm_matrix): m, n norm_matrix.shape # 计算比重 p norm_matrix / norm_matrix.sum(axis0, keepdimsTrue) # 计算信息熵避免log(0) p[p 0] 1e-10 e -np.sum(p * np.log(p), axis0) / np.log(m) # 计算差异系数 d 1 - e # 计算权重 w d / d.sum() return w weights calculate_entropy_weight(norm_data) print(各指标熵权, weights)这一步结束后我们就得到了每个指标的客观权重。你会发现像“景区质量”这种城市间差异巨大的指标权重通常会很高而“气候指数”可能大家差不多权重就低。3.3 TOPSIS计算排序有了标准化矩阵和权重向量就可以计算每个城市与正负理想解的距离。def topsis_method(norm_matrix, weights): weighted_matrix norm_matrix * weights # 加权标准化矩阵 # 确定正负理想解 ideal_best weighted_matrix.max(axis0) ideal_worst weighted_matrix.min(axis0) # 计算欧氏距离 dist_best np.sqrt(((weighted_matrix - ideal_best) ** 2).sum(axis1)) dist_worst np.sqrt(((weighted_matrix - ideal_worst) ** 2).sum(axis1)) # 计算相对接近度 score dist_worst / (dist_best dist_worst) return score city_scores topsis_method(norm_data, weights) # 将得分与城市名对应 result_df pd.DataFrame({ 城市: city_names, 综合得分: city_scores }).sort_values(by综合得分, ascendingFalse) print(城市吸引力排名) print(result_df)至此我们得到了20个城市的吸引力排名。根据经验我们会选择排名前**30%-50%**的城市比如前8-12名进入下一阶段的线路优化。选择多少需要结合题目给出的总预算和总时间进行粗略估算。实操心得熵权TOPSIS计算简单但有几个坑极易踩中。第一数据标准化前必须统一指标方向否则结果完全错误。第二计算信息熵时概率p可能出现0导致np.log(0)报错必须用一个极小值如1e-10替代。第三权重的解释一定要在论文中阐述权重的结果比如“景区质量权重最高达0.45说明其在评价体系中最为重要”这能体现你对模型输出的理解而不是机械套用。4. 基于动态规划的旅游线路优化模型构建筛选出N个核心城市后假设N10我们面临一个经典的组合优化问题从起点比如上海出发访问其中M个城市M≤N最后返回起点在总成本和总时间不超过上限的前提下最大化访问城市的吸引力总分。4.1 模型定义与状态设计这是一个带约束的路径选择问题。我们将其形式化集合V {0, 1, 2, ..., N}其中0代表起点上海1到N代表筛选出的N个城市。参数score[i]: 城市i的吸引力得分来自TOPSIS。cost[i][j]: 从城市i到城市j的交通成本可以是金钱或时间根据题目定。stay_cost[i]: 在城市i的停留成本住宿、门票等。B_max: 总预算上限。T_max: 总时间上限。决策变量x[i][j]是否从i走到j。直接建模求解非常困难。我们采用动态规划其关键在于设计“状态”。一个高效的状态设计是dp[S][i][b][t]: 表示当前已访问过的城市集合为S用二进制状态压缩表示当前位于城市i已花费成本为b已用时间为t时所能获得的最大吸引力得分之和。但这是一个四维状态如果N10B和T稍微细分一下状态空间就可能爆炸2^10 * 10 * B * T。因此必须降维。4.2 状态压缩与降维策略实战中我们常采用两种简化将成本和时间约束转化为对访问城市数量的约束通过估算平均每个城市的访问成本和耗时我们可以倒推出在预算和时间限制下最多能访问K个城市。这样问题简化为从N个城市中选择不超过K个并排序成一条回路使得总得分最高。状态可以简化为dp[S][i][k]表示已访问集合S当前位置i已访问了k个城市时的最大得分。忽略成本和时间的精确值在DP完成后进行可行性校验先以最大化得分为目标进行DP得到若干条候选路径然后再计算每条路径的实际成本和耗时筛选出满足约束的路径。这种方法更简单但可能错过一些在约束边界上的最优解。我们采用第一种思路。假设我们估算出最多能访问K5个城市不含起点。那么状态设计如下S: 一个N位的二进制数表示哪些城市已被访问1表示已访问。S的范围是0到(1N)-1。i: 当前所在城市编号0~N0是起点。k: 已经访问的城市数量0~K。状态转移方程dp[S|(1j)][j][k1] max(dp[S|(1j)][j][k1], dp[S][i][k] score[j])转移条件是城市j未被访问过(Sj) 1 0并且从i到j是可行的通常我们预计算一个距离或成本矩阵如果成本无穷大则表示不可直达。4.3 动态规划的实现细节import itertools def dp_tsp_opt(scores, dist_matrix, K): scores: 列表城市吸引力得分scores[0]为起点得分通常为0 dist_matrix: 距离/成本矩阵dist_matrix[i][j]表示从i到j的成本 K: 最多访问城市数 N len(scores) # 包括起点 INF float(-inf) # 初始化dp数组dp[S][i][k] dp [[[INF] * (K1) for _ in range(N)] for _ in range(1N)] dp[1][0][0] 0 # 起点状态只访问了起点(0)位于0访问了0个城市起点不计入 # 预处理确保距离矩阵对称且无自环 for i in range(N): dist_matrix[i][i] 0 # 状态转移 for S in range(1N): for i in range(N): for k in range(K): if dp[S][i][k] INF: continue # 尝试访问下一个城市j for j in range(1, N): # 从1开始因为0是起点 if (S j) 1: # j已访问 continue if dist_matrix[i][j] INF: # 不可达 continue new_S S | (1 j) new_score dp[S][i][k] scores[j] if new_score dp[new_S][j][k1]: dp[new_S][j][k1] new_score # 寻找最优解最终要回到起点0 best_score INF best_path_info None for S in range(1N): for i in range(1, N): for k in range(1, K1): if dp[S][i][k] INF: continue # 检查是否能从i返回起点0 if dist_matrix[i][0] INF: continue total_score dp[S][i][k] # 此时得分已包含所有访问城市的得分 if total_score best_score: best_score total_score best_path_info (S, i, k) # 路径回溯略根据best_path_info反向推导访问顺序 return best_score, best_path_info注意事项上述DP框架是核心思想展示实际实现时需要考虑记忆化搜索以提升效率并且dist_matrix[i][j]为INF表示不可直达这在现实中是可能的比如两地无直达交通。此外K的设定非常关键。如果设得太大DP状态爆炸设得太小可能漏掉最优解。一个稳妥的做法是先用贪心算法快速估算一个路径长度作为K的参考或者设置K从1到N进行遍历选择满足约束的最优解。5. 模型整合、求解与结果分析我们将TOPSIS和DP两个模块串联起来形成完整的求解流水线。5.1 数据流与参数传递输入原始城市数据指标、城市间交通成本矩阵、总预算B、总时间T。模块一TOPSIS处理原始数据输出每个城市的综合得分score[i]。根据得分排序选择Top N个城市进入优化池。同时根据B和T以及城市平均消费和耗时估算最大访问城市数K。模块二DP优化从优化池中提取这N个城市对应的score子集以及它们之间的子成本矩阵dist_matrixN x N。调用DP函数求解在最多访问K个城市约束下的最优路径和最大得分。输出最优访问路径城市序列、路径总吸引力得分、实际总成本、实际总耗时。5.2 求解实例与结果展示假设我们经过TOPSIS筛选出8个城市编号1-8加上起点上海编号0共9个节点。估算出K4。运行DP后得到最优路径为上海 - 杭州 - 苏州 - 南京 - 上海总得分为8.75假设得分经过标准化。 接下来我们需要验证这条路径的实际成本和时间是否超出上限。计算路径的交通成本总和、各城市停留成本总和与B_max比较计算交通时间与停留时间总和与T_max比较。如果均未超限则该解为可行最优解。如果超限则需要调整K值重新求解或者采用更精细的DP状态包含成本维度。在论文中呈现结果时不要只扔出一个路径。应该包括表1城市吸引力综合评价结果展示所有城市原始指标、标准化值、权重、综合得分及排名。图1长三角核心城市吸引力得分雷达图或柱状图直观展示TOP城市的优势指标。表2城市间交通成本/时间矩阵部分展示。图2最优旅游线路规划图在地图上绘制出最优路径清晰美观。表3最优线路详情列出行程每一天的安排包括出发城市、到达城市、交通方式、成本、游览景点、吸引力得分累计等。5.3 模型检验与灵敏度分析一个完整的数模论文必须有模型检验部分。对于本题稳定性检验改变TOPSIS中标准化方法如改用Z-score观察城市排名是否发生剧烈变化。如果排名基本稳定说明模型稳健。参数灵敏度分析分析总预算B_max和总时间T_max的变化对最优线路的影响。例如将预算提高10%最优路径增加了某个高消费高得分的城市如黄山说明该城市是“预算敏感型”景点。算法对比可以将DP得到的结果与贪心算法每次选当前最近/得分最高的城市的结果进行对比展示DP在全局优化上的优势。也可以尝试用模拟退火算法求近似解与DP的精确解对比在小规模问题上验证二者接近程度。踩坑实录与技巧数据归一化的陷阱TOPSIS中如果某个指标所有城市数据完全相同方差为0熵权法会赋予其权重0。这虽然在数学上合理但有时与常识不符。遇到这种情况可以考虑将该指标与其他相关指标合并或改用AHP赋予一个基础权重。DP状态设计过载最初总想设计一个包含所有约束的完美DP状态结果导致程序根本无法运行。一定要学会简化。先解决核心问题最大化得分再将约束以筛选或校验的方式加入。路径回溯的代码调试DP求最大值容易但记录路径稍麻烦。通常需要用一个并行的path或pre数组来记录状态转移的前驱节点。调试时先确保在小规模数据如3个城市上能正确输出路径。论文写作中的图表很多队伍算法做得不错但论文图表丑陋。强烈建议使用Python的Matplotlib或Seaborn库绘制专业图表。地图路径图可以用Basemap或Folium库生成。一张精美的图能给论文加分不少。时间管理三天比赛第一天应完成选题、思路设计和数据预处理第二天上午完成TOPSIS模块并开始DP编码第二天下午到晚上完成DP求解、结果分析和初稿写作第三天全天用于模型检验、灵敏度分析、论文精修和摘要撰写。切忌在某个难点上卡死太久。6. 常见问题排查与扩展思考在实际编程和写作过程中你肯定会遇到各种报错和疑惑。这里汇总一些典型问题Q1: TOPSIS计算出的得分非常接近区分度不大怎么办A1: 这通常是因为数据标准化后各城市在不同指标上“互有胜负”导致综合得分趋同。可以尝试①增加指标寻找更具区分度的评价指标。②调整权重如果使用熵权法结果不理想可以尝试结合主观赋权法如AHP形成组合权重。③改变标准化方法尝试向量归一化等方法。Q2: 动态规划程序运行速度太慢N15就卡住了。A2: 状态压缩DP的复杂度是O(2^N * N^2 * K)N15时状态数已超过3000万确实慢。优化方法①剪枝在循环中如果当前状态dp[S][i][k]为无效值INF直接跳过。②使用更高效的数据结构用字典存储有效状态而不是庞大的三维数组。③降维打击用启发式算法如遗传算法替代DP求近似最优解这在N15时是更实际的选择。Q3: 题目要求同时优化“满意度”和“成本”是多目标问题如何处理A3: 这是本题的深化。处理多目标优化主要有两种方法①加权求和法将满意度得分和成本取倒数或负值赋予权重加权为一个综合目标函数。权重的设定需要说明如根据公司战略是更看重口碑还是利润。②帕累托前沿法寻找一系列“非劣解”即无法在不损害一个目标的情况下改进另一个目标。可以用多目标进化算法来求解并绘制帕累托前沿图让决策者根据偏好选择。Q4: 如何将时间约束更精细地纳入模型A4: 我们之前的模型将时间简化为城市间交通时间和固定停留时间。更精细的建模可以考虑①时间窗某些景点只在特定时间段开放。②交通方式选择城市间可选择高铁、汽车等其时间和成本不同。这会将问题扩展为更复杂的“带时间窗的多模式交通旅行商问题”。此时DP状态需要加入“当前时刻”维度模型复杂度急剧上升通常需采用启发式算法求解。扩展思考模型的实际应用与局限性我们这个“TOPSISDP”框架本质上是将复杂的现实问题分解为评价和优化两个相对独立的阶段。它的优势是思路清晰模块化易于理解和实现。在竞赛中这种扎实的框架能确保拿到基础分数。 但其局限性也很明显1.两阶段割裂TOPSIS评价时未考虑城市间的协同效应比如“苏州园林”和“杭州西湖”具有互补性一起游览满意度可能更高。2.DP的规模限制无法处理大规模节点。在实际的旅游线路规划中节点数可能成百上千必须依赖更强大的启发式或元启发式算法如大规模邻域搜索、强化学习等。 因此在论文的“模型评价与推广”部分可以诚实地指出这些不足并提出改进方向例如设计一个将评价与路径同步优化的迭代算法或者引入机器学习模型来预测游客对特定线路组合的满意度。这能体现你对问题更深层次的思考。 TOPSIS与动态规划在旅游线路优化中的实战应用
1. 项目概述与赛题背景2021年长三角高校数学建模竞赛的A题“Go!Fun游长三角”是一个典型的、融合了运筹优化与综合评价的复杂现实问题。拿到这个题目第一感觉就是“味儿对了”——它不像一些纯理论推导题那样飘在空中而是把数学模型实实在在地摁在了旅游规划这个接地气的场景里。题目要求参赛者为一家旅游公司设计一条覆盖长三角多个城市的旅游线路这听起来像是经典的旅行商问题但细看之下远不止于此。它不仅要你规划出一条“走遍”的路径还要综合考虑每个城市的“游玩价值”、游客的“满意度”、以及最重要的“成本控制”。换句话说它要求你在有限的预算和时间内拿出一条能让游客玩得爽、公司赚得稳的“黄金线路”。这种多目标、带约束的优化问题正是数学建模从课本走向产业应用的核心体现非常考验参赛者对模型进行拆解、融合与创新的能力。从网络热词的集中度来看“TSP”、“动态规划”、“TOPSIS”、“层次分析法”是大家讨论和求解本题时绕不开的几个核心工具。这很合理因为题目本身的结构就天然分成了几个模块如何量化每个城市的吸引力评价问题如何基于这些吸引力和其他约束生成可行的线路路径优化问题。前者是静态的评价排序适合用综合评价方法后者是动态的序列决策适合用优化算法。所以一个成熟的解题框架应该是先用AHP或熵权TOPSIS对各个候选城市进行打分排序筛选出高价值目的地再将这些城市作为节点构建一个考虑时间、成本、满意度等多重约束的改进型TSP模型进行线路规划。动态规划则可能是求解这个复杂TSP模型的一种有效手段尤其是在节点数经过筛选后规模可控的情况下。接下来我就结合自己多次带队参赛和评审的经验把这个“解题全过程”掰开揉碎了讲清楚从思路构建到程序实现包括那些论文里不会写的“坑”和“技巧”。2. 核心思路拆解与模型选型逻辑面对“Go!Fun游长三角”这种多目标规划题最忌讳的就是一上来就埋头写公式、调代码。我的经验是先花足够的时间把题目“翻译”成数学语言并设计一个清晰的、模块化的求解流水线。整个解题的顶层逻辑可以概括为“评价-筛选-优化-验证”四步走。第一步定义目标与量化指标。题目中隐含了至少三个目标最大化旅游线路的总体吸引力让游客满意最小化总成本让公司盈利以及满足时间约束行程可行。这三个目标往往是相互冲突的便宜的路线可能不好玩好玩的路线可能超预算。因此我们通常不追求同时达到三个最优而是采用“主要目标法”或“约束法”。在本题中更实际的思路是将“最大化吸引力”作为主要目标将“总成本”和“总时间”作为硬性约束。也就是说我们在不超过预算和规定天数的前提下找出一条吸引力最高的线路。第二步城市吸引力综合评价对应TOPSIS/AHP。哪些城市值得去题目通常会提供或暗示一系列评价指标比如城市的旅游资源等级5A/4A景区数量、文化底蕴指数、交通便利度、消费水平、气候舒适度等。我们的任务就是给每个候选城市一个综合得分。这里有两个主流方法层次分析法适合指标间存在层次关系且需要融入一定主观经验如专家打分的情况。通过构建判断矩阵计算权重一致性检验最后得到每个城市的加权得分。它的优势是能处理定性指标逻辑清晰缺点是主观性较强当指标或城市较多时构造判断矩阵的工作量巨大且容易不一致。熵权TOPSIS法这是一种客观赋权法。它根据各指标数据本身的离散程度熵来确定权重信息量越大的指标权重越高。然后通过计算每个城市与正理想解、负理想解的相对接近度来排序。它的优势是完全依赖客观数据避免了人为干扰特别适合本题这种可能给出大量定量数据的情况。从实战角度看在数学建模竞赛中熵权TOPSIS因其客观、可解释性强、编程实现简单正逐渐成为综合评价类问题的首选。我们通常会优先采用它除非题目明确要求考虑专家意见。第三步线路优化建模对应TSP/动态规划。给城市打完分后我们得到的是一个城市的“价值”列表。但旅游不是简单的价值叠加城市之间的连接成本交通费、时间至关重要。这就引入了经典的旅行商问题如何访问一系列城市并返回起点使得总路程或总成本最短。但本题的TSP是“带妆出场”的带权访问每个节点城市有一个吸引力得分价值我们追求的是路径上节点价值之和最大而不是路径本身最短。这变成了一个** Prize-Collecting TSP** 或Orienteering Problem的变体。多约束总花费路径成本节点访问成本和总时间有上限。不一定访问所有节点因为预算和时间有限我们只能选择一部分高价值城市访问。面对这种复杂的组合优化问题精确算法如动态规划在节点数稍多20时就会遭遇“组合爆炸”。因此分层策略是明智的先用综合评价法筛选出得分最高的10-15个城市大幅减少问题规模。然后对于这个中等规模的问题我们可以尝试动态规划DP对于15个城市左右的问题状态压缩DP是可行的。我们可以定义状态dp[S][i]表示已经访问过的城市集合为S当前位于城市i所能获得的最大吸引力值。通过状态转移来求解。DP能得到精确解是论文中体现模型严谨性的亮点。元启发式算法如遗传算法、模拟退火。当节点数更多或约束更复杂时这是更实用的选择。它们能快速给出高质量近似解且编程框架相对固定。在我们的解题方案中为了兼顾解的精确性和模型的完整性采用了“熵权TOPSIS筛选 动态规划精确优化”的双层框架。先用TOPSIS从所有长三角城市中选出核心目的地群再对这个精选的集合运用动态规划求解最优线路。3. 基于熵权TOPSIS的城市吸引力综合评价实战理论说得再多不如一行代码。我们假设组委会提供了长三角20个主要旅游城市的详细数据包括景区质量评分、人均消费、高铁班次、酒店均价、气候指数等5个指标。我们的目标是计算每个城市的综合得分。3.1 数据预处理与标准化首先指标通常有正向越大越好如景区评分和负向越小越好如人均消费。我们需要将所有指标转化为极大型。import pandas as pd import numpy as np # 假设df是包含20个城市、5个指标的数据框 # 假设前两列是城市名和编号后五列是指标 df pd.read_excel(city_data.xlsx) data df.iloc[:, 2:].values # 获取指标数据矩阵 city_names df.iloc[:, 0].values # 定义指标方向假设第0,2,4列是正向指标第1,3列是负向指标 pos_indices [0, 2, 4] neg_indices [1, 3] # 标准化处理 - 极差法 def normalize_matrix(matrix, pos_indices, neg_indices): norm_matrix np.zeros_like(matrix, dtypefloat) for j in range(matrix.shape[1]): col matrix[:, j] max_val, min_val col.max(), col.min() if max_val min_val: # 避免除零 norm_matrix[:, j] 1 else: if j in pos_indices: norm_matrix[:, j] (col - min_val) / (max_val - min_val) elif j in neg_indices: norm_matrix[:, j] (max_val - col) / (max_val - min_val) return norm_matrix norm_data normalize_matrix(data, pos_indices, neg_indices)注意数据标准化方法除了极差法还有Z-score标准化等。在TOPSIS中极差法更常用因为它能将结果严格限定在[0,1]区间便于后续计算相对接近度。务必检查数据中是否存在缺失值或异常值需在预处理阶段处理。3.2 计算熵权熵权法的核心思想是指标的数据越离散差异越大其包含的信息量就越大权重也应越高。# 计算熵权 def calculate_entropy_weight(norm_matrix): m, n norm_matrix.shape # 计算比重 p norm_matrix / norm_matrix.sum(axis0, keepdimsTrue) # 计算信息熵避免log(0) p[p 0] 1e-10 e -np.sum(p * np.log(p), axis0) / np.log(m) # 计算差异系数 d 1 - e # 计算权重 w d / d.sum() return w weights calculate_entropy_weight(norm_data) print(各指标熵权, weights)这一步结束后我们就得到了每个指标的客观权重。你会发现像“景区质量”这种城市间差异巨大的指标权重通常会很高而“气候指数”可能大家差不多权重就低。3.3 TOPSIS计算排序有了标准化矩阵和权重向量就可以计算每个城市与正负理想解的距离。def topsis_method(norm_matrix, weights): weighted_matrix norm_matrix * weights # 加权标准化矩阵 # 确定正负理想解 ideal_best weighted_matrix.max(axis0) ideal_worst weighted_matrix.min(axis0) # 计算欧氏距离 dist_best np.sqrt(((weighted_matrix - ideal_best) ** 2).sum(axis1)) dist_worst np.sqrt(((weighted_matrix - ideal_worst) ** 2).sum(axis1)) # 计算相对接近度 score dist_worst / (dist_best dist_worst) return score city_scores topsis_method(norm_data, weights) # 将得分与城市名对应 result_df pd.DataFrame({ 城市: city_names, 综合得分: city_scores }).sort_values(by综合得分, ascendingFalse) print(城市吸引力排名) print(result_df)至此我们得到了20个城市的吸引力排名。根据经验我们会选择排名前**30%-50%**的城市比如前8-12名进入下一阶段的线路优化。选择多少需要结合题目给出的总预算和总时间进行粗略估算。实操心得熵权TOPSIS计算简单但有几个坑极易踩中。第一数据标准化前必须统一指标方向否则结果完全错误。第二计算信息熵时概率p可能出现0导致np.log(0)报错必须用一个极小值如1e-10替代。第三权重的解释一定要在论文中阐述权重的结果比如“景区质量权重最高达0.45说明其在评价体系中最为重要”这能体现你对模型输出的理解而不是机械套用。4. 基于动态规划的旅游线路优化模型构建筛选出N个核心城市后假设N10我们面临一个经典的组合优化问题从起点比如上海出发访问其中M个城市M≤N最后返回起点在总成本和总时间不超过上限的前提下最大化访问城市的吸引力总分。4.1 模型定义与状态设计这是一个带约束的路径选择问题。我们将其形式化集合V {0, 1, 2, ..., N}其中0代表起点上海1到N代表筛选出的N个城市。参数score[i]: 城市i的吸引力得分来自TOPSIS。cost[i][j]: 从城市i到城市j的交通成本可以是金钱或时间根据题目定。stay_cost[i]: 在城市i的停留成本住宿、门票等。B_max: 总预算上限。T_max: 总时间上限。决策变量x[i][j]是否从i走到j。直接建模求解非常困难。我们采用动态规划其关键在于设计“状态”。一个高效的状态设计是dp[S][i][b][t]: 表示当前已访问过的城市集合为S用二进制状态压缩表示当前位于城市i已花费成本为b已用时间为t时所能获得的最大吸引力得分之和。但这是一个四维状态如果N10B和T稍微细分一下状态空间就可能爆炸2^10 * 10 * B * T。因此必须降维。4.2 状态压缩与降维策略实战中我们常采用两种简化将成本和时间约束转化为对访问城市数量的约束通过估算平均每个城市的访问成本和耗时我们可以倒推出在预算和时间限制下最多能访问K个城市。这样问题简化为从N个城市中选择不超过K个并排序成一条回路使得总得分最高。状态可以简化为dp[S][i][k]表示已访问集合S当前位置i已访问了k个城市时的最大得分。忽略成本和时间的精确值在DP完成后进行可行性校验先以最大化得分为目标进行DP得到若干条候选路径然后再计算每条路径的实际成本和耗时筛选出满足约束的路径。这种方法更简单但可能错过一些在约束边界上的最优解。我们采用第一种思路。假设我们估算出最多能访问K5个城市不含起点。那么状态设计如下S: 一个N位的二进制数表示哪些城市已被访问1表示已访问。S的范围是0到(1N)-1。i: 当前所在城市编号0~N0是起点。k: 已经访问的城市数量0~K。状态转移方程dp[S|(1j)][j][k1] max(dp[S|(1j)][j][k1], dp[S][i][k] score[j])转移条件是城市j未被访问过(Sj) 1 0并且从i到j是可行的通常我们预计算一个距离或成本矩阵如果成本无穷大则表示不可直达。4.3 动态规划的实现细节import itertools def dp_tsp_opt(scores, dist_matrix, K): scores: 列表城市吸引力得分scores[0]为起点得分通常为0 dist_matrix: 距离/成本矩阵dist_matrix[i][j]表示从i到j的成本 K: 最多访问城市数 N len(scores) # 包括起点 INF float(-inf) # 初始化dp数组dp[S][i][k] dp [[[INF] * (K1) for _ in range(N)] for _ in range(1N)] dp[1][0][0] 0 # 起点状态只访问了起点(0)位于0访问了0个城市起点不计入 # 预处理确保距离矩阵对称且无自环 for i in range(N): dist_matrix[i][i] 0 # 状态转移 for S in range(1N): for i in range(N): for k in range(K): if dp[S][i][k] INF: continue # 尝试访问下一个城市j for j in range(1, N): # 从1开始因为0是起点 if (S j) 1: # j已访问 continue if dist_matrix[i][j] INF: # 不可达 continue new_S S | (1 j) new_score dp[S][i][k] scores[j] if new_score dp[new_S][j][k1]: dp[new_S][j][k1] new_score # 寻找最优解最终要回到起点0 best_score INF best_path_info None for S in range(1N): for i in range(1, N): for k in range(1, K1): if dp[S][i][k] INF: continue # 检查是否能从i返回起点0 if dist_matrix[i][0] INF: continue total_score dp[S][i][k] # 此时得分已包含所有访问城市的得分 if total_score best_score: best_score total_score best_path_info (S, i, k) # 路径回溯略根据best_path_info反向推导访问顺序 return best_score, best_path_info注意事项上述DP框架是核心思想展示实际实现时需要考虑记忆化搜索以提升效率并且dist_matrix[i][j]为INF表示不可直达这在现实中是可能的比如两地无直达交通。此外K的设定非常关键。如果设得太大DP状态爆炸设得太小可能漏掉最优解。一个稳妥的做法是先用贪心算法快速估算一个路径长度作为K的参考或者设置K从1到N进行遍历选择满足约束的最优解。5. 模型整合、求解与结果分析我们将TOPSIS和DP两个模块串联起来形成完整的求解流水线。5.1 数据流与参数传递输入原始城市数据指标、城市间交通成本矩阵、总预算B、总时间T。模块一TOPSIS处理原始数据输出每个城市的综合得分score[i]。根据得分排序选择Top N个城市进入优化池。同时根据B和T以及城市平均消费和耗时估算最大访问城市数K。模块二DP优化从优化池中提取这N个城市对应的score子集以及它们之间的子成本矩阵dist_matrixN x N。调用DP函数求解在最多访问K个城市约束下的最优路径和最大得分。输出最优访问路径城市序列、路径总吸引力得分、实际总成本、实际总耗时。5.2 求解实例与结果展示假设我们经过TOPSIS筛选出8个城市编号1-8加上起点上海编号0共9个节点。估算出K4。运行DP后得到最优路径为上海 - 杭州 - 苏州 - 南京 - 上海总得分为8.75假设得分经过标准化。 接下来我们需要验证这条路径的实际成本和时间是否超出上限。计算路径的交通成本总和、各城市停留成本总和与B_max比较计算交通时间与停留时间总和与T_max比较。如果均未超限则该解为可行最优解。如果超限则需要调整K值重新求解或者采用更精细的DP状态包含成本维度。在论文中呈现结果时不要只扔出一个路径。应该包括表1城市吸引力综合评价结果展示所有城市原始指标、标准化值、权重、综合得分及排名。图1长三角核心城市吸引力得分雷达图或柱状图直观展示TOP城市的优势指标。表2城市间交通成本/时间矩阵部分展示。图2最优旅游线路规划图在地图上绘制出最优路径清晰美观。表3最优线路详情列出行程每一天的安排包括出发城市、到达城市、交通方式、成本、游览景点、吸引力得分累计等。5.3 模型检验与灵敏度分析一个完整的数模论文必须有模型检验部分。对于本题稳定性检验改变TOPSIS中标准化方法如改用Z-score观察城市排名是否发生剧烈变化。如果排名基本稳定说明模型稳健。参数灵敏度分析分析总预算B_max和总时间T_max的变化对最优线路的影响。例如将预算提高10%最优路径增加了某个高消费高得分的城市如黄山说明该城市是“预算敏感型”景点。算法对比可以将DP得到的结果与贪心算法每次选当前最近/得分最高的城市的结果进行对比展示DP在全局优化上的优势。也可以尝试用模拟退火算法求近似解与DP的精确解对比在小规模问题上验证二者接近程度。踩坑实录与技巧数据归一化的陷阱TOPSIS中如果某个指标所有城市数据完全相同方差为0熵权法会赋予其权重0。这虽然在数学上合理但有时与常识不符。遇到这种情况可以考虑将该指标与其他相关指标合并或改用AHP赋予一个基础权重。DP状态设计过载最初总想设计一个包含所有约束的完美DP状态结果导致程序根本无法运行。一定要学会简化。先解决核心问题最大化得分再将约束以筛选或校验的方式加入。路径回溯的代码调试DP求最大值容易但记录路径稍麻烦。通常需要用一个并行的path或pre数组来记录状态转移的前驱节点。调试时先确保在小规模数据如3个城市上能正确输出路径。论文写作中的图表很多队伍算法做得不错但论文图表丑陋。强烈建议使用Python的Matplotlib或Seaborn库绘制专业图表。地图路径图可以用Basemap或Folium库生成。一张精美的图能给论文加分不少。时间管理三天比赛第一天应完成选题、思路设计和数据预处理第二天上午完成TOPSIS模块并开始DP编码第二天下午到晚上完成DP求解、结果分析和初稿写作第三天全天用于模型检验、灵敏度分析、论文精修和摘要撰写。切忌在某个难点上卡死太久。6. 常见问题排查与扩展思考在实际编程和写作过程中你肯定会遇到各种报错和疑惑。这里汇总一些典型问题Q1: TOPSIS计算出的得分非常接近区分度不大怎么办A1: 这通常是因为数据标准化后各城市在不同指标上“互有胜负”导致综合得分趋同。可以尝试①增加指标寻找更具区分度的评价指标。②调整权重如果使用熵权法结果不理想可以尝试结合主观赋权法如AHP形成组合权重。③改变标准化方法尝试向量归一化等方法。Q2: 动态规划程序运行速度太慢N15就卡住了。A2: 状态压缩DP的复杂度是O(2^N * N^2 * K)N15时状态数已超过3000万确实慢。优化方法①剪枝在循环中如果当前状态dp[S][i][k]为无效值INF直接跳过。②使用更高效的数据结构用字典存储有效状态而不是庞大的三维数组。③降维打击用启发式算法如遗传算法替代DP求近似最优解这在N15时是更实际的选择。Q3: 题目要求同时优化“满意度”和“成本”是多目标问题如何处理A3: 这是本题的深化。处理多目标优化主要有两种方法①加权求和法将满意度得分和成本取倒数或负值赋予权重加权为一个综合目标函数。权重的设定需要说明如根据公司战略是更看重口碑还是利润。②帕累托前沿法寻找一系列“非劣解”即无法在不损害一个目标的情况下改进另一个目标。可以用多目标进化算法来求解并绘制帕累托前沿图让决策者根据偏好选择。Q4: 如何将时间约束更精细地纳入模型A4: 我们之前的模型将时间简化为城市间交通时间和固定停留时间。更精细的建模可以考虑①时间窗某些景点只在特定时间段开放。②交通方式选择城市间可选择高铁、汽车等其时间和成本不同。这会将问题扩展为更复杂的“带时间窗的多模式交通旅行商问题”。此时DP状态需要加入“当前时刻”维度模型复杂度急剧上升通常需采用启发式算法求解。扩展思考模型的实际应用与局限性我们这个“TOPSISDP”框架本质上是将复杂的现实问题分解为评价和优化两个相对独立的阶段。它的优势是思路清晰模块化易于理解和实现。在竞赛中这种扎实的框架能确保拿到基础分数。 但其局限性也很明显1.两阶段割裂TOPSIS评价时未考虑城市间的协同效应比如“苏州园林”和“杭州西湖”具有互补性一起游览满意度可能更高。2.DP的规模限制无法处理大规模节点。在实际的旅游线路规划中节点数可能成百上千必须依赖更强大的启发式或元启发式算法如大规模邻域搜索、强化学习等。 因此在论文的“模型评价与推广”部分可以诚实地指出这些不足并提出改进方向例如设计一个将评价与路径同步优化的迭代算法或者引入机器学习模型来预测游客对特定线路组合的满意度。这能体现你对问题更深层次的思考。