The two-echelon location-routing problem with time windows: Formulation, branch-and-price, and clustering

In this study, we consider the two-echelon location-routing problem with time windows (2E-LRPTW) to address the strategic and tactical decisions of the urban freight transportation. In the rst echelon, freights are delivered from city distribution centers (CDCs) to intermediate facilities, called satellites, in large batches. In the second echelon, goods are consolidated into smaller vehicles to be delivered to the customers. Therefore, given a set of candidate CDC locations, a set of candidate satellite locations, and a set of customers, the 2E-LRPTW seeks the minimum total transportation cost consisting of CDC and satellite opening costs as well as rst and second echelon vehicle routing costs such that all costumer demands are satis ed. The problem is constrained by CDC, satellite, and vehicle capacities as well as customer time windows. We provide the set-partitioning formulation of the problem and propose an exact solution approach based on column generation. To tackle larger problems, we develop two heuristics based on hierarchical structure of the problem. Our computational study shows the performance of three approaches on solving a large set of problem instances with di erent sizes and characteristics and highlights the bene ts of using clustering-based heuristics to solve large-size instances.

Article

Download

View PDF