Yıl 2016, Cilt 17 , Sayı 2, Sayfalar 299 - 313 2016-07-14

A MULTI-CRITERIA HEURISTIC ALGORITHM FOR PERSONALIZED ROUTE PLANNING
A MULTI-CRITERIA HEURISTIC ALGORITHM FOR PERSONALIZED

Sinem BOZKURT KESER [1] , Ahmet YAZICI [2] , Serkan GÜNAL [3]


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.

Multi-criteria optimization, Heuristic, A* search algorithm, Route planning, Driver preference
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • Saaty TL. The Analytic Hierarchy Process, Planning, Priority Setting. Resource Allocation 1980; McGraw-Hill, New York, NY, USA.
  • Malenkovska TM, Donceva R, Bunevska J. Role of functional classification of highways in road traffic safety. Transport Problems 1980; 4: 97-104.
  • 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.
  • Malczewski J. GIS and Multicriteria Decision Analysis. Wiley 1999, New York, NY, USA.
  • Dijkstra EW. A Note on Two Problems in Connexion with Graphs. Numerische Mathematik 1959, 1: 269-271.
  • 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.
Bölüm Araştırma Makalesi
Yazarlar

Yazar: Sinem BOZKURT KESER

Yazar: Ahmet YAZICI

Yazar: Serkan GÜNAL

Tarihler

Yayımlanma Tarihi : 14 Temmuz 2016

Bibtex @ { aubtda257964, journal = {Anadolu University Journal of Science and Technology A - Applied Sciences and Engineering}, issn = {1302-3160}, eissn = {2146-0205}, address = {}, publisher = {Eskişehir Teknik Üniversitesi}, year = {2016}, volume = {17}, pages = {299 - 313}, doi = {10.18038/btda.06501}, title = {A MULTI-CRITERIA HEURISTIC ALGORITHM FOR PERSONALIZED ROUTE PLANNING}, key = {cite}, author = {Bozkurt Keser, Sinem and Yazıcı, Ahmet and Günal, Serkan} }
APA Bozkurt Keser, S , Yazıcı, A , Günal, S . (2016). A MULTI-CRITERIA HEURISTIC ALGORITHM FOR PERSONALIZED ROUTE PLANNING . Anadolu University Journal of Science and Technology A - Applied Sciences and Engineering , 17 (2) , 299-313 . DOI: 10.18038/btda.06501
MLA Bozkurt Keser, S , Yazıcı, A , Günal, S . "A MULTI-CRITERIA HEURISTIC ALGORITHM FOR PERSONALIZED ROUTE PLANNING" . Anadolu University Journal of Science and Technology A - Applied Sciences and Engineering 17 (2016 ): 299-313 <https://dergipark.org.tr/tr/pub/aubtda/issue/24338/257964>
Chicago Bozkurt Keser, S , Yazıcı, A , Günal, S . "A MULTI-CRITERIA HEURISTIC ALGORITHM FOR PERSONALIZED ROUTE PLANNING". Anadolu University Journal of Science and Technology A - Applied Sciences and Engineering 17 (2016 ): 299-313
RIS TY - JOUR T1 - A MULTI-CRITERIA HEURISTIC ALGORITHM FOR PERSONALIZED ROUTE PLANNING AU - Sinem Bozkurt Keser , Ahmet Yazıcı , Serkan Günal Y1 - 2016 PY - 2016 N1 - doi: 10.18038/btda.06501 DO - 10.18038/btda.06501 T2 - Anadolu University Journal of Science and Technology A - Applied Sciences and Engineering JF - Journal JO - JOR SP - 299 EP - 313 VL - 17 IS - 2 SN - 1302-3160-2146-0205 M3 - doi: 10.18038/btda.06501 UR - https://doi.org/10.18038/btda.06501 Y2 - 2021 ER -
EndNote %0 Anadolu Üniversitesi Bilim Ve Teknoloji Dergisi A - Uygulamalı Bilimler ve Mühendislik A MULTI-CRITERIA HEURISTIC ALGORITHM FOR PERSONALIZED ROUTE PLANNING %A Sinem Bozkurt Keser , Ahmet Yazıcı , Serkan Günal %T A MULTI-CRITERIA HEURISTIC ALGORITHM FOR PERSONALIZED ROUTE PLANNING %D 2016 %J Anadolu University Journal of Science and Technology A - Applied Sciences and Engineering %P 1302-3160-2146-0205 %V 17 %N 2 %R doi: 10.18038/btda.06501 %U 10.18038/btda.06501
ISNAD Bozkurt Keser, Sinem , Yazıcı, Ahmet , Günal, Serkan . "A MULTI-CRITERIA HEURISTIC ALGORITHM FOR PERSONALIZED ROUTE PLANNING". Anadolu University Journal of Science and Technology A - Applied Sciences and Engineering 17 / 2 (Temmuz 2016): 299-313 . https://doi.org/10.18038/btda.06501
AMA Bozkurt Keser S , Yazıcı A , Günal S . A MULTI-CRITERIA HEURISTIC ALGORITHM FOR PERSONALIZED ROUTE PLANNING. AUBTD-A. 2016; 17(2): 299-313.
Vancouver Bozkurt Keser S , Yazıcı A , Günal S . A MULTI-CRITERIA HEURISTIC ALGORITHM FOR PERSONALIZED ROUTE PLANNING. Anadolu University Journal of Science and Technology A - Applied Sciences and Engineering. 2016; 17(2): 299-313.
IEEE S. Bozkurt Keser , A. Yazıcı ve S. Günal , "A MULTI-CRITERIA HEURISTIC ALGORITHM FOR PERSONALIZED ROUTE PLANNING", Anadolu University Journal of Science and Technology A - Applied Sciences and Engineering, c. 17, sayı. 2, ss. 299-313, Tem. 2016, doi:10.18038/btda.06501