Operations Research Applications in the Last Mile Distribution System

Mengtong Wang
Department of Industrial Engineering
Tsinghua University, China

Nowadays, the last mile distribution system accounts for about 30% of the total distribution cost, which has become the biggest problem plaguing logistics companies, e-commerce companies and related businesses. These organizations face a tradeoff between controlling the cost for logistics and enhancing customer experience. Improving the quality of service may incur unbearably high distribution costs while decreasing the cost of logistics may degrade the service quality. In contrast to the conventional parcel delivery, diversified delivery services are more attractive in the context of e-commerce last mile delivery. For example, many major e-tailers such as Amazon or JD maintain their own fleet to handle same-day deliveries (McKinsey & Company, 2014). Similarly, some logistics companies like Australia Post provide self-pick-up service for customers by placing parcel lockers at opportune locations. In addition, increasing awareness about the need for alleviating the environmental footprint of logistics operations has increased the necessity of reverse logistics and accelerated the adoption of low-emission vehicles (e.g., electric vehicles). For example, UPS has recently expanded the size of its fleet of electric vehicles (EVs) by working with a wide array of manufacturers (UPS, 2018).

Within this context, logistics companies face many issues and interesting problems which fit well within the optimization framework. For example, companies need to decide whether to incorporate new delivery services or EVs into their current distribution systems. Companies also need to consider which delivery services to select, such as home delivery, collection of convenience stores or parcel lockers. Finally, a key issue for companies is to redesign their pickup and delivery options while reducing the total cost as much as possible. Applying operations research techniques can provide invaluable help in addressing these issues to achieve better decision-making. Many of the relevant optimization problems have been well studied by researchers.

The most relevant problem for last mile delivery operations is the two-echelon vehicle routing problem with covering options (2E-VRP-CO) developed by Enthoven et al. (2020). In their study, they consider a two-echelon distribution system including the last mile distribution system as the second echelon. Customers can be served by home delivery (cargo bikes) or parcel lockers within a specified covering range. They also design an efficient adaptive large neighborhood search (ALNS) heuristic for the 2E-VRP-CO to provide high quality and near optimal solutions for real-sized instances. It is worth mentioning that ALNS proposed in Ropke and Pisinger (2006) has been successfully used on related vehicle routing problems (VRPs) and location routing problems (LRPs). The ALNS is based on the heuristic algorithm of destroy and repair mechanisms and has strong universality since it does not depend on the specific problem structure.

Another related problem is the vehicle routing with demand allocation problem (VRDAP) proposed by Reihaneh and Ghoniem (2019). This problem arises in the food bank distribution system. The decision-maker tries to assign customers to delivery sites and route a fleet of vehicles to deliver goods from a central depot to designated delivery sites. The authors investigated an effective branch-and-price (B&P) algorithm to provide optimal solutions. Furthermore, computational results demonstrated that the proposed algorithm greatly outperforms commercial solvers such as CPLEX and decomposition-based heuristics in the literature. In fact, due to the high input and operating costs, many practical scenarios of the problem require high accuracy of solutions. Therefore, the application of exact algorithms, such as branch-and-price-and-cut (B&P&C) algorithm, is quite important for making profitable decisions. We refer the reader to Costa et al. (2019) for a survey on the leading B&P&C algorithms for VRPs.

Currently, a wide range of relevant research problems are also related to the use of EVs for goods distribution. Recent publications mainly focus on the following three aspects: (a) the charging strategies of EVs (partial recharges or full recharges), (b) the locations of charging facilities (recharging stations or battery swapping stations), (c) the uncertainty related to batteries (travel range or energy consumption). For the first two aspects, researchers usually define the battery level and the location of charging stations as new decision variables, respectively. For the last aspect, approaches that integrate uncertainty into optimization models, stochastic optimization and robust optimization, are developed to solve problems. Gounaris et al. (2013) study several VRP variants with uncertain demand and Costa et al. (2019) provide an extensive review of exact algorithms for the robust VRPs. In general, new problems can be solved by extending or modifying existing problems, and then the existing algorithms can be applied to solve the problems. Hence, we refer the reader to Savelsbergh and Van Woensel (2016) for a survey on the solution methodologies for city logistics. For recent surveys of the related technological and marketing background of EVs, we refer the reader to Pelletier et al. (2016). For a comprehensive overview of optimization models for EVs, we refer the reader to Shen et al. (2019).

To conclude, the technological edge and convenience offered by e-commerce has driven a steady increase of parcel volumes, which accentuates the pressure on last-mile delivery systems and leads to a demand for new logistics solutions. Therefore, applying operations research methods to optimize the last mile distribution system in order to realize resource sharing and improve service quality is particularly important.



Costa, L., Contardo, C., & Desaulniers, G. (2019). Exact Branch-Price-and-Cut Algorithms for Vehicle Routing. Transportation Science, 53(4), 946-985.

Enthoven, D. L., Jargalsaikhan, B., Roodbergen, K. J., Broek, M. A., & Schrotenboer, A. H. (2020). The two-echelon vehicle routing problem with covering options: City logistics with cargo bikes and parcel lockers. Computers & Operations Research.

Gounaris, C. E., Wiesemann, W., & Floudas, C. A. (2013). The Robust Capacitated Vehicle Routing Problem Under Demand Uncertainty. Operations Research, 61(3), 677-693.

McKinsey&Company. (2014). Same-day delivery: The next evolutionary step in parcel logistics. URL https://www.mckinsey.com/industries/travel-transport-and-logistics/our- insights/ same-day-delivery-the-next-evolutionary-step-in-parcel-logistics.

Pelletier, S., Jabali, O., & Laporte, G. (2016). 50th Anniversary Invited Article-Goods Distribution with Electric Vehicles: Review and Research Perspectives. Transportation Science, 50(1), 3-22.

Ropke, S., & Pisinger, D. (2006). An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows. Transportation Science, 40(4), 455- 472.

Reihaneh, M., & Ghoniem, A. (2019). A branch-and-price algorithm for a vehicle routing with demand allocation problem. European Journal of Operational Research, 272(2), 523-538.

Savelsbergh, M. M., & Van Woensel, T. (2016). 50th Anniversary Invited Article—City Logistics: Challenges and Opportunities. Transportation Science, 50(2), 579-590.

UPS. (2018). Initiative supports continued strategic electrification of ups global fleet. URL https://pressroom.ups.com/pressroom/ContentDetailsViewer.page?ConceptType=Press Releases&id= 1532964104882-384.