Pickup and delivery selection with compulsory requests

Abstract

The operational planning decisions of a carrier consist of accepting transport requests of customers and constructing daily vehicle routes. Several customers may have less-than-truckload requests to be transported between two specified locations: these customers are consolidated into vehicle tours by the carrier. However, a carrier has only a limited capacity within his own vehicle fleet. Therefore he can only serve a selection of clients. Transport requests of clients are only accepted if they contribute to a higher total profit. A paired pickup and delivery selection problem is hardly investigated in literature. Due to long term contract or for other commercial reasons, some of the requests cannot be neglected, even if they do not contribute fully to profit. This practical aspect is modeled with the Pickup and Delivery with selection of customers. A mixed-integer programming formulation is given. It is indicated how the problem is solved by means of a meta-heuristic, more specifically a tabu-embedded simulated annealing algorithm.