STTR Phase I: Parallel Algorithms for Route Optimization

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.