Search results for "Rural Postman"

showing 7 items of 17 documents

The Hierarchical Mixed Rural Postman Problem: Polyhedral analysis and a branch-and-cut algorithm

2017

[EN] The Hierarchical Mixed Rural Postman Problem is defined on a mixed graph where arcs and edges that require a service are divided into clusters' that have to be serviced in a hierarchical order. The problem generalizes the Mixed Rural Postman Problem and thus is NP-hard. In this paper, we provide a polyhedral analysis of the problem and propose a branch-and-cut algorithm for its solution based on the introduced classes of valid inequalities. Extensive computational experiments are reported on benchmark instances. The exact approach allows to find the optimal solutions in less than 1 hour for instances with up to 999 vertices, 2678 links, and five clusters.

Information Systems and ManagementHierarchical Routing ProblemsGeneral Computer Science0211 other engineering and technologiesMixed graph02 engineering and technologyManagement Science and Operations ResearchIndustrial and Manufacturing EngineeringCombinatorics0502 economics and businessOrder (group theory)Mixed Rural Postman ProblemPolyhedral analysisBranch-and-cut Hierarchical Routing Problems Mixed Rural Postman Problem Polyhedral analysis Modeling and Simulation Management Science and Operations Research Information Systems and ManagementMathematicsDiscrete mathematics050210 logistics & transportation021103 operations research05 social sciencesBranch-and-cutModeling and SimulationBenchmark (computing)Polyhedral analysisMATEMATICA APLICADABranch and cutAlgorithmEuropean Journal of Operational Research
researchProduct

The stacker crane problem and the directed general routing problem

2015

[EN] This article deals with the polyhedral description and the resolution of the directed general routing problem (DGRP) and the stacker crane problem (SCP). The DGRP contains a large number of important arc and node routing problems as special cases, including the SCP. Large families of facet-defining inequalities for the DGRP are described and a branch-and-cut algorithm for these problems is presented. Extensive computational experiments over different sets of DGRP and SCP instances are included.

Mathematical optimizationDirected general routing problemStacker crane problemComputer Networks and CommunicationsStackerNode (networking)Branch-and-cut algorithmDirected graphResolution (logic)Directed rural postman problemHardware and ArchitectureRouting (electronic design automation)MATEMATICA APLICADASoftwareInformation SystemsMathematics
researchProduct

On the Distance-Constrained Close Enough Arc Routing Problem

2021

[EN] Arc routing problems consist basically of finding one or several routes traversing a given set of arcs and/or edges that must be serviced. The Close-Enough Arc Routing Problem, or Generalized Directed Rural Postman Problem, does not assume that customers are located at specific arcs, but can be serviced by traversing any arc of a given subset. Real-life applications include routing for meter reading, in which a vehicle equipped with a receiver travels a street network. If the vehicle gets within a certain distance of a meter, the receiver collects its data. Therefore, only a few streets which are close enough to the meters need to be traversed. In this paper we study the generalization…

Mathematical optimizationInformation Systems and ManagementGeneral Computer ScienceClose-enoughComputer scienceHeuristic (computer science)0211 other engineering and technologies02 engineering and technologyManagement Science and Operations ResearchIndustrial and Manufacturing EngineeringSet (abstract data type)Rural Postman0502 economics and businessDistance constraintsRouting050210 logistics & transportation021103 operations researchHeuristic05 social sciencesBranch and cutModeling and SimulationBenchmark (computing)Routing (electronic design automation)MATEMATICA APLICADAArc routingAutomatic meter readingStreet network
researchProduct

Lower bounds and heuristics for the Windy Rural Postman Problem

2020

[EN] In this paper we present several heuristic algorithms and a cutting-plane algorithm for the Windy Rural Postman Problem. This problem contains several important Arc Routing Problems as special cases and has very interesting real-life applications. Extensive computational experiments over different sets of instances are also presented.

Mathematical optimizationInformation Systems and ManagementGeneral Computer ScienceHeuristic (computer science)Management Science and Operations ResearchUpper and lower boundsIndustrial and Manufacturing EngineeringWindy Rural Postman ProblemModeling and SimulationCutting planesHeuristicsRouting (electronic design automation)HeuristicsMATEMATICA APLICADAAlgorithmArc routingCutting-plane methodMathematicsRouting
researchProduct

An ILS-Based Metaheuristic for the Stacker Crane Problem

2012

[EN] In this paper we propose a metaheuristic algorithm for the Stacker Crane Problem. This is an NP-hard arc routing problem whose name derives from the practical problem of operating a crane. Here we present a formulation and a lower bound for this problem and propose a metaheuristic algorithm based on the combination of a Multi-start and an Iterated Local Search procedures. Computational results on a large set of instances are presented.

Mathematical optimizationIterated local searchComputer scienceStackerComputerApplications_COMPUTERSINOTHERSYSTEMSMetaheuristicsUpper and lower boundsParallel metaheuristicDirected rural postman problemCombinatorial OptimizationCombinatorial optimizationLarge set (combinatorics)MATEMATICA APLICADAMetaheuristicArc routingAlgorithm
researchProduct

New Results on the Mixed General Routing Problem

2005

[EN] In this paper, we deal with the polyhedral description and the resolution of the Mixed General Routing Problem. This problem, in which the service activity occurs both at some of the nodes and at some of the arcs and edges of a mixed graph, contains a large number of important arc and node routing problems as special cases. Here, a large family of facet-defining inequalities, the Honeycomb inequalities, is described. Furthermore, a cutting-plane algorithm for this problem that incorporates new separation procedures for the K-C, Regular Path-Bridge, and Honeycomb inequalities is presented. Branch and bound is invoked when the final solution of the cutting-plane procedure is fractional. …

Mathematical optimizationmedicine.medical_specialtyBranch and boundPolyhedral combinatoricsMixed graphHoneycomb (geometry)Mixed rural postman problemManagement Science and Operations ResearchPolyhedral combinatoricsComputer Science ApplicationsRural postman problemVehicle routing problemmedicineDestination-Sequenced Distance Vector routingRouting (electronic design automation)General routing problemMATEMATICA APLICADACutting-plane methodMathematics
researchProduct

New facets and an enhanced branch-and-cut for the min-max K -vehicles windy rural postman problem

2011

[EN] The min-max windy rural postman problem is a multiple vehicle version of the windy rural postman problem, WRPP, which consists of minimizing the length of the longest route to find a set of balanced routes for the vehicles. In a previous paper, an ILP formulation and a partial polyhedral study were presented, and a preliminary branch-and-cut algorithm that produced some promising computational results was implemented. In this article, we present further results for this problem. We describe several new facet-inducing inequalities obtained from the WRPP, as well as some inequalities that have to be satisfied by any optimal solution. We present an enhanced branch-and-cut algorithm that t…

Postman problemsMathematical optimizationComputer Networks and CommunicationsFacetsWindy postman problemSet (abstract data type)Rural postman problemWindy rural postman problemsHardware and ArchitectureLarge set (Ramsey theory)Multi-vehiclesWindy rural postman problemMATEMATICA APLICADABranch and cutMetaheuristicAlgorithmsSoftwareMultivehicleInformation SystemsMathematicsNetworks
researchProduct