Improved bounds for large scale capacitated arc routing problem

DOI10.1016/j.cor.2013.02.013zbMath1348.90476OpenAlexW2077930570MaRDI QIDQ336459

Marcus Poggi, Anand Subramanian, Rafael Martinelli

Publication date: 10 November 2016

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2013.02.013

zbMATH Keywords

integer programmingdual ascentarc routingiterated local searchcapacity cuts

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Applications of graph theory (05C90) Integer programming (90C10)

Related Items

Divide-and-conquer large scale capacitated arc routing problems with route cutting off decomposition ⋮ MEALS: a multiobjective evolutionary algorithm with local search for solving the bi-objective ring star problem ⋮ A hybrid metaheuristic approach for the capacitated arc routing problem ⋮ An iterated ``hyperplane exploration approach for the quadratic knapsack problem ⋮ Efficient local search limitation strategy for single machine total weighted tardiness scheduling with sequence-dependent setup times ⋮ Exact and heuristic algorithms for order acceptance and scheduling with sequence-dependent setup times ⋮ Constructive heuristics for the mixed capacity arc routing problem under time restrictions with intermediate facilities ⋮ Two phased hybrid local search for the periodic capacitated arc routing problem ⋮ Fast upper and lower bounds for a large‐scale real‐world arc routing problem ⋮ A branch-and-cut algorithm for the soft-clustered vehicle-routing problem ⋮ A hybrid evolutionary search for the generalized quadratic multiple knapsack problem ⋮ Iterated local search and column generation to solve arc-routing as a permutation set-covering problem ⋮ Exact algorithms for the multi-compartment vehicle routing problem with flexible compartment sizes ⋮ A unified heuristic and an annotated bibliography for a large class of earliness-tardiness scheduling problems

Cites Work

• Unnamed Item
• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Optimizing over the first Chvátal closure
• A deterministic tabu search algorithm for the capacitated arc routing problem
• A variable neighborhood search for the capacitated arc routing problem with intermediate facilities
• A parallel heuristic for the vehicle routing problem with simultaneous pickup and delivery
• Exploiting sparsity in pricing routines for the capacitated arc routing problem
• Variable neighborhood search
• Transforming arc routing into node routing problems
• A cutting plane algorithm for the capacitated arc routing problem
• A guided local search heuristic for the capacitated arc routing problem
• Improved lower bounds and exact algorithm for the capacitated arc routing problem
• Robust branch-and-cut-and-price for the capacitated vehicle routing problem
• Solving capacitated arc routing problems using a transformation to the CVRP
• A dual ascent approach for steiner tree problems on a directed graph
• Exact methods based on node-routing formulations for undirected arc-routing problems
• Multi-Terminal Network Flows
• Capacitated arc routing problems
• Odd Minimum Cut-Sets and b-Matchings
• The Capacitated Arc Routing Problem: Lower bounds
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Cut-First Branch-and-Price-Second for the Capacitated Arc-Routing Problem