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

我们用ti表示旅客从第i个景点的停留时间;用xij表示旅客是否从第i个景点直接到达第j个景点的0---1变量，由于旅客游览十个景点，且是一次巡回，所以我们得旅客在路上所用时间为：

11111m2???xij?ti?tj?

2i?1j?1

⑶ 旅客可能住宿时间：

用ei表示旅客从第i个景点可能住宿时间;用xij表示旅客是否从第i个景点直接到达第j个景点的0---1变量，由于旅客游览十个景点，且是一次巡回，所以我们得旅客在路上所用时间为：

11111m3???xij?ei?ej?

2i?1j?1综上所述，我们可的总的目标函数为：

1111111111MinT?m1?m2?m3=??tijxij???xij?ti?tj?+??xij?ei?ej? （5.2.1.1）

2i?1j?12i?1j?1i?1j?15.2.2 约束条件：

①旅游景点的约束

根据问题一的旅游景点的约束，我们可以利用结论，即根据题目要求及假设情况，我们用

1111??xi?1j?11111ij表示旅游的景点数，则我们假设旅游的景点数为

n(n=2,3,4,5,6,7,8,9,10),因为旅客要游览十个景点，所以n=11。故旅游景点数约束为：

??xi?1j?11111ij?11 （n=2,3,4,5,6,7,8,9,10）

②0—1变量约束

根据问题一的变量约束，我们可以看出，问题二与问题一都是货郎担问题（TSP），由于前面已经证明，所以这里将不再证明。

为了使旅游时间最少，则我们需要选择不同的旅游路线，因为本题为环形路线，且是一次巡回，所以我们可以把所有的景点连成一个圈，而把每一个景点看做圈上一个点。对于每个点来说，只允许最多一条边进入，同样只允许最多一条边出来，并且只要有一条边进入就要有一条边出去。因此可得约束：

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

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

i?1 8

j?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.2.3 模型建立：

根据对题目的理解，我们可以总的模型为：

1111111111MinT?m1?m2?m3=??tijxij+???xij?ti?tj?+??xij?ei?ej? （5.2.3.1）

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

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

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

j?1

xij?xji?0 （i,j=2，3??9,10,11）

5.2.4 模型求解域结果分析：

根据模型，使用Lingo编程求出最短路线，综合实际条件做适当调整得出较优路线如下：徐州→青岛→常州→舟山→黄山→北京→洛阳→西安→祁县→武汉→九江→徐州。具体行程见下表： 票价逗留时间日期 起点-终点 车次/航班 发时-到时 住宿情况 (元) （h） 5月1日 徐州-青岛 K171/k174 10:52~20:03 177 6 5月2日 青岛-常州 K293/K296 14:13~05:57 274 4 30 185 常州-舟山 0519A201 14:00~18：香华街28号5月3日 6 宁波中转 融家小院80 高级大巴 18:40~20：40 10 FM9426 15:40~16：25 580 舟山-黄山 天都路52号：5月4日 7 上海中转 52幸运之家 FM9432 22:30~23:15 563 国际机场：金5月5日 黄山-北京 CA1552 21:35~23：35 965 航绿港酒店3 （300）

9

北京-洛阳 5月6日 洛阳-西安 MU5695 G2025 CZ6319 12:55~14：40 18:23~20：15 10:50~12：00 787 535 330 7 7 480 327 45 西安-祁县 5月7日 太原中转 城东商务区：骏景宿218元 庐山景区：家庭旅馆（30） 3 2 3 2602/2603 12:27~13：41 L7816 16:49~18：07 祁县-太原-5月7日HO1134 21:20~23:30 上海-武汉 ~5月8日 D3002/D3003 06:48~12:23 5月8日 武汉-九江 长途汽车 14:40~18：40 2 7 5月9日九江-徐州 K612/K613 17:05~05:24 87 ~10日 共计：约九天

5.3 模型三的求解

5.3.1 问题的再次分析：

