The Stacker Crane Problem and the Directed General Routing Problem

被引：13

作者：

Avila, Thais ^{[1
]}

Corberan, Angel ^{[1
]}

Plana, Isaac ^{[1
]}

Sanchis, Jose M. ^{[2
]}

机构：

[1] Univ Valencia, Dept Estadist & Invest Operat, Valencia, Spain

[2] Univ Politecn Valencia, Dept Matemat Aplicada, E-46071 Valencia, Spain

来源：

NETWORKS | 2015年 / 65卷 / 01期

关键词：

directed rural postman problem; directed general routing problem; stacker crane problem; branch-and-cut algorithm; ALGORITHM;

D O I：

10.1002/net.21591

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

In this article, we deal with the polyhedral description and the resolution of the directed general routing problem (DGRP) and the stacker crane problem (SCP). The DGRP, in which the service activity occurs both at some of the nodes and at some of the arcs of a directed graph, contains a large number of important arc and node routing problems as special cases, including the SCP. We describe large families of facet-defining inequalities for the DGRP. Furthermore, a branch-and-cut algorithm for these problems is presented. Extensive computational experiments over different sets of DGRP and SCP instances are included. These results show that our algorithm is among the best solution procedures proposed for both problems. (c) 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 65(1), 43-55. 2015

引用

页码：43 / 55

页数：13

共 21 条

[11] Frederickson G. N., 1976, 17 ANN S FDN COMP SC, P216
[12] APPROXIMATION ALGORITHMS FOR SOME ROUTING PROBLEMS
FREDERICKSON, GN
HECHT, MS
KIM, CE
[J]. SIAM JOURNAL ON COMPUTING, 1978, 7 (02) : 178 - 193
[13] z-approximations
Hassin, R
Khuller, S
[J]. JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 2001, 41 (02): : 429 - 442
[14] Johnson D.S., 2007, COMB OPT (SER), P445
[15] Modeling and solving several classes of arc routing problems as traveling salesman problems
Laporte, G
[J]. COMPUTERS & OPERATIONS RESEARCH, 1997, 24 (11) : 1057 - 1061
[16] THE SYMMETRICAL TRAVELING SALESMAN POLYTOPE AND ITS GRAPHICAL RELAXATION - COMPOSITION OF VALID INEQUALITIES
NADDEF, D
RINALDI, G
[J]. MATHEMATICAL PROGRAMMING, 1991, 51 (03) : 359 - 400
[17] Savall J. V., 1990, THESIS U VALENCIA
[18] Are Stacker Crane Problems easy? A statistical study
Srour, F. Jordan
van de Velde, Steef
[J]. COMPUTERS & OPERATIONS RESEARCH, 2013, 40 (03) : 674 - 690
[19] Srour J., 2010, THESIS ERASMUS U ROT
[20] ZHANG L, 1995, 1995 IEEE INTERNATIONAL CONFERENCE ON SYSTEMS, MAN AND CYBERNETICS, VOLS 1-5, P1061

← 1 2 3 →