旅游线路的优化设计1.doc 29页

HYPERLINK "/" 问题重述 随着人们的生活不断提高，旅游已成为提高人们生活质量的重要活动。江苏徐州有一位旅游爱好者打算在今年的五月一日早上8点之后出发，到全国一些著名景点旅游，最后回到徐州。由于跟团旅游会受到若干限制，他(她)打算自己作为背包客出游。他预选了十个省市旅游景点，如附表1（见附录I）所示。 假设 (A)城际交通出行可以乘火车(含高铁)、长途汽车或飞机（不允许包车或包机），并且车票或机票可预订到。 (B)市内交通出行可乘公交车(含专线大巴、小巴)、地铁或出租车。 (C)旅游费用以网上公布为准，具体包括交通费、住宿费、景点门票(第一门票)。晚上20：00至次日早晨7：00之间，如果在某地停留超过6小时，必须住宿，住宿费用不超过200元/天。吃饭等其它费用60元/天。 (D)假设景点的开放时间为8:00至18:00。 问题： 根据以上要求，针对如下的几种情况，为该旅游爱好者设计详细的行程表，该行程表应包括具体的交通信息(车次、航班号、起止时间、票价等)、宾馆地点和名称，门票费用，在景点的停留时间等信息。 (1) 如果时间不限，游客将十个景点全游览完，至少需要多少旅游费用？请建立相关数学模型并设计旅游行程表。 (2) 如果旅游费用不限，游客将十个景点全游览完，至少需要多少时间？请建立相关数学模型并设计旅游行程表。 (3) 如果这位游客准备2000元旅游费用，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。 (4) 如果这位游客只有5天的时间，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。 (5) 如果这位游客只有5天的时间和2000元的旅游费用，想尽可能多游览景点，请建立相关数学模型并设计旅游行程表。 问题假设 1、忽略乘坐出租车时经过收费路段所交的费用； 2、在每个城市中停留时，难免会遇到等车、堵车等延时情况，在此问题中我们不做考虑； 3、所有旅馆都未客满，并且忽略从旅馆到火车站或景点的时间； 4、列车车次和飞机航班没有晚点等情况发生； 5、列车和飞机的票足够，没有买不到票的情况发生； 6、景点的开放，列车和航班的运营不受天气的影响； 7、绘图时，经线和纬线近似平行分布； 8、将城市和路径的关系转化为图论问题； 9、在时间的认识上，我们把当天的8点至次日的8点作为一天。 符号说明 有向图矩阵 城市 路径 要经过的城市总数 任意两城市之间的距离 是否经过两座城市 路径上的信息量 启发函数 信息启发式因子 期望启发式因子 蚂蚁在时刻由城市转向城市的转移概率 第只蚂蚁的禁忌搜索表 信息素挥发系数 时刻蚂蚁在路径上留下的信息素量 到目前为止所找到的全局最短路径长度 蚂蚁携带的信息素量 本次循环中第只蚂蚁所走的路程长度 蚂蚁的总数量 蚂蚁的编号 所记录的循环次数 最大循环次数 问题分析 4.1问题一的分析 针对问题一，要求求出将旅游景点全游览完，所需的最少旅游费用。这和问题,即旅行商问题有些类似，所以本文将问题向问题进行一定的转化，从而进行求解。 因为运用传统的动态规划解法，解法的空间复杂性和时间复杂性都十分庞大，不利于求解，所以采用蚁群算法，通过计算机软件进行编程得到路程最短的旅行路线。 因题目要求时间不限，用最少的旅游费用游览全部景点，而考虑到不同交通工具的速度和票价都不相同，各个旅馆的住宿费用也不相同，所以我们对其行程进行详细的安排，尽量减少其在交通和住宿上的费用，减少不必要的花费。 最后得出一个最少旅游费用的旅游行程表。 4.2问题二的分析 针对问题二，要求求出将旅游景点全游览完，所需的最少时间。因为考虑到交通工具的不同导致时间上的差异问题，所以仅用问题一的模型不能求解。但是由于任意两座城市之间都能相连接起来，且每座城市只经过一次，所以将任意两座城市之间的路程转变为时间，建立最优化模型，通过计算机软件进行编程，到时间最短的旅游路线。 然后，根据题目要求，再对其行程进行详细的安排，尽量避免不必要的时间。 最后得出一个最短时间的旅游行程表。 4.3问题三的分析 针对问题三，题目给出了限制条件，旅游费用不超过2000元。只用2000元游览完全部景点是不可能的，所以我们对其行程进行优化。 首先，将问题一的旅游行程根据旅游景点和交通路线划分成21个部分（包括10个景点和11条交通线路），并计算出每一个部分所要花费的旅游费用。 然后，对旅游行程进行优化计算，为了简化运算，我们假设交通线路上花费的费用只是简单相加。通过除去旅游景点计算出2000元以下的费用最优解。 最后得出一个2000元以下的旅游行程表。 4.4问题四的分析 针对问题四，题目也给出了限制条件，旅游时间不超过5天。只用5天游览完全部景点是不可能的，所以我们对其行程进行优化。解法与问题三大致相同。 首先，对问题二的旅游行程也根据旅游景点和交