Multi-Period Multi-Depot Vehicle Routing Problem for Mobile Center-Based Last Mile Delivery

초록

In response to the rapid growth of e-commerce and the resulting operational challenges in urban last mile logistics, this study introduces the Multi-period Multi-depot Vehicle Routing Problem with Mobile Center (MPMDVRP-MC). The proposed model jointly determines, over multiple periods, which candidate depot sites to activate for deploying mobile centers, how to assign customers to the activated sites, and how to construct capacity-feasible delivery routes, while allowing mobile centers to be opened, closed, and repositioned across days to respond to time-varying demand. We develop a mixed-integer linear programming (MILP) formulation and a genetic algorithm-based heuristic tailored to this multi-period setting. Computational experiments on adapted Solomon benchmark instances show that the heuristic matches or closely approximates MILP solutions on small instances and produces high-quality solutions on larger instances where the MILP frequently reaches the time limit or fails to prove optimality. Sensitivity analyses further reveal systematic trade-offs among travel, opening/operating, and repositioning costs, clarifying when the system behaves as a mobile, adaptive network versus a more static depot configuration. A case study using public parking-lot data from Seoul provides a proof-of-concept illustration of how repositioning can reduce travel costs under shifting demand patterns. Beyond cost efficiency, the mobile-center paradigm combined with light electric delivery modes has potential implications for reducing reliance on heavy vehicles in dense urban areas with fixed depot positions, which we discuss as a qualitative motivation.

키워드