The point-to-point delivery and connection problems: complexity and algorithms

Chung Lun Li, S. Thomas McCormick, David Simchi-Levi

Research output: Journal article publicationJournal articleAcademic researchpeer-review

24 Citations (Scopus)

Abstract

We consider the computational complexity of point-to-point delivery problems. These problems involve shipping one item from each one of p sources to p destinations might be prematched to sources (the fixed destination case), or a source's item might go to any destination (the nonfixed destination case). The networks can be directed or undirected. Up to K items at once can share a truck on an arc, and costs are linear in the number of trucks used. We also consider the closely related point-to-point connection problems, which are to find a minimum cost arc subset connecting sources with destinations. We find that all variations of both problems are strongly NP-hard for all K≤2, but that there are polynomial algorithms in some cases if p is fixed, or if the underlying network is a grid with sources on one side, destinations on the other.
Original languageEnglish
Pages (from-to)267-292
Number of pages26
JournalDiscrete Applied Mathematics
Volume36
Issue number3
DOIs
Publication statusPublished - 28 May 1992
Externally publishedYes

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Cite this