MIXED POSTMAN PROBLEM

被引：11
作者：
KAPPAUF, CH [1 ]
KOEHLER, GJ [1 ]
机构：
[1] UNIV FLORIDA, DEPT MANAGEMENT, GAINESVILLE, FL 32611 USA
来源：
DISCRETE APPLIED MATHEMATICS | 1979年 / 1卷 / 1-2期
关键词：
D O I：
10.1016/0166-218X(79)90016-7
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
The mixed postman problem is formulated as an integer linear program. A one to one correspondence is established between the extreme points of the linear programming polyhedron and prime assigned Euler networks. A prime assigned Euler network gives rise to a set of length equivalent prime postman tours. Some prime postman tour is optimal. Thus, it is sufficient to search the extreme points of the polyhedron to find an optimal postman tour. © 1979.
引用
收藏
页码：89 / 103
页数：15
相关论文
共 13 条
[1]  
ANDREW G, 1968, GENERALIZED SET COVE
[2]  
Beltrami EJ, 1974, NETWORKS, V4, P65, DOI DOI 10.1002/NET.3230040106
[3]  
BENDERS JF, 1962, NUMER MATH, V4, P238, DOI [DOI 10.1007/S10287-004-0020-Y, 10.1007/BF01386316, DOI 10.1007/BF01386316]
[4]  
Dantzig G. B., 1967, J COMPUTER SYSTEM SC, V1, P213, DOI [DOI 10.1016/S0022-0000%2867%2980015-1, 10.1016/S0022-0000%2867%2980015-1]
[5]  
EDMONDS, 1973, MATH PROGRAM, V5, P88
[6]  
Ford Lester R., 1962, FLOWS NETWORKS
[7]  
Harary F., 1969, GRAPH THEORY, DOI DOI 10.21236/AD0705364
[8]  
KAPPAUF CH, 1975, THESIS NW U
[9]   SET COVERING BY SINGLE-BRANCH ENUMERATION WITH LINEAR-PROGRAMMING SUBPROBLEMS [J].
LEMKE, CE ;
SALKIN, HM ;
SPIELBERG, K .
OPERATIONS RESEARCH, 1971, 19 (04) :998-+
[10]  
MARSHALL CW, 1971, APPLIED GRAPH THEORY
12