An effective Progressive Hedging algorithm for the two-layers time window assignment vehicle routing problem in a stochastic environment

Mahdi Jalilvand, Mahdi Bashiri, Erfaneh Nikzad

Research output: Contribution to journalArticlepeer-review

Abstract

This paper presents an effective Progressive Hedging algorithm for vehicle routing problem with two-layers time window assignment and stochastic service times (2L-TWAVRPSST). Based on a predefined exogenous time window determined by the customers, an endogenous time window is assigned to each customer. Endogenous time windows have flexible width and composed of two-layers. The outer layer is wider than inner layer and is determined by violation variable. This approach aims to giving more flexibility to career companies for serving more customers using less vehicles. Customers could be visited even after the end of their assigned time windows by paying proportional penalty, while extra violation from the outer layer is not permitted. This problem is formulated as a two-stage stochastic model with the first-stage decisions of assigning inner and outer layers time window. Then in the second stage, routes are planned for each scenario combination of stochastic demand and service time. The validity and effectiveness of the proposed model was examined by various numerical examples. The problem was solved by a Progressive Hedging (PH) algorithm for large-scale instances. The results confirm efficiency of the considered solution approach in different instances.

Original languageEnglish
Article number113877
JournalExpert Systems with Applications
Volume165
Early online date30 Aug 2020
DOIs
Publication statusE-pub ahead of print - 30 Aug 2020

Keywords

  • Progressive Hedging algorithm
  • Scenario decomposition
  • Stochastic programming
  • Stochastic service time
  • Time window assignment
  • Vehicle routing

ASJC Scopus subject areas

  • Engineering(all)
  • Computer Science Applications
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'An effective Progressive Hedging algorithm for the two-layers time window assignment vehicle routing problem in a stochastic environment'. Together they form a unique fingerprint.

Cite this