A Multi-Trip Split-Delivery Vehicle Routing Problem with Time Windows for Inventory Replenishment Under Stochastic Travel Times

James C. Chu, Shangyao Yan, Han Jheng Huang

Research output: Contribution to journalArticlepeer-review

17 Scopus citations

Abstract

This study considers a multi-trip split-delivery vehicle routing problem with soft time windows for daily inventory replenishment under stochastic travel times. Considering uncertainty in travel times for vehicle routing problems is beneficial because more robust schedules can be generated and unanticipated consequences can be reduced when schedules are implemented in reality. However, uncertainties in model parameters have rarely been addressed for the problems in this category mainly due to the high problem complexity. In this study, an innovative and practical approach is proposed to consider stochastic travel times in the planning process. In the planning model, the possible outcomes of vehicle arrivals and product delivery at retailers are systematically categorized and their associated penalty and reward are estimated. Thus, unanticipated costs for every scheduling decision can be incorporated into the planning model to generate vehicle routing schedules that are more robust facing uncertain traffic conditions. To solve the model that is characterized as an NP-hard problem in a reasonable amount of time, a two-stage heuristic solution algorithm is proposed. Finally, the stochastic model is compared with the deterministic model in both planning and simulated operation stages using the data of a supply chain in Taiwan. The result confirms that the schedule generated by the stochastic model is more robust than the one created with the deterministic model because undesired outcomes such as unfulfilled demands are greatly reduced.

Original languageEnglish
Pages (from-to)41-68
Number of pages28
JournalNetworks and Spatial Economics
Volume17
Issue number1
DOIs
StatePublished - 1 Mar 2017

Keywords

  • Heuristic
  • Multi-trip split-delivery
  • Stochastic travel time
  • Time-space network
  • Vehicle routing problem with time windows

Fingerprint

Dive into the research topics of 'A Multi-Trip Split-Delivery Vehicle Routing Problem with Time Windows for Inventory Replenishment Under Stochastic Travel Times'. Together they form a unique fingerprint.

Cite this