STTR Phase I: Parallel Algorithms for Route Optimization

这项小型企业创新技术转移研究（STTR）第一阶段项目将研究将并行算法集成到商业软件应用程序中。具体而言，该研究将侧重于开发用于自动车辆定位（AVL）和路线优化（RO）应用的并行算法，并以扩展到其他市场为长期目标。AVL/RO市场有着巨大的增长机会，并且可以从该技术所带来的改进的业务实践中受益匪浅。这项研究的智力价值在于开发了并行邻域搜索和其他所谓的元启发式的新技术，并使这项技术可供商业用户使用。该项目还将研究如何将这些方法与精确的优化方法集成在一起，形成强大的混合算法，使这项技术的潜在商业用户能够比现在更快地解决大型、复杂的优化问题。精确优化方法可以为中等规模的优化问题提供可证明的最优解，并为事后的解决方案分析提供有用的信息。然而，这些信息的成本很高。并行化可以改善这种情况，但是对于具有现实约束的大型困难问题，元启发式方法是流行的方法。这些方法采用与精确方法类似的解决方案空间搜索过程，但搜索是以一种适应更大空间的特殊方式执行的。这些方法的并行化在文献中很少受到关注，但有可能极大地扩展它们的范围。在该项目的第一阶段，将通过通用c++类库开发邻域搜索和其他元启发式算法的并行实现。这项研究的更广泛的影响是使更广泛的优化应用程序的商业用户能够访问和负担得起并行处理的能力。这将通过降低使用这项技术的财政和技术壁垒来实现。第一个测试市场将是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.