  Carpooling has gained considerable importance in developed as well as in
developing countries as an effective solution for controlling vehicular
pollution, both sound and air. As carpooling decreases the number of vehicles
used by commuters, it results in multiple benefits like mitigation of traffic
and congestion on the roads, reduced demand for parking facilities, lesser
energy or 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
Genetic algorithm provides optimal solutions, A* algorithm because of its
efficiency in providing the shortest route between any two points based on
heuristics, enhances the optimal routes obtained using 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 with the corresponding data
obtained using the existing algorithm. Various statistical analyses like
boxplots have also confirmed that the proposed algorithm regularly performed
better than the existing algorithm using only Genetic Algorithm.
