The Personalized Multi-criteria Route Planning Problem in Repeated Travel and Its Solution Algorithm

摘要

Existing research on the personalized multi-criteria route planning (PMRP) problem seldom considers drivers' travel characteristics for different types of travel, which significantly affects a driver's performance in reality. In this research, the PMRP problem in repeated travel is presented and defined. The relative differences between route-costs and their respective minimums are considered as the driver's route choice criteria for repeated travel. The range of each criterion value from the driver's experience data is introduced into the problem definition as the constraint. In addition, a travel-law-based route planning (TRP) algorithm is designed, implemented, and evaluated in comparison to the genetic algorithm (GA) for solving the proposed problem. The comparison results show that the TRP algorithm achieved better results in terms of running time, criteria values, and comprehensive objective function values. The experimental results also show that for the given cases, the TRP algorithm effectively avoided impractical solutions and achieved a 0.96-second average run time to reach approximate comprehensive objective function values for the routes chosen by two drivers in practice over a real-road network with 2000 nodes and 7014 edges using a PC with a 2.53-GHz-CoreTM i5-based dual-core processor.