0000000000148231

AUTHOR

Marco Colombi

showing 2 related works from this author

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 directed profitable rural postman problem with incompatibility constraints

2017

[EN] In this paper, we study a variant of the directed rural postman problem (RPP) where profits are asso- ciated with arcs to be served, and incompatibility constraints may exist between nodes and profitable arcs leaving them. If convenient, some of the incompatibilities can be removed provided that penalties are paid. The problem looks for a tour starting and ending at the depot that maximizes the difference between collected profits and total cost as sum of traveling costs and paid penalties, while satisfying remaining incompatibilities. The problem finds application in the domain of road transportation service, and in particular in the context of horizontal collaboration among carriers …

050210 logistics & transportationService (systems architecture)Mathematical optimization021103 operations researchInformation Systems and ManagementGeneral Computer ScienceComputer science05 social sciences0211 other engineering and technologiesContext (language use)Incompatibility constraints02 engineering and technologyManagement Science and Operations ResearchGeneralized independent set problem Incompatibility constraints Routing Rural postman problem Management Science and Operations Research Information Systems and ManagementIndustrial and Manufacturing EngineeringGeneralized independent set problemDomain (software engineering)Rural postman problemModeling and SimulationIndependent set0502 economics and businessRouting (electronic design automation)MATEMATICA APLICADARouting
researchProduct