Все выпуски

[ Switch to English ]

A hybrid multi-objective carpool route optimization technique using genetic algorithm and A* algorithm

Beed R.S., Sarkar S., Roy A., Dutta Biswas S., Biswas S.
 pdf (22565K)

Carpooling has gained considerable importance as an effective solution for reducing pollution, mitigation of traffic and congestion on the roads, reduced demand for parking facilities, lesser energy and fuel consumption and most importantly, reduction in carbon emission, thus improving the quality of life in cities. This work presents a hybrid GA-A* algorithm to obtain optimal routes for the carpooling problem in the domain of multiobjective optimization having multiple conflicting objectives. Though the Genetic Algorithm provides optimal solutions, the A* algorithm because of its efficiency in providing the shortest route between any two points based on heuristics, enhances the optimal routes obtained using the Genetic algorithm. The refined routes obtained using the GA-A* algorithm, are further subjected to dominance test to obtain non-dominating solutions based on Pareto-Optimality. The routes obtained maximize the profit of the service provider by minimizing the travel and detour distance as well as pick-up/drop costs while maximizing the utilization of the car. The proposed algorithm has been implemented over the Salt Lake area of Kolkata. Route distance and detour distance for the optimal routes obtained using the proposed algorithm are consistently lesser for the same number of passengers when compared to the corresponding results obtained from an existing algorithm. Various statistical analysis like boxplots have also confirmed that the proposed algorithm regularly performed better than the existing algorithm using only Genetic Algorithm.

Ключевые слова: carpooling, A* algorithm, genetic algorithms, pathfinding, Pareto optimality
Цитата: Beed R.S., Sarkar S., Roy A., Dutta Biswas S., Biswas S. A hybrid multi-objective carpool route optimization technique using genetic algorithm and A* algorithm // Компьютерные исследования и моделирование, 2021, т. 13, № 1, с. 67-85
Citation in English: Beed R.S., Sarkar S., Roy A., Dutta Biswas S., Biswas S. A hybrid multi-objective carpool route optimization technique using genetic algorithm and A* algorithm // Computer Research and Modeling, 2021, vol. 13, no. 1, pp. 67-85
DOI: 10.20537/2076-7633-2021-13-1-67-85
URL: http://crm.ics.org.ru/journal/article/3029/
Creative Commons License Статья доступна по лицензии Creative Commons Attribution-NoDerivs 3.0 Unported License.

Журнал индексируется в Scopus

Полнотекстовая версия журнала доступна также на сайте научной электронной библиотеки eLIBRARY.RU

Журнал входит в систему  Российского индекса научного цитирования.

Журнал включен в базу данных Russian Science Citation Index (RSCI) на платформе Web of Science

Международная Междисциплинарная Конференция "Математика. Компьютер. Образование"

Международная Междисциплинарная Конференция МАТЕМАТИКА. КОМПЬЮТЕР. ОБРАЗОВАНИЕ.

Copyright © 2009–2024 Институт компьютерных исследований