数学建模竞赛论文-基于hamilton回路算法的最优旅游路线设计问题 16页

题目基于Hamilton回路算法的最优旅游路线设计问题摘要本文围绕五一黄金周的旅游问题进行了定量评估，对无时限的旅游费用问题、无费用限制的旅游时间问题、有费用限制的旅游质量问题、有时限的旅游质量问题、既有时限又有费用限制的旅游质量问题分别建立了数学模型并设计了旅游行程表，对求解结果进行了分析。问题一放开了对时间的限制，要求设计一条用尽可能少的费用游览十个景点的旅游线路。首先，我们对预选的旅游景点之间消耗的费用和时间进行了分析。由于约束条件只要求费用最低，因此我们从火车和长途汽车班次中选取费用最低的并记录下来建立了最优通行费表。第二步，根据Hamilton回路算法的有关方法，以费用为参考量，我们建立了一个适用于本问题最优规划模型。第三步，用C语言编写模型的指令，运行后得到最优旅游路线：ààààààààààà；第四步，综合考虑安排，建立行程表；计算可得最少的总旅行费用为3101元。问题二在不限制费用的条件下，要求用最短的时间游览完十个景点。其原理与问题一非常相似，故可用问题一的数学模型及方法，改用景点之间消耗的时间作为参考量，最终得到行程表且知最优旅游路线：ààààààààààà；最短的旅行总时间8天22小时23分。问题三要求我们在只有2000元旅游费用的条件下游览尽可能多的城市。因此我们引入0—1变量表示是否游览某个景点，从而推出交通费用和景点花费的函数表达式，给出相应的约束条件。这样寻找不同景点数时的最优旅游路线，并计算其总费用。则最优旅游路线的总花费为1795元，游览了7个景点，是不超过2000元的最大值，据此构建行程表。问题四中我们要在5天的时间内游览最多的景点并回到徐州。其实质是把问题三中的费用约束条件变成了时间约束，故在此我们依然可用问题三中的模型进行求解，得到最多可游览6个景点，耗时4天13小时（106小时），据此建立行程表。问题五可看做是问题三、四的合并，其中费用和时间都是约束条件。因此我们综合问题三、四中的算法，运用问题三中的模型对其进行全面分析，得到最多可游览6个景点，并建立行程表。关键词：Hamilton回路算法C语言最优旅游路线0—1模型 1.问题重述随着人们的生活不断提高，旅游已成为提高人们生活质量的重要活动。江苏徐州有一位旅游爱好者打算现在的今年的五月一日早上8点之后出发，到全国一些著名景点旅游，最后回到徐州。由于跟团旅游会受到若干限制，他(她)打算自己作为背包客出游。他预选了十个省市旅游景点，如表1所示。表1.预选的十个省市旅游景点省市景点名称在景点的最短停留时间江苏常州市恐龙园4小时山东青岛市崂山6小时北京八达岭长城3小时山西祁县乔家大院3小时河南洛阳市龙门石窟3小时安徽黄山市黄山7小时湖北武汉市黄鹤楼2小时陕西西安市秦始皇兵马俑2小时江西九江市庐山7小时浙江舟山市普陀山6小时假设：(A)城际交通出行可以乘火车(含高铁)、长途汽车或飞机（不允许包车或包机），并且车票或机票可预订到。(B)市内交通出行可乘公交车(含专线大巴、小巴)、地铁或出租车。(C)旅游费用以网上公布为准，具体包括交通费、住宿费、景点门票(第一门票)。晚上20：00至次日早晨7：00之间，如果在某地停留超过6小时，必须住宿，住宿费用不超过200元/天。吃饭等其它费用60元/天。(D)假设景点的开放时间为8:00至18:00。问题：根据以上要求，针对如下的几种情况，为该旅游爱好者设计详细的行程表，该行程表应包括具体的交通信息(车次、航班号、起止时间、票价等)、宾馆地点和名称，门票费用，在景点的停留时间等信息。(1)如果时间不限，游客将十个景点全游览完，至少需要多少旅游费用？请建立相关数学模型并设计旅游行程表。(2)如果旅游费用不限，游客将十个景点全游览完，至少需要多少时间？请建立相关数学模型并设计旅游行程表。(3)如果这位游客准备2000元旅游费用，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。(4)如果这位游客只有5天的时间，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。(5)如果这位游客只有5天的时间和2000元的旅游费用，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。15 2.模型的假设与符号说明2.1模型的假设五一黄金周正值旅游旺季，各地旅游景点吸引了大批游客前往观光。考虑到该游客的旅游路线跨越区域较大，交通情况尚存在一些不确定因素。为了研究方便，我们给出以下假设：（1）城际交通出行可以乘火车(含高铁)、长途汽车或飞机（不允许包车或包机），并且车票或机票可预订到；（2）市内交通出行可乘公交车(含专线大巴、小巴)、地铁或出租车；（3）旅游费用以网上公布为准，具体包括交通费、住宿费、景点门票(第一门票)，晚上20：00至次日早晨7：00之间，如果在某地停留超过6小时，必须住宿，住宿费用不超过200元/天。吃饭等其它费用60元/天；（4）假设景点的开放时间为8:00至18:00；（5）假设火车、汽车和飞机均正点到达，行程中无事故、无阻碍；（6）假设由火车换乘汽车或者汽车换乘火车的时间很短，忽略不计；（7）假设旅游过程中天气条件良好，不影响行程；（8）由于考虑到在城市内有时需坐公交（大巴）有时需坐出租车，经过近似计算，取每个城市内交通费用为10元。2.2模型的符号说明（1）i,j表示第i个城市（景点）或第j个城市（景点），i，j=0,1,2·······10，分别表示徐州、常州、青岛、北京、祁县、洛阳、黄山、武汉、西安、九江、舟山；（2）表示计划行程中的总费用；（3）表示各城市（景点）之间的交通费用的总和，表示各城市（景点）之间的交通费用；（4）表示第i个城市（景点）内的交通费用；（5）表示第i个城市（景点）内的食宿费用；（6）表示第i个城市的景点门票费用。2.2模型的符号说明（1）i,j表示第i个城市（景点）或第j个城市（景点），i，j=0,1,2·······10；（2）表示计划行程中的总费用；（3）表示各城市（景点）之间的交通费用的总和，表示各城市（景点）之间的交通费用；（4）表示在景点所在城市的总花费，其中包括表示第i个城市（景点）内的交通费用，表示第i个城市（景点）内的食宿费用，表示第i个城市的景点门票费用，表示第i个城市（景点）内的总费用，故；（5）表示在第i个城市（景点）的逗留时间，表示从第i个景点到第j个景点路途中所需时间，T表示本次旅游的总时间；（6）3.问题的分析15 3.1问题背景的分析根据对题目的理解我们知道，旅游时的总费用包括交通费用、住宿费用和在景点旅游时的费用，在研究确定旅游路线和选用的交通工具后，我们的目标就是在所有的约束条件情况下，求出所求目标的最优解。3.2对问题一和问题二的分析问题一要求我们在不限定时间的情况下，游览完十个景点，并设计出花费最少的旅游路线，故要尽量选择便宜的交通工具。这里我们的做法是以任意两景点间的交通费用为权值，构建一个完备图；然后利用Hamilton回路算法[1]计算出近似最佳旅游路线，进而得出最佳方案。问题二实质上是在问题一的基础上改变了约束条件，在不限资金的条件下尽快结束十个景点的旅程。故可用与问题一类似的方法，且应尽量乘坐飞机以减少时间。3.3对问题三和问题四的分析经过分析，我们可以知道这两个问题所要实现的目标是，使游客在规定的时间内和规定的花费内游览尽可能多的地方。游览的总费用由两部分组成，分别为交通总费用和在旅游景点的花费。对于问题三，花费在2000元以内且游览的景点尽量多是该问题的目标。因此，我们的做法是在满足相应的约束条件下，先确定游览的景点数，然后利用Hamilton回路算法和0--1模型[2]计算出在这种情况下的最小花费，这样最终会得出几种旅游路线。问题四中，花费在2000元以内的条件改为限定时间为最多5天，故可使用与问题三类似的方法求得最优解。3.4对于问题五的分析问题五是对问题三和问题四进一步综合，要求我们用5天的时间和2000元的旅游费用游览尽可能多的景点。故可采用与问题三、四类似的方法，进行综合性的求解。4.模型的准备先给11个旅游城市分别进行编号，徐州、常州、青岛、北京、祁县、洛阳、黄山、武汉、西安、九江、舟山分别编为、、、、、、、、、、，则这11个城市和其交通线路构成了一个网络图。这些城市可看作该网络图的节点，这些节点由相应的交通线路相连，节点之间的边就是交通线路。4.20——1模型4.2.1目标函数的确立：15 游览的总费用由2部分组成，分别为交通总费用和在旅游景点的花费。我们已经定义：——旅游总花费；——交通总费用；——旅游景点的花费；从而得到目标函数：（1）交通总花费因为表示第i个景点到第j个景点所需的交通费用，而是判断游客们是否从第i个景点直接到第j个景点的0——1变量，因此我们可以很容易的得到交通总费用为：（2）旅游景点的花费因为表示游客在i个景点的总消费，也可以表示出是否到达过第i个和第j个景点，而整个旅游路线又是一个环形，因此实际上将所到景点的花费计算了两遍，从而我们可以得到旅游景点的花费为：从而我们可以得到目标函数为：4.2.2约束条件:①时间约束旅游时间应该不超过5天，而这些时间包括在路途中的时间和在旅游景点逗留的时间。因为表示从第i个景点到第j个景点路途中所需时间，所以路途中所需的总时间为；表示在第i个景点的逗留时间，故在旅游景点的总逗留时间为。因此，总的时间约束为：②旅游景点数约束根据假设，整个旅游路线是环形，即最终要回到徐州，因此即表示旅游的景点数，这里我们假定要旅游的景点数为n（n=1，2，3，……，10）。因此旅游景点数约束为：③0——1变量约束[3]我们可以吧所有的景点连成一个圈，而把妹一个景点看做圈上一个点。对于每个景点来说，只允许最多一条边进入，同样只允许最多一条边出来，并且有一条边进入就要15 有一条边出去。因此可得约束：当i=1时，因为徐州是出发点，所以；j=1时，因为最终要回到徐州，所以。综上所述，我们可以得到总的模型为：约束条件：各大景点门票信息[4]景点常州市恐龙园青岛市崂山八达岭长城祁县乔家大院洛阳龙门石窟黄山市黄山武汉市黄鹤楼西安市秦始皇兵马俑九江市庐山舟山市普陀山门票160元65元45元40元120元230元80元90元180元200元5.模型的建立与求解5.1建立无时限的旅游费用Hamilton回路模型根据问题一中的约束条件，由于要求在没有时间限制的条件下旅行，因此为了保证游完十个景点所花费用最少，我们选择了耗资最少的方式旅行：首先在选择交通工具时飞机的费用明显过高，予以排除，从现有火车和汽车方案中选择便宜的进行计算；其次，在景点所在城市尽量减少住宿费和餐饮费。根据此思路，搜集资料得出任意两景点之间的最优通行费用表（见下表），以表内费用值作为Hamilton回路图中各边的权值。最优通行费用表[5]最少旅费（元）徐州常州青岛北京祁县洛阳黄山武汉西安九江舟山（宁波）停留时间15 徐州0347053/3499/55501300小时常州34015078/12573199165173734小时青岛701500116/125182/1651703506小时北京5378116053531822801361453323小时祁县///530///41//3小时洛阳3412512553/0/872862/3小时黄山9973182182//078/681647小时武汉/199/280/87780137513002小时西安551651651364128/1370701942小时九江50173170145/626851700115.57小时舟山（宁波）13073350332//16430019411506小时注：“/”代表耗费时间、金钱明显过多的路线，不考虑在内编写基于Hamilton回路算法的C语言程序，输入上表数据（“/”一律按500输入），运行得出无限时条件下的最优路线方案如下图：故旅游的最优城市顺序为：ààààààààààà进一步规划，综合考虑，得出行程表：行程表时间行程15 5月2日00:10乘1641于8:40到常州（票价34），坐公交车去看恐龙园（门票160），22:30坐K78于5:14到宁波（票价73）5月3日坐大巴到舟山市普陀山（票价32），从8点开始游览10小时（门票200）后乘大巴返回宁波，5月4日1:00坐汽车到九江，12:50乘2534于2:38到九江（票价94）5月5日从火车站坐公交车到长途汽车站，转车上庐山（门票180），游览7小时后返回庐山火车站，18:03乘K799于1:22到赣州（票价76）5月6日19：36乘K45于7:33到黄山（票价130）5月7日坐公交去景区游览7小时（门票230），然后回火车站，19:52乘2026于03:20到合肥（票价49）,10:08换乘D3002于12:28到武汉（票价111），坐公交去看黄鹤楼（门票80），游览2小时后，15:35乘K864于23:44到洛阳（票价87），坐公交车至洛阳金谷园56号的天香宾馆住宿（80）5月8日8:00坐公交至龙门石窟游览10小时(门票120)，22:06乘1296于4:04到西安（票价28）5月9日早上8:00坐公交去看9小时秦始皇兵马俑（门票90），21:16乘2670于7:00到祁县（票价39）5月10日8:00坐公交去乔家大院游览3小时（门票40），13:34乘2604于4:00到北京（票价53）5月11日坐大巴8:00抵达八达岭游览3小时（门票45），22:48乘T25于7:40到青岛（票价116）5月12日8:00坐公交至崂山游览6小时（门票65），19:10乘K70于5:06回到徐州（票价99）城市之间的交通费=34+（73+32*2）+94+（76+130）+（49+111）+87+28+39+53+116+99=1053（元）市内的交通费（元）食宿费(元)景点门票费（元）所以总旅行费用1053+100+740+1210=3101（元）5.2建立无费用限制的旅游时间Hamilton回路模型问题二要求我们不限旅游费用，用最短的时间游完十个景点并回到徐州。分析了此问题的约束条件，我们应建立模型近似得出耗时最少的方案。注意到：飞机、动车和高铁相比其他运输方式耗时少，所以优先考虑；此外还要尽最大可能规划以减少在景点的时间以及住宿时间15 。综合多方面因素，通过各种渠道，我们建立了任意两景点之间的最优耗时表（如下表）：最优耗时表[6]徐州常州青岛北京祁县洛阳黄山武汉西安九江舟山（宁波）停留时间徐州03.3621.5242.662.082.412.412.081.910小时常州3.3602.911.75243.412.663.161.832.832.754小时青岛22.9101.33243.161.832.081.912.52.336小时北京1.51.751.33013.71.7522.0822.331.913小时祁县24242413.7024242410.924243小时洛阳243.413.171.752403.082.832.673.082.673小时黄山2.082.661.832243.0802.422.172.081.927小时武汉2.423.162.082.08242.832.4201.420.582.332小时西安2.421.831.92210.92.672.171.4203.082.922小时九江2.082.832.52.33243.082.080.583.0801.927小时舟山（宁波）1.922.752.331.92242.671.922.332.921.9206小时注：表中注为“24”小时的格子代表耗时明显较多的路线，不予考虑编写基于Hamilton回路算法的C语言程序，输入上表数据，运行得出无费用限制条件下的最优路线方案如下图：故旅游的最优城市顺序为：ààààààààààà进一步规划，综合考虑，得出行程表：行程表时间行程5月1日10:52乘K174于20:23到青岛（票价99），坐出租车至15 崂山区仙霞岭路48号的青岛大公岛酒店住宿5月2日8:00进崂山景区游览6小时（门票65），15：15乘长途卧铺客车于1:15到安庆（票价160）5月3日7:50乘长途客车于10:50到黄山（票价80），进入黄山景区游览7小时（门票230），19:10乘K8420于4:46至常州（票价73）5月4日8:00进常州恐龙园（门票160），游览4小时后，17:45乘T116与7:57至西安（票价165）5月5日8:00观赏秦始皇兵马俑2小时（门票90），10:35乘MU2105航班于12:20至北京（票价530），坐大巴至八达岭游览3小时（门票45），再坐大巴返回机场，21:20乘HU7372航班于22:35至太原（票价470）5月6日5:05乘2463于6:10至祁县（票价7），坐出租车至乔家大院，8:00进景区游览3小时（门票40），12:29乘1096于13:47至太原（票价7），20:36乘1625于2:23至安阳（票价32）5月7日3:15乘K269于7:50至洛阳（票价47），游览龙门石窟3小时（门票120），11:10乘JR1532航班于12:20至太原（票价220），14:40乘MU2363航班于15:40至武汉（票价270），坐出租车至黄鹤楼，游览2小时（门票80），19:07乘D3249于21:11至德安（票价67），21:29乘D6348于21:55至九江（票价17），坐出租车至庐山芦林路11号的庐山太极宾馆住宿5月8日进景区游览7小时（门票180），21:45乘FM9272航班于23:10至上海（票价180），在靠近浦东机场的上海江蓉大酒店住宿5月9日7:25乘FM9423航班于8:15至舟山（票价210），进普陀山游览6小时（门票200），22:30乘FM9432航班于23:15至上海（票价210），5月10日8:15乘FM9297航班于9:15回到徐州（票价180）所以总旅行时间为从徐州出发至回到徐州的时间，即为5．3建立有费用限制的0——1模型旅游质量Hamilton回路模型由于问题三只限制总费用，对时间未作限制，故0——1模型没有限制条件：结合旅游质量Hamilton回路模型计算可得下表：旅游景点数n1234578总花费（元）286539763789105217952148路线0→5→00→5→8→00→4→8→5→00→3→4→8→5→00→2→3→4→8→5→00→1→7→5→8→4→3→2→00→2→3→4→8→5→7→9→1→0由上表可知在限制2000元花费时，最多浏览7个景点。根据已知数据安排行程表15 行程表时间行程5月2日00:10乘1641于8:40到常州（票价34），坐公交车去恐龙园游览4小时（门票160），14：51乘K1512于1:21到武汉5月3日8：00坐公交去看黄鹤楼（门票80），游览2小时后，15:35乘K864于23:44到洛阳（票价87），坐公交车至洛阳金谷园56号的天香宾馆住宿（80）5月4日8:00坐公交至龙门石窟游览10小时(门票120)，22:06乘1296于4:04到西安（票价28）5月5日早上8:00坐公交去看9小时秦始皇兵马俑（门票90），21:16乘2670于7:00到祁县（票价39）5月6日8:00坐公交去乔家大院游览3小时（门票40），13:34乘2604于4:00到北京（票价53）5月7日坐大巴8:00抵达八达岭游览3小时（门票45），22:48乘T25于7:40到青岛（票价116）5月8日8:00坐公交至崂山游览6小时（门票65），19:10乘K70于5:06回到徐州（票价99）5.4建立有时限的旅游质量Hamilton回路模型由于只限制时间而没要求花费，故只将目标函数作为参照，通过结合Hamilton回路模型计算可得下表：旅游景点数n4567时间（小时）8499109128路线0→4→8→5→3→00→3→4→8→7→5→00→8→3→4→5→7→9→00→2→8→3→4→5→7→9→0由上表可知在限制5天（120小时）时，最多浏览6个景点。根据所得数据建立行程表：行程表5月1日12:25乘JD5260航班于13:55至杭州（票价350），17:55乘MU2202航班于20：15至西安（票价400），乘出租车至西安临潼区秦陵北路199号的秦安大酒店住宿5月2日8:00观赏秦始皇兵马俑2小时（门票90），10:35乘MU2105航班于12:20至北京（票价530），坐大巴至八达岭游览3小时（门票45），再坐大巴返回机场，21:20乘HU7372航班于22:35至太原（票价470）5月3日5:05乘2463于6:10至祁县（票价7），坐出租车至乔家大院，8:00进景区游览3小时（门票40），12:29乘1096于13:47至太原（票价7），20:36乘1625于2:23至安阳（票价32）5月4日15 3:15乘K269于7:50至洛阳（票价47），游览龙门石窟3小时（门票120），11:10乘JR1532于12:20至太原（票价220），14:40乘MU2363于15:40至武汉（票价270），坐出租车至黄鹤楼，游览2小时（门票80），19:07乘D3249于21:11至德安（票价67），21:29乘D6348于21:55至九江（票价17），坐出租车至庐山芦林路11号的庐山太极宾馆住宿5月5日进景区游览7小时（门票180），21:45乘FM9272航班于23:10至上海，在靠近浦东机场的上海江蓉大酒店住宿5月6日8:15乘FM9297航班于9:15回到徐州（票价180）5.5建立既有时限又有费限的旅游质量Hamilton回路模型由于规定了费用2000元和时间5天，所以这是一个完整的0——1模型，通过对综合模型和结合Hamilton回路模型的运算，可得下表：旅游景点数n4567总花费（元）876113219882238路线0→8→4→5→3→00→8→4→7→3→5→00→3→8→4→5→7→9→00→2→8→5→4→3→9→7→0根据已知数据，设计行程表：行程表5月2日6:25乘T32于13:57至北京（票价106），坐出租车至八达岭游览3小时（门票45），21:48乘K1363于12:42至西安（票价137）5月3日坐公交去看2小时秦始皇兵马俑（门票90），21:16乘2670于7:00到祁县（票价39）5月4日坐公交车至乔家大院，8:00进景区游览3小时（门票40），12:29乘1096于13:47至太原（票价7），20:36乘1625于2:23至安阳（票价32）5月5日3:15乘K269于7:50至洛阳（票价47），游览龙门石窟3小时（门票120），11:10乘JR1532航班于12:20至太原（票价220），14:40乘MU2363航班于15:40至武汉（票价270），坐出租车至黄鹤楼，游览2小时（门票80），19:07乘D3249于21:11至德安（票价67），21:29乘D6348于21:55至九江（票价17），坐出租车至九江庐山区十里大道280号的富士宾馆住宿（票价70）5月6日8:00进景区游览7小时（门票180），于15:51乘K1122于20:57至潢川（票价54），21:44乘2614于4:23回到徐州（票价25）共计4天零21小时58分，花费1988元。6.模型的结果分析问题一：推荐最优旅游路线：ààààààààààà旅游总费用：3101元15 问题二：推荐最优旅游路线：ààààààààààà旅游总耗时：8天22小时23分问题三：推荐最优旅游路线：àààààààà旅游景点数：7旅游总费用：1795元问题四：推荐最优旅游路线：ààààààà旅游景点数:6旅游总耗时：4天13小时（109小时）问题五：推荐最优旅游路线：ààààààà旅游景点数：6旅游总费用：1988元旅游总耗时：4天22小时（118小时）本文通过建立基于Hamilton回路算法的旅游路线模型和引入0—1模型进行规划，在五种不同的约束条件下为游客设计了不同的近似最优旅行路线。由于用了0—1模型进行简化，建模和编程得以顺利完成；经后期检验，所得结果能满足题目的要求，最大程度减少了时间或资金的消耗，具有较好的实际意义。但由于数据量过于庞大，模型中为了方便研究又有一些假设，所以所得结果只是近似最优解。7.模型的评价本文根据游客的旅行路线进行了合理假设，简化了次要因素，把问题转化为图论上最佳旅行商回路问题解决，思路比较清晰，模型恰当，得出的方案相对合理,使问题得到了比较合理的解决；成功的使用了0——1变量，使模型的建立和求解得以顺利进行。但是，由于数据庞大，对程序的要求很高，尽管经过了检验，但结果依然比较粗糙，有待进一步的改进。实际情况中，两景点之间的交通方式比较复杂，如公路、铁路、航班之间可以转换，增加这些考虑后，结果会更加合理。且数据资料搜集的不完整，有一定的局限性，准确性也有待商榷，而且没有对最终方案进行更为细致的研究讨论，这些方面还有待改进。参考文献[1]卢开澄，卢华明编著，图论及其应用，北京：清华大学出版社，1996。[2]刘来福，增文艺，数学模型与数学建模，北京师范大学出版社，1998。[3]刁在筠，郑汉鼎，运筹学，北京：高等教育出版社，2006.7。[4]列车时刻表，http://zhidao.baidu.com/,2011年5月1日。[5]长途客运站信息，http://www.piaojia.cn/changtuzhan/,2010年5月1日。[6]航班信息查询，http://www.17u.cn/,2011年5月2日。附：Hamilton回路模型的C语言程序#include#include15 #include#includeusingnamespacestd;#defineN11intcurLightestWeight=1000000;intcurDepth=0;intcurWeight=0;intdepth;intcurCircle[N],bestCircle[N];boolused[N];floatp[N][N];voidupdate();voidshow();voidgenGraphic(intmaxWeight){inti;for(i=0;i=curLightestWeight){curDepth--;used[curVertex]=false;return;}elseif(curDepth==depth){intthisWeight=p[curVertex][0];curWeight+=thisWeight;if(curWeight";cout<