Integrated Loading and Transportation Problem: Complexity

Abstract

We consider an integrated loading and transportation problem that arises in a number of practical settings. In this problem, jobs first are loaded on semitrailers with a given capacity by a single crane and then delivered from a yard to a port by tractors. When the semitrailer and the tractor return to the yard, they may be separated such that the semitrailer may be loaded with new jobs while the tractor can pull another semitrailer loaded completely to the port. The problem is to find a joint loading and delivery schedule to minimize the arrival time of the last job. In this paper, we consider the problem that is motivated by real-world applications and analyze its computational complexity.