基于Hamilton回路算法的最优旅游路线设计问题.doc

题 目 摘要???????????； 第四步，综合考虑安排，建立行程表；计算可得最少的总旅行费用为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小时 山西 祁县乔家大院洛阳龙门石窟 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元的旅游费用，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。 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）表示各城市（景点）之间的交通费用的总和，表示各城市（景点）之间的