The rendezvous vehicle routing problem

We consider a novel scheme for same-day delivery with a strong potential to reduce transportation costs. A delivery company has two distinct fleets for last-mile delivery: trucks with known (i.e., fixed) delivery routes leaving early in the day carrying one or more-day delivery packages, and shuttles leaving later in the day carrying same-day delivery packages. By allowing shuttles to intercept trucks and hand off packages for truck delivery it may be possible to leverage the unfinished portion of truck routes to shorten the delivery routes of the shuttles. We refer to this as the Rendezvous Vehicle Routing Problem. We present a mathematical formulation of the problem, as well as a column generation algorithm that can quickly find optimal solutions for instances with up to 200 nodes. We also develop and demonstrate the effectiveness of a specialized heuristic for use in larger instances with up to 1000 nodes. Our computational study validates the efficacy of truck-shuttle synchronization in this scheme, demonstrating an average savings of 20% across the test instances.