第八届苏北数学建模联赛B题一等奖获奖论文 - 旅游路线的优化设计模型 - 图文

交通总费用为：

a1???xij?cij

i?1j?1nn（2）旅游景点的花费（包括该在该景点的住宿费及）

因为bi和di表示该旅游者在i个景点的消费，xij也可以表示出代表们是否到达第i个和第j个景点，而整个旅游路线又是一个环形，因此实际上将代表们在所景点的花费计算了两遍，从而我们可得旅游景点的花费为：

1nn1nnbi?di =??xij?bi?bj????xij?di?dj?

2i?1j?12i?1j?15.3.5条件约束

①本题中，有费用约束，所以

1nn1nncijxij???xij?bi?bj????xij?di?dj??2000 （5.3.5.1） ??2i?1j?12i?1j?1i?1j?1②0——1变量约束

因为题目要求从徐州出发，再回到徐州，那么我们可以把所有的景点连成一个圈，而把每一个景点看做圈上一个点。对于每个点来说，只允许最多一条边进入，同样只允许最多一条边出来，并且只要有一条边进入就要有一条边出去，该题在前面已经得到证明，这里不再证明。所以约束为：

nn?x??xijijnnij?1 （i,j=1，2，3??9,10,11）

当i?1时，因为徐州是出发点，所以?xij?1；

i?1j?1时，因为旅客最终要回到徐州，所以?xij?1.

j?1根据题目所述，我们可以得到以下结论：

?x??xijijij?1

?xi?1ij?1 ?xij?1 （i,j=1，2，3??9,10,11）

j?1同样，当i，j?2时，根据题意不可能出现xij?xji?1，即不可能出

现游客在两地间往返旅游，因为本题为一次巡回，则综上所述，我们可得约束为：

xij?xji?0

5.3.6 模型建立

根据对问题的论述，我们得到

12

1nn1nncijxij???xij?bi?bj????xij?di?dj??2000 ??2i?1j?12i?1j?1i?1j?15.3.7 模型的求解与结果分析：

综合车次航班等因素，我们得到较优路线：

徐州→常州→黄山→九江→武汉→西安→洛阳→祁县→徐州。 具体行程见下表: 日期 起点-终点 车次/航班 发时-到时 住宿情况 5月2日 徐州-常州 5月2日常州-黄山 ~5月3日 5月4日 黄山-九江 5月5日 九江-武汉 K736/737 K782/K783 K921/K924 K921/K924 03:31~09:19 14:44~00:27 01:47~06:27 01:47~06:27 天都路52号52幸运之家 nn逗留（h） 票价(元) 4 7 7 2 2 70 73 51 51 143 5月6日 武汉-西安 K1296/K1297 10:04~01:24 5月7日 西安-洛阳 长途汽车 10:20~15:20 3 43 5月8日 洛阳-祁县 K238/K239 19:00~06:41 3 98 5 祁县-徐州 6185PM-普快 06:53~08:24 5月9日 太原中转 1095PK-普快 20:29~07:22 41 费用总计：车票(577)+景点门票(830)+住宿(60)+吃饭及其他费用(420)=1887元

5.4 模型四的求解 5.4.1问题分析：

问题四要求我们设计一条路线，满足在5天的期限内游览尽可能多的景点。但是，实际问题中由于较约束条件限制，如交通班次不衔接、到达目的地景点关闭、住宿等问题，导致我们无法从全局求解出最优路线，因此，我们选用贪婪法[4]从局部最优求解此题。

5.4.2模型建立：

经过对题目分析，我们可以知道本题所要实现的目标是在5天内游览尽可能多的地方。显然，时间最短和游览的景点尽量多是该问题的两个目标。所以利用贪婪法从旅游耗时、路程长短、住宿耗时几方面综合考虑，确定局部最优解。首先，我们先删除耗时最多和相对距离较远的景点：青岛、舟山、黄山、九江。剩下的景点相对比较聚集且景点逗留时间较短，我们每一次都从与本地相邻的几个城市中选择耗时最短并且满足交通班次与景点逗留时间不产生矛盾的目的地，达到局部优化时隙分配的目的。依次类推，确定一条包揽尽可能多景点的路线在5天之内返回徐州。 5.4.3模型求解：

