Heuristic algorithm for searching multiple paths

Telematics is expected to be one of the fastest growing businesses in information technology area. It may create a new emerging market in industry related to automotive, telecommunications, and information services. Especially vehicle navigation service is considered as a killer application among telematics service applications. The current vehicle navigation service typically recommends a single path that is based on the traveling time or distance from the origin to the destination. The system provides two options for users to choose either via highway or via any road. Since the traffics and road conditions of big cities are very complicated and dynamic, the demand of multi-path guidance system is increasing in telematics market. The multi-path guidance system should allow drivers to choose a path based on their individual preferences such as traveling time, distance, or route familiarity. Using the Lawler's algorithm, it is possible to find multiple paths; however, due to the lengthy computational time, it is not suitable for the real-time services. This study suggests a computationally feasible and efficient heuristic multiple paths finding algorithm that is reliable for the real-time vehicle navigation services.