Pickup and delivery selection with a fixed vehicle cost

Abstract

A pickup and delivery problem is a special case of the vehicle routing problem in which goods at customer sites are either picked up or delivered. A carrier has only a limited capacity within his own vehicle fleet. Therefore the carrier can only serve a selection of customers. Transport requests of clients are accepted only if they contribute to a higher total profit. A paired pickup and delivery selection problem is hardly investigated in literature. In case the carrier has a fixed fleet with a set of drivers, it is realistic that drivers have to be paid whether the truck is used or not. This leads to a fixed cost per vehicle in the decision problem. This practical aspect is modeled with the Pickup and Delivery with selection of customers. A mixed-integer programming formulation is given. A meta-heuristic method, more specifically a tabu-embedded simulated annealing algorithm, is developed to solve the problem in an efficient way. The heuristic is explained in detail.