Divide-and-conquer large scale capacitated arc routing problems with route cutting off decomposition
From MaRDI portal
Publication:2123554
DOI10.1016/J.INS.2020.11.011zbMATH Open1484.90132arXiv1912.12667OpenAlexW2998698683MaRDI QIDQ2123554FDOQ2123554
Authors: Yuzhou Zhang, Yi Mei, Buzhong Zhang, Keqin Jiang 
Publication date: 14 April 2022
Published in: Information Sciences (Search for Journal in Brave)
Abstract: The capacitated arc routing problem is a very important problem with many practical applications. This paper focuses on the large scale capacitated arc routing problem. Traditional solution optimization approaches usually fail because of their poor scalability. The divide-and-conquer strategy has achieved great success in solving large scale optimization problems by decomposing the original large problem into smaller sub-problems and solving them separately. For arc routing, a commonly used divide-and-conquer strategy is to divide the tasks into subsets, and then solve the sub-problems induced by the task subsets separately. However, the success of a divide-and-conquer strategy relies on a proper task division, which is non-trivial due to the complex interactions between the tasks. This paper proposes a novel problem decomposition operator, named the route cutting off operator, which considers the interactions between the tasks in a sophisticated way. To examine the effectiveness of the route cutting off operator, we integrate it with two state-of-the-art divide-and-conquer algorithms, and compared with the original counterparts on a wide range of benchmark instances. The results show that the route cutting off operator can improve the effectiveness of the decomposition, and lead to significantly better results especially when the problem size is very large and the time budget is very tight.
Full work available at URL: https://arxiv.org/abs/1912.12667
Recommendations
- A cutting plane algorithm for the capacitated arc routing problem
- An approximation algorithm for the capacitated arc routing problem
- The commodity-split multi-compartment capacitated arc routing problem
- The capacitated arc routing problem: exact algorithms
- Approximate solutions for the capacitated arc routing problem
- Cut-first branch-and-price-second for the capacitated arc-routing problem
- The Capacitated Arc Routing Problem: Lower bounds
Cites Work
- A note on two problems in connexion with graphs
- A guided local search heuristic for the capacitated arc routing problem
- Heuristic method for a mixed capacitated arc routing problem: A refuse collection application
- Improved lower bounds and exact algorithm for the capacitated arc routing problem
- Capacitated arc routing problems
- The Capacitated Arc Routing Problem: Lower bounds
- Arc Routing Problems, Part II: The Rural Postman Problem
- Cut-first branch-and-price-second for the capacitated arc-routing problem
- A cutting plane algorithm for the capacitated arc routing problem
- Solving capacitated arc routing problems using a transformation to the CVRP
- The fleet size and mix problem for capacitated arc routing
- Improved bounds for large scale capacitated arc routing problem
- Exact methods based on node-routing formulations for undirected arc-routing problems
- Competitive memetic algorithms for arc routing problems
- A deterministic tabu search algorithm for the capacitated arc routing problem
- A variable neighborhood search for the capacitated arc routing problem with intermediate facilities
- Title not available (Why is that?)
- Large scale evolutionary optimization using cooperative coevolution
- Node, edge, arc routing and turn penalties: multiple problems -- one neighborhood extension
- POPMUSIC for a real-world large-scale vehicle routing problem with time windows
- New large-scale data instances for CARP and new variations of CARP
Cited In (1)
This page was built for publication: Divide-and-conquer large scale capacitated arc routing problems with route cutting off decomposition
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2123554)
