A branch-and-price algorithm for a routing problem with inbound and outbound requests br

摘要

In this paper we present a new problem arising in the context of non-emergency transportation of patients.We consider a hospital (the depot) and a set of patients with a medical appointment. Patients require eitherto go from home to hospital (inbound request) or from hospital to home (outbound request). The problem canbe addressed as a Pickup and Delivery Problem, but the fact that all transportation requests are connectedto the depot also allows tackling it as a special Multi-Trip Vehicle Routing Problem. We adopt the secondstandpoint and call it the Multi-Trip Vehicle Routing Problem with Mixed Pickup and Delivery, and Releaseand Due dates. We propose a specialized branch-and-price algorithm and demonstrate computationally thatour approach outperforms a classical branch-and-price algorithm based on the Pickup and Delivery Problemmodeling. We also show how our algorithm can be adapted to the solution of the Vehicle Routing Problemwith Simultaneous Pickup and Delivery and Time Windows, and obtain new optimal solutions on benchmark instances