Skip to main content

Research Repository

Advanced Search

A hyper-heuristic with two guidance indicators for bi-objective mixed-shift vehicle routing problem with time windows

Chen, Binhui; Qu, Rong; Bai, Ruibin; Laesanklang, Wasakorn

Authors

Binhui Chen Binhui.Chen@nottingham.ac.uk

Profile Image

RONG QU rong.qu@nottingham.ac.uk
Associate Professor

Ruibin Bai

Wasakorn Laesanklang



Abstract

In this paper, a Mixed-Shift Vehicle Routing Problem is proposed based on a real-life container transportation problem. In a long planning horizon of multiple shifts, transport tasks are completed satisfying the time constraints. Due to the different travel distance and time of tasks, there are two types of shifts (long shift and short shift) in this problem. The unit driver cost for long shifts is higher than that of short shifts. A mathematical model of this Mixed-Shift Vehicle Routing Problem with Time Windows (MS-VRPTW) is established in this paper, with two objectives of minimizing the total driver payment and the total travel distance.

Due to the large scale and nonlinear constraints, exact search showed not suitable to MS-VRPTW. An initial solution construction heuristic (EBIH) and a selective perturbation Hyper-Heuristic (GIHH) are thus developed. In GIHH, five heuristics with different extents of perturbation at the low level are adaptively selected by a high level selection scheme with Hill Climbing acceptance criterion. Two guidance indicators are devised at the high level to adaptively adjust the selection of the low level heuristics for this multi-objective problem. The two indicators estimate the objective value improvement and the improvement direction over the Pareto Front, respectively.

Citation

Chen, B., Qu, R., Bai, R., & Laesanklang, W. (2018). A hyper-heuristic with two guidance indicators for bi-objective mixed-shift vehicle routing problem with time windows. Applied Intelligence, 48(12), 4937–4959. https://doi.org/10.1007/s10489-018-1250-y

Journal Article Type Article
Acceptance Date Jul 12, 2018
Online Publication Date Aug 9, 2018
Publication Date Dec 1, 2018
Deposit Date Jul 26, 2018
Journal Applied Intelligence
Print ISSN 0924-669X
Electronic ISSN 1573-7497
Publisher Springer Verlag
Peer Reviewed Peer Reviewed
Volume 48
Issue 12
Pages 4937–4959
DOI https://doi.org/10.1007/s10489-018-1250-y
Keywords Hyper-heuristic; Mixed-shift vehicle routing problem with time windows; Bi-objective; Container transportation
Public URL http://eprints.nottingham.ac.uk/id/eprint/53156
Publisher URL https://link.springer.com/article/10.1007%2Fs10489-018-1250-y
Copyright Statement Copyright information regarding this work can be found at the following address: http://eprints.nottingham.ac.uk/end_user_agreement.pdf