Using decomposition-based multi-objective algorithm to solve Selective Pickup and Delivery Problems with Time Windows. (September 2022)

• Record Type: Journal Article
• Authors: Ben-Said, Asma; Moukrim, Aziz; Guibadj, Rym Nesrine; Verny, Jérôme
• Is Part Of: Computers & operations research. Volume 145(2022)
• Publication Date: 2022-09
• Subjects: Multi-objective optimization -- Selective pickup and delivery problem -- Meta-heuristics -- Decomposition algorithm -- Pareto local search; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2022.105867
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: In this paper, several variants of multi-objective Selective Pickup and Delivery Problems with Time Windows are investigated. These problems have been widely addressed from a single-objective point of view to look for a solution with the most profitable set of requests while respecting a set of constraints. Handling simultaneously profit maximization and travel cost minimization poses a challenging optimization task in this class of routing problems. We propose a two-phase framework based on the decomposition of the search space in several linearly aggregated sub-problems. The aggregated problems are first optimized by an efficient local search with dedicated removal and insertion operators. An update is then applied on the weights of the least efficient sub-problems. We show that the perturbation of these weighted sum problems enables the exploration of more regions of the search space, and thus ensures the diversification of the Pareto front approximation. The obtained results on the selective variants of the Pickup and Delivery Problem show the effectiveness of our algorithm based on solutions quality and computational time. The proposed algorithm strictly improves 36 best known solutions of the single-objective problem and achieves the best results on all the instances of the lexicographic variant. Its performance is also confirmed on the bi-objective variant since we obtain better Pareto front approximation in terms of hyper volume, set cover, and computational time indicators. We discuss the results and explain the positive contribution of each component based on statistical tests. Highlights: The Selective Pickup and Delivery Problem with Time Windows is addressed as bi-objective problem. Efficient two-phase Pareto Local Search based on problem decomposition. New adaptive insertion criterion for the bi-objective Pickup and Delivery Problem. Performance study to evaluate the impact of each key component. Outperformance of the proposed approach in terms of quality and computational time.