Solving the prize-collecting rural postman problem

DOI10.1016/j.ejor.2008.04.037zbMath1176.90411OpenAlexW2018139583MaRDI QIDQ1041930

Julián Aráoz, Oscar Meza, Elena Fernández

Publication date: 7 December 2009

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

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

zbMATH Keywords

integer programmingcombinatorial optimizationarc routing problems

Mathematics Subject Classification ID

Integer programming (90C10) Combinatorial optimization (90C27)

Related Items

The target visitation arc routing problem ⋮ New results for the directed profitable rural postman problem ⋮ Integer programming formulation and polyhedral results for windy collaborative arc routing problem ⋮ A branch-and-cut algorithm for the profitable windy rural postman problem ⋮ Multi-vehicle prize collecting arc routing for connectivity problem ⋮ On the collaboration uncapacitated arc routing problem ⋮ Multi-depot rural postman problems ⋮ A branch-and-cut algorithm for the maximum benefit Chinese postman problem ⋮ A scatter search algorithm for time-dependent prize-collecting arc routing problems ⋮ The profitable close-enough arc routing problem ⋮ The restricted Chinese postman problems with penalties ⋮ The orienteering problem: a survey ⋮ The generalized arc routing problem ⋮ An ILP-refined tabu search for the directed profitable rural postman problem ⋮ Approximation algorithms for the restricted \(k\)-Chinese postman problems with penalties ⋮ Solving elementary shortest-path problems as mixed-integer programs ⋮ The undirected capacitated general routing problem with profits ⋮ The directed profitable rural postman problem with incompatibility constraints ⋮ The Steiner traveling salesman problem and its extensions ⋮ Local search for the undirected capacitated arc routing problem with profits ⋮ The undirected capacitated arc routing problem with profits ⋮ Recent results on Arc Routing Problems: An annotated bibliography ⋮ City streets parking enforcement inspection decisions: the Chinese postman's perspective ⋮ The directed profitable location rural postman problem ⋮ Analysis of effective sets of routes for the split-delivery periodic inventory routing problem ⋮ Profitable mixed capacitated arc routing and related problems ⋮ An effective PSO-inspired algorithm for the team orienteering problem

Uses Software

• CPLEX

Cites Work

• Unnamed Item
• Unnamed Item
• On the cycle polytope of a binary matroid
• The general routing problem polyhedron: Facets from the RPP and GTSP polyhedra
• A polyhedral approach to the rural postman problem
• The capacitated arc routing problem: Valid inequalities and facets
• A branch-and-cut algorithm for the undirected rural postman problem
• The one-period bus touring problem: Solved by an effective heuristic for the orienteering tour problem and improvement algorithm
• A cutting plane algorithm for minimum perfect 2-matchings
• Privatized rural postman problems
• Reductions to 1–matching polyhedra
• Min-Max K -vehicles windy rural postman problem
• Outline of an algorithm for integer solutions to linear programs
• On the Undirected Rural Postman Problem: Tight Bounds Based on a New Formulation
• Multi-Terminal Network Flows
• Odd Minimum Cut-Sets and b-Matchings
• Improvement Procedures for the Undirected Rural Postman Problem
• A branch & cut algorithm for the windy general routing problem and special cases
• Integer Programming and Combinatorial Optimization
• A cutting plane algorithm for the general routing problem