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.
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Applied Mathematics