点的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
我们用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
第八届苏北数学建模联赛B题一等奖获奖论文---旅游路线的优化设计模型
