A MIP-Based Heuristic for Pickup and Delivery on Rectilinear Layout

The Vehicle Routing Problem with Pickups and Deliveries (VRPPD) arises in many application contexts and has been intensively studied in the last decades. We investigate the special case where pickup and delivery locations are distributed on a line. Although this situation is frequent when handling material in manufacturing systems with rectilinear layout, this case has not received enough attention so far. Derived from a real application, our general model also features load/unload times, vehicle capacities and the absence of a depot. A two-stage MIP-based heuristic that exploits such a special topology is devised, and its performance is assessed within an industrial case study provided by a large semiconductor manufacturer. We first compare our method to a standard Clarke and Wright type heuristic, then document its practical impact when implemented in a dynamic environment.