A cutting plane algorithm for the General Routing Problem

被引：44

作者：

Corberán, A

Letchford, AN

Sanchis, JM

机构：

[1] Univ Valencia, Fac Math, DEIO, E-46003 Valencia, Spain

[2] Univ Lancaster, Dept Management Sci, Lancaster LA1 4YW, England

[3] Univ Valencia, Dept Math Appl, E-46003 Valencia, Spain

来源：

MATHEMATICAL PROGRAMMING | 2001年 / 90卷 / 02期

关键词：

valid inequalities; cutting planes; General Routing Problem; Rural Postman Problem; Graphical Travelling Salesman Problem;

D O I：

10.1007/PL00011426

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

The General Routing Problem (GRP) is the problem of finding a minimum cost route for a single vehicle, subject to the condition that the vehicle visits certain vertices and edges of a network. It contains the Rural Postman Problem, Chinese Postman Problem and Graphical Travelling Salesman Problem as special cases. We describe a cutting plane algorithm for the GRP based on facet-inducing inequalities and show that it is capable of providing very strong lower bounds and, in most cases, optimal solutions.

引用

页码：291 / 316

页数：26

共 30 条

[1]

[Anonymous], ANNOTATED BIBLIOGRAP

[2]

APPLEGATE D, 1995, 9505 DIMACS TR RUTG

[3]

AUGERAT P, 1995, RR9497 ARTEMISIMAG

[4] The capacitated arc routing problem: Valid inequalities and facets [J].