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 language | English |
---|---|
Pages (from-to) | 267-292 |
Number of pages | 26 |
Journal | Discrete Applied Mathematics |
Volume | 36 |
Issue number | 3 |
DOIs | |
Publication status | Published - 28 May 1992 |
Externally published | Yes |
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Applied Mathematics