基本信息
- 项目名称：
- “旅行商问题的研究与应用”
- 来源：
- 第十二届“挑战杯”省赛作品
- 小类：
- 管理
- 简介：
- 在旅游业和物流业快速发展的今天，旅行商问题（TSP）成为当代倍受社会关注的问题，如何有效地节省出行费用和时间一直都是游客、旅行社、物流企业探索和研究的内容。在方案的研究中，运用蚁群算法进行求解，最终得出路程最短、用时最短、花费最少等等出行方案，为有各种不同需求的人群提供全面、有效、合理的参考，并被大众所接受。因此，本文的研究结果对出行费用的节省、时间的有效利用、物流企业利润的提高有着显著的意义。
- 详细介绍：
- 随着旅游业的快速发展，大量的旅客在旅途中浪费了不必要的时间和金钱，而这些不必要的浪费完全可以通过对旅行路线的合理规划来避免。而在互联网继续扩大普及的时代，电子商务也迎来了期待已久的春天，同时物流产业也随之水涨船高。毫无疑问，高效、低成本、低能耗成了各个物流企业追求的目标，更加合理的配送路线能明显地为物流公司增大利润。因此，旅行商问题（TSP）有着广泛的应用领域和巨大的发展空间。 本文从旅行商问题的重要意义出发，分析了当前国内外旅游业的发展现状，继而就对最短路线、最省时路线、最省钱路线等问题进行研究，为有不同需要的人群提供了较丰富的出行方案。在求解这些旅行方案的过程中，本文应用蚁群算法这一先进的方法，合理且高效的求解出各种旅行路线。这些方案基本符合实际情况，能被大众所接受，为游客出行和物流配送提供了有价值的参考。 在旅行商问题的研究领域，仍有大量其他的算法在被有效地应用，例如神经网络，遗传算法、量子竞争决策算法等等。各种算法都有其优缺点，本文并未一一归纳。但是单一机制的优化算法很难实现全局优化，且效率较低，如果能使多种优化机制相混合，就可以提高全局优化度和鲁棒性，并可一定程度上放松对单一算法参数选择的苛刻性，所以混合优化策略会是一种解决旅行商问题的趋势。
作品专业信息
撰写目的和基本思路
- 在当代社会，旅游业和物流业迅速发展，而大部分的游客和物流企业并没有合理、有效地规划他们的出行路线，也就造成了大量时间和金钱的浪费。本文通过对旅行商问题的研究，建立组合优化模型求解出最短路程、最省时间、最省金钱等等最优路线，为各种人群提供全面的参考。
科学性、先进性及独特之处
- 本文建立了组合优化模型，并采用蚁群算法这一先进算法对模型进行求解，合理的标准化了时间和金钱的数值，使得人们可以根据自己的情况随意设定权重，进而制定出最适合自己的出行方案。较高的准确性和灵活性使得该方法容易被大众所接受。
应用价值和现实意义
- 大部分家庭一般是根据自己的经验来规划旅行路线，由于缺乏精确的计算，这些不合理的路线造成了许多不必要的浪费。而本文建立的模型能方便地被每个家庭使用，特别能根据不同的需求制定出不同的旅行方案。同时，在电子商务繁荣的刺激下，物流产业呈几何倍数增长。业务量的激增导致该产业中有许多规划不合理，若能制定出更加快捷的物流配送路线，大量的交通费用、时间、能耗将被节省下来。 由此可见，旅行商问题有很大的研究意义。
作品摘要
- 在旅游业和物流业快速发展的今天，旅行商问题（TSP）成为当代倍受社会关注的问题，如何有效地节省出行费用和时间一直都是游客、旅行社、物流企业探索和研究的内容。出行路线的选择其实是旅行最优商问题（TSP），是一个组合优化问题。在方案的研究中，为求最短距离，通过建立了组合优化模型，运用蚁群算法进行求解，最终得出路程最短、用时最短、花费最少等等出行方案，为有各种不同需求的人群提供全面、有效、合理的参考。该方法得出的旅行路线符合实际，被大众所接受。因此，本文的研究结果对出行费用的节省、时间的有效利用、物流企业利润的提高有着显著的参考意义。
获奖情况及评定结果
- 无
参考文献
- [1]李臣,王露,基于层次分析和图论模型的旅游线路设计及其评估,中南大学机电工程学院 [2]俞立平,潘云涛,武夷山,学术期刊综合评价数据标准化方法研究 [3]李祚泳,钟俊,彭荔红,基于蚁群算法的两地之间的最佳路径选择,系统工程,2004.7 [4]刘乃文,刘方爱,蚁群算法用于ＴＳＰ的并行策略及模型,计算机应用研究,2007 [5]张旭梅，邱晗光,基于权重编码的粒子群算法求解旅行商问题的速度范围研究,重庆大学经济与工商管理学院, 重庆400044 [6]吴启迪,汪镭,智能蚁群算法及应用[M],上海科技教育出版社,2004 [7]刘艳秋,张一兰,B2C电子商务物流配送模式研究,沈阳工业大学
调查方式
- ■ 个别交谈 ■ 图片、照片 ■ 书报刊物 ■ 统计报表 ■ 集体组织
同类课题研究水平概述
- 旅行商问题(traveling salesman problem，TSP)的历史很久，最早的描述是1759年欧拉研究的骑士周游问题，后来由美国RAND公司于1948年引入，该公司的声誉以及线性规划这一新方法的出现使得TSP成为一个知名且流行的问题。如果用穷举的办法解决该问题，现有的计算机可能无法在可接受的时间内求解出该问题，因此很多高效的算法被用于尝试求解TSP。 纵观近几年的研究成果，研究者主要使用了以下几种方法对TSP进行了研究：(1)使用各种纯数学的方法构造时间复杂度为多项式的近似算法。(2)使用常规的启发式算法：通常首先构造一个所有顶点回路，然后使用2-opt、3-opt和其它局部优化方法对回路进行优化。(3)使用遗传算法、蚁群算法、模拟退火算法、粒子群算法和神经网络等仿自然算法。由于遗传算法、蚁群算法和粒子群算法具有较强的群体搜索能力，但同时又存在可能陷入局部最优的问题，因而研究者通常将其它搜索算法和这些算法相结合以构造更高效的混合算法。神经网络和自组织图由于具有自学习、联想存储功能和高速寻找优化解的能力，使用它们和其它方法相结合的研究得到了研究者的重视。 为了进一步提高算法的全局优化能力，避免搜索过程陷入局部极小，现已提出的改进策略主要有：并行多邻域搜索，平滑优化曲面形状，引进重升温、熵抽样等高级技术等。对于复杂优化问题，单一机制的优化算法很难实现全局优化，且效率较低，多种优化机制和邻域搜索结构相混合，是能较大程度提高全局优化度和鲁棒性的有力途径，并可一定程度上放松对单一算法参数选择的苛刻性，所以混合优化策略会是一种趋势。
