The Multicommodity-Ring Location Routing Problem

The multicommodity-ring location routing problem (MRLRP) studied in this paper is an NP-hard minimization problem arising in city logistics. The aim is to locate a set of urban distribution centers (UDCs) and to connect them via a ring in which massive flows of goods will circulate. Goods are transported from gates located outside the city to a UDC, and either join a second UDC through the ring before being delivered in electric vans to the final customers or are delivered directly to the customers from the first UDC. The reverse trip with pickup and transportation to the gates is also possible. A delivery service path starts at a particular UDC, then visits a subset of customers and ends at the same UDC, another UDC, or a self-service parking lot (SPL). A pickup route can start from an SPL or a UDC and ends at a UDC. The objective is to minimize the sum of the installation costs of the ring, flow transportation costs, and routing costs. The MRLRP belongs to the class of location-routing problems (LRP). We model it with a set-partitioning-like representation of delivery and pickup trips and arc-flow elements to describe goods transportation in the ring and between the ring and the gates. We present three approaches to solving the MRLRP: an exact method for small-size instances, a matheuristic for instances of a larger size, and a hybrid approach that applies the exact method to the columns output by the matheuristic. Numerical results are provided for an exhaustive set of instances, obtained by extending benchmark instances of the capacitated LRP with additional MRLRP features.