Vehicle routing with arrival time diversification

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

Unpredictable routes may be generated by varying the arrival time at each customer over successive visits. Inspired by a real-life case in cash distribution, this study presents an efficient solution approach for the vehicle routing problem with arrival time diversification by formulating it as a vehicle routing problem with multiple time windows in a rolling horizon framework. Because waiting times are not allowed, a novel algorithm is developed to efficiently determine whether routes or local search operations are time window feasible. To allow infeasible solutions during the heuristic search, four different penalty methods are proposed. The proposed algorithm and penalty methods are evaluated in a simple iterated granular tabu search that obtains new best-known solutions for all benchmark instances from the literature, decreasing average distance by 29% and reducing computation time by 93%. A case study is conducted to illustrate the practical relevance of the proposed model and to examine the trade-off between arrival time diversification and transportation cost.

Original languageEnglish
Pages (from-to)93-107
Number of pages15
JournalEuropean Journal of Operational Research
Volume275
Issue number1
DOIs
Publication statusPublished - 16 May 2019

Fingerprint

Vehicle Routing
Vehicle routing
Arrival Time
Diversification
Penalty Method
Vehicle Routing Problem
Time Windows
Average Distance
Tabu search
Heuristic Search
Tabu Search
Efficient Solution
Waiting Time
Local Search
Horizon
Customers
Trade-offs
Benchmark
Costs
Model

Keywords

  • Heuristics
  • Multiple time windows
  • Routing
  • Security constraints

Cite this

@article{75157af7fb304d40afe136ea8fe21e58,
title = "Vehicle routing with arrival time diversification",
abstract = "Unpredictable routes may be generated by varying the arrival time at each customer over successive visits. Inspired by a real-life case in cash distribution, this study presents an efficient solution approach for the vehicle routing problem with arrival time diversification by formulating it as a vehicle routing problem with multiple time windows in a rolling horizon framework. Because waiting times are not allowed, a novel algorithm is developed to efficiently determine whether routes or local search operations are time window feasible. To allow infeasible solutions during the heuristic search, four different penalty methods are proposed. The proposed algorithm and penalty methods are evaluated in a simple iterated granular tabu search that obtains new best-known solutions for all benchmark instances from the literature, decreasing average distance by 29{\%} and reducing computation time by 93{\%}. A case study is conducted to illustrate the practical relevance of the proposed model and to examine the trade-off between arrival time diversification and transportation cost.",
keywords = "Heuristics, Multiple time windows, Routing, Security constraints",
author = "Maaike Hoogeboom and Wout Dullaert",
year = "2019",
month = "5",
day = "16",
doi = "10.1016/j.ejor.2018.11.020",
language = "English",
volume = "275",
pages = "93--107",
journal = "European Journal of Operational Research",
issn = "0377-2217",
publisher = "Elsevier",
number = "1",

}

Vehicle routing with arrival time diversification. / Hoogeboom, Maaike; Dullaert, Wout.

In: European Journal of Operational Research, Vol. 275, No. 1, 16.05.2019, p. 93-107.

Research output: Contribution to JournalArticleAcademicpeer-review

TY - JOUR

T1 - Vehicle routing with arrival time diversification

AU - Hoogeboom, Maaike

AU - Dullaert, Wout

PY - 2019/5/16

Y1 - 2019/5/16

N2 - Unpredictable routes may be generated by varying the arrival time at each customer over successive visits. Inspired by a real-life case in cash distribution, this study presents an efficient solution approach for the vehicle routing problem with arrival time diversification by formulating it as a vehicle routing problem with multiple time windows in a rolling horizon framework. Because waiting times are not allowed, a novel algorithm is developed to efficiently determine whether routes or local search operations are time window feasible. To allow infeasible solutions during the heuristic search, four different penalty methods are proposed. The proposed algorithm and penalty methods are evaluated in a simple iterated granular tabu search that obtains new best-known solutions for all benchmark instances from the literature, decreasing average distance by 29% and reducing computation time by 93%. A case study is conducted to illustrate the practical relevance of the proposed model and to examine the trade-off between arrival time diversification and transportation cost.

AB - Unpredictable routes may be generated by varying the arrival time at each customer over successive visits. Inspired by a real-life case in cash distribution, this study presents an efficient solution approach for the vehicle routing problem with arrival time diversification by formulating it as a vehicle routing problem with multiple time windows in a rolling horizon framework. Because waiting times are not allowed, a novel algorithm is developed to efficiently determine whether routes or local search operations are time window feasible. To allow infeasible solutions during the heuristic search, four different penalty methods are proposed. The proposed algorithm and penalty methods are evaluated in a simple iterated granular tabu search that obtains new best-known solutions for all benchmark instances from the literature, decreasing average distance by 29% and reducing computation time by 93%. A case study is conducted to illustrate the practical relevance of the proposed model and to examine the trade-off between arrival time diversification and transportation cost.

KW - Heuristics

KW - Multiple time windows

KW - Routing

KW - Security constraints

UR - http://www.scopus.com/inward/record.url?scp=85057000493&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85057000493&partnerID=8YFLogxK

U2 - 10.1016/j.ejor.2018.11.020

DO - 10.1016/j.ejor.2018.11.020

M3 - Article

VL - 275

SP - 93

EP - 107

JO - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 1

ER -