i 1 j 1 k 1 m 11 11 3
其中， Gijkm 表示从第 i 个城市到 j 个城市选用第 k 的第 m 个班次的交通费用。 根据实际情况，我们将城际交通工具分为三类，分别是飞机、火车（包括高 铁和动车） 、长途汽车。不同的交通方式也对应着不同的时刻表、行程时间和所 需的交通费用。 由上表达式可以看出 m 的值，直接决定了被约束变量 x 的大小，而 x 的大小 又与计算量密切相关。对于不同的 i，j，k，通常对应不同的 m。 而在实际的编 程中矩阵的格式的要求，不同的 i，j，k 必须对应大小相当的 m。为了减少计算 时间，我应当尽量使 m 小。方法就是，对于班次较多的情况，我们做人工剔除， 提出那些费用和时间相近的班次，使 m 大大减小，减少计算时间。 （2）城内交通费： M 2 N i
第 4 页 共 23 页
根据题中所给的条件，将旅游费用分为五类，分别是城际交通费、城内交通 费、住宿费、门票费和餐饮费。其中，城际交通费是指在不同城市之间进行旅行 产生的交通费用之和；城内交通费是指在城内往返火车站、汽车站或机场与旅游 景点时产生的费用之和。 （1）城际交通费： M 1 xijkm .Gijkm
三、符号与说明
i, j
xijkm
第 i 个城市或者第 j 城市的编号 从第 i 个城市到 j 个城市是否选用第 k 的第 m 个班次，为 0-1 变量 表示从第 i 个城市到 j 个城市选用第 k 的第 m 个班次的交通费用
表示到达第 i 个城市的时刻 表示离开第 i 个城市的时刻 表示在第 i 个城市的景点门票费用
第 5 页 共 23 页
8 ti1 ti 2 ，那么根据题意知无需住宿的条件是离开该地的时间在当天 8 ti1 ti 2
和次日 2 点之间；为当 Tai 8 ti1 时，即达到景点的时间必须在 Tai ti1 以后，则 离开城市的最早的时刻为 8 2ti1 ti 2 ，那么根据题意知无需住宿的条件是离开该 地的时间在当天 8 2ti1 ti 2 和次日 2 点之间。所以我们建立以下关系式： 条件 1： Tai [1,18 ti1 ti 2 ] 条件 2： Tdi 1 2 3 其中， 1 为当 Tai 8 ti1 时，由 8 ti1 ti 2 Tdi 24 得出 Tdi 的区间范围；
第 3 页 共 23 页
T
j 1 k 1 m
11
3
d 1 jkm
.xijkm 8 这一条件要求我们只需查找从徐州八点以后出发的交通方
式对应的班次。以下五个问题不在重复这一条件 2.当班次很多时， 为了简化计算量我们去掉了从早上六点到中午十二点的班 次让其尽量在晚上出行，另外将时间相近的车次省略。 3.如果两个城市间没有合适的火车直达， 我们通过上网寻找出分时段的依靠 中间站转车到达的三至五条最佳路径代替。 经过上述简化之后，我们可以通过 Lingo 解出结果，并根据结果建立陆相应 游线路时刻表。
i 2 11
其中， N i 表示在第 i 城市内，去景点游玩时往返所需的交通费用。 根据实际情况，我们将城内的交通方式分为公交（包括地铁）和出租车。同 样，不同的交通方式也对应着不同的行程时间和所需的交通费用。 （3）住宿费： M 3 Si hi
i 2 11
其中， S i 表示在第 i 个城市是否需要住宿，需要则 S i 为 1，不需要则 S i 为 0；
j 1 k 1 m i j
11
3
ijkm
1
i 1,2,,11
但是，仅以上约束小件不能避免再一次遍历中产生多余一个互不连通的回 路，为此我们引入额外变量 ui （ i 1,2,,11 ） ，附加以下充分约束条件：
ui u j 11 xijkm 10
k 1 m
3
1 i j 11
1，若选用从第i个城市到第j个城市第k种交通方式的第m个班次 xijkm 0，若未选用从第i个城市到第j个城市第k种交通方式的第m个班次
考虑到每个城市前只有一个城市，则
x
i 1 k 1 m i j
11
3
ijkm
1
j 1,2, ,11
考虑到每个城市后只有一个城市，则
x
第 1 页 共 23 页源自(2) 如果旅游费用不限，游客将十个景点全游览完，至少需要多少时间？请建立 相关数学模型并设计旅游行程表。 (3) 如果这位游客准备 2000 元旅游费用，想尽可能多游览景点，请建立相关数 学模型并设计旅游行程表。 (4) 如果这位游客只有 5 天的时间，想尽可能多游览景点，请建立相关数学模型 并设计旅游行程表。 (5) 如果这位游客只有 5 天的时间和 2000 元的旅游费用，想尽可能多游览景点， 请建立相关数学模型并设计旅游行程表。
二、问题的假设
1) 晚上 20：00 至次日早晨 7：00 之间，如果在某地停留超过 6 小时，必须住 宿； 2) 假设景点的开放时间为 8:00 至 18:00； 3) 假设不考虑买票困难，即随时都能买到符合规定的票； 4) 不考虑出游、交通时的意外状况； 5) 假设交通工具的班次固定不变； 6) 假设网上的宾馆住宿费用，门票费用，车费确实可信，且不因五一黄金周到 来而改变； 7）忽略因自然原因及人为原因造成的交通堵塞，航班取消等可能。
hi 表示在在第 i 个城市的住宿费用。
① S i 的求解： 根据题中所给条件，在第 i 个城市是否需要住宿的充分必要条件是晚上 20： 00 至次日早晨 7：00 之间，如果在第 i 个城市停留超过 6 小时。当 Tai 8 ti1 时， 即景点未开门前已可以到达景点，则游览完后，离开该城市最早的时刻为
问题： 根据以上要求，针对如下的几种情况，为该旅游爱好者设计详细的行程表，该行 程表应包括具体的交通信息(车次、航班号、起止时间、票价等)、宾馆地点和名 称，门票费用，在景点的停留时间等信息。 (1) 如果时间不限，游客将十个景点全游览完，至少需要多少旅游费用？请建立 相关数学模型并设计旅游行程表。
五、模型的建立与求解
5.1 问题一：时间不限，费用最少
5.1.1 模型的概述 在实际情况中，对于处于在经济水平不算很高的群体来说，比如学生，往往 他们能投入的旅游资金较少，而时间确可以很充裕。问题一要求在时间不限的前 提下，找出旅游完所有景点花费最少费用的旅游线路。所以从徐州旅游完 10 个 城市回到徐州花费最少即为所求的目标函数。 根据题中所给的约束条件我们建立 了约束条件方程组，利用 Lingo 软件求解即可得出该目标函数下的最优解。 5.1.2 模型的建立 设 0-1 矩阵 x 表示经过的各城市之间的线路，则
7.948 天游览完所有旅游景点的行程安排。
问题三要求在有限费用下尽可能多的游览景点，相较于前两问，此处旅游景 点的选择也成为模型的决策变量。如何合理地反映这一因素是第三问的难点。通 过重新修改了 TSP 模型中的入度和出度条件，在问题一的基础上建立了关于旅 游景点数目最多的整数规划模型， 求解得到了实际旅游景点数目为 7 个的旅游方 案，并在文中给出了具体行程安排。 问题四是在问题三的基础上将旅费约束换为时间约束。类似问题三，以游览 景点数目最多为目标，建立了规划模型，并同样得出旅游景点数目为 7 个的旅游 方案，并在文中给出了具体行程安排。 对于问题五，以问题三和问题四为基础，加入两个约束条件即旅费约束和时 间约束，最终得到了实际游览景点数目为 5，旅游总花费 1432.5 元，历时 5 天的 结果，并在论文中给出了具体的日程安排。 该模型可以有效解决旅游线路规划问题。
关键字：旅游规划 线路优化设计 TSP 模型
一、问题的重述
随着人们的生活不断提高，旅游已成为提高人们生活质量的重要活动。江苏 徐州有一位旅游爱好者打算现在的今年的五月一日早上 8 点之后出发， 到全国一 些著名景点旅游，最后回到徐州。由于跟团旅游会受到若干限制，他(她)打算自 己作为背包客出游。他预选了十个省市旅游景点，如表 1 所示。 表 1. 预选的十个省市旅游景点 省市 江苏 山东 北京 山西 河南 安徽 湖北 陕西 江西 浙江 假设： (A) 城际交通出行可以乘火车(含高铁)、长途汽车或飞机（不允许包车或包机） ， 并且车票或机票可预订到。 (B) 市内交通出行可乘公交车(含专线大巴、小巴)、地铁或出租车。 (C) 旅游费用以网上公布为准，具体包括交通费、住宿费、景点门票(第一门票)。 晚上 20：00 至次日早晨 7：00 之间，如果在某地停留超过 6 小时，必须住宿， 住宿费用不超过 200 元/天。吃饭等其它费用 60 元/天。 (D) 假设景点的开放时间为 8:00 至 18:00。 景点名称 常州市恐龙园 青岛市崂山 八达岭长城 祁县乔家大院 洛阳市龙门石窟 黄山市黄山 武汉市黄鹤楼 西安市秦始皇兵马俑 九江市庐山 舟山市普陀山 在景点的最短停留时间 4 小时 6 小时 3 小时 3 小时 3 小时 7 小时 2 小时 2 小时 7 小时 6 小时
旅游线路的优化设计 摘要
旅游一向被认为是提高人们生活质量的重要活动， 如何针对旅行者的不同要 求或者偏好，从而设计一条合理的旅游线路，已经成为旅游爱好者及旅游公司的 关注热点。本文通过分析旅游行程安排与旅游用时及所需费用间的动态影响，以 整个旅游日程安排系统为研究对象，通过 Lingo 求解获得可信结果。 问题一要求找出旅游 10 个景点在所给出的约束条件下所需的最少费用的旅 游线路。对此，在传统 TSP 基础上，根据实际情况，把费用分为城际交通费、 城内交通费、住宿费、门票费和餐饮费，确立相应的约束条件和目标函数，最终 得到了最小费用为 2949.5 元的行程安排。 问题二实质上是在问题一的基础上将旅游费用约束改为对时间的约束。 文中 以旅游用时最短为优化目标，在重新建立与时间无关的约束条件，最终得到了
Gijkm
Tai Tdi
Ji
其他符号在问内均有详细说明在此不再一一列出。
第 2 页 共 23 页