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

    19 Citations (Scopus)

    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 statusPublished - 1 Mar 2021

    Keywords

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

    ASJC Scopus subject areas

    • General Engineering
    • 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