The Delivery Man Problem and Cumulative Matroids
研究了送货员问题，提出新的整数线性规划模型和基于拟阵结构的下界，并设计精确算法，可求解多达60个顶点的实例。
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.