Strategic design of parcel locker networks for urban delivery

This paper focuses on the strategic design of a Parcel Locker (PL) network in the context of last-mile delivery. While PLs are emerging as a promising alternative to home delivery, their implementation poses practical challenges, including high deployment costs, inefficient capacity utilization, replenishment scheduling, and coordination with end users. To address this, we consider a network consisting of a depot, candidate locations for PLs, and service regions, each representing a group of customers with known aggregate daily demand distributed across multiple periods. Each period corresponds to a time window preferred by some customers for parcel pickup. The problem extends the classical location-routing problem by incorporating a multi-period horizon, a two-echelon network structure, and flexible replenishment planning. The objective is to minimize upfront strategic costs and anticipated operational costs over the network’s economic life. Strategic decisions concern selecting locations and capacities for PLs, and the size of a fleet to replenish PLs from the depot. Operational decisions, which can be revisited after the network is deployed, involve planning replenishment and routes over a single-day, multi-period horizon. The problem is formulated as a mixed-integer linear program and solved using a variable neighborhood search embedded in a branch-and-cut framework, leveraging tailored valid inequalities and local search moves. Computational experiments, along with a case study in Chicago using real data from Amazon, demonstrate that incorporating expected operational costs into network design process leads to more cost-efficient PL networks. Moreover, flexibility in replenishment planning affects both operational cost and network configuration, leading to further improvements in overall system efficiency.