A comparison of two different formulations for arc routing problems on mixed graphs

被引：13

作者：

Corberan, Angel

Mota, Enrique

Sanchis, Jose M.

机构：

[1] Univ Valencia, Fac Matemat, Dept Estadist & Invest Operat, E-46100 Burjassot, Valencia, Spain

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

来源：

COMPUTERS & OPERATIONS RESEARCH | 2006年 / 33卷 / 12期

关键词：

arc routing; mixed Chinese postman problem; mixed rural postman problem; mixed general routing problem;

D O I：

10.1016/j.cor.2005.02.010

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

Arc routing problems on mixed graphs have been modelled in the literature either using just one variable per edge or associating to each edge two variables, each one representing its traversal in the corresponding direction. In this paper, and using the mixed general routing problem as an example, we compare theoretical and computationally both formulations as well as the lower bounds obtained from them using Linear Programming based methods. Extensive computational experiments, including some big and newly generated random instances, are presented. (c) 2005 Elsevier Ltd. All rights reserved.

引用

页码：3384 / 3402

页数：19

共 18 条

[1]

[Anonymous], 1993, GEOMETRIC ALGORITHMS

[2]

BENAVENT E, 2000, ARC ROUTING THEORY S

[3]

Christofides N., 1984, LECT NOTES CONTROL I, V59

[4]

Christofides N, 1981, ICOR815 IMP COLL

[5] The mixed general routing polyhedron [J].

Corberán, A ;

Romero, A ;

Sanchis, JM .

MATHEMATICAL PROGRAMMING, 2003, 96 (01) :103-137

[6]

CORBERAN A, 2005, IN PRESS OPERATIONS, V53

[7]

Dror M., 2000, Arc routing : Theory, solutions and applications

[8]

Edmonds J., 1973, Mathematical Programming, V5, P88, DOI 10.1007/BF01580113

[9] ARC ROUTING-PROBLEMS .2. THE RURAL POSTMAN PROBLEM [J].

EISELT, HA ;

GENDREAU, M ;

LAPORTE, G .

OPERATIONS RESEARCH, 1995, 43 (03) :399-414

[10]

Ford L. R, 1962, FLOWS NETWORKS

← 1 2 →