经过筛选，我们确定了一条较优的路线：

徐州→北京→祁县→常州→武汉→西安→洛阳→徐州。在5天时间内游览了6各景点。具体行程表如下：

车次/航票价逗留日期 起点-终点 发时-到时 住宿情况 班 (元) （h）

13

5月1日 5月1日 5月2日 徐州-北京 北京-祁县 太原中转 祁县-常州 太远中转 5月2日常州-武汉 ~5月3日 5月3日武汉-西安 ~5月4日 5月4日 5月5日 西安-洛阳 洛阳-徐州 KN2094 MUS9278 1095 1096 K371/K374 D3042/D3043 MU2547 G2034 K1352/K1353 09:35~10:45 17:03~18~30 19:14~20:27 12：29~13：47 17:53~12:58 17:31~21:34 14:40~15:55 18:15~19:48 12:07~18:32 70 590 46 67 165 267 550 294 131 居仙宾馆（50） 建设路3号:如家王城218元 3 3 4 2 2 3 5.5 模型五的求解

5.5.1 目标函数的确立

根据问题五，我们知道，旅客有五天时间和2000元旅游费用，要想游览较多的景点，那么我们设计的路线必须满足时间和费用的要求，所以时间和费用便成了约束条件。通过分析，我们知道，本题是在问题三和问题四为基础，所以我们可以利用问题三和问题四的结论来解决问题五。故目标函数为：

1nn1nncijxij???xij?bi?bj????xij?di?dj??2000元 （5.5.1.1） ??2i?1j?12i?1j?1i?1j?11nn1nntijxij???xij?ti?tj?+??xij?ei?ej??120?h? （5.5.1.2） ??2i?1j?12i?1j?1i?1j?15.5.2 约束条件

问题五综合了问题三和问题四的约束条件，为了简化模型，我们在这里将不再重述。 5.5.3 模型的求解与结果分析

综合考虑问题三和问题四，根据实际情况作适当筛选，得到满足问题五中约束条件的一条较优路线：徐州→常州→黄山→武汉→洛阳→祁县→徐州。具体行程见下表： 票价日期 起点-终点 车次/航班 发时-到时 住宿情况 逗留（h） (元) 5月1日 徐州-常州 K58/K55 9:35~15:19 70 4 5月1日常州-黄山 K8418/K8419 20:02~6:55 73 7 ~5月2日 5月4日 黄山-武汉 K8420/K8417 19:10~3:45 5月4日 武汉-洛阳 K624/K621 5月5日 汽车 洛阳-祁县 太原中转 2462/2463 16:45~1:16 17:00~3:00 5:00~6:08 14

nnnn101 143 98 7 无 2 3 3

5月6日 祁县-徐州 1095 20:19~7:22 93 费用总计：车票(585)+景点门票(460) +吃饭及其他费用(300)=1345元

六．模型的评价

1、各模型中求解目标明确、思路清晰。

2、模型中车票、门票均可成功预订、交通无阻塞、时隙衔接紧密等假设较理想，而在现实中会出现诸多意外情况。

3、由于本题涉及交通班次有无、景点开放时间、时隙衔接等实际问题，所以无法严格按照lingo求解出的最短路径确定符合要求的最优线路，需综合考虑各种约束条件作必要调整。

4、问题解决过程需从网上搜索大量数据，有些数据可信度或准确性可能不是很高。 5、现实条件约束太多，确定线路过程太繁琐，工作量较大。

七．参考文献

[1]谢金星 薛毅，《优化建模与LINDO/LINGO软件》，北京：清华大学出版社，2005。 [2]杜端甫. 运筹图论(图、网络理论中的运筹问题) [M ]. 北京航空航天大学出版社, 240- 258.

[3]肖位枢. 图论及其算法[M ]. 北京: 航空工业出版社, 186- 238. [4]宋文. 《算法设计与分析》. 重庆大学出版社，2008.

15