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

Shangyao Yan, James C. Chu, Fei Yen Hsiao, Han Jheng Huang

Research output: Contribution to journalArticlepeer-review

22 Scopus citations

Abstract

Abstract 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.

Original languageEnglish
Article number4068
Pages (from-to)383-393
Number of pages11
JournalComputers and Industrial Engineering
Volume87
DOIs
StatePublished - 13 Jun 2015

Keywords

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

Fingerprint

Dive into the research topics of 'A planning model and solution algorithm for multi-trip split-delivery vehicle routing and scheduling problems with time windows'. Together they form a unique fingerprint.

Cite this