The Capacitated Arc Routing Problem: Lower bounds

DOI10.1002/net.3230220706zbMath0762.90077OpenAlexW2036924136MaRDI QIDQ4022732

Enrique Mota, Angel Corberán, Enrique Benavent, Vicente Campos

Publication date: 17 January 1993

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.3230220706

zbMATH Keywords

lower boundscapacitated arc routing problemChinese postmanminimum total costvehicle capacityminimum cost perfect matching

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Transportation, logistics and supply chain management (90B06) Dynamic programming (90C39) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items (47)

A guided local search heuristic for the capacitated arc routing problem ⋮ New large-scale data instances for CARP and new variations of CARP ⋮ Divide-and-conquer large scale capacitated arc routing problems with route cutting off decomposition ⋮ The shortest-path problem with resource constraints with \((k, 2)\)-loop elimination and its application to the capacitated arc-routing problem ⋮ New results for the directed profitable rural postman problem ⋮ An efficiency-based path-scanning heuristic for the capacitated arc routing problem ⋮ Solvable cases of the \(k\)-person Chinese postman problem ⋮ A hybrid metaheuristic approach for the capacitated arc routing problem ⋮ The capacitated arc routing problem with refill points ⋮ Improved bounds for large scale capacitated arc routing problem ⋮ GRASP with evolutionary path-relinking for the capacitated arc routing problem ⋮ Location-arc routing problem: heuristic approaches and test instances ⋮ Hybrid genetic algorithm for the open capacitated arc routing problem ⋮ Constructive heuristics for the mixed capacity arc routing problem under time restrictions with intermediate facilities ⋮ Routing problems: A bibliography ⋮ An improved multi-objective framework for the rich arc routing problem ⋮ Memetic algorithm based on extension step and statistical filtering for large-scale capacitated arc routing problems ⋮ On matchings, T‐joins, and arc routing in road networks ⋮ An ILP-refined tabu search for the directed profitable rural postman problem ⋮ Improved lower bounds and exact algorithm for the capacitated arc routing problem ⋮ Approximation algorithms for the restricted \(k\)-Chinese postman problems with penalties ⋮ An Open-Source Desktop Application for Generating Arc-Routing Benchmark Instances ⋮ The capacitated arc routing problem with intermediate facilities ⋮ Solving large-scale time capacitated arc routing problems: from real-time heuristics to metaheuristics ⋮ A deterministic tabu search algorithm for the capacitated arc routing problem ⋮ A multi-population cooperative coevolutionary algorithm for multi-objective capacitated arc routing problem ⋮ A Decade of Capacitated Arc Routing ⋮ Combinatorial optimization and green logistics ⋮ The undirected capacitated general routing problem with profits ⋮ Solving an urban waste collection problem using ants heuristics ⋮ Ant colony optimization for the arc routing problem with intermediate facilities under capacity and length restrictions ⋮ An optimization-based heuristic for the multi-objective undirected capacitated arc routing problem ⋮ Combinatorial optimization and green logistics ⋮ Lower and upper bounds for the mixed capacitated arc routing problem ⋮ A tabu search algorithm for the Min-Max \(k\)-Chinese postman problem ⋮ New lower bound for the capacitated arc routing problem ⋮ The open capacitated arc routing problem ⋮ The directed profitable location rural postman problem ⋮ Cut-First Branch-and-Price Second for the Capacitated Arc-Routing Problem ⋮ An improved heuristic for the capacitated arc routing problem ⋮ Exploiting sparsity in pricing routines for the capacitated arc routing problem ⋮ A scatter search for the periodic capacitated arc routing problem ⋮ A compact transformation of arc routing problems into node routing problems ⋮ Profitable mixed capacitated arc routing and related problems ⋮ Solving capacitated arc routing problems using a transformation to the CVRP ⋮ Local-ideal-points based autonomous space decomposition framework for the multi-objective periodic generalized directed rural postman problem under length restrictions with intermediate facilities ⋮ A cutting plane algorithm for the capacitated arc routing problem

This page was built for publication: The Capacitated Arc Routing Problem: Lower bounds