Two-Echelon Prize-Collecting Vehicle Routing with Time Windows and Vehicle Synchronization: A Branch-and-Price Approach

The steady growth in e-commerce and grocery deliveries within cities strains the available infrastructure in urban areas by increasing freight movements, aggravating traffic congestion, and air and noise pollution. This research introduces the Two-Echelon Prize-Collecting Vehicle Routing Problem with Time Windows and Vehicle Synchronization, where deliveries are carried out by smaller low- or zero-emission vehicles and larger trucks. Given their capacity restrictions, the smaller vehicles can only deliver small-sized orders and must be replenished via depot locations or larger-sized trucks. Besides replenishing smaller vehicles at satellite locations, larger trucks can deliver small orders and larger items. Managing these two types of fleets in an urban setting under consideration of capacity limitations, tight delivery time windows, vehicle synchronization, and selective order fulfillment is challenging. We model this problem on a time-expanded network and apply network reduction by considering the time window constraints. In addition, we propose a branch-and-price algorithm capable of solving instances with up to 200 customers, which continuously outperforms a state-of-the-art general-purpose optimization solver. Moreover, we present several managerial insights concerning synchronization, vehicles, and the placement of depot/satellite locations.