A heuristic algorithm for solving a Multiple Criteria Carpooling Optimization (MCCO) problem

The authors consider in this paper a carpooling optimization problem, which is formulated (based on their previous work) as a constrained multiple criteria decision-making problem. Different aspects and contradictory preferences of individual stakeholders/carpoolers (drivers and passengers), including: economic, comfort- and safety-oriented, and social are considered. The formulated problem is focused on the joint matching of carpoolers and planning their routes in order to maximize the utility of all travelers. To solve the problem, the authors develop a heuristic computational procedure that applies a problem-specific heuristic method (carpooler's matching component) combined with a utility-based shortest path algorithm (routing component). The procedure aggregates all of the considered criteria by a weighted scaling function and then applies a greedy algorithm to generate most satisfactory routes for all of the carpoolers. The proposed approach is tested through simulations on a set of real cities, and a comprehensive analysis of the results is then presented.