Exact algorithms and heuristics for capacitated covering salesman problems
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.
Code (0)
등록된 구현이 없습니다.
Methods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
The Generalized Traveling Salesman Problem solved with Ant Algorithms
A well known N P-hard problem called the Generalized Traveling Salesman Problem (GTSP) is considered. In GTSP the nodes of a complete undirected graph are partitioned into clusters. The objective is to find a minimum cos…
Traveling Salesman ProblemLearning Improvement Heuristics for Solving Routing Problems
Recent studies in using deep learning to solve routing problems focus on construction heuristics, the solutions of which are still far from optimality. Improvement heuristics have great potential to narrow this gap by it…
Deep Reinforcement LearningReinforcement LearningLearning to Sparsify Travelling Salesman Problem Instances
In order to deal with the high development time of exact and approximation algorithms for NP-hard combinatorial optimisation problems and the high running time of exact solvers, deep learning techniques have been used in…
Diversity Optimization for Travelling Salesman Problem via Deep Reinforcement Learning
Existing neural methods for the Travelling Salesman Problem (TSP) mostly aim at finding a single optimal solution. To discover diverse yet high-quality solutions for Multi-Solution TSP (MSTSP), we propose a novel deep re…
DecoderDeep Reinforcement LearningDiversityClustering Heuristics for Robust Energy Capacitated Vehicle Routing Problem (ECVRP)
The paper presents an approach to solving the Robust Energy Capacitated Vehicle Routing Problem (RECVRP), focusing on electric vehicles and their limited battery capacity. A finite number of customers, each with their ow…
Clustering