A MULTI-CRITERIA HEURISTIC ALGORITHM FOR PERSONALIZED ROUTE PLANNING
Abstract
This paper proposes a heuristic function for multi-criteria route planning problems. The Analytical Hierarchy Process (AHP) is used for the multi-criteria aggregation process both for actual and heuristic cost functions. Travel distance, travel time, safety and fuel consumption are considered to be the selected criteria. Additionally, while considering real data sets, road safety and fuel consumption models are developed. The proposed multi-criteria heuristic function is consistent; therefore, the A* algorithm finds optimal routes. The proposed algorithm is tested and compared with existing algorithms in the literature using a real dataset for a specific region in Eskisehir, Turkey.
Keywords
Multi-criteria optimization, Heuristic, A* search algorithm, Route planning, Driver preference
References
- Herbert W, Mili F. Route Guidance: state of the art vs. state of the practice. In: IEEE 2008 Intelligent Vehicles Symposium; 2008; Eindhoven, NETHERLANDS: IEEE. pp. 988-995.
- Fu L, Yazici A, Ozguner U. Route planning for OSU-ACT autonomous vehicle in DARPA urban challenge. In: IEEE 2008 Intelligent Vehicles Symposium; 2008; Eindhoven, NETHERLANDS: IEEE. pp. 928-933.
- Jagadeesh GR, Srikanthan T, Quek KH. Heuristic techniques for accelerating hierarchical routing on road networks. IEEE Transactions on Intelligent Transportation Systems 2002; 3: 301-309.
- Chabini I, Lan S. Adaptations of the A* algorithm for the computation of fastest paths in deterministic discrete-time dynamic networks. IEEE Transactions on Intelligent Transportation Systems 2002; 3: 60-74.
- Huang B, Wu Q, Zhan FB. A shortest path algorithm with novel heuristics for dynamic transportation networks. International Journal of Geographical Information Science 2007; 21: 625- 644.
- Olczyk A, Galuszka A. Finding routes in a public transport network. A case study. In: IEEE 19th International Conference on Methods and Models in Automation and Robotics (MMAR); 2014; Miedzyzdroje: IEEE. pp. 800-803.
- Fu L, Sun D, Rilett LR. Heuristic shortest path algorithms for transportation applications: state of the art. Computers & Operations Research 2006; 33: 3324-3343.
- Safar M. Minimum cost path for a shared nothing architecture. International Arab Journal of Informational Technology 2005; 2: 281-290.
- Bozkurt S, Yazici A, and Keskin K. A multicriteria route planning approach considering driver preferences. In: IEEE International Conference on Vehicular Electronics and Safety (ICVES); 2012; İstanbul, Turkey: IEEE. pp. 324-328.
- Wahle J, Annen O, Schuster C, Neubert L, Schreckenberg M. A dynamic route guidance system based on real traffic data. European Journal of Operational Research 2001; 131: 302-308.