图 1 问题一旅游路线设计
图中节点表示旅游景点， 箭头指向表示行进方向。最终得到的城际最少交通费用 为 782 元。 5.1.2 城内费用 在乘坐市内交通时，考虑到某些城市来时车站（机场）与去时车站（机场） 不同，因此会导致往返于景点与车站（机场）的交通费用不同，如下图所示：
车站（机场）A
交通费用①
旅游总费用 Z
城际费用 S
吃饭及其他费用 C
城内费用 s
乘 坐 火 车 费 用
乘 坐 汽 车 费 用
乘 坐 飞 机 费 用
市 内 交 通 费 用
景 点 门 票 费 用
宾 馆 住 宿 费 用
然后建立模型对每一种费用进行优化，从而得到总费用最优。 问题二中，在费用不限的情况下，以旅游总时间最小为优化目标建立模型。 首先分析旅游总时间的组成，如下图所示：
旅游总时间 P 城际时间 T 城内时间 t
乘 坐 火 车 时 间
乘 坐 汽 车 时 间
乘 坐 飞 机 时 间
市 内 交 通 时 间
景 点 游 玩 时 间
然后建立模型对每一种费用进行优化，从而得到总费用最优。 问题三和问题四分别是在问题一和问题二的基础上做了进一步的约束， 而问 题五则是问题三和四的结合。
若构成回路，有 xij 1, x jk 1, xki 1 ，则 ui u j 1， u j uk 1 ， uk ui 1 ， 从而有 0 3 ，导致矛盾。其它情况依此类推。 于是我们可以得到如下的模型：
min Z
i , j 1
S
n
ij ij
x
n xij 1, j 1,..., n 1 ii j n xij 1, i 1,..., n j 1 s.t. j i ui u j nxij n 1, 1 i j n ，i, j 1,..., n xij 0或1 ui为实数，i 1,..., n
二、 模型假设 1、城际交通出行可以乘火车(含高铁)、长途汽车或飞机（不允许包车或包机） ， 并且车票或机票可预订到。 2、市内交通出行可乘公交车(含专线大巴、小巴)、地铁或出租车。 3、旅游费用以网上公布为准，具体包括交通费、住宿费、景点门票(第一门票)。 晚上 20：00 至次日早晨 7：00 之间，如果在某地停留超过 6 小时，必须住宿， 住宿费用不超过 200 元/天。吃饭等其它费用 60 元/天。 4、假设景点的开放时间为 8:00 至 18:00。 5、不考虑堵车、晚点等交通问题带来的影响； 6、不考虑更换交通方式时所用时间； 7、假设所查到的宾馆在当晚均可以住宿，不考虑客满等情况。
ui u j nxij n 1， 1 i j n
该约束的解释为：① i 与 j 不会构成回路，若构成回路有 xij 1, x ji 1 ，则
ui u j 1， u j ui 1，从而有 0 2 ，导致矛盾；② i ， j 与 k 不会构成回路，
关键词：巡回旅行商问题（TSP） ；人工修正；LINGO；旅游线路优化；
一、 问题重述 随着人们的生活不断提高，旅游已成为提高人们生活质量的重要活动。江苏 徐州有一位旅游爱好者打算现在的今年的五月一日早上 8 点之后出发， 到全国一 些著名景点旅游，最后回到徐州。由于跟团旅游会受到若干限制，他(她)打算自 己作为背包客出游。他预选了十个省市旅游景点，如表 1 所示。 表 1. 预选的十个省市旅游景点 省市 景点名称 在景点的最短停留时间 江苏 常州市恐龙园 4 小时 山东 青岛市崂山 6 小时 北京 八达岭长城 3 小时 山西 祁县乔家大院 3 小时 河南 洛阳市龙门石窟 3 小时 安徽 黄山市黄山 7 小时 湖北 武汉市黄鹤楼 2 小时 陕西 西安市秦始皇兵马俑 2 小时 江西 九江市庐山 7 小时 浙江 舟山市普陀山 6 小时 问题： 根据以上要求，针对如下的几种情况，为该旅游爱好者设计详细的行程表，该行 程表应包括具体的交通信息(车次、航班号、起止时间、票价等)、宾馆地点和名 称，门票费用，在景点的停留时间等信息。 (1) 如果时间不限，游客将十个景点全游览完，至少需要多少旅游费用？请建立 相关数学模型并设计旅游行程表。 (2) 如果旅游费用不限，游客将十个景点全游览完，至少需要多少时间？请建立 相关数学模型并设计旅游行程表。 (3) 如果这位游客准备 2000 元旅游费用，想尽可能多游览景点，请建立相关数 学模型并设计旅游行程表。 (4) 如果这位游客只有 5 天的时间，想尽可能多游览景点，请建立相关数学模型 并设计旅游行程表。 (5) 如果这位游客只有 5 天的时间和 2000 元的旅游费用，想尽可能多游览景点， 请建立相关数学模型并设计旅游行程表。
73 79 93 41 81 28 41 94 113 87
城际交通的总费用 S =792元 。
表 2 城内行程表 城市 常州 宁波 黄山 九江 武汉 洛阳 西安 祁县 北京 青岛 单程路线 火车站-29 路-恐龙园 汽车站-大巴-沈家门-船-普陀山 火车站-中巴-寨西-景区交通-黄 山 火车站-1 路-长途汽车站-大巴庐山 火车站-643 路-小李村-401 路-黄 鹤楼 火车站-81 路-龙门石窟 火车站-游 5-兵马俑 县城广场-乔家大院 火车站-2 号线-积水潭-919 快-八 达岭长城 火车站-304-崂山 交通费 用（往 返） /元 2× 1 2×55 2×28 2×10 2× 2 2× 1 2× 7 2× 5 2× 3 2× 1 景点 门票/ 元 180 200 230 180 80 120 110 40 45 80 游玩时 间/小 时 4 6 7 7 2 3 2 3 3 6 住宿/ 天 2 1 2 2 2 1 2 1 0 1
摘
要
旅游是提高人们生活质量的重要活动， 游客在追求旅途体验的过程中往往期 望花费最少。本文中提出了基于 TSP 模型对不同约束条件下旅游线路优化设计 的方法。 首先，针对旅游费用和时间的约束条件分别建立 TSP 模型，通过 LINGO 求 解，得到城际最优线路。根据城际最优路线制定初步的旅游行程表，并计算相应 的旅游费用和时间。 然后，通过分析初步行程表中对目标因素影响最大的因子，从而有针对性地 对城际线路进行人工修正以达到全局较优，再计算出修正后的旅游总费用和时 间，并与修正前的进行比较得出结论：如果时间不限，游完景点至少需要 3507 元；如果费用不限，游完景点至少需要 8 天时间；问题三、四分别在问题一、二 的基础上做出修正改进，剔除对目标影响最大的部分，得到以下结果：在费用不 超过 2000 元的情况下，最多可以游览 6 个景点；在时间不超过 5 天的情况下， 最多可以游览 6 个景点；问题五在问题三、四的基础上，进一步修正优化，结果 为：在费用不超过 2000 元并且时间不超过 5 天地情况下，最多可以游览 5 个景 点。 最后，给出每一种情况下的旅游行程表，包括城际行程表、城内行程表以及 宾馆信息表。
x
j 1 j i n
n
ij
1
， i 1, 2,..., n
考虑每个城市前只有一个城市，则
x
i 1 i j
ij
1 ， j 1, 2,..., n
但仅有以上约束条件不能避免在一次遍历中产生多于一个互不连通回路。 为 此我们引入额外变量 ui (i 1,..., n) ，附加以下充分约束条件，即
表 1 城际行程表 城市 徐州-常州 车次 4310 发车 日期 5.1 时间 10:05 5.1 到达 日期 时间 15:48 票价/ 元 62
常州-宁波 宁波-黄山 黄山-九江 九江-武汉 武汉-洛阳 洛阳-西安 西安-祁县 祁县-北京 北京-青岛 青岛-徐州
K75/K78 K8498-K8409 K45-K308/K305 K398/K395 K238/K239 1085 1096 2604/2601 K712/K709 1564/1565
G 的 Hamilton 圈 C ，使得 C 的总权 W (C ) w(e) 最小， e E (C ) 。
几十年来，出现了很多近似优化算法，如近邻法、贪心算法、最近插值法、 最远插值法、 模拟退火算法以及遗传算法。 这里我们利用 LINGO 软件进行求解， 具体如下： 设城市之间费用用矩阵 S 来表示，Sij 表示城市 i 到城市 j 的交通费用。 设 0-1 矩阵 x 用来表示经过的各城市之间的路线。设 若城市i不到城市j 0, xij 若城市i到城市j，且i在j前 1, 考虑每个城市后只有一个城市，则
对于问题一， 需要得到花费最少的路线，由于火车的票价一般低于长途汽车 和飞机，所以选择火车作为城际交通工具。模型中的城际费用矩阵 Sij 就是城市 i 到城市 j 最便宜的火车票价。我们通过 LINGO 编程得到最优路线为：徐州—— 常州恐龙园——浙江舟山普陀山——安徽黄山是黄山——九江市庐山——武汉 市黄鹤楼——河南洛阳龙门石窟——西安市秦始皇兵马俑——山西祁县乔家大 院——北京八达岭长城——青岛市崂山——徐州，如下图所示：
五、 模型建立与求解 5.1 问题一模型的建立与求解 根据问题分析中对总费用的分类，可以得到总费用最小的模型： min Z S C s 其中 Z 表是总费用， S 表示城际交通费用， s 表示城内费用， C 表示吃饭等其他 费用。我们首先根据城际交通费用最小设计优化线路，并给出相应的行程表；然 后分析结果，对线路作出人为修正，得到总费用最低的优化线路，并给出旅游行 程表。 5.1.1 城际线路的优化设计 本题是一个巡回旅行商问题（Traveling Salesman Problem,TSP）,也称为货郎 担问题。问题可以描述为：一旅行商想去走访若干城市，然后回到他的出发地， 问如何安排他的路线可使总时间最短。 用图论描述 TSP，给出一个图 G(V , E ) ，每边 e E 上有非负权值 w(e) ，寻找
三、
符号
符号说明
含义 旅游总费用 城际费用 吃饭及其他费用 城内费用 旅游总时间 城际时间 城内时间 经过的各城市之间的路线