...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Transactions in GIS: TG >A Comparative Analysis of Traveling Salesman Solutions from Geographic Information Systems
【24h】

A Comparative Analysis of Traveling Salesman Solutions from Geographic Information Systems

机译：地理信息系统旅行商解决方案的比较分析

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

The Traveling Salesman Problem is one of the most prominent problems in combinatorial optimization, and is regularly employed in a wide variety of applications. The objective of this article is to demonstrate the extent of sub-optimality produced by Traveling Salesman solution procedures implemented in the context of Geographic Information Systems and to discuss the consequences that such solutions have for practice. Toward that end, an analysis is made of Traveling Salesman solutions from implementations in four Geographic Information System packages. These implementations are tested against the optimal solution for a range of problem sizes. Computational results are presented in the context of a school bus routing application. This analysis concludes that no Traveling Salesman implementation in GIS is likely to find the optimal solution when problems exceed 10 stops. In contrast, optimal solutions can be generated with desktop linear programming software for up to 25 cities. Moreover, one GIS implementation consistently found solutions that were closer to optimal than its competitors. This research strongly suggests that for applications with fewer than 25 stops, the use of an optimal solution procedure is advised, and that GIS implementations can benefit from the integration of more robust optimization techniques.
机译：旅行商问题是组合优化中最突出的问题之一，并且经常在各种应用中使用。本文的目的是演示在地理信息系统的情况下实施的Traveling Salesman解决方案过程产生的次优程度，并讨论此类解决方案对实践的影响。为此，分析了来自四个地理信息系统软件包中的实现的Traveling Salesman解决方案。针对各种问题规模，针对最佳解决方案对这些实现进行了测试。计算结果在校车路线选择应用程序的上下文中显示。该分析得出的结论是，当问题超过10个停靠点时，在GIS中没有Traveling Salesman实施方案可能找不到最佳解决方案。相比之下，可以使用台式机线性编程软件为多达25个城市生成最佳解决方案。此外，一个GIS实施始终发现比其竞争对手更接近最优的解决方案。这项研究强烈建议对于少于25个站点的应用程序，建议使用最佳解决方案，并且GIS实施可以受益于更强大的优化技术的集成。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号