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

A MULTI-CRITERIA HEURISTIC ALGORITHM FOR PERSONALIZED

Abstract

References

1. 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.
2. 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.
3. 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.
4. 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.
5. 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.
6. 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.
7. Fu L, Sun D, Rilett LR. Heuristic shortest path algorithms for transportation applications: state of the art. Computers & Operations Research 2006; 33: 3324-3343.
8. Safar M. Minimum cost path for a shared nothing architecture. International Arab Journal of Informational Technology 2005; 2: 281-290.

9. 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.
10. 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.
11. Lin IC, Chou SY, Hsu HY. Developing adaptive driving route guidance systems based on fuzzy neural network. In: IEEE 2009 International Conference on Systems on Man and Cybernetics (SMC 2009); 2009; Antonio, TX: IEEE. pp. 4293-4298.
12. Nadi S, Delavar MR. Multi-criteria, personalized route planning using quantifier-guided ordered weighted averaging operators. International Journal of Applied Earth Observation and Geoinformation 2011; 13: 322-335.
13. Niaraki AS, and Kim K. Ontology based personalized route planning system using a multi- criteria decision making approach. Expert Systems with Applications 2009; 36: 2250-2259.
14. Yang B, Guo C, Ma Y, Jensen CS. Toward personalized, context-aware routing. The International Journal on Very Large Data Bases 2015; 24: 297-318.
15. Rosyidi L, Pradityo HP, Gunawan D, Sari RF. Timebase dynamic weight for Dijkstra Algorithm implementation in route planning software. In: International Conference on Intelligent Green Building and Smart Grid (IGBSG); 2014. pp. 23-25.
16. Saaty TL. The Analytic Hierarchy Process, Planning, Priority Setting. Resource Allocation 1980; McGraw-Hill, New York, NY, USA.
17. Malenkovska TM, Donceva R, Bunevska J. Role of functional classification of highways in road traffic safety. Transport Problems 1980; 4: 97-104.
18. Coelho MC, Frey HC, Rouphail NM, Zhai H, Pelkmans L. Assessing methods for comparing emissions from gasoline and diesel light-duty vehicles based on microscale measurements. Transportation Research Part D-Transport and Environment 2009; 14: 91-99.
19. Malczewski J. GIS and Multicriteria Decision Analysis. Wiley 1999, New York, NY, USA.
20. Dijkstra EW. A Note on Two Problems in Connexion with Graphs. Numerische Mathematik 1959, 1: 269-271.
21. Hart PE, Nilsson NJ, Raphael B. A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics 1968; 4: 100-107.