|
This article is cited in 5 scientific papers (total in 5 papers)
MODELS IN PHYSICS AND TECHNOLOGY
A hybrid multi-objective carpool route optimization technique using genetic algorithm and A* algorithm
R. S. Beeda, S. Sarkarb, A. Royc, S. D. Biswasa, S. Biswasa a Department of Computer Sc., St. Xavier’s College (Autonomous),
30 Mother Teresa Sarani Kolkata 700016 West Bengal, India
b Department of Computer Sc. & Engineering, Assam University,
Silchar, Assam 788011, India
c Department of Computer Sc., Assam University,
Silchar, Assam 788011, India
Abstract:
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 multi-objective 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.
Received: 26.06.2020 Revised: 02.12.2020 Accepted: 02.12.2020
Citation:
R. S. Beed, S. Sarkar, A. Roy, S. D. Biswas, S. Biswas, “A hybrid multi-objective carpool route optimization technique using genetic algorithm and A* algorithm”, Computer Research and Modeling, 13:1 (2021), 67–85
Linking options:
https://www.mathnet.ru/eng/crm870 https://www.mathnet.ru/eng/crm/v13/i1/p67
|
Statistics & downloads: |
Abstract page: | 100 | Full-text PDF : | 49 | References: | 24 |
|