6533b853fe1ef96bd12ac99f

RESEARCH PRODUCT

The min-max close-enough arc routing problem

ÁNgel CorberánMiguel ReulaIsaac PlanaJosé M. SanchisNicola Bianchessi

subject

Set (abstract data type)Balance (metaphysics)Mathematical optimizationInformation Systems and ManagementTraverseGeneral Computer ScienceComputer scienceModeling and SimulationManagement Science and Operations ResearchArc routingIndustrial and Manufacturing Engineering

description

Abstract Here we introduce the Min-Max Close-Enough Arc Routing Problem, where a fleet of vehicles must serve a set of customers while trying to balance the length of the routes. The vehicles do not need to visit the customers, since they can serve them from a distance by traversing arcs that are “close enough” to the customers. We present two formulations of the problem and propose a branch-and-cut and a branch-and-price algorithm based on the respective formulations. A heuristic algorithm used to provide good upper bounds to the exact procedures is also presented. Extensive computational experiments to compare the performance of the algorithms are carried out.

https://doi.org/10.1016/j.ejor.2021.10.047