Leveraging single-objective heuristics to solve bi-objective problems: Heuristic box splitting and its application to vehicle routing

After decades of intensive research on the vehicle routing problem (VRP), many highly efficient single-objective heuristics exist for a multitude of VRP variants. But when new side-objectives emerge—such as service quality, workload balance, pollution reduction, consistency—the prevailing approach has been to develop new, problem-specific, and increasingly complex multiobjective (MO) methods. Yet in principle, MO problems can be efficiently solved with existing single-objective solvers. This is the fundamental idea behind the well-known ϵ-constraint method (ECM). Despite its generality and conceptual simplicity, the ECM has been largely ignored in the domain of heuristics and remains associated mostly with exact algorithms.

In this article, we dispel these preconceptions and demonstrate that ϵ-constraint-based frameworks can be a highly effective way to directly leverage the decades of research on single-objective VRP heuristics in emerging MO settings.