Approximation algorithms for solving the constrained arc routing problem in mixed graphs

DOI10.1016/J.EJOR.2014.04.039MaRDI QIDQ297063zbMATH OpenOpenAlexFDO

Authors Honglin Ding, Jianping Li, Ko-Wei Lih

Publication date 24 June 2016

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ejor.2014.04.039

zbMATH Keywords

combinatorial optimizationapproximation algorithmcombinatorial algorithmarc routinglower/upper demand bound

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Recommendations

• Approximation algorithms for a mixed postman problem with restrictions on the arcs
• scientific article; zbMATH DE number 1187150
• A 3/2-Approximation Algorithm for the Mixed Postman Problem
• Approximation Algorithms for Mixed, Windy, and Capacitated Arc Routing Problems
• The mixed general routing polyhedron

Cites work

• scientific article; zbMATH DE number 3174052 (Why is no real title available?)
• scientific article; zbMATH DE number 3871059 (Why is no real title available?)
• scientific article; zbMATH DE number 3661082 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1219584 (Why is no real title available?)
• scientific article; zbMATH DE number 1520350 (Why is no real title available?)
• scientific article; zbMATH DE number 3231691 (Why is no real title available?)
• A 3/2-Approximation Algorithm for the Mixed Postman Problem
• A Faster Strongly Polynomial Minimum Cost Flow Algorithm
• A GRASP heuristic for the mixed Chinese postman problem
• A branch-and-cut-and-price algorithm for the cumulative capacitated vehicle routing problem
• A general vehicle routing problem
• A guided local search heuristic for the capacitated arc routing problem
• A strongly polynomial minimum cost circulation algorithm
• A threshold of ln n for approximating set cover
• An efficient transformation of the generalized vehicle routing problem
• An optimal algorithm for the mixed Chinese postman problem
• Approximation Algorithms for Some Postman Problems
• Capacitated arc routing problems
• Eulerian graphs and related topics. Part 1, Volume 2
• Finding minimum-cost circulations by canceling negative cycles
• Heuristic method for a mixed capacitated arc routing problem: A refuse collection application
• Local search for the undirected capacitated arc routing problem with profits
• Matching, Euler tours and the Chinese postman
• Maximum matching and a polyhedron with 0,1-vertices
• Multi-objective vehicle routing problems
• On a routing problem
• On the complexity of edge traversing
• On the mixed Chinese postman problem
• The vehicle routing problem
• The vehicle routing problem. Latest advances and new challenges.
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems

Cited in

(9)

• Approximation algorithms for a mixed postman problem with restrictions on the arcs
• Approximation algorithms for two clustered arc routing problems
• A parameterized approximation algorithm for the mixed and windy Capacitated Arc Routing Problem: theory and experiments
• A comparison of two different formulations for arc routing problems on mixed graphs
• An updated annotated bibliography on arc routing problems
• Approximation algorithms for solving the vertex-traversing-constrained mixed Chinese postman problem
• scientific article; zbMATH DE number 1568938 (Why is no real title available?)
• scientific article; zbMATH DE number 2108935 (Why is no real title available?)
• Approximation algorithm for min-max cycle cover problem on a mixed graph

Describes a project that uses

Uses Software

• Algorithm 97

This page was built for publication: Approximation algorithms for solving the constrained arc routing problem in mixed graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q297063)