A Branch-and-Price Algorithm for the Two-Echelon Vehicle Routing Problem with Time Windows and Time-Dependent Travel Times

Abstract

Urban logistics frequently relies on two-level distribution networks, where large vehicles deliver goods to intermediate facilities from which smaller vehicles complete last-mile deliveries in accessrestricted city centers, where travel times vary considerably throughout the day. Fluctuating traffic conditions directly affect route planning and time window feasibility. Yet most studies on vehicle routing simplify or ignore this effect, assuming static travel times throughout the planning horizon. In this paper, we propose a branch-and-price algorithm for the two-echelon vehicle routing problem with time windows and time-dependent travel times. A baseline model is formulated and evaluated through a preliminary computational study, yielding promising results that demonstrate the viability of the approach. We further discuss the limitations of the current model and outline targeted improvements aimed at solving instances of practical size to optimality, as well as establishing solid benchmarks for emerging heuristics.