A hyper-heuristic with two guidance indicators for bi-objective mixed-shift vehicle routing problem with time windows
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 distances and time of tasks, there are two...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Springer
2018
|
| Subjects: | |
| Online Access: | https://eprints.nottingham.ac.uk/53488/ |
| _version_ | 1848798948051910656 |
|---|---|
| author | Chen, Binhui Qu, Rong Bai, Ruibin Laesanklang, Wasakorn |
| author_facet | Chen, Binhui Qu, Rong Bai, Ruibin Laesanklang, Wasakorn |
| author_sort | Chen, Binhui |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | 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 distances 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, the exact search showed is 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 the 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 bi-objective problem. The two indicators estimate the objective value improvement and the improvement direction over the Pareto Front, respectively. To evaluate the generality of the proposed algorithms, a set of benchmark instances with various features is extracted from real-life historical datasets. The experiment results show that GIHH significantly improves the quality of the final Pareto Solution Set, outperforming the state-of-the-art algorithms for similar problems. Its application on VRPTW also obtains promising results. |
| first_indexed | 2025-11-14T20:27:52Z |
| format | Article |
| id | nottingham-53488 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| language | English |
| last_indexed | 2025-11-14T20:27:52Z |
| publishDate | 2018 |
| publisher | Springer |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-534882021-06-07T07:33:24Z https://eprints.nottingham.ac.uk/53488/ 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 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 distances 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, the exact search showed is 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 the 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 bi-objective problem. The two indicators estimate the objective value improvement and the improvement direction over the Pareto Front, respectively. To evaluate the generality of the proposed algorithms, a set of benchmark instances with various features is extracted from real-life historical datasets. The experiment results show that GIHH significantly improves the quality of the final Pareto Solution Set, outperforming the state-of-the-art algorithms for similar problems. Its application on VRPTW also obtains promising results. Springer 2018-08-09 Article PeerReviewed application/pdf en cc_by https://eprints.nottingham.ac.uk/53488/1/s10489-018-1250-y.pdf Chen, Binhui, Qu, Rong, Bai, Ruibin and Laesanklang, Wasakorn (2018) A hyper-heuristic with two guidance indicators for bi-objective mixed-shift vehicle routing problem with time windows. Applied Intelligence . ISSN 1573-7497 Hyper-heuristic; Mixed-shift vehicle routing problem with time windows; Bi-objective; Container transportation http://dx.doi.org/10.1007/s10489-018-1250-y doi:10.1007/s10489-018-1250-y doi:10.1007/s10489-018-1250-y |
| spellingShingle | Hyper-heuristic; Mixed-shift vehicle routing problem with time windows; Bi-objective; Container transportation Chen, Binhui Qu, Rong Bai, Ruibin Laesanklang, Wasakorn A hyper-heuristic with two guidance indicators for bi-objective mixed-shift vehicle routing problem with time windows |
| title | A hyper-heuristic with two guidance indicators for bi-objective mixed-shift vehicle routing problem with time windows |
| title_full | A hyper-heuristic with two guidance indicators for bi-objective mixed-shift vehicle routing problem with time windows |
| title_fullStr | A hyper-heuristic with two guidance indicators for bi-objective mixed-shift vehicle routing problem with time windows |
| title_full_unstemmed | A hyper-heuristic with two guidance indicators for bi-objective mixed-shift vehicle routing problem with time windows |
| title_short | A hyper-heuristic with two guidance indicators for bi-objective mixed-shift vehicle routing problem with time windows |
| title_sort | hyper-heuristic with two guidance indicators for bi-objective mixed-shift vehicle routing problem with time windows |
| topic | Hyper-heuristic; Mixed-shift vehicle routing problem with time windows; Bi-objective; Container transportation |
| url | https://eprints.nottingham.ac.uk/53488/ https://eprints.nottingham.ac.uk/53488/ https://eprints.nottingham.ac.uk/53488/ |