6533b857fe1ef96bd12b3c3b
RESEARCH PRODUCT
The General Routing Problem polyhedron: Facets from the RPP and GTSP polyhedra
José M. SanchisÁNgel Corberánsubject
Facet (geometry)Information Systems and ManagementGeneral Computer ScienceGeneralizationHoneycomb (geometry)Facets of polyhedraGraph theoryManagement Science and Operations ResearchTravelling salesman problemIndustrial and Manufacturing EngineeringRural Postman ProblemGeneral Routing ProblemCombinatoricsPolyhedronModeling and SimulationGraphical Traveling Salesman ProblemCombinatorial optimizationMathematics::Metric GeometryRouting (electronic design automation)MATEMATICA APLICADAMathematicsRoutingdescription
[EN] In this paper we study the polyhedron associated with the General Routing Problem (GRP). This problem, first introduced by Orloff in 1974, is a generalization of both the Rural Postman Problem (RPP) and the Graphical Traveling Salesman Problem (GTSP) and, thus, is NP -hard. We describe a formulation of the problem such that from every non-trivial facet-inducing inequality for the RPP and GTSP polyhedra, we obtain facet-inducing inequalities for the GRP polyhedron, We describe a new family of facet-inducing inequalities for the GRP, the honeycomb constraints, which seem to be very useful for solving GRP and RPP instances. Finally, new classes of facets obtained by composition of facet-inducing inequalities are presented.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 1998-08-01 |