An investigation into many-objective optimization on combinatorial problems: Analyzing the pickup and delivery problem

Many-objective optimization focuses on solving optimization problems with four or more objectives. Effort has been made mainly on studying continuous problems, with interesting results and for which several proposals have appeared. An important result states that the problem does not necessarily becomes more difficult while more objectives are considered. Nevertheless, combinatorial problems have not received an appropriate attention, making this an open research area. This investigation takes this subject on by studying a many-objective combinatorial problem, particularly, the pickup and delivery problem (PDP), which is an important combinatorial optimization problem in the transportation industry and consists of finding a collection of routes with minimum cost. Traditionally, cost has been associated with the number of routes and the total travel distance, however, in many applications, some other objectives emerge, for example, travel time, workload imbalance, and uncollected profit. If we consider all these objectives equally important, PDP can be tackled as a many-objective problem. This study is concerned with the study of: (i) the performance of four representative multi-objective evolutionary algorithms on PDP varying the number of objectives, (ii) the properties of the many-objective PDP regarding scalability, i.e. the conflict between each pair of objectives and the proportion of non-dominated solutions as the number of objectives is varied, and finally (iii) the change of PDP's difficulty when the number of objectives is increased. Results show that the regarded objectives are actually in conflict and that the problem is more difficult to solve while more objectives are considered.