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

下面证明（2）：

采用构造法。对于任意的总巡回1ii...in?11，可取

ui=访问城市i的顺序数，取值范围为?0,1,...n?2?

因此，ui?uj?n?2，2?i?j?n.下面来证明总巡回满足该约束条件。 （i）总巡回上的边：

?ui1?ui2?n?n?1?n?1??ui2?ui3?n?n?1?n?1 ??........................................?u?u?n?n?1?n?1?in?2in?1（ii）非总巡回上的边：

??uir?uj?n?2?n?1r?1,2,...,n?2,j??2,3,...n???ir?ir?1? ?u?u?n?2?n?1j?2,3,...n?i??r??in?1j??从而结论（2）得证。

根据以上的证明，再结合本题的题目，我们可以知道在不受时间限制的情况下，要想游览的景点多，并且费用较少，经过分析可得，旅游的费用由三部分组成，即路费、门票费用和可能的费用（包括住宿费用、吃饭的费用等），所以我们定义： A—旅客旅游所花费的总费用；

； a1--旅客在路上所花费的总费用（组要是路费，其他的不考虑）

a2--旅客在各景点所花费的门票费；

； a3--旅客可能花费的费用（住宿费、吃饭的费用等）所以建立的目标函数为：

MinA?ai?a2?a3

（1）交通总花费

因为cij表示旅客从第i个景点到第j个景点所需的交通费用;用xij表示旅客是否从第i个景点直接到达第j个景点的0---1变量，由于旅客游览十个景点，且是一次巡回，所以我们得到交通总费用为：

a1???cijxij

i?1j?11111（2）旅游景点的门票花费

用bi表示旅客在第i个景点的消费，用xij表示旅客是否从第i个景点直接到达第j景

4

点的0---1变量，由对本题的分析可知，本题为环形路线，且是一次巡回，所以我们得到旅游景点的门票费用为：

11111a2???xij?bi?bj?

2i?1j?1（3）可能的费用

用di表示旅客在第i个景点消费费用，其中有住宿费、吃饭费用和其他方面的费用；用xij表示旅客是否从第i个景点到达第j景点的0---1变量，由对本题的分析可知，本题为环形路线，且是一次巡回，所以我们得到可能的费用为：

11111a3???xij?di?dj?

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

1111111111MinA?ai?a2?a3=??cijxij+??xij?bi?bj?+??xij?di?dj? （5.1.1.1）

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

①旅游景点数的约束

根据题目要求及假设情况，我们用??xij表示旅游的景点数，则我们假设旅游的

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

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

②0—1变量约束

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

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

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

i?1j?1时，因为代表们最终要回到徐州，所以?xij?1.

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

?x??xijijij?1

5

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

根据对本题的分析，我们可以得到总的模型为：

1111111111MinA?ai?a2?a3???cijxij+??xij?bi?bj?+??xij?di?dj? （5.1.3.1）

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

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

?x??xijijij?1 （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.1.4 模型求解与结果分析：

根据模型，利用Lingo软件求解出最短路线。由于现实条件约束，参照最短路线综合考虑各种因素，求解出最低费用为2924元的较优路线：徐州→常州→舟山→黄山→九江→武汉→西安→洛阳→祁县→北京→青岛→徐州。 具体行程如下表： 票价逗留时日期 起点-终点 车次 发时-到时 住宿情况 景点门票 (元) 间（h） 00：10~07：5月2日 徐州-常州 1461 硬座62 4 150 35 K75-K78 22：30~05:19 硬座73 香华街28常州-舟山 5月3日 号融家小6 130 宁波中转 豪华大巴 05:40~08：40 32 院（80） 天都路5200 32 舟山-黄山 豪华大巴 14:00~17：5月4日 号:52幸7 200 宁波中转 长途汽车 17：10~01:10 133 运之家50 2232 20：56~05:21 硬座32 庐山风景5月5日 黄山-九江 区：庭旅7 180 ~五月6日 向塘中转 K302 05：30~0718 硬座22 馆（30） 6

5月7日 5月7~5月8日 5月8日 九江-武汉 武汉-西安 西安-洛阳 长途汽车 07:00~11:00 58 火车上休息 2 2 3 50 90 120 50 40 70 K241/K244 15:38~05:55 硬座137 K386/K387 09：59~14：41 硬座55 5月8日洛阳-祁县 K238/K239 19：00~06:41 硬座98 3 ~5月9日 火车上休5月9日息 ~5月10祁县-北京 2601/2604 15:04~04：00 硬座87 3 日 5月10日北京-青岛 T25 22:48~07：38 硬座116 6 ~11日 5月11~5青岛-徐州 1112/1113 15:16~00：33 硬座87 月12日 费用总计：交通费用（1024）+住宿（160）+景点门票（1080）=2924元

5.2 模型二的求解

5.2.1 目标函数的确立：

根据问题一的理解及问题一的证明，同时该证明在问题二同样适用。我们对于问题二能够有这样的认知：在旅游费用不限的情况下，要求游览十个景点，使时间最少。根据我们对题目的理解，我们认为旅客的使用时间由三部分组成,即在路上的时间，在景点停留的时间和可能住宿时间。所以我们定义： T---旅客使用的总时间；

m1---旅客在路上所花费的时间;

m2---旅客在景点停留的时间； m3---旅客可能花费的住宿时间； 综上所述，我们得到总的目标函数为：

MinT?m1?m2?m3

⑴ 旅客在路上花费的时间：

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

m1???tijxij

i?1j?11111

⑵ 旅客在景点停留的时间：

7