论文部分内容阅读
摘要：基于0-1规划模型设定目标函数与约束条件，并通过LINGO软件求解，给出了游览潘安湖7个景点，每个景点至少游览一次的最短路径安排。景点在有游览时间和开放时间的限制下，通过增加约束条件，给出了三个旅游团景点游览最大时长的路线安排。
关键词：0-1规划 旅游团 最短路
一、引言
随着中国经济的快速发展，旅游产业在以更迅猛的速度前进。当下越来越多的人选择空闲的时间去旅游，而报团旅游成为多数人的一个选择。对于旅游团组织者来说设计一个合理的旅游线路，使旅游者能够以最短的时间获得最大的观赏效果尤为重要。笔者以徐州潘安湖风景区为例，以最短路模型设计最优的旅游线路。
潘安湖景区有游客服务中心、阳光草坪等7个景点，景点之间最短步行距离如表1所示。现有两个问题：问题1游客从V0景石出发，步行游览V1游客服务中心，V2阳光草坪，V3森林小剧场，V4儿童科普体验区，V5儿童戏水场，V6湿地博物馆，V7湿地商业街，找出一条以V0景石为起点，以V7湿地商业街为终点的最短路线，并且要求V1-V7每个景点至少经过一次;问题2现在有三个旅游团同时到潘安湖景区旅游，V1-V6每个景点在同一时间只能接待一个旅游团，即在某一景点后到的旅游团需等前面的旅游团游览完才能游览，三个旅游团步行的速度是一定的，同时V3森林小剧场，只有整点或半点才能开放，若三个旅游团第一个参观的景点为V3则必然有等待时间，旅游团在每个景点的游览时间在一定时间范围内可调节，为使在景点的游览时间最长，给出三个旅游团的浏览路线。
二、问题分析
对于问题1，已知任意两个景点之间的最短步行距离，寻找从景石到湿地商业街的最短路线，且中间要经过V1-V6至少一次，景点游览的顺序不同，路线的长短也会不同。此问题看似和最短路问题相似，但不是最短路问题，最短路问题是求起点到终点的最短路，给出的中间点可以不全部通过，但此问题设定的是V1-V6至少要通过一次，所有的点通过一次，这类问题又和哈密尔顿圈问题相似，但哈密尔顿圈问题是经过所有的点最终要回到原点，这里我们所有的点不回到原点。因此，我们需要对哈密尔顿圈问题进行适当的改进以此来解决此问题。这里采用0-1规划模型[1-2]，以所有的点连接距离最短为目标函数，添加相应的等式作为约束条件，用LINGO软件求解此问题。
对于问题2，三个旅游团在其中游览，为使三个旅游团在景点总的游览时间达到最长，应该使在景点间走路的时间最短，同时应尽量错开旅游团在同一景点同一时间的游览，以避免等待时间。目标函数依旧为游览所有的景点距离最短，以此来使景点间走路时间最短，同时约束条件应增加限制，错开各旅游团的路线，利用可在某个景点游览时间的长短，错开两个旅游团在同一个景区的等待时间，使游览时间达到最长。
三、模型建立与求解
（一）问题1模型的建立与求解
用表示景点i与景点j之间的距离，引入0—1变量，表示从景点i到景点j的路线在最短路径上，表示该路线不在最短路径上。
则目标函数为：
约束条件（设为①式）：
对于约束条件表示从第1个点即起点出发，只有一条路连接到其他点;对于表示路中间的点只能一条路进，一条路出;对于表示第8个点即终点，只有一条路进入。通过LINGO软件求解，得到0-1变量为1的为，旅游最短路线为V0→V3→V5→V1→V2→V4→V6→V7，最短总步行距离为1820（米）及游览景点间具体距离如表2所示。
（二）问题2模型的建立与求解
若想增大旅游团在景点的游览时间，必须要缩短在景点间的步行时间。游客步行速度是一定的，因此为游客设计最大的景点游览时间线路，就是设计从景石出发到湿地商业街的最短路径。问题1给出了从景石出发到湿地商业街的最短路径，现在有三个旅游团对景点进行游览，并且森林小剧场只有整点或者半点开放。问题1最短旅游路线从景石出发第一个旅游点为森林小剧场，由于森林小剧场是半点或整点开放，若第一个游览点为森林小剧场必然会等待，因此旅行团第一个点不应该经过森林小剧场，为此应增加约束，在①式基础上增加x14=0这个约束，于是第一个旅游团目标函数：
约束条件：
通过LINGO软件求解，可得变量x13，x27，x35，x46，x54，x62，x78为1，所以第一个旅游团的行走线路为V0景石V2阳光草坪V4儿童科普体验区V3森林小剧场V5儿童戏水场V1旅游服务中心V6湿地博物馆V7湿地商业街。
对于第二旅游团来说，第一个游览的点不能为森林小剧场，同時为了不等待第一个旅游团第一个游览的点，因此第二旅游团第一个不能浏览的点也就是阳光草坪，因此约束条件在①式基础上增加约束：x14=0，x13=0。通过LINGO软件求解，可得变量x12，x26，x35，x43，x57，x64，x78为1，在第二个旅游团第一个点不游览森林小剧场和阳光草坪的条件下，最短旅游路线为：V0景石V1旅游服务中心V5儿童戏水馆V3森林小剧场V2阳光草坪V4儿童科普体验区V6湿地博物馆V7湿地商业街。
对于第三个旅游团，和第二个旅游团类似，第一个游览的点不能为森林小剧场，同时也不能为第一个旅游团第一个游览的点与第二个旅游团第一个游览的点，即不能为阳光草坪与旅游服务中心，因此约束条件在①式基础上增加约束：x14=0，x13=0，x12=0。 通过LINGO软件求解，可得变量x16，x27，x43，x52，x64，x78为1，即第三个旅游团的最短旅游路线为：V0景石V5儿童戏水场V3森林小剧场V2阳光草坪V4儿童科普体验区V1游客服务中心V6湿地博物馆V7湿地商业街。
四、结语
旅游团安排路线是一个较为复杂的问题，本文基于0-1规划模型给出将所有的景点都至少经过一次的最短路径，并给出了三个旅游团旅游的时间安排。本模型还可以推广到n个景点的最短路设计，以及m个旅游团的游览安排。此模型利用LINGO软件求解方便准确，以此安排旅游路线，提高了游客的游玩效率，便于旅游团旅行安排。
参考文献：
[1] 谢金星，薛毅.优化建模与LINDO/LINGO软件[M].北京：清华大学出版社，2005.
[2] 韩中庚.数学建模方法及其应用（第二版）[M].北京：高等教育出版社，2009.
基金项目：浙江机电职业技术学院教育教学改革重点培育项目“高职高等数学趣味化教学探究”（编号：A015218314）。
（作者单位：浙江机电职业技术学院）
关键词：0-1规划 旅游团 最短路
一、引言
随着中国经济的快速发展，旅游产业在以更迅猛的速度前进。当下越来越多的人选择空闲的时间去旅游，而报团旅游成为多数人的一个选择。对于旅游团组织者来说设计一个合理的旅游线路，使旅游者能够以最短的时间获得最大的观赏效果尤为重要。笔者以徐州潘安湖风景区为例，以最短路模型设计最优的旅游线路。
潘安湖景区有游客服务中心、阳光草坪等7个景点，景点之间最短步行距离如表1所示。现有两个问题：问题1游客从V0景石出发，步行游览V1游客服务中心，V2阳光草坪，V3森林小剧场，V4儿童科普体验区，V5儿童戏水场，V6湿地博物馆，V7湿地商业街，找出一条以V0景石为起点，以V7湿地商业街为终点的最短路线，并且要求V1-V7每个景点至少经过一次;问题2现在有三个旅游团同时到潘安湖景区旅游，V1-V6每个景点在同一时间只能接待一个旅游团，即在某一景点后到的旅游团需等前面的旅游团游览完才能游览，三个旅游团步行的速度是一定的，同时V3森林小剧场，只有整点或半点才能开放，若三个旅游团第一个参观的景点为V3则必然有等待时间，旅游团在每个景点的游览时间在一定时间范围内可调节，为使在景点的游览时间最长，给出三个旅游团的浏览路线。
二、问题分析
对于问题1，已知任意两个景点之间的最短步行距离，寻找从景石到湿地商业街的最短路线，且中间要经过V1-V6至少一次，景点游览的顺序不同，路线的长短也会不同。此问题看似和最短路问题相似，但不是最短路问题，最短路问题是求起点到终点的最短路，给出的中间点可以不全部通过，但此问题设定的是V1-V6至少要通过一次，所有的点通过一次，这类问题又和哈密尔顿圈问题相似，但哈密尔顿圈问题是经过所有的点最终要回到原点，这里我们所有的点不回到原点。因此，我们需要对哈密尔顿圈问题进行适当的改进以此来解决此问题。这里采用0-1规划模型[1-2]，以所有的点连接距离最短为目标函数，添加相应的等式作为约束条件，用LINGO软件求解此问题。
对于问题2，三个旅游团在其中游览，为使三个旅游团在景点总的游览时间达到最长，应该使在景点间走路的时间最短，同时应尽量错开旅游团在同一景点同一时间的游览，以避免等待时间。目标函数依旧为游览所有的景点距离最短，以此来使景点间走路时间最短，同时约束条件应增加限制，错开各旅游团的路线，利用可在某个景点游览时间的长短，错开两个旅游团在同一个景区的等待时间，使游览时间达到最长。
三、模型建立与求解
（一）问题1模型的建立与求解
用表示景点i与景点j之间的距离，引入0—1变量，表示从景点i到景点j的路线在最短路径上，表示该路线不在最短路径上。
则目标函数为：
约束条件（设为①式）：
对于约束条件表示从第1个点即起点出发，只有一条路连接到其他点;对于表示路中间的点只能一条路进，一条路出;对于表示第8个点即终点，只有一条路进入。通过LINGO软件求解，得到0-1变量为1的为，旅游最短路线为V0→V3→V5→V1→V2→V4→V6→V7，最短总步行距离为1820（米）及游览景点间具体距离如表2所示。
（二）问题2模型的建立与求解
若想增大旅游团在景点的游览时间，必须要缩短在景点间的步行时间。游客步行速度是一定的，因此为游客设计最大的景点游览时间线路，就是设计从景石出发到湿地商业街的最短路径。问题1给出了从景石出发到湿地商业街的最短路径，现在有三个旅游团对景点进行游览，并且森林小剧场只有整点或者半点开放。问题1最短旅游路线从景石出发第一个旅游点为森林小剧场，由于森林小剧场是半点或整点开放，若第一个游览点为森林小剧场必然会等待，因此旅行团第一个点不应该经过森林小剧场，为此应增加约束，在①式基础上增加x14=0这个约束，于是第一个旅游团目标函数：
约束条件：
通过LINGO软件求解，可得变量x13，x27，x35，x46，x54，x62，x78为1，所以第一个旅游团的行走线路为V0景石V2阳光草坪V4儿童科普体验区V3森林小剧场V5儿童戏水场V1旅游服务中心V6湿地博物馆V7湿地商业街。
对于第二旅游团来说，第一个游览的点不能为森林小剧场，同時为了不等待第一个旅游团第一个游览的点，因此第二旅游团第一个不能浏览的点也就是阳光草坪，因此约束条件在①式基础上增加约束：x14=0，x13=0。通过LINGO软件求解，可得变量x12，x26，x35，x43，x57，x64，x78为1，在第二个旅游团第一个点不游览森林小剧场和阳光草坪的条件下，最短旅游路线为：V0景石V1旅游服务中心V5儿童戏水馆V3森林小剧场V2阳光草坪V4儿童科普体验区V6湿地博物馆V7湿地商业街。
对于第三个旅游团，和第二个旅游团类似，第一个游览的点不能为森林小剧场，同时也不能为第一个旅游团第一个游览的点与第二个旅游团第一个游览的点，即不能为阳光草坪与旅游服务中心，因此约束条件在①式基础上增加约束：x14=0，x13=0，x12=0。 通过LINGO软件求解，可得变量x16，x27，x43，x52，x64，x78为1，即第三个旅游团的最短旅游路线为：V0景石V5儿童戏水场V3森林小剧场V2阳光草坪V4儿童科普体验区V1游客服务中心V6湿地博物馆V7湿地商业街。
四、结语
旅游团安排路线是一个较为复杂的问题，本文基于0-1规划模型给出将所有的景点都至少经过一次的最短路径，并给出了三个旅游团旅游的时间安排。本模型还可以推广到n个景点的最短路设计，以及m个旅游团的游览安排。此模型利用LINGO软件求解方便准确，以此安排旅游路线，提高了游客的游玩效率，便于旅游团旅行安排。
参考文献：
[1] 谢金星，薛毅.优化建模与LINDO/LINGO软件[M].北京：清华大学出版社，2005.
[2] 韩中庚.数学建模方法及其应用（第二版）[M].北京：高等教育出版社，2009.
基金项目：浙江机电职业技术学院教育教学改革重点培育项目“高职高等数学趣味化教学探究”（编号：A015218314）。
（作者单位：浙江机电职业技术学院）