Exploiting sparsity in pricing routines for the capacitated arc routing problem

DOI10.1016/j.cor.2008.09.008zbMath1158.90321OpenAlexW1997401436WikidataQ57702228 ScholiaQ57702228MaRDI QIDQ1013413

Adam N. Letchford, Amar Oukil

Publication date: 17 April 2009

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

Full work available at URL: https://eprints.lancs.ac.uk/id/eprint/45150/1/10.pdf

zbMATH Keywords

column generationarc routingbranch-cut-and-price

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Transportation, logistics and supply chain management (90B06) Deterministic network models in operations research (90B10)

Related Items

The time-dependent shortest path and vehicle routing problem, The shortest-path problem with resource constraints with \((k, 2)\)-loop elimination and its application to the capacitated arc-routing problem, Improved bounds for large scale capacitated arc routing problem, Pricing routines for vehicle routing with time windows on road networks, Optimally solving the joint order batching and picker routing problem, Arc routing problems: A review of the past, present, and future, Improved lower bounds and exact algorithm for the capacitated arc routing problem, Solving large-scale time capacitated arc routing problems: from real-time heuristics to metaheuristics, Using dual feasible functions to construct fast lower bounds for routing and location problems, A Decade of Capacitated Arc Routing, Iterated local search and column generation to solve arc-routing as a permutation set-covering problem, An optimization-based heuristic for the multi-objective undirected capacitated arc routing problem, Ray projection for optimizing polytopes with prohibitively many constraints in set-covering column generation, Cut-First Branch-and-Price Second for the Capacitated Arc-Routing Problem, Modelling and Solving the Joint Order Batching and Picker Routing Problem in Inventories, A branch-and-price algorithm for the capacitated arc routing problem with stochastic demands, Compact formulations of the Steiner traveling salesman problem and related problems

Uses Software

• CVRPSP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A deterministic tabu search algorithm for the capacitated arc routing problem
• A result on projection for the vehicle routing problem
• Stabilized column generation
• The capacitated arc routing problem: Valid inequalities and facets
• Transforming arc routing into node routing problems
• A cutting plane algorithm for the capacitated arc routing problem
• A new branch-and-cut algorithm for the capacitated vehicle 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
• The Shortest-Path Problem with Resource Constraints and k-Cycle Elimination for k ≥ 3
• Exact methods based on node-routing formulations for undirected arc-routing problems
• Capacitated arc routing problems
• Capacitated Vehicle Routing on Trees
• The Capacitated Arc Routing Problem: Lower bounds
• Fibonacci heaps and their uses in improved network optimization algorithms