2017/05/29 by Piotr Matl, Richard F. Hartl, Matl, Piotr +3
Computer Science · Engineering · #Advanced Multi-Objective Optimization Algorithms #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Mathematical Programming #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.1705.10174
openalex publication_date 2017/05/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Real-life problems are often characterized by conflicting optimization\nobjectives. Consequently, there has been a growing interest not only in\nmulti-objective models, but also in specialized multi-objective metaheuristics\nfor solving those models. A wide variety of methods, e.g. NSGA-II, SPEA, IBEA,\nscatter search, Pareto local search, and many others, have thus been proposed\nover the years. Yet in principle, multi-objective problems can be efficiently\nsolved with existing tailored single-objective solvers -- this is the central\nidea behind the well-known epsilon-constraint method (ECM). Despite its\ntheoretical properties and conceptual simplicity, the epsilon-constraint method\nhas been largely ignored in the domain of heuristics and remains associated\nmostly with exact algorithms. In this article we dispel these preconceptions\nand demonstrate that the epsilon-constraint framework can be a highly effective\nway to directly leverage the existing research on single-objective optimization\nfor solving multi-objective problems.\n We propose an improved version of the classical ECM adapted to the challenges\nand requirements specific to heuristic search. The resulting framework is\nimplemented with an existing state-of-the-art single-objective solver for the\nCapacitated Vehicle Routing Problem (CVRP) and tested on the VRP with Route\nBalancing (VRPRB). Based on an extensive computational study, we show the added\nvalue of our adaptations compared to the classical ECM, and demonstrate that\nour simple epsilon-constraint algorithm significantly outperforms the current\nstate-of-the-art multi-objective metaheuristics with respect to multiple\nquality metrics. We conclude with a discussion of relevant success factors and\npromising directions for further research.\n