The general routing problem polyhedron: Facets from the RPP and GTSP polyhedra |
| |
| Institution: | 1. Department of Economics and Management, University of Brescia, Contrada S. Chiara 50, Brescia 25122, Italy;2. Warsaw University of Technology, Institute of Control and Computation Engineering, Warsaw, Poland;1. Department of Statistics and Operations Research, Faculty of Mathematics, Universidad de Murcia, Spain;2. Instituto de Matemáticas de la Universidad de Sevilla (IMUS), Spain;3. Centre interuniversitaire de recherche sur les réseaux d’enterprise, la logistique et le transport (CIRRELT), Montreal, Canada;4. Department of Mechanical, Industrial and Aerospace Engineering, Gina Cody School of Engineering and Computer Science, Concordia University, Montreal, Canada |
| |
| Abstract: | 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. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
