Search results for "Multivehicle"

showing 3 items of 3 documents

Formulations and exact algorithms for the distance-constrained generalized directed rural postman problem

2017

[EN] The generalized directed rural postman problem is an arc routing problem with many interesting real-life applications, such as routing for meter reading. In this application, a vehicle with a receiver travels through a series of neighborhoods. If the vehicle gets closer than a certain distance to a meter, the receiver is able to record the gas, water, or electricity consumption. Therefore, the vehicle does not need to traverse every street, but only a few, to get close enough to each meter. We study an extension of this problem in which a fleet of vehicles is available. Given the characteristics of the mentioned application, the vehicles have no capacities but there is a maximum distan…

90C27Mathematical optimizationControl and OptimizationTraverseManagement Science and Operations ResearchMathematicsT57-57.97Applied mathematics. Quantitative methodsSeries (mathematics)Extension (predicate logic)90C1090B99QA75.5-76.9590C57Constraint (information theory)Computational MathematicsClose-enough arc routing problemBranch-and-cutModeling and SimulationElectronic computers. Computer scienceRouting (electronic design automation)Distance constrainedMATEMATICA APLICADABranch and cutArc routingAlgorithmAutomatic meter readingMultivehicleGeneralized directed rural postman problem
researchProduct

A Branch-Price-and-Cut Algorithm for the Min-Max k -Vehicle Windy Rural Postman Problem

2013

[EN] The min-max k -vehicles windy rural postman problem consists of minimizing the maximal distance traveled by a vehicle to find a set of balanced routes that jointly service all the required edges in a windy graph. This is a very difficult problem, for which a branch-and-cut algorithm has already been proposed, providing good results when the number of vehicles is small. In this article, we present a branch-price-and-cut method capable of obtaining optimal solutions for this problem when the number of vehicles is larger for the same set of required edges. Extensive computational results on instances from the literature are presented.

Difficult problemService (systems architecture)Mathematical optimizationComputer Networks and CommunicationsBranch and priceColumn generationSet (abstract data type)Rural postman problemHardware and ArchitectureCutting planesGraph (abstract data type)Branch-and-priceColumn generationWindy rural postman problemMATEMATICA APLICADAAlgorithmSoftwareInformation SystemsMathematicsMultivehicle
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