THE DELIVERY MAN PROBLEM AND CUMULATIVE MATROIDS
成果类型：
Article
署名作者：
FISCHETTI, M; LAPORTE, G; MARTELLO, S
署名单位：
University of Turin; University of Bologna
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.41.6.1055
发表日期：
1993
页码：
1055-1064
关键词：
摘要：
Given a complete directed graph G = (V, A), the delivery man problem (DMP) consists of determining a Hamiltonian circuit minimizing the sum of distances (along the circuit) from a given vertex v(1), to every vertex of V, including v(1) itself. There exists a number of applications of the DMP in the fields of distribution and machine scheduling. The DMP is NP-hard. The objective of this paper is to develop new theoretical results and an exact algorithm for the problem. A new, integer linear programming formulation is provided, and results on the matroidal structure of a class of combinatorial problems are developed. These are used to derive lower bounds for the DMP. These bounds are embedded into an enumerative algorithm. The largest problems solved to optimality with the proposed algorithm involve 60 vertices. This compares favorably with previously published methods.