论文部分内容阅读
【摘要】本论文利用数学建模的方法，根据游客的喜好推荐最优旅行路线.首先，通过调查游客对于旅行景区不同因素的重视程度和各景点在不同方面的既有评分，用改进层次分析法得到各景区排名，对景区进行初步筛选.其次，运用Dijkstra算法得到所有可选景点之间的最短路程，并使旅程时间和费用多少与旅程长短成正比.最后，根据游客需求分别设定目标函数和限制条件得到基于非线性规划问题的最优旅行路线模型.本文将北京部分景区的数据代入模型进行验证，得到了不同游客需求下的旅行最优路线.
【关键词】最优旅行路线;游客体验;Dijkstra算法;非线性规划
一、引言
随着全球化的到来，人们对于旅行的需求不断增大，旅游半径从居住地周围的城市，逐渐扩大到省、国家乃至世界范围内的景区.然而，旅游服务并没有成熟的旅程规划系统为人们提供便捷的旅行规划条件.因此，本论文希望通过建立数学模型，根据游客的个性化需求从景点库中筛选出适合游客的目的地，并规划最优路线.
截止到目前，有许多学者对旅行路线的相关问题进行研究.有的学者曾将游客旅行效用表示为与出行时间和出行费用有关的函数，原因是发现拥挤度对游客旅行体验有主要影响[1-2];有的学者采用逐步分层、蚁群算法、Floyd算法、“面包屑”拟合等研究方法进行旅行规划[3-5].
本文将主要根据游客的喜好，用改进后的层次分析法对景点进行排序、用Dijkstra算法计算每两个景点之间的最优旅行路线，并计算在旅行整体效果最好的情况下应该以何种顺序前往哪些景点.本文将游客的需求分为三类：一是因假期时间有限对旅游总时间有限制要求的“时间限制型”;二是因财务状况有限对旅游总花费有限制要求的“金额限制型”;三是对两者都有要求的“双重限制型”.论文中针对以上三种情况分别设定了目标函数和限制条件，定义了若干目标函数，每种目标函数与旅行效率和游客满意度成正比、与游客不充足拥有量成反比.只需代入具体的景点，根据以往数据和游客的个人偏好即可计算出游客的具体旅行路线.
二、问题的描述
一个由若干人组成的旅行团在某一确定的区域内旅行，共有n个旅游目的地可供选择（i=1，2，…，n）.此模型的最终结果将用有序数对（a，b）表示从a景点前往b景点.从这些数对中我们也可以分析出人们是否前往某一景点以及访问景点的顺序.
三、改进层次分析法确定目的地优先级
可选的景点数不胜数，但是在同一次旅行中游客能够前往的地点是有限的.因此在开始计算前，我们要根据游客的喜好将所有目的地进行排序.该顺序将作为目的地被考虑的先后顺序.游客对景点的喜好值将决定景点是否可以被纳入考虑的范围，并将被用来衡量游客对于最终的方案的满意度.
我们按照图1所示方式将目标、游客喜好和景点分别填入层次分析法的目标层O、准则层C和方案层P.某一指定方案Pj的最终评分为
Sj=∑mi=1Cij×Aj，j=1，2，…，n
（1）
图1层次分析法用于景点排序的流程图
在该评分系统下，分值高的景点表示倾向于被游客选择.在各景点Sj已知后，按照从大到小的顺序排序，即可得到景点被该（组）游客喜好的排名.当景点过多时，我们为了简化算法，假设游客总旅程天数为D0，由于每天旅行的景点有限，景点过多会极大地影响游客旅行体验，因此不妨假设景点不超过3个，则在筛选时仅保留排名约为3，旅程天数为D0及以前的景点，排名位于3，旅程天数为D0以后的景点不做考虑.
四、Dijkstra算法寻找两点之间最优路径
Dijkstra算法一般用于计算多点之间无向线段的最短路程.以某一节点作为起始点，Dijkstra算法可以得出该点和任意一点间的最短距离[6].
每一条线段上的数值amn为综合考虑费用和时间的结果，赋值计算方法为
amn=fmn×tmn（2）
其中fmn表示每一小段路上的费用，tmn表示每一小段路上的时间.
图2Dijkstra算法示例图
在确定每条线段上的数值后，我们计算最短路径.如图2，假设需计算从故宫出发前往颐和园的最短距离，已知每条路线的距离（在现实中可以是公交线路、地铁线路或者打车线路）.分别计算到每一节节点的值，如果两点之间没有路线则作为 ∞计算，每次固定此时图中的最小值，逐步往前推进，直到确定了最终的值.产生最小值的路径即为所求的最短路徑，终点处的数值为所求距离.按照这种方法，我们可以计算出从故宫到达颐和园的最优路线是（故宫→C→D→颐和园），距离为12[7].该路程上的时间和费用将作为后文中的中转费用Fij和中转时间Tij.
五、旅行问题变量定义
在开始建立模型和得到具体数据前，先定义以下变量.
定义1：决策变量.xij为决策变量，取决于游客是否从一指定地点前往另一指定地点参观.
xij=1，该游客从i点前往j点xij=0，该游客不从i点前往j点
i=1，2，3…，n.j=1，2，3…，n.i≠j.（3）
通常情况下，某次旅行时同一个景点最多只去一次，也就是说，如果该游客前往j点，则在所有的变量xnj中，只有一个会等于1.
定义2：停留时间.下式表示该旅行团体在j处停留的时间.其中α0为游客对该类景点感兴趣的程度，数值越大，游客对该景点该兴趣程度越大.Tmean，j为该地游客的平均停留时间.W0为天气变量，取决于该季度平均的天气适宜指数，数字大表示气候宜人，适合观赏景点;反之则表示气候恶劣，不适合观赏景点.wj为该景区受天气影响的程度，如果天气对于该地点的游览影响较小（如室内展览馆）则该值接近于0. Tj=α0×Tmean，j×（W0wj（4）
定义3：总旅行天数.Ttotal为游览所有景点所需时间，由所有景点之间，即路程上的时间Tij和景区内游览的时间Ti求和得到;tactive为该组游客每天在外游览的时间.
Dtotal=Ttotaltactive=∑ni=1∑nj=1[Xij×（Tij Tj）]tactive
（5）
定义4：总旅行费用.旅行费用分为基础费用和目的地游览费用.其中基础费用即每晚的酒店费用Fhotel乘以住宿天数和每天的食品花销求和得到.目的地游览费用由所有景点之间，即路程上的费用Fij和景区内游览所需费用Fi求和得到
Ftotal=∑ni=1∑nj=1Xij×Fij Fj Fhotel×（Dtotal-1） Ffood×Dtotal
（6）
定义5：景区平均停留时间.Topen为该景区的平均开园时间.由于大部分景區拥有某固定时刻景区内平均人数Pmoment的数据和每日平均客流量Paverage的数据，因此用以上三个数据一起计算出Tmean，j.
Tmean，j=PmomentPaverage×Topen（7）
定义6：旅行效率.定义为景点游览的时间占总时间的比例.通过对于景点顺序的合理规划，可以有效减少在路上的无效时间，提高此旅行效率值Uefficiency.
Uefficiency=TvisitTtotal=∑ni=1∑nj=1Xij×Tj∑ni=1∑nj=1[Xij×（Tij Tj）]
（8）
定义7：游客满意程度.运用层次分析法求得的排名.因为认为游客的满意度与景点数无关，只与游客对前往景点的感兴趣程度有关，所以将各个所选景点排名相加并除以景点个数，得到游客对于不同旅行方案的满意度.
Usatisfaction=1（∑ni=1Si）/（∑ni=1xij
（9）
六、三类非线性规划模型
1.金额限定型
定义F0为游客要求的金额上限
目标函数：
MAXE=Uefficiency×UsatisfactionFtotal
=∑ni=1∑nj=1Xij×Tj∑ni=1∑nj=1[Xij（Tij Tj）]×1∑ni=1Sj/∑ni=1xj∑ni=1∑nj=1Xij（Fij Fj）
（10）
约束条件：
Ftotal≤F0
（11）
2.时间限定型
定义T0为游客要求的时间上限
目标函数：
MAXE=Uefficiency×UsatisfactionDtotal
=∑ni=1∑nj=1Xij×Tj∑ni=1∑nj=1Xij（Tij Tj）]×1（∑ni=1Sj）/（∑ni=1xj∑ni=1∑nj=1[Xij×（Tij Tj）]tactive
（12）
限制条件：
Dtotal≤D0
（13）
3.双重限定型
这种限制条件为前两种的结合，即游客既受到时间上的限制，必须在一定时间内完成旅行，又受到费用上的限制.
目标函数：
MAXE=Uefficiency×UsatisfactionFtotal×Dtotal（14）
限制条件：
Ftotal≤F0，Dtotal≤D0.（15）
七、模型验证与求解
本文带入了北京市景区的数据对模型进行验证.
首先，从北京城区内随机选择较受欢迎的30个目的地[9].游客喜好评分仅作为示例，其中景色、人文、休闲和刺激四项参考了旅评网http：//www.ilvping.com/view/Index/home.html.对于景点的评分，拥挤和交通参考了苹果地图的路线规划（可供选择的公共方式越多该项评分越高）.
不妨设游客的预计游玩时间为3天，根据第三部分固定保留n=3×3=9个项目.得到的前十名景点分别是（23）颐和园、（22）长城、（24）十三陵、（25）香山、（11）798艺术中心、（13）圆明园、（28）鲁迅博物馆、（8）北京三联韬奋书店和（9）五道营胡同.
八、结语
本文通过层次分析法、Dijkstra算法和三类非线性规划建立了选择旅行景点的模型，能够针对游客的不同需求从任意的景点库中筛选出景点并确定前往顺序.
该论文的研究结果可以用于实际生活中的旅行规划，同时使游客、景点、当地政府获利.对于游客，此规划可以有效减少旅行者在设计旅行方案时的烦琐过程，同时拥有更好的旅游体验.对于当地的景点，只要在运转此模型时拥有足够大的景点库，便可以选出许多不为人熟知，却符合游客兴趣的景点，更好地促进旅游业平衡发展.同时，当地政府，将“旅行效率”纳入主要考虑因素之一，可以减少游客路上时间，减缓路面负担，让城市交通运转更加顺利.该方式并不受旅行目的地大小范围的影响，选择的目的地可以大到几个国家之间旅行的范围，也可以小到一个城市内不同景点、餐厅、商场之间的选择，应用范围较广.
【参考文献】
[1]伍雄斌，关宏志，韩艳.多约束下基于游客体验的旅游路线优化模型[J].科学技术与工程，2018，18（13）：8-13.
[2]Lim，Kwan Hui.Recommending and Planning Trip Itineraries for Individual Travellers and Groups of Tourists[J].International Conference on Automated Planning
【关键词】最优旅行路线;游客体验;Dijkstra算法;非线性规划
一、引言
随着全球化的到来，人们对于旅行的需求不断增大，旅游半径从居住地周围的城市，逐渐扩大到省、国家乃至世界范围内的景区.然而，旅游服务并没有成熟的旅程规划系统为人们提供便捷的旅行规划条件.因此，本论文希望通过建立数学模型，根据游客的个性化需求从景点库中筛选出适合游客的目的地，并规划最优路线.
截止到目前，有许多学者对旅行路线的相关问题进行研究.有的学者曾将游客旅行效用表示为与出行时间和出行费用有关的函数，原因是发现拥挤度对游客旅行体验有主要影响[1-2];有的学者采用逐步分层、蚁群算法、Floyd算法、“面包屑”拟合等研究方法进行旅行规划[3-5].
本文将主要根据游客的喜好，用改进后的层次分析法对景点进行排序、用Dijkstra算法计算每两个景点之间的最优旅行路线，并计算在旅行整体效果最好的情况下应该以何种顺序前往哪些景点.本文将游客的需求分为三类：一是因假期时间有限对旅游总时间有限制要求的“时间限制型”;二是因财务状况有限对旅游总花费有限制要求的“金额限制型”;三是对两者都有要求的“双重限制型”.论文中针对以上三种情况分别设定了目标函数和限制条件，定义了若干目标函数，每种目标函数与旅行效率和游客满意度成正比、与游客不充足拥有量成反比.只需代入具体的景点，根据以往数据和游客的个人偏好即可计算出游客的具体旅行路线.
二、问题的描述
一个由若干人组成的旅行团在某一确定的区域内旅行，共有n个旅游目的地可供选择（i=1，2，…，n）.此模型的最终结果将用有序数对（a，b）表示从a景点前往b景点.从这些数对中我们也可以分析出人们是否前往某一景点以及访问景点的顺序.
三、改进层次分析法确定目的地优先级
可选的景点数不胜数，但是在同一次旅行中游客能够前往的地点是有限的.因此在开始计算前，我们要根据游客的喜好将所有目的地进行排序.该顺序将作为目的地被考虑的先后顺序.游客对景点的喜好值将决定景点是否可以被纳入考虑的范围，并将被用来衡量游客对于最终的方案的满意度.
我们按照图1所示方式将目标、游客喜好和景点分别填入层次分析法的目标层O、准则层C和方案层P.某一指定方案Pj的最终评分为
Sj=∑mi=1Cij×Aj，j=1，2，…，n
（1）
图1层次分析法用于景点排序的流程图
在该评分系统下，分值高的景点表示倾向于被游客选择.在各景点Sj已知后，按照从大到小的顺序排序，即可得到景点被该（组）游客喜好的排名.当景点过多时，我们为了简化算法，假设游客总旅程天数为D0，由于每天旅行的景点有限，景点过多会极大地影响游客旅行体验，因此不妨假设景点不超过3个，则在筛选时仅保留排名约为3，旅程天数为D0及以前的景点，排名位于3，旅程天数为D0以后的景点不做考虑.
四、Dijkstra算法寻找两点之间最优路径
Dijkstra算法一般用于计算多点之间无向线段的最短路程.以某一节点作为起始点，Dijkstra算法可以得出该点和任意一点间的最短距离[6].
每一条线段上的数值amn为综合考虑费用和时间的结果，赋值计算方法为
amn=fmn×tmn（2）
其中fmn表示每一小段路上的费用，tmn表示每一小段路上的时间.
图2Dijkstra算法示例图
在确定每条线段上的数值后，我们计算最短路径.如图2，假设需计算从故宫出发前往颐和园的最短距离，已知每条路线的距离（在现实中可以是公交线路、地铁线路或者打车线路）.分别计算到每一节节点的值，如果两点之间没有路线则作为 ∞计算，每次固定此时图中的最小值，逐步往前推进，直到确定了最终的值.产生最小值的路径即为所求的最短路徑，终点处的数值为所求距离.按照这种方法，我们可以计算出从故宫到达颐和园的最优路线是（故宫→C→D→颐和园），距离为12[7].该路程上的时间和费用将作为后文中的中转费用Fij和中转时间Tij.
五、旅行问题变量定义
在开始建立模型和得到具体数据前，先定义以下变量.
定义1：决策变量.xij为决策变量，取决于游客是否从一指定地点前往另一指定地点参观.
xij=1，该游客从i点前往j点xij=0，该游客不从i点前往j点
i=1，2，3…，n.j=1，2，3…，n.i≠j.（3）
通常情况下，某次旅行时同一个景点最多只去一次，也就是说，如果该游客前往j点，则在所有的变量xnj中，只有一个会等于1.
定义2：停留时间.下式表示该旅行团体在j处停留的时间.其中α0为游客对该类景点感兴趣的程度，数值越大，游客对该景点该兴趣程度越大.Tmean，j为该地游客的平均停留时间.W0为天气变量，取决于该季度平均的天气适宜指数，数字大表示气候宜人，适合观赏景点;反之则表示气候恶劣，不适合观赏景点.wj为该景区受天气影响的程度，如果天气对于该地点的游览影响较小（如室内展览馆）则该值接近于0. Tj=α0×Tmean，j×（W0wj（4）
定义3：总旅行天数.Ttotal为游览所有景点所需时间，由所有景点之间，即路程上的时间Tij和景区内游览的时间Ti求和得到;tactive为该组游客每天在外游览的时间.
Dtotal=Ttotaltactive=∑ni=1∑nj=1[Xij×（Tij Tj）]tactive
（5）
定义4：总旅行费用.旅行费用分为基础费用和目的地游览费用.其中基础费用即每晚的酒店费用Fhotel乘以住宿天数和每天的食品花销求和得到.目的地游览费用由所有景点之间，即路程上的费用Fij和景区内游览所需费用Fi求和得到
Ftotal=∑ni=1∑nj=1Xij×Fij Fj Fhotel×（Dtotal-1） Ffood×Dtotal
（6）
定义5：景区平均停留时间.Topen为该景区的平均开园时间.由于大部分景區拥有某固定时刻景区内平均人数Pmoment的数据和每日平均客流量Paverage的数据，因此用以上三个数据一起计算出Tmean，j.
Tmean，j=PmomentPaverage×Topen（7）
定义6：旅行效率.定义为景点游览的时间占总时间的比例.通过对于景点顺序的合理规划，可以有效减少在路上的无效时间，提高此旅行效率值Uefficiency.
Uefficiency=TvisitTtotal=∑ni=1∑nj=1Xij×Tj∑ni=1∑nj=1[Xij×（Tij Tj）]
（8）
定义7：游客满意程度.运用层次分析法求得的排名.因为认为游客的满意度与景点数无关，只与游客对前往景点的感兴趣程度有关，所以将各个所选景点排名相加并除以景点个数，得到游客对于不同旅行方案的满意度.
Usatisfaction=1（∑ni=1Si）/（∑ni=1xij
（9）
六、三类非线性规划模型
1.金额限定型
定义F0为游客要求的金额上限
目标函数：
MAXE=Uefficiency×UsatisfactionFtotal
=∑ni=1∑nj=1Xij×Tj∑ni=1∑nj=1[Xij（Tij Tj）]×1∑ni=1Sj/∑ni=1xj∑ni=1∑nj=1Xij（Fij Fj）
（10）
约束条件：
Ftotal≤F0
（11）
2.时间限定型
定义T0为游客要求的时间上限
目标函数：
MAXE=Uefficiency×UsatisfactionDtotal
=∑ni=1∑nj=1Xij×Tj∑ni=1∑nj=1Xij（Tij Tj）]×1（∑ni=1Sj）/（∑ni=1xj∑ni=1∑nj=1[Xij×（Tij Tj）]tactive
（12）
限制条件：
Dtotal≤D0
（13）
3.双重限定型
这种限制条件为前两种的结合，即游客既受到时间上的限制，必须在一定时间内完成旅行，又受到费用上的限制.
目标函数：
MAXE=Uefficiency×UsatisfactionFtotal×Dtotal（14）
限制条件：
Ftotal≤F0，Dtotal≤D0.（15）
七、模型验证与求解
本文带入了北京市景区的数据对模型进行验证.
首先，从北京城区内随机选择较受欢迎的30个目的地[9].游客喜好评分仅作为示例，其中景色、人文、休闲和刺激四项参考了旅评网http：//www.ilvping.com/view/Index/home.html.对于景点的评分，拥挤和交通参考了苹果地图的路线规划（可供选择的公共方式越多该项评分越高）.
不妨设游客的预计游玩时间为3天，根据第三部分固定保留n=3×3=9个项目.得到的前十名景点分别是（23）颐和园、（22）长城、（24）十三陵、（25）香山、（11）798艺术中心、（13）圆明园、（28）鲁迅博物馆、（8）北京三联韬奋书店和（9）五道营胡同.
八、结语
本文通过层次分析法、Dijkstra算法和三类非线性规划建立了选择旅行景点的模型，能够针对游客的不同需求从任意的景点库中筛选出景点并确定前往顺序.
该论文的研究结果可以用于实际生活中的旅行规划，同时使游客、景点、当地政府获利.对于游客，此规划可以有效减少旅行者在设计旅行方案时的烦琐过程，同时拥有更好的旅游体验.对于当地的景点，只要在运转此模型时拥有足够大的景点库，便可以选出许多不为人熟知，却符合游客兴趣的景点，更好地促进旅游业平衡发展.同时，当地政府，将“旅行效率”纳入主要考虑因素之一，可以减少游客路上时间，减缓路面负担，让城市交通运转更加顺利.该方式并不受旅行目的地大小范围的影响，选择的目的地可以大到几个国家之间旅行的范围，也可以小到一个城市内不同景点、餐厅、商场之间的选择，应用范围较广.
【参考文献】
[1]伍雄斌，关宏志，韩艳.多约束下基于游客体验的旅游路线优化模型[J].科学技术与工程，2018，18（13）：8-13.
[2]Lim，Kwan Hui.Recommending and Planning Trip Itineraries for Individual Travellers and Groups of Tourists[J].International Conference on Automated Planning