基于Lingo的旅游计划制定方法(含代码)

海南大学

《数学模型课程设计》论文

题目：基于Lingo的旅游计划制定方法班级：信息与计算科学

姓名：体贴的瑾色

学号：

指导教师：

日期：2017.06

目录

基于Lingo的旅游计划制定方法 (3)

摘要 (3)

一、问题描述 (3)

二、模型假设 (3)

三、问题分析 (3)

四、符号说明 (4)

五、模型建立 (4)

六、问题解决 (7)

七、回答问题 (9)

八、模型推广 (10)

九、心得体会 (11)

参考文献 (11)

程序附录 (11)

基于Lingo 的旅游计划制定方法

摘要

本文针对海南十八个城市制定旅游规划，在收集了大量的数据情况下，建立评价指标，找到最优的旅游路线。

对于问题一因为不要求求出具体的路程最小值，所以我们使用matlab 处理海南省的地图，找到每个城市在地图的相对坐标，从而得到城市之间的相对距离。以距离为权，以旅程的长度为评价标准建立模型，规划最优路线得到最小相对距离1488。11，注意这里的最小距离并不是实际上的最小距离。 对于问题二将最小费用矩阵代替距离矩阵，以旅程的总车费为评价标准建立模型，规划最优路线，得到最小费用为276元。

对于问题三，在一二问的基础上，综合考虑省时省钱，得到评价标准表达式

1488.11276

min 0.50.51488.11276

D M --=+，建立模型，规划最优路线。

一、问题描述

本题要求在不同的约束条件下规划出海南的最佳旅游路线，路线的基本要求是

必须从海口出发并回到海口，并且经过且经过海南的每个城市（包括县城）一次，并且每个市县玩两天。不同的问题约束条件是： （1）要求总路程最短。 （2）允许选择动车和大巴作为出行工具，规划的路线使得出行总交通费用最少。 （3）综合考虑一二问的条件，得到最优路线，设定出相应的评价准则和指标，修正模型。

二、模型假设

（1） 城市之间路程用城市的直线距离代替。

（2） 近期城市之间的动车价格和大巴价格视为定值。 （3） 城市之间路费取自动车价格和大巴价格的最小值。 （4） 假设不同城市之间的交通工具的速度均相差不大，即旅行时间由旅行

路程唯一决定。

三、问题分析

通过查询知道海南的市县数量总共是有18个（三沙市除外），那么显然这个问题是一个18个城市的TSP 问题。用图论的内容来等价话描述为：设(,,)

G V E W =

是一个有向赋权图，其中将城市看做节点构成顶点集V ，如果i V 和j V 之间存在边

,i j E ，即表示制定的旅游方案中是从城市i 到城市j 。,i j W 表示边,i j E 所赋的非负权重。那么该问题就是指在带权有向图G 中,寻找从指定起始节点的一条经过且仅经过一次所有节点的具有最小权值总和的闭合路径。 不同的问题中所赋的权重代表的内容不同：

（1） 问题一中，因为不要求求出具体的最小值，所以我们使用matlab 处

理海南省的地图，找到每个城市在地图的具体坐标，从而得到城市之间的距离。以距离为权建立模型，规划最优路线。

（2） 问题二中，针对不同城市间的交通条件，选择合适的交通方式，通

过互联网票务查询得到结果。

（3） 问题三中，综合考虑条件，设计出省时又省钱的最优化路线。

四、符号说明

,i j W 城市i 与城市j 之间的距离（路程，费用等）

,10i j i x i j ⎧=⎨

⎩

与j 有边相连

与无边相连 i u 与城市i 相对应的任意实数

n 城市的数量

1,2,...,18i = 1,2,...,18j =

M 旅行车费

D 旅行路程

五、模型建立

首先建立一二问的模型： 目标函数为：

1818

,,11

min *i j i j j i W x ===∑∑

保证从每个城市只离开一次：

18

,11i j

j x

==∑

保证只进入每个城市一次：

18

,1

1i j

i x

==∑

变量约束：

,01i j x =或者

但是满足上述变量并不能保证找到最优解，因为如果生成的路径包含有两个不连通的闭合子路径，也满足上述条件，但并不符合题意。所以还要增加约束使得不出现这种情况。文献[1]中证明了如果满足下述条件：

,*1i j i j u u n x n -+≤-

其中i j ≠，1,2,...,18i =，1,2,...,18j =，那么能保证不出现独立的闭合子路径。 城市之间的距离估算使用如下图一所示海南省行政图作为对象，使用matlab 的ginput 函数，找到每个市县的具体坐标，后如下图二所示对城市进行编号，计算得到城市之间的距离矩阵，结果如下图三所示，注意这里并不需要考虑城市间是否有交通工具来往，因为查询知道相近的城市均有直达车次，只有部分相距较远的城市不可来往，而第一问要求的是路程最短，所以路线选择只可能考虑相近城市来往。

之间并无直达车次，我们规定如果去其他城市转乘次数不超过一次，那么这两个城市间的车费就是转乘后的总车费，若转乘次数超过两次，两个城市就视为不能直接来往。在第二问中，因为要求计算车费最小的路线，所以我们规定不能直接来往的城市车费记为10000元。数据结果显示如下图四。

第三问要求综合考虑省时，省钱，制定最优方案。由假设条件知，本题的目标函数应该为：

min (1)aD a M =+-

其中a 为(0,1)区间的一个实数，但是因为路程和费用的量纲不同，这样得到的结果并不是很好，所以我们对目标函数做一个修正，设一二问求得的最短的路程和最少的车费分别为*D 和*M ，目标函数（评价标准）为：

**

**

min (1)D D M M a a D M --=+-

我们假设游客对省时和省钱同样的看中，即0.5a =，那么目标函数为：

**

**

min 0.50.5D D M M D M

--=+ 本文的约束条件是一二问所有的约束条件。