The min-max close-enough arc routing problem
Nicola Bianchessi, Ángel Corberán, Isaac Plana, Miguel Reula, José M. Sanchis
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.
Topics & Concepts
Arc routingTraverseArc (geometry)Computer scienceHeuristicRouting (electronic design automation)Branch and cutColumn generationMathematical optimizationBranch and boundVehicle routing problemSet (abstract data type)Branch and priceHeuristicsAlgorithmInteger programmingMathematicsComputer networkGeodesyGeographyGeometryProgramming languageVehicle Routing Optimization MethodsOptimization and Packing ProblemsTransportation and Mobility Innovations