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.

Keywords: carpooling, A* algorithm, genetic algorithms, pathfinding, Pareto optimality
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
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-en.ics.org.ru/journal/article/3029/
Creative Commons License This work is licensed under a Creative Commons Attribution-NoDerivs 3.0 Unported License.

Indexed in Scopus

Full-text version of the journal is also available on the web site of the scientific electronic library eLIBRARY.RU

The journal is included in the Russian Science Citation Index

The journal is included in the RSCI

International Interdisciplinary Conference "Mathematics. Computing. Education"

Copyright © 2009–2024 Institute of Computer Science