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 条

[1] Static pickup and delivery problems: a classification scheme and survey
Berbeglia, Gerardo
Cordeau, Jean-Francois
Gribkovskaia, Irina
Laporte, Gilbert
[J]. TOP, 2007, 15 (01) : 1 - 31
[2] Exact solution of the generalized routing problem through graph transformations
Blais, M
Laporte, G
[J]. JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2003, 54 (08) : 906 - 910
[3] Campos V., 1995, Computational Optimization and Applications, V4, P67, DOI 10.1007/BF01299159
[4] Exact solution of large-scale, asymmetric traveling salesman problems
Carpaneto, G
DellAmico, M
Toth, P
[J]. ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE, 1995, 21 (04): : 394 - 409
[5] CHRISTOFIDES N, 1986, MATH PROGRAM STUD, V26, P155, DOI 10.1007/BFb0121091
[6] Cirasella J., 2001, The Asymmetric Traveling Salesman Problem: Algorithms, Instance Generators, and Tests, volume 2153 of Lecture Notes in Computer Science, V2153, P32, DOI DOI 10.1007/3-540-44808-X
[7] New results on the mixed general routing problem
Corberán, A
Mejía, G
Sanchis, JM
[J]. OPERATIONS RESEARCH, 2005, 53 (02) : 363 - 376
[8] The mixed general routing polyhedron
Corberán, A
Romero, A
Sanchis, JM
[J]. MATHEMATICAL PROGRAMMING, 2003, 96 (01) : 103 - 137
[9] A branch & cut algorithm for the windy general routing problem and special cases
Corberan, Angel
Plana, Isaac
Sanchis, Jose M.
[J]. NETWORKS, 2007, 49 (04) : 245 - 257
[10] ARC ROUTING-PROBLEMS .2. THE RURAL POSTMAN PROBLEM
EISELT, HA
GENDREAU, M
LAPORTE, G
[J]. OPERATIONS RESEARCH, 1995, 43 (03) : 399 - 414

← 1 2 3 →