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 language | English |
|---|---|
| Pages (from-to) | 93-107 |
| Number of pages | 15 |
| Journal | European Journal of Operational Research |
| Volume | 275 |
| Issue number | 1 |
| DOIs | |
| Publication status | Published - 16 May 2019 |
Fingerprint
Keywords
- Heuristics
- Multiple time windows
- Routing
- Security constraints
Cite this
}
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 Journal › Article › Academic › peer-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 -