2021年长三角高校数学建模竞赛
A题 Go!Fun游长三角
原题再现：
又到一年毕业季，来自浙江杭州的一位大学生小李同学，家境良好，平时学习刻苦，在即将毕业之际，准备给自己安排一个毕业旅行，同时帮助“长三角旅游推广联盟”考察一下长三角地区旅游资源的开发及利用情况。在做旅行计划时，他希望这是一个有美食、有风景、令人难忘的毕业旅行。请你们搜集相关数据，建立数学模型，帮助小李同学规划旅行计划，讨论并解决以下问题：
1．若小李同学只有两个星期的旅行时间，请你们的团队为他规划旅行计划。
2．若小李同学时间比较充裕，但能够支配的旅行资金只有 5000 元钱，请你们的团队为他规划旅行计划。
3．若小李同学只有两个星期的旅行时间，也只有 5000 元钱作为旅行资金，请你们的团队为他规划旅行计划。
4．小李的爷爷是个退伍军人，目前已经退休在家，时常怀念曾经的峥嵘岁月，听说小李要去毕业旅行，于是来到杭州准备爷孙同游，请你们为小李和他的爷爷规划不超过两个星期、两人旅行总费用不超过 1 万元的旅行计划。
5．小李还是一个兼职新媒体人，bilibili 平台（以下简称“B 站”）粉丝数达 52.5万。在旅行中，他想通过 B 站更新，在涨粉的同时为旅行经费添砖加瓦。小李的 B 站收入仅限于创作激励，即“播放量+点赞数+投币+收藏”所带来的流量变现，且该收益与当天的具体旅游景点密切相关。为保证收益，假设在其旅行时间内更新频率为日更，更新内容为当天旅行的 1 小时 vlog，vlog 是指视频记录、视频博客、视频网络日志。若报酬按日结算，结算的费用可以补充为旅行费用，请你们自行查找数据，重新完成 2-4 问。
整体求解过程概述(摘要)
本文基于优劣解距离法以及动态规划 TSP 法，帮助毕业生小李在不同条件的约束下规划出相较而言最适合的旅行线路。
针对问题 1，我们以两个星期时间、位于长三角地区为约束条件；以游玩最多的景点数为目标函数；以是否前往该景点游玩为决策变量；以各个景点之间的来往时间消耗来综合建立最优决策模型。
由于对经济没有约束，我们选择用时最短的交通方式，记录耗时最短的数据。我们首先采取 TOPSIS 法（优劣解距离法）对模型进行评分，选出最优秀的 14 个景点。然后通过动态规划 TSP 法，计算出耗时最短的路线。得到的最优旅行线路是：西湖→西溪湿地→鲁迅故里沈园→天台山→乌镇→南浔古镇→拙政园→周庄→嘉兴南湖→横店→中山陵→侵华日军南京大屠杀遇难同胞纪念馆→皖南古村→千岛湖。此线路耗时 14 天，消费 7356.4 元。
针对问题 2，我们在题 1TOPSIS 评分模型的基础上，以 5000 元为约束条件采用动态规划的 TSP 法求解路线，因为旅行经费有限，所以用较为经济的交通方式，虽然增加了路程时间，但是支付的路费更少，目标为在 14 天的时间内游玩尽可能多的景点。
得到的最优旅行线路是：西湖→西溪湿地→中山陵→拙政园→侵华日军南京大屠杀遇难同胞纪念馆→天台山→鲁迅故里沈园→千岛湖→周庄→乌镇→皖南古村→嘉兴南湖。此线路耗时 12 天，消费 4997.6 元。
针对问题 3，根据规则，对旅行的时间和花销同时做出了约束。首先（通过对数据的分析），选择权衡金钱与时间的最优的交通方式。以是否前往入选的景点决策条件；以游玩最多的景点数为目标函数；以游玩时间与所带金钱为约束条件；以及旅行过程中时间金钱的消耗情况综合建立最优决策模型。基于动态规划 TSP 法，使旅行计划能尽可能的减少时间与金钱的消耗，达到在规则下游玩景点最多、获得最优体验的目的。
得到的最优旅行线路是：西湖→西溪湿地→中山陵→拙政园→侵华日军南京大屠杀遇难同胞纪念馆→天台山→鲁迅故里沈园→千岛湖→周庄→乌镇→皖南古村→嘉兴南湖。此线路耗时 12 天，消费 4997.6 元。
针对问题 4，由于爷爷的加入，景点的选择将会向具有历史意义的人文景点偏移。我们采用层次分析法，对各个景点赋予权重，重新筛选出最适合去的多个景点。基于动态规划 TSP 法，考虑双人日消耗费用和门票费用的增加，求得最优旅行线路是：西湖→皖南古村→侵华日军南京大屠杀遇难同胞纪念馆→雨花台风景区→中山陵→拙政园→周庄→宋庆龄故居→嘉兴南湖→乌镇→南浔古镇→千岛湖→天台山→鲁迅故里，此线路耗时 14 天，消费 7025.5 元
针对问题 5，由于小李可以通过流量变现助力旅行，我们采用 TOPSIS 法的思想，考虑景点的热门程度对视频播放量的影响，并将热门度作为影响权重的重要因素，重新筛选出最适合去的多个景点。运用公式预测出小李的视频收入，用以减少其每日消耗。
处于问题 5 的条件下，问题 2 的最优旅行线路是：西湖→拙政园→朱家角古镇→南浔古镇→鼋头渚→普陀山→天台山→黄山→皖南古村→夫子庙→横店影视城→乌镇→同里古镇→周庄，此线路耗时 14 天，消费 2579.9 元；问题 3 的最优旅行线路是：西
湖→拙政园→朱家角古镇→南浔古镇→鼋头渚→普陀山→天台山→黄山→皖南古村→夫子庙→横店影视城→乌镇→同里古镇→周庄，此线路耗时 14 天，消费 2579.9 元；问题 4 的最优旅行线路是：西湖→横店影视城→天台山→普陀山→乌镇→南浔古镇→朱家角古镇→周庄→同里古镇→拙政园→中山陵→夫子庙→黄山→皖南古村，此线路耗时 14 天，消费 3577.8 元。
本文最后讨论了模型的优缺点，并对模型的应用与推广做了进一步的思考。
模型假设：
(1) 假设旅行期间天气适宜和旅行期间正常作息；
(2) 假设一天只能游玩一个景点；
(3) 假设区域间交通线完善，且路费与距离成具有相关性；
(4) 假设各个城市的三餐和住宿费用固定且相同（单人每天 300 元，双人每天 400元）；
(5) 假设小李的视频不限流、粉丝活跃度稳定且更新频率为日更；
(6) 假设爷爷已达 70 岁高龄，可以享受票价优惠。
问题分析：
针对问题 1
在问题 1 中采用美食、风景、令人难忘程度作为评价指标，依据多目标决策TOPSIS 模型，得到每个景点的归一化得分，因为指标体系经过合理正向化、标准化，最终得分越高，表示景点推荐度越高。小李同学的旅行时间限定为两个星期，而旅行资金不受限制。根据各景点距离与交通时间的关系，牺牲部分旅行开销换取最快的交通方式，并以时间为约束条件采用动态规划的 TSP 法[2]求解路线，目标为在 14 天的时间内游玩尽可能多的景点。
针对问题 2
本问中参考问题一的 TOPSIS 模型，获取每个景点的得分。小李同学的旅行资金限定为 5000 元，而旅行时间不受限制，故牺牲部分旅行时间换取最便宜的交通方式，制定性价比高的旅行方案，并以相关消费为约束条件建立动态规划的 TSP 法求解路线目标为在 5000 元的经费内游玩尽可能多的景点。
针对问题 3
此问中小李同学的旅行时间限定为两个星期，而旅行资金限定为 5000 元，即旅行时间和旅行消费同时制约的情况下，要使旅行的景点最多。首先参考问题一的 TOPSIS模型，获取每个景点的得分。以相关时间、消费为约束条件建立动态规划的 TSP 法求解路线，在两个限制条件内制定最佳旅行方案。
针对问题 4
本问小李和爷爷同游，首先由于爷爷是个军人且怀念峥嵘岁月，对于景点的选择，可以更多加入具有人文气息的红色景点。故采用美食、风景、令人难忘程度和人文气息作为评价指标，其中对于人文气息使用层次分析法赋予其较高权重，依据多目标决策 TOPSIS 模型，得到各景点得分，以此体现推荐度。其次，爷孙同游的旅行时间限定为两个星期，而旅行资金限定为 10000 元，即旅行时间和旅行消费同时制约的情况下，要使旅行的景点最多。最后，以相关时间、消费为约束条件建立动态规划的TSP 法求解路线，在两个限制条件内制定最佳旅行方案。
针对问题 5
该问题中小李兼职自媒体行业，“播放量+点赞数+投币+收藏”带来的流量可以变现并用于补充旅行资金，而收益与当天的旅游景点网络热度相关。因此，采用美食、风景、令人难忘程度和网络热度作为评价指标，其中对于网络热度使用层次分析法赋予其较高权重，依据多目标决策 TOPSIS 模型，得到各景点得分，以此体现推荐度。在此模型的基础上：
(1) 针对问题 2，以相关消费为约束条件建立动态规划的 TSP 法求解路线；
(2) 针对问题 3，以相关时间、消费为约束条件建立动态规划的 TSP 法求解路线；
(3) 针对问题 4，增加人文气息作为评价指标，以相关时间、消费为约束条件建立动态规划的 TSP 法求解路线。
模型的建立与求解整体论文缩略图
全部论文请见下方“ 只会建模 QQ名片” 点击QQ名片即可
程序代码：(代码和文档not free)
A=[1 1 1 0.25 0.2;1 1 1 0.25 0.2;1 1 1 0.25 0.2;4 4 4 1 0.33;5 5 5 3 1];
n=5;
Prduct_A = prod(A,2);
Prduct_n_A = Prduct_A .^ (1/n);
disp(Prduct_n_A ./ sum(Prduct_n_A))
function [circle,dis]=minCycle_dp(adjM,pS,startPnt)
%预处理
A=size(adjM,1);
switch 1
case nargin==1,pS=1:A;startPnt=1;
case nargin==2,startPnt=pS(1);
end
pS=pS(:);
%动态规划
dpSheet=inf.*ones(A,2^(A-1));
for m=1:A
dpSheet(m,1)=adjM(m,1);
end
for m=1:2^(A-1)
for n=1:A
binnum=dec2bin(m-1);
binnum=binnum(length(binnum):-1:1);
comSet=find(binnum=='1');
for k=1:length(comSet)
subSet=comSet;
subSet(subSet==comSet(k))=[];
decNum=sum(2.^(subSet-1))+1;
if dpSheet(n,m)>adjM(n,comSet(k)+1)+dpSheet(comSet(k)+1,decNum)
dpSheet(n,m)=adjM(n,comSet(k)+1)+dpSheet(comSet(k)+1,decNum);
end
end
end
end
%输出路径
circlePath=1;
comSet=2:A;
while ~isempty(comSet)
tempNum=1;
tempD=inf;
for m=1:length(comSet)
subSet=comSet;
subSet(subSet==comSet(m))=[];
decNum=sum(2.^(subSet-2))+1;
if tempD>adjM(circlePath(end),comSet(m))+dpSheet(comSet(m),decNum)
tempD=adjM(circlePath(end),comSet(m))+dpSheet(comSet(m),decNum);
tempNum=comSet(m);
end
end
circlePath=[circlePath,tempNum];
comSet(comSet==tempNum)=[];
end
%总长
circle=pS(circlePath)';
startPntPos=find(circle==startPnt);
circle=[circle(startPntPos:end),circle(1:startPntPos)];
dis=sum(adjM((circlePath-1)*A+circlePath([end 1:(end-1)])));
end