A planning model and solution algorithm for multi-trip split-delivery vehicle routing and scheduling problems with time windows

• The single-trip assumption in SDVRPTW is relaxed to allow multi-trip routing.
• The time–space network method is used to formulate multi-trip SDVRPTW.
• Actual operating conditions for inventory replenishments are considered.
• A two-stage heuristic algorithm using problem decomposition is proposed.
• A real-world scale example is performed to test the methodology.

This study proposes a daily vehicle routing model for minimizing the total cost of replenishing inventory within a supply chain. The first major contribution of this research is to allow multiple use of vehicles in a split delivery vehicle routing problem with time windows (SDVRPTW), which is more realistic for various real-life applications. The multi-trip SDVRPTW (MTSDVRPTW) is formulated using the time–space network technique, which provides greater flexibility for formulating the complicated interactions between vehicles and products when multi-trip, split delivery, and delivery time windows are simultaneously considered. The resulting formulation of the MTSDVRPTW can be categorized as an integer multi-commodity network flow problem with side constraints. A two-step solution algorithm is proposed to solve this NP-hard problem, which is the second major contribution of this research. Finally, a real-world scale numerical example is performed to demonstrate and to test the methodology. The results indicate that these vehicle routing problems can be solved effectively and efficiently and that the proposed methodology has great potential for inventory replenishment scheduling where split deliveries and multiple trips for a single vehicle are allowed and time window constraints are imposed.