[ Switch to English ]

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

 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
Creative Commons License Статья доступна по лицензии Creative Commons Attribution-NoDerivs 3.0 Unported License.

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

Журнал входит в Перечень российских рецензируемых научных журналов, в которых должны быть опубликованы основные научные результаты диссертаций на соискание ученых степеней доктора и кандидата наук ВАК, группы специальностей: 01.01.00, 01.02.00.
 

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

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

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

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