R2 Indicator based Multiobjective Memetic Optimization for the Pickup and Delivery Problem with Time Windows and Demands (PDP-TW-D)

This paper defines a multiobjective variant of the Pickup and Delivery Problem (PDP), called PDP with Time Windows and Demands (PDP-TW-D), and approaches the problem with a novel memetic optimization algorithm. With respect to multiple optimization objectives, the goal of PDP-TW-D is to find a set of Pareto-optimal routes for a fleet of vehicles in order to serve given transportation requests. This paper considers five optimization objectives for PDP-TW including the number of vehicles, the total travel distance and the total waiting time. The proposed algorithm is designed as an evolutionary multiobjective optimization algorithm that is augmented by a local search algorithm. It uses the population of individuals, each of which represents a solution candidate, and evolves them via genetic operators (e.g., crossover and mutation operators) through generations. In addition to this global search process, it allows individuals to improve themselves in each generation through local search. Experimental results show that the global and local search processes complement to improve convergence speed and can effectively obtain quality trade-off solutions with respect to conflicting objectives.