A Location-Routing Problem With Multiple Trips Arising In E-Commerce Delivery

Official URL: https://risc01.sabanciuniv.edu/record=b3205831

The classical location routing problem (LRP) is a well studied combinatorial optimization problem that aims to identify optimal depot location(s) and the routing decisions. In this study, we consider a two-echelon location routing problem with multiple trips under constrained distances as a generalization of the traditional LRP. Given the location of the single distribution center, we determine the locations of the regional depots among a set of candidate locations and decide how to serve the customers - from which regional depot and via which route. We consider a setting where vehicles can perform multiple trips originated from their regional depots as long as the total distance traveled does not exceed a predetermined level. We develop different mathematical models for the problem and strengthen them with simple valid inequalities. We also propose a heuristic solution method that gives feasible solutions in reasonable times even for very large problem instances. The computational experiments are designed and conducted to observe the performance of all formulations and enhancements for solving different problem sizes and parameter settings. The results of the computational experiments show that using valid inequalities improves the solution performance and different modeling approaches perform differently in terms of their run-time and solution quality in small and large instances.