On the Exact Solution of the Capacitated Arc Routing Problem

ehicle Routing Problems (VRPs) are fundamental combinatorial optimization challenges that arise in various real-world applications, encompassing delivery services, transportation logistics, and supply chain management. These problems involve efficiently routing a fleet of vehicles to service a set of geographically dispersed locations while minimizing overall costs, such as travel distance, time, or fuel consumption. The Capacitated Arc Routing Problem (CARP) is a specific variant where vehicles are required to traverse predefined arcs to deliver goods or provide services. This thesis examines the transformation of the Capacitated Arc Routing Problem to a modified version of the Capacitated Vehicle Routing Problem (CVRP) formulation, first introduced by Baldacci and Maniezzo [7] in 2006. Capacitated Vehicle Routing Problem is the most extensively studied version concerning vehicle routing: its objective is to transport products from a depot to customers while reducing total transportation expenses, and adhering to capacity constraints on each vehicle. The exact solution to these complex problems today is addressed to Branch-and-Cut-and-Price (BCP) algorithms, that integrate a branch-and-cut framework with column generation techniques, addressing the inherent complexity of the problem through a decomposition approach. The state-of-the-art Branch-and-Cut-and-Price algorithms are represented by the VRPSolver framework, by Pessoa et al.. The aim of this study is to modify the Capacitated Vehicle Routing Problem to model it as a Resource Constraint Shortest Path Problem (RCSPP) and combine it with features from the capacitated arc routing literature, such as valid inequalities and branching properties, to adapt it to the VRPSolver. Computational experiments demonstrate promising results by solving almost all classical instances from the literature. Furthermore, the efficacy of this solution could be compared to the cutting-edge approach for the capacitated arc routing problem proposed by Pecin and Uchoa