走遍全中国的最优路线问题

《走遍全中国的最优路线问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、走遍全中国的最优路线问题摘要：针对周先生旅游最短路线的设计，首先，将周先生的旅游视为生活享受游，其次，一个城市的经纬度为坐标，并运用Hopfeild神经网络算法求解出最短旅行路线，之后，参考网上订票的具体信息，并结合周先生的年龄问题，选取了空航、动车、快车卧铺三种较舒适的旅行方式，以经济性，省时省钱为指标进行建模分析，最后通过各部分加权比重进行综合评价，拟定出最佳订票方案，见下文。并且进行了算法的适当分析与模型的优化。关键词：经纬度、最短路线、订票方案、算法分析一：问题重述：周游先生退休后想到各地旅游。

2、计划走遍全国的省会城市、直辖市、香港、澳门、台北。请你为他按下面要求制定出行方案：1．按地理位置（经纬度）设计最短路旅行方案；2．如果2010年5月1日周先生从哈尔滨市出发，每个城市停留3天，可选择航空、铁路（快车卧铺或动车），设计最经济的旅行互联网上订票方案；3．要综合考虑省钱、省时又方便，设定你的评价准则，建立数学模型，修订你的方案；4．对你的算法作复杂性、可行性及误差分析；5．关于旅行商问题提出对你自己所采用的算法的理解及评价。二：基本假设：在旅途中旅游车的准时出发到达,且不考虑突发事件干扰车子的

3、行程;在旅游的过程中,当天旅游目的地附近都有宾馆,且第一天的目的地就是第二天的出发点；在每个城市的吃饭、购物、在城市中观光景点等所需的费用费用视为相同；三：评价标准、基本符号、变量。【1】根据旅客要求，寻找按经纬度最短的旅行途径，故先将各省会、直辖市、特别行政区的经纬度列在下面表格中：城市名称经度纬度北京e116°28′n39°54′上海e121°29′n31°14′天津e117°11′n39°09′重庆e106°32′n29°32′哈尔滨e126°41′n45°45′长春e125°19′n43°52′

4、沈阳e123°24′n41°50′呼和浩特e111°48′n40°49′石家庄e114°28′n38°02′太原e112°34′n37°52′济南e117°n36°38′郑州e113°42′n34°48′西安e108°54′n34°16′兰州e103°49′n36°03′银川e106°16′n38°20′西宁e101°45′n36°38′乌鲁木齐e87°36′n43°48′合肥e117°18′n31°51′南京e118°50′n32°02′杭州e120°09′n30°14′长沙e113°n28°11′南

5、昌e115°52′n28°41′武汉e114°21′n30°37′成都e104°05′n30°39′贵阳e106°42′n26°35′福州e119°18′n26°05′台北e121°31′n25°03′广州e113°15′n23°08′海口e110°20′n20°02′南宁e108°20′n22°48′昆明e102°41′n25°拉萨e91°10′n29°40′香港e114°10′n22°18′澳门e113.5n22.2【1】在以经纬度为基础上算出的行程最短路线上，进行网上订票，本题中，考虑到周先生年龄

6、问题，又是退休后旅游，是以归为生活享受游，为了使其有精力地更长时间参观景点，在乘车方式的选取上进行如下考虑：在不同的乘车方式上，若距离较远，可考虑空航、动车、快车卧铺三种方式；若为较短距离旅行可考虑动车、快车卧铺和硬座；在很短的距离可考虑快车硬座和公交车。而在相同的乘车方式上（例如：均为快车卧铺，应先考虑哪辆车次），考虑到票价、乘车所需时间均基本相同，是以优先考虑列车的起始和终止时刻，考虑到旅游的观光目的和精力问题，是以列出两个优先原则。第一优先原则：尽量晚上到站，可在当地宾馆休息一晚，次日即可旅游；第

7、二优先原则：在不能满足第一优先原则的前提下，若为短途，则可考虑早出发早到原则；优先原则三：在有些情况下，某些列车的票价较低、乘车所需时间较短，是以可优先考虑。【2】根据体重提出的几个要素指标，现在归纳如下：1、乘车费用（即票费，用Y表示在各因素中所占权重）2、旅行中交通方便性（乘车方式，用B表示在各因素中所占权重）3、旅行时间（尽量使在景点停留时间长，乘车时间短，这是旅游本来的目的，符合旅客的要求，用T表示在各因素中所占权重），【3】在评价模型的建立与求解过程中，各个因素的指标均选取模糊集为衡量标准，票

8、价和乘车时间可按比例选取｛优、良、中、差｝四个等级；旅行方便程度可按乘车方式飞机、动车、快车卧铺划分为｛好、中、差｝三个等级；最后进行整合，进行权重计算。四：模型建立路线设计：按经纬度距离最短的行程路线模型假设：运用Hopfeild神经网络算法来解决旅行路线最佳问题。首先将问题映射到Hopfeild网络上，故将33个城市视为神经元，任何一个城市在最终路径上的访问次序可用一个N维向量来表示，因此每个城市需要33个神经元表示，我们不妨规定第i个