Search results for " Rural postman problem"

showing 3 items of 13 documents

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