(1) 对问题3, 由于题中条件的限制, 考虑实际问题中从旅游景点i 到旅游景点j 要尽量走最短路，而不会绕远, 并进一步考虑问题中所提到的尽量均衡的要求。我们试着将整个网络图大致划分为从徐州出发的向北、向南两个区域(见图a ),对每个区域, 分别运用解Hamilton - 圈问题的逐次改进法求出近似解。

(2) 作法: ①用图论软件包求出G 中任两个顶点之间的最短路; ②对分区域后的各组顶点, 构造出其完全图; ③输入(2) 中完全图上的一个初始Hamilton - 圈S 0; ④若存在: w ( i, j ) + w ( i+ 1, j+ 1) < w ( i, i+ 1) + w ( j , j + 1) , 则在S 0 中删去边( i, i+ 1) 和( j , j+ 1) , 而加入边( i, j )和( i+ 1, j+ 1) , 形成新的回路S 1; ⑤回到④反复进行, 直至不能改进为止。

图 [2]

（景点间直线距离示意图）

⑶ 本题可从第一题的答案中得到大概的旅游景点数约为≧5

由题中给出的问题条件, 分析出这是一个寻求最佳旅游最多景点的问题。把各个旅游景点所在地看做节点, 根据路线图可构造一个赋权网络图G=〈N , E ,W 〉, 其中N =

10

{0, 1, 2, ?, 11}; E = { ( i, j ) ? i, j ∈N }; W = {w ( i, j ) ? i, j ∈N }根据图论中的结论, 最佳旅游最多城市问题可转化为最佳哈密尔顿回路的问题。方法是,

在图G 的基础上构造一个完备图G′,点集仍为N , 每条边( i, j ) 的权w ′( i, j ) 为点i 与j 在G中最短路的长。于是, 在G 中寻求最佳旅游最多城市的问题即为在G′中寻求最佳Hamilton - 回路的 5.3.2 模型建立

?1旅客从第i景点到第j个景点 令决策变量为xij??

0其他? 数学模型

目标函数： min??wijxij

i?1j?1nn约束条件 ?xij?1,?xij?1 （i,j=1，2，3??9,10,11）

i?1j?1xij必须形成一条巡回路线

由于Hamilton - 圈问题属NP?完全问题, 且对于这11 个点的图(还要增加m - 1

个点) 来说, 要求得真正的最优解是不太现实的, 于是我们考虑根据几何观采用启发式算法, 来求得近似最优解。 5.3.3 每组近似最优解：

第一组——南区1?2?3?4?5?6?7?8?1总路线长为2872公里 第二组——北区1?8?7?9?10?11?1总2577公里 两组总路程和为5499公里

定义：

max(ci)?min(ci)??max(ci)其中Ci 为第i 组的最佳路线的长。称A为偏差程度。

若A≤10﹪ , 偏差程度要弱一些, 即均衡性比较好。

从这个结果算看，第一组路程2872公里，第二组路程为2577公里，取偏差

2872-2577=295，295/2872=0.103，虽然这个偏差与0.01相比大了些，但相对于其他分组，相对来说是小的，所以，可以认为是比较均衡的。因为题目要求旅游较多景点，所以，开始路线为从徐州到常州，及南区开始。 5.3.4 目标条件的确立

经过对题目的分析，我们知道本题所要实现的目标是,总费用在2000以内的的情况下，游览尽可能多的景点，因此，我们的做法是在满足相应的条件下，先大致确定一下景点的个数。

旅游的总费用由两部分组成，分别为交通总费用和旅游景点的花费。则根据问题一的结论，我们可的目标函数为：

1nn1nncijxij???xij?bi?bj????xij?di?dj??2000（5.3.4.1） ??2i?1j?12i?1j?1i?1j?1（1）交通总花费

因为cij表示从第i个景点到第j个景点所需的交通费用，因此我们可以很容易的得到

11

nn