基于图论的自驾游路线设计的创新与实践

【摘要】随着人们生活水平的提高，越来越多的家庭以自驾游的方式旅游.如何设计符合自身要求的路线是首先要考虑的问题.为将旅游线路设计的普适性与个性化结合，设计出一种更加符合自驾游者自身条件的旅游路线，结合图论、运筹学方法建立了旅游路线设计单目标优化模型，并用lingo编程实现.

【关键词】图论；单目标优化；旅游线路；lingo

【基金项目】2015年安徽省大学生创新训练项目：基于图论的自驾游路线的设计与实践（201510380025）.

随着经济的发展，家庭汽车的普及，人们不满足于传统的旅游方式，自驾游出行成为人们出游的重要方式.随之人们需要一个更加符合自身要求的旅游路线.因此，以人本主义为出发点，将旅游线路设计的普适性与个性化结合，设计出一种更加符合自驾游者自身条件的旅游路线，有着极大的市场需求，并且会促进整个旅游业的健康发展.

通过我们的网络调查问卷，对收集到的问卷进行分析，结果表明自驾游爱好者主要是大学生及上班的工作人员，自驾游出行时间主要集中在假期，影响自驾游出行路线的主要因素有时间（自驾游车程所耗费的时间）、费用（自驾游车程所耗费的费用）、路程、到达目的地所转折的道路节点数等.现选取6个旅游景点作为自驾游的目的地进行相关的线路优化设计.

一、模型假设

1.在自驾过程中汽车平均以60 km/h的速度行驶，行程中无其他意外突发事件，以最短路径作为行车路线.

2.每天的自驾时间和旅游时间为10小时，然后就找住宿的地方休息.

3.汽车在自驾过程中耗油为0.5元/km.（包括过桥、过路费用）.

4.旅游外出时间主要是自驾时间和旅游景点游玩时间，其他时间不计入.

5.每个景点的游玩费用固定不变，景点每天都按时间正常开放.

6.自驾游爱好者在景点的食宿费用为每个景点所在地一户人家一天的平均消费费用.

二、模型的建立与求解

把游客要游览的每个景点看作图中的一个节点，各景点之间的距离、时间、费用看作图中对应边上的权，各景点的线路网就转化成一个加权无向图G.自驾游爱好者从某一节点出发，游遍图中的每一个节点有且H有一次，最终回到出发点使得总时间、总费用或总路程最优的自驾游路线，即旅行售货员问题，旅行售货员问题是一个完全NP问题[1].对于单目标优化问题，问题可行解的优劣可以通过比较解的大小来判断优劣，从而得出问题的最优解[2].我们将以芜湖为出发地，其他地点作为自驾游的目的地.其中，将游览景点的节点分别记为vi（i=1表示在出发地芜湖，i=2，3，…，6分别代表游览景点黄山、杭州、舟山、扬州、南京），通过经纬度换算等方式计算给出以下相关的数据，分别建立了以路程最短和费用最少为目标函数的路线模型.

（一）以距离最优的自驾游线路设计求解

在自驾游中，有部分旅游者旅游偏好是更想走最近的路.不考虑其他因素，距离最优设计方法为[3]：目标函数：min=∑6i=1∑6j=1sijxij.