中国省会城市旅游线路的设计

0 中国省会城市旅游线路的设计 摘要 本文解决了周游先生周游全中国的最短路径的选取及基于省钱、省时又方便的互联网订票方案。 首先就问题一，周游先生想到全国各地旅游，计划走遍全国的省会城市、直辖市、香港、澳门、台北。按照地理位置（经纬度）设计计算最短旅行线路方案。根据图论和运筹学知识建立最短旅行路线数学模型。根据以求最优Hamilton回路的lingo程序和Dijkstra最短路算法应用Matlab程序进行运算解出最优线路选择方案。

关键词：最优线路选择 Hamilton回路 周游全中国 1

一、问题重述 周游先生退休后想到各地旅游。计划走遍全国的省会城市、直辖市、香港、澳门、台北。请你为他按下面要求制定出行方案： 1．按地理位置（经纬度）设计最短路旅行方案； 2．如果2010年5月1日周先生从重庆市出发，每个城市停留4天，可选择航空、铁路（快车卧铺或动车）、轮船，设计最经济的旅行互联网上订票方案，并计算出旅游结束返回重庆的时间； 3． 要综合考虑省钱、省时又方便，设定你的评价准则，建立数学模型，修订你的方案； 4．对你的算法作复杂性、可行性及误差分析； 5．关于旅行商问题提出对你自己所采用的算法的理解及评价。

二、模型假设 1、通过计算拟合后将我国地图假设成二维平面。 2、任意两城市之间路程按两点之间线段计算。 3、在每个城市中停留时，难免遇到等车、堵车等延时情况在此问题中我们不作考虑。 4、在网上订票只考虑理想情况，即票足够。 5、在订票时不考虑节假日等打折优惠。 6、忽略某些地区不能在互联网上的票的限制。 7、忽略火车的晚点和航班的延误。 8、 9、 10、

三、符号说明 iD或jD 表示城市，其中

1,34i，1,34j 2

ijDD 表示两个城市之间的距离

N 表示纬度（北） E 表示经度（东）

iN 或jN 表示第i或j城市的纬度

iE或jE 表示第i或j城市的经度 N 表示纬度每变化1时南北的平均距离差 E 表示经度每变化1时东西的平均距离差 A 表示城市间距离矩阵 S 表示旅游完34个城市的总路程

ijB 表示两个城市间的连接状况，0为不相连，1为相连

四、问题分析 问题一：要求出最短路旅行方案，关键是怎样求出城市间的距离。由于地球不是一个标准的球体，首先，将地球假设成标准的球体，则纬度变化一度南北距离差111.7Km，但经度变化一度东西变化差不固定随着纬度的升高每一经度的变化对应的东西距离差也随之变化，见下表： 表1：不同纬度每1°经度对应东西距离差（Km）：

纬度 20° 26° 30° 36° 40° 44° 51° 1°经度（东） 104 100 96 90 85 80 70

如果用这样不固定的距离差计算是很困难的，所以我们以简便为主，将我国的曲面地图拟合成一个平面，利用上述表中经度的平均值以及平均纬度变化值来计算，这样根据两城市间的经纬度我们就可以直接算出来他们之间的距离。我们在最后将对误差进行分析并判断是否对整体的求解产生过大的影响。根据图论和运筹学知识建立最短旅行路线数学模型。根据以求最优Hamilton回路的lingo程序和Dijkstra最短路算法应用Matlab程序进行运算解出最优线路选择方案。

五、模型建立与求解 3

5.1问题一的模型建立与求解 5.1.1问题一的模型建立

根据上面的分析，我们在相关资料上查到纬度每变化1时南北的平均距离差

=111.7kmN，根据表1计算得到经度每变化1时东西的平均距离差89.3Ekm。

将我国的曲面地图拟合成一个平面，通过数学方法得到平面上两个城市之间的距离计算公式，如下所示：

22

ijijijDDNNNEEE

然后我又列出了计算城市间的距离矩阵

21313313411213

133134

0...0.......0........0........0........0.......0.......0DDDDDDDDDDDD

ADDDD



下面是省会城市的编号以及经纬度

省会城市 东经 北纬 1哈尔滨 E126°41′ N45°45′

