下载此文档

2008年D题全国一等奖论文12.doc


文档分类:资格/认证考试 | 页数:约17页 举报非法文档有奖
1/17
下载提示
  • 1.该资料是网友上传的,本站提供全文预览,预览什么样,下载就什么样。
  • 2.下载该文档所得收入归上传者、原创者。
  • 3.下载的文档,不会出现我们的网址水印。
1/17 下载此文档
文档列表 文档介绍
2008年D题全国一等奖论文12.docB:走遍全中国
摘要
本文以周游先生退休后想到各地旅游,计划走遍全国的省会城市、直辖市、香港、澳门、台北为背景,以全国34个城市为研究对象,运用数学建模的方法对旅游的日程进行安排,从时间性和经济性的角度进行定量分析和评价。
对于问题1,本文考虑运用高斯坐标将各城市的经纬度转换成平面坐标。在平面坐标系的基础上,运用遗传算法编程设计出最短旅行方案。
对于问题2,通过互联网找到前五年五一期间相关的机票和火车票价格,进行趋势分析,预测出今年的价格。通过C++编程运用遗传算法和决策优化求解出最经济的旅行方案。
对于问题3,通过网络调查得到消费者对时间性和经济性的偏好,拟合出时间性的经济性的权重,制定出评价准则。运用遗传算法和降维思想,修订旅行方案。
对于问题4、5,本文将对算法的复杂性、可行性及误差进行综合分析,将结合本文采用的算法对旅行商问题提出自己理解和评价。
关键词:旅行商问题遗传算法趋势分析最优化
问题重述
周游先生退休后想到各地旅游。计划走遍全国的省会城市、直辖市、香港、澳门、台北。要求我们按照各城市的地理位置,即经纬度设计出最短的旅行路线方案。如果2010年5月1日周先生从哈尔滨市出发,每个城市停留3天,可选择航空、铁路两种,在实际调查互联网的基础上,提出最经济的互联网订票方案。如果综合考虑既省钱、省时又方便的方法,要求设计出评价准则,建立数学模型,修订我们的方案。在完成上述方案的设计后,要对算法的复杂性、可行性及误差进行分析。最后要结合我们的算法对旅行商问题进行评价。
问题分析
题目要求分析旅行安排方案对时间和费用的影响,并建立数学模型求解出最短路旅行方案、最经济旅行方案以及两者结合的优化方案。在旅行的安排的过程中需要考虑到:实际情况与理论上的差异,如两个城市间没有交通工具(以下交通工具均指航空或铁路)可以直达,则设它们之间交通费用为无穷大;如何确定时间和费用在优化方案的评价中占得比重;在知道时间和费用的权重后,怎样建立目标函数值使评价指标科学合理:
对于问题1,在将各城市的地理位置,即经纬度利用高斯坐标转换成平面坐标以后,再求出两两城市之间的距离,通过计算机编程,利用遗传算法,即可求出最短的旅行方案。
对于问题2,考虑到在实际背景的前提条件下,通过互联网采集5月1日至
6月3日的铁路(快车卧铺或动车)和航空的历年价格数据,运用趋势分析的方法预测出今年的价格情况。得到价格数据以后再在1的基础上求解出最经济的旅行方案。
对于问题3,要在问题1、2的基础上,通过网络调查得到消费者对时间性和经济性的偏好,拟合出时间性的经济性的权重,制定出评价准则。建立数学模型进行优化分析,得到是目标函数最理想的结果。
对于问题4、5,要在综合分整个方案的基础上,合理的对算法的复杂性、可行性及误差进行分析。最后要结合我们的算法对旅行商问题进行评价。


1、若两城市之间没有直达的交通工具,则假定费用为无穷大
2、互联网上各航空公司历年的报价具有可信性,所选价格为实际执行价格,即考虑打折、赔偿等因素后的价格
3、由于周先生在每个城市停留3天,假设在每个城市停留整3天后有去其他城市(从该城市出发存在直达交通工具的城市)的交通工具

:表示第个城市
:表示城市的集合
:表示第个访问的城市顺序数
:表示一个访问顺序
:表示第个城市到第-1个城市的距离
:表示工作单元
:表示工作单元的集合
:表示基因座
:表示交叉之后的基因座
:表示适应度函数
:表示总路程


本题是一个典型的旅行商问题(Traveling Salesman Problem,简称TSP),可以将问题转换为:
已知n个城市之间的相互距离,现有一推销员必须遍访这n个城市,并且每个城市只能访问一次,最后又必须返回出发城市。如何安排他对这些城市的访问次序,可使其旅行路线的中长度最短?
用图论的术语来说,假设有一个图,其中是顶点集,是边集,设是由顶点和顶点之间的距离所组成的距离矩阵,旅行商问题就是求出一条通过所有顶点且每个顶点只通过一次的具有最短距离的回路。
若对于城市的一个访问顺序为,其中,且记,则旅行商问题的数学模型为:
旅行商问题是一个典型的组合优化问题,并且是一个NP难题,其可能的路径数目与城市数目是呈指数型增长的,所以一般很难精确地求出其最优解,因而寻找其有效的近似求解算法有很重要的意义。
具有代表性的旅行商问题求解的交叉算法,主要有:由Grefenstette等提出的常规单点交叉或多点交叉算法,由Goldberg等提出部分映射交叉算法(Partially Mapped Crossover,简称PMX),由Da

2008年D题全国一等奖论文12 来自淘豆网www.taodocs.com转载请标明出处.

相关文档 更多>>
非法内容举报中心
文档信息
  • 页数17
  • 收藏数0 收藏
  • 顶次数0
  • 上传人marry201208
  • 文件大小713 KB
  • 时间2018-04-25