The Delivery Man Problem and Cumulative Matroids

Matteo Fischetti, Gilbert Laporte and Silvano Martello
Additional contact information
Matteo Fischetti: University of Padova, Padova, Italy
Gilbert Laporte: University of Torino, Torino, Italy
Silvano Martello: University of Bologna, Bologna, Italy

Operations Research, 1993, vol. 41, issue 6, 1055-1064

Abstract: 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.

Keywords: mathematics; combinatorics: cumulative matroid problems; transportation; scheduling: single machine sequencing with change-over costs; transportation; vehicle routing: routing problems with cumulative distances (search for similar items in EconPapers)
Date: 1993
References: Add references at CitEc
Citations: View citations in EconPapers (30)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.41.6.1055 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:41:y:1993:i:6:p:1055-1064

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().