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

作者：Yan Shangyao; Chu James C^*; Hsiao Fei Yen; Huang Han Jheng

来源：Computers & Industrial Engineering, 2015, 87: 383-393.

DOI：10.1016/j.cie.2015.05.034

• Multi-trip
• Split-delivery vehicle routing problem with time windows (SDVRPTW)
• Time-space network
• Integer multi-commodity network flow problem
• Heuristic algorithm

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.

• 出版日期2015-9
• 单位中央民族大学