Global and Local Pareto Optimality in Coevolution for Solving Carpool Service Problem With Time Windows

In metropolitan areas, drivers share their vehicles with people who commute daily via carpooling. In this paper, we first defined a multiobjective carpool service problem with time windows (MOCSPTW) by considering four optimized objectives; subsequently, we propose a coevolutionary algorithm for two solution sets, population and archive, using objective-wise local search and set-based simulated binary operation in order to address the MOCSPTW. In the evolution module of the proposed algorithm, three different methods, namely, objective-wise local search in an archive, set-based simulated binary operation in a population, and set-based simulated binary operation both in a population and in an archive, were used to generate the offspring. Meanwhile, the $\epsilon $ -domination and normal domination in the update module were adopted to control the convergence and diversity of the population and archive. In the experimental result, 48 sets of tests, including three moving patterns in a metropolitan area for the MOCSPTW, were prepared. The results of the quantitative comparison and objective visualization showed that the proposed algorithm can obtain superior Pareto-optimal solutions regarding convergence and diversity compared with a fast nondominated sorting genetic algorithm.