STTR Phase I: Parallel Algorithms for Route Optimization

这个小企业创新技术转移研究（STTR）第一阶段项目将研究并行算法集成到商业软件应用程序。 具体而言，该研究将专注于开发用于自动车辆定位（AVL）和路线优化（RO）应用的并行算法，长期目标是扩展到其他市场。 AVL/RO市场有着巨大的增长机会，可以从该技术将实现的改进的商业实践中受益匪浅。 这项研究的智力价值在于开发了用于并行化邻域搜索和其他所谓的元搜索的新技术，并使这项技术可供商业用户使用。 该项目还将研究如何将这些方法与精确优化方法相结合，形成强大的混合算法，使该技术的潜在商业用户能够比现在更快地解决大型复杂的优化问题。 精确优化方法可以为中等规模的优化问题提供可证明的最佳解决方案，并为事后解决方案分析提供有用的信息。 然而，这些信息的成本很高。 抽象化可以改善这种情况，但对于解决具有现实约束的大型难题，元启发式方法是主流方法。 这些方法采用解空间搜索过程，像精确方法一样，但是搜索以适应大得多的空间的自组织方式执行。 在文献中，这些方法的分类很少受到关注，但有可能极大地扩展其范围。 在这个项目的第一阶段，并行实现的邻域搜索和其他元启发式算法，通过一个通用的C++类库将developed.The更广泛的影响，这项研究是在使并行处理的权力访问和负担得起的更广泛的商业用户的优化应用。 这将通过降低使用这项技术的财政和技术障碍来实现。 第一个测试市场将是AVL/RO市场，该市场基本上尚未开发，总体市场渗透率仅为10%。由于联邦要求在2005年底前为所有蜂窝电话配备E911接收器，最近可负担得起的无线GPS跟踪系统出现爆炸式增长，这一市场将迅速扩大。 如果该技术能够负担得起，能够使用这些设备提供的信息来优化车队路线和调度的应用将产生巨大的潜在影响。 这种商业模式的设计将使客户能够访问一个按需远程服务器，该服务器能够通过安装在客户现场并与客户自己的数据库集成的前端并行分析大型复杂模型。 该产品将有一个低的初始成本沿着与每月订阅费涵盖服务器维护和升级的成本。

This Small Business Innovation Technology Transfer Research (STTR) Phase I project will investigate the integration of parallel algorithms into commercial software applications. Specifically, the research will focus on the development of parallel algorithms for use in an automatic vehicle location (AVL) and route optimization (RO) application, with a long-term goal of expanding to other markets. The AVL/RO market has significant growth opportunities and can benefit greatly from the improved business practices the technology will enable. The intellectual merit of this research is in the development of new techniques for parallelizing neighborhood search and other so-called metaheuristics, and making this technology available to commercial users. The project will also investigate ways in which these methods can be integrated with exact optimization methods to form powerful hybrid algorithms that will allow potential commercial users of this technology to solve large, complex optimization problems more quickly than is possible today. Exact optimization methods can provide provably optimal solutions to modestly sized optimization problems, as well as providing information useful for post-facto solution analysis. However, this information comes at a high cost. Parallelization can improve the situation, but for attacking large, difficult problems with real-world constraints, metaheuristic methods are the prevailing methodology. These methods employ a solution space search procedure, like exact methods, but the search is performed in an ad-hoc manner that accommodates a much larger space. Parallelization of these methods has received little attention in the literature, but has the potential to dramatically extend their reach. In Phase I of this project, parallel implementations of neighborhood search and other metaheuristic algorithms through a generic C++ class library will be developed.The broader impact of this research is in making the power of parallel processing accessible and affordable to a wider range of commercial users of optimization applications. This will be done by lowering the financial and technical barriers to the use of this technology. The first test market will be the AVL/RO market, which is largely untapped and has an overall market penetration of only 10 percent. This market is set to expand at a rapid pace with the recent explosion in affordable wireless GPS tracking systems spurred by the federal mandate to equip all cellular phones with E911 receivers by the end of 2005. Applications capable of using the information provided by these devices to optimize fleet routing and scheduling will have a huge potential impact, if the technology is made affordable. This business model will be designed to provide the client with access to an on-demand remote server capable of analyzing large, complex models in parallel through a front end installed at the customer site and integrated with the customer's own databases. The product will have a low initial cost along with a monthly subscription fee covering the cost of server maintenance and upgrades.