A three-phase heuristic for a multi-size container transport problem with partially specified requests

The present paper studies a generalization of the less-than-truckload pickup and delivery problem. The problem at hand arises in the hinterland of container terminal where empty and loaded containers have to be transported between a container depot and a set of customer locations. However, requests including empty containers are only partially specified. That is, either the pickup location or the delivery location of a request including the transportation of an empty container is a priori known. Customers who demand an empty container do not care which specific empty container is provided, i.e., while the delivery location is given, the pickup location is part of the problem's solution. To solve this problem, an iterated three-phase heuristic is introduced. The first phase completes the partially specified requests, the second phase solves a standard pickup and delivery problem, the third phase changes parameters of the objective function and the process iterates. Computational results on a set of 1,000 test instances are presented.