arXiv:2403.06995v1 Announce Type: new
Abstract: This paper introduces the Capacitated Covering Salesman Problem (CCSP), approaching the notion of service by coverage in capacitated vehicle routing problems. In CCSP, locations where vehicles can transit are provided, some of which have customers with demands. The objective is to service customers through a fleet of vehicles based in a depot, minimizing the total distance traversed by the vehicles. CCSP is unique in the sense that customers, to be serviced, do not need to be visited by a vehicle. Instead, they can be serviced if they are within a coverage area of the vehicle. This assumption is motivated by applications in which some customers are unreachable (e.g., forbidden access to vehicles) or visiting every customer is impractical. In this work, optimization methodologies are proposed for the CCSP based on ILP (Integer Linear Programming) and BRKGA (Biased Random-Key Genetic Algorithm) metaheuristic. Computational experiments conducted on a benchmark of instances for the CCSP evaluate the performance of the methodologies with respect to primal bounds. Furthermore, our ILP formulation is extended in order to create a novel MILP (Mixed Integer Linear Programming) for the Multi-Depot Covering Tour Vehicle Routing Problem (MDCTVRP). Computational experiments show that the extended MILP formulation outperformed the previous state-of-the-art exact approach with respect to optimality gaps. In particular, optimal solutions were obtained for several previously unsolved instances.
The Capacitated Covering Salesman Problem and its Multi-Disciplinary Nature
In the field of operations research and optimization, the Capacitated Covering Salesman Problem (CCSP) is introduced as a novel approach to the notion of service by coverage in capacitated vehicle routing problems. The problem assumes the existence of locations where vehicles can transit, some of which have customers with demands. The objective is to efficiently service these customers through a fleet of vehicles based in a depot, while minimizing the total distance traveled by the vehicles.
What sets CCSP apart from traditional vehicle routing problems is its unique approach to servicing customers. Instead of requiring each customer to be visited by a vehicle, CCSP allows for customers to be serviced if they fall within the coverage area of a vehicle. This assumption is motivated by real-world applications where certain customers may be unreachable due to constraints such as forbidden access to vehicles or impracticality of visiting every customer.
The multi-disciplinary nature of CCSP becomes evident when considering its applicability to various real-world scenarios. The problem can be applied in industries such as transportation, logistics, and delivery services, where the need to efficiently service customers while considering constraints on vehicle access or impracticality of visiting every customer is prevalent. Furthermore, CCSP can also be extended to tackle related problems, such as the Multi-Depot Covering Tour Vehicle Routing Problem (MDCTVRP).
This paper presents optimization methodologies for solving CCSP, utilizing both Integer Linear Programming (ILP) and Biased Random-Key Genetic Algorithm (BRKGA) metaheuristic. The proposed methodologies are evaluated through computational experiments conducted on a benchmark of CCSP instances, assessing their performance in terms of primal bounds. The results demonstrate the effectiveness of the ILP and BRKGA approaches in solving the CCSP, providing valuable insights into their applicability in real-world scenarios.
In addition, the paper extends the ILP formulation to create a novel Mixed Integer Linear Programming (MILP) formulation for the MDCTVRP. Computational experiments conducted on previously unsolved instances show that the extended MILP formulation outperforms the existing exact approach in terms of optimality gaps, producing optimal solutions for multiple instances. This highlights the potential of the MILP formulation in solving complex multi-depot vehicle routing problems, further enhancing the practicality and effectiveness of the proposed methodologies.
Conclusion
The Capacitated Covering Salesman Problem (CCSP) introduces a unique approach to the concept of service by coverage in capacitated vehicle routing problems. This paper has presented optimization methodologies based on Integer Linear Programming (ILP) and Biased Random-Key Genetic Algorithm (BRKGA) to solve CCSP, showcasing their effectiveness through computational experiments. The multi-disciplinary nature of CCSP and its potential applications in real-world scenarios make it a valuable concept in the field of operations research. Furthermore, the extension of the ILP formulation to solve the Multi-Depot Covering Tour Vehicle Routing Problem (MDCTVRP) demonstrates the versatility and scalability of the proposed methodologies. Overall, this paper contributes to the advancement of optimization techniques for solving complex vehicle routing problems with coverage constraints.