2长春 E125°19′ N43°52′ 3沈阳 E123°24′ N41°50′ 4北京 E116°28′ N39°54′ 5天津 E117°11′ N39°09′ 6石家庄 E114°28′ N38°02′ 7郑州 E113°42′ N34°48′ 8济南 E117° N36°38′ 9太原 E112°34′ N37°52′ 10西安 E108°54′ N34°16′ 4

11武汉 E114°21′ N30°37′ 12长沙 E113° N28°11′ 13合肥 E117°18′ N31°51′ 14南京 E118°50′ N32°02′ 15南昌 E115°52′ N28°41′ 16杭州 E120°09′ N30°14′ 17福州 E119°18′ N26°05′ 18上海 E121°29′ N31°14′ 19重庆 E106°32′ N29°32′ 20成都 E104°05′ N30°39′ 21贵阳 E106°42′ N26°35′ 22昆明 E102°41′ N25° 23广州 E113°15′ N23°08′ 24南宁 E108°20′ N22°48′ 25香港 E114°10′ N22°18′ 26澳门 E113°35′ N22°14′ 27海口 E110°20′ N20°02′ 28台北 E121°31′ N25°03′ 29呼和浩特 E111°48′ N40°49′ 30银川 E106°16′ N38°20′ 31兰州 E103°49′ N36°03′ 32西宁 E101°45′ N36°38′ 33乌鲁木齐 E87°36′ N43°48′ 5

34拉萨 E91°10′ N29°40′ 根据上文的符号说明，我们知道ijDD代表两个城市间的距离，假设ijB表示两城市间的连接状况， 1,0ijijDDB从到，代表其他 1,34i，1,34j

根据根据图论和运筹学知识建立下面最短H回路的模型： min： 3411ijijijSDDB

约束条件为： 34

13411..101ijiijjijBstBB







或

约束条件（1）表示每个点只有一条边出去，约束条件（2）表示每个点只有一条边进入，而且要满足除起点与终点外，各边不构成圈。 5.1.2问题一模型的求解 根据前面建立的数学模型，我们可以确切地得到最短路程S的目标函数，求解MIN S就是求解Hamilton回路，由此我们将此问题看成是一个旅行商问题，基于旅行商问题的数学表达式应用lingo数学处理软件，写出相应的lingo程序进行计算，从而求出最优的旅游路程。下面是结果：

将此代码翻译，由城市代号可知旅行线路图为： 哈尔滨→长春→沈阳→天津→济南→石家庄→太原→西安→郑州→合肥→南京→上海→ 杭州→台湾→福州→南昌→武汉→长沙→广州→香港→澳门→海口→南宁→贵阳→昆明→重庆→成都→拉萨→乌鲁木齐→西宁→兰州→银川→呼和浩特→北京→哈尔滨 全程共15917.795Km。 6

图形路线如下： 参考文献 [1] 赵静，但琪，数学建模与数学实验（第二版）[M]，北京市西城区德外大街4号：高等教育出版社，38-63，2003. [2] Mark M.Meerschaert，Mathematical Modeling(Second Edition)[M]，北京市西城区百万庄大街22号：机械工业出版社，43-72，2005. [3]雍龙泉．一类0-1二次规划最优解的新算法[J]，数学的实践与认识，39(6)：194—197，2009. [4]王丽萍，能岗匹配的方法基础[J]，中国人力资源开发，（2）：49-53，2002. [5]张德，人力资源开发与管理[M]，北京清华大学出版社，73-75，2001.

上海 7

附录 如何计算经纬度之间的距离 提问者：海蓝云天(学长) (2006-03-29 15:20:56) 用GPS测出两个点的经纬度后，如何计算这两个点之间的距离呢。用的是便携式GPS，只有经纬度显示，无坐标显示和输出。 麻烦专家解答一下，最好给个公式。

答： 以下是对提问者：dangxhong (2005-09-19)“地球上两地的地理坐标已知求两地间的实际距离”的回答,copy于此。 (2005-09-24 22:40:44)

设两点A、B的经、纬度分别为(jA,wA)(jB,wB)，则半径为R的球面上两点间的最短距离(大圆弧)为： 弧AB=R*arccos[sin(wA)sin(wB)+cos(wA)cos(wB)*cos(jA-jB)] 图见附件。