A branch-and-cut algorithm for the undirected traveling purchaser problem

被引:55
作者
Laporte, G
Riera-Ledesma, J
Salazar-González, JJ
机构
[1] HEC Montreal, Montreal, PQ H3T 2A7, Canada
[2] Univ La Laguna, Fac Matemat, DEIOC, Tenerife 38271, Spain
关键词
transportation : vehicle routing networks/graphs : traveling salesman;
D O I
10.1287/opre.51.6.940.24921
中图分类号
C93 [管理学];
学科分类号
12 [管理学]; 1201 [管理科学与工程]; 1202 [工商管理学]; 120202 [企业管理];
摘要
The purpose of this paper is to present a branch-and-cut algorithm for the undirected Traveling Purchaser Problem which consists of determining a minimum-cost route through a subset of markets, where the cost is the sum of travel and purchase costs. The problem is formulated as an integer linear program, and several families of valid inequalities are derived to strengthen the linear relaxation. The polyhedral structure of the formulation is analyzed and several classes of valid inequalities are proved to be facet defining. A branch-and-cut procedure is developed and tested over four classes of randomly generated instances. Results show that the proposed algorithm outperforms all previous approaches and can optimally solve instances containing up to 200 markets.
引用
收藏
页码:940 / 951
页数:12
相关论文
共 20 条
[1]
[Anonymous], TRAVELING SALESMAN P
[2]
ON THE SET COVERING POLYTOPE .1. ALL THE FACETS WITH COEFFICIENTS IN (0, 1, 2) [J].
BALAS, E ;
NG, SM .
MATHEMATICAL PROGRAMMING, 1989, 43 (01) :57-69
[3]
The circuit polytope: Facets [J].
Bauer, P .
MATHEMATICS OF OPERATIONS RESEARCH, 1997, 22 (01) :110-145
[4]
A HEURISTIC METHOD FOR A JOB-SCHEDULING PROBLEM [J].
BURSTALL, RM .
OPERATIONAL RESEARCH QUARTERLY, 1966, 17 (03) :291-&
[5]
BUZACOTT JA, 1971, NAV RES LOGIST Q, V18, P78
[6]
CAPRARA A, 1997, ANNOTATED BIBLIOGRAP
[7]
SOLVING LARGE-SCALE ZERO-ONE LINEAR-PROGRAMMING PROBLEMS [J].
CROWDER, H ;
JOHNSON, EL ;
PADBERG, M .
OPERATIONS RESEARCH, 1983, 31 (05) :803-834
[8]
A branch-and-cut algorithm for the symmetric generalized traveling salesman problem [J].
Fischetti, M ;
Gonzalez, JJS ;
Toth, P .
OPERATIONS RESEARCH, 1997, 45 (03) :378-394
[9]
THE SYMMETRICAL GENERALIZED TRAVELING SALESMAN POLYTOPE [J].
FISCHETTI, M ;
GONZALEZ, JJS ;
TOTH, P .
NETWORKS, 1995, 26 (02) :113-123
[10]
2 GENERALIZATIONS OF THE TRAVELING SALESMAN PROBLEM [J].
GOLDEN, B ;
LEVY, L ;
DAHL, R .
OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE, 1981, 9 (04) :439-441