Dijkstra solution algorithm considering fuzzy accessibility degree for patch optimization problem


APPLIED SOFT COMPUTING, vol.130, 2022 (SCI-Expanded) identifier

  • Publication Type: Article / Article
  • Volume: 130
  • Publication Date: 2022
  • Doi Number: 10.1016/j.asoc.2022.109674
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Applied Science & Technology Source, Compendex, Computer & Applied Sciences, INSPEC
  • Keywords: Public transport network, Optimal path recommendation, Fuzzy accessibility, Dijkstra algorithm, BUS-TRANSPORT NETWORKS, DESTINATION ESTIMATION, ORIGIN, MODEL
  • Dokuz Eylül University Affiliated: Yes


One of the most widely used applications for urban public transport passengers, especially for tourists, are route recommendation applications. These applications are generally based on criteria such as the shortest route, the least number of line transfers, and the least travel time. In some recent studies, there are fuzzy models that consider qualitative indicators such as comfort and accessibility in addition to these criteria. In our study, a new model and a new FuzzyDijkstra algorithm based on the Dijkstra algorithm are proposed to produce routes with the shortest path, the least transfer criteria, as well as the highest degree of accessibility. In the calculation of the accessibility degrees of the routes, concepts such as fuzzy stop neighborhoods, fuzzy intensity inside the bus, and fuzzy line accessibility were used. In the proposed algorithm, fuzzy penalty values are used to produce higher ranked routes. The validity of the proposed model and algorithm has been tested using Izmir city public transport network data. Optimal routes were generated for 100 source-target bus stop pairs that were handled randomly in the calculation experiments. Although the indicators such as the average distance traveled by the vehicle and the average number of transfers are approximately the same in the routes produced by the algorithms, it is seen that the FuzzyDijkstra algorithm gives better results compared to others with an average of 11.5% higher degree of accessibility and an average of 13.3% less walking distances between the transfer stops. In contrast, the FuzzyDijkstra algorithm used an average of 2.2% more time to solve. It is clear that this time delay, the actual value of which is less than 0.5 s, will not affect the practical use of the algorithm much.(c) 2022 Published by Elsevier B.V.