The cumulative capacitated vehicle routing problem with min-sum and min-max objectives: An effective hybridisation of adaptive variable neighbourhood search and large neighbourhood search
The cumulative capacitated vehicle routing problem (CCVRP) is a relatively new variant of the classical capacitated vehicle routing problem in which the objective is to minimise the sum of arrival times at customers (min-sum) instead of the total route distance. While the literature for the CCVRP is...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Elsevier Ltd
2017
|
| Subjects: | |
| Online Access: | http://ir.unimas.my/id/eprint/16359/ http://ir.unimas.my/id/eprint/16359/1/The%20cumulative%20capacitated%20vehicle%20routing%20problem%20%28abstract%29.pdf |
| _version_ | 1848838046828462080 |
|---|---|
| author | Jeeu, Fong Sze Said, Salhi Niaz, A. Wassan |
| author_facet | Jeeu, Fong Sze Said, Salhi Niaz, A. Wassan |
| author_sort | Jeeu, Fong Sze |
| building | UNIMAS Institutional Repository |
| collection | Online Access |
| description | The cumulative capacitated vehicle routing problem (CCVRP) is a relatively new variant of the classical capacitated vehicle routing problem in which the objective is to minimise the sum of arrival times at customers (min-sum) instead of the total route distance. While the literature for the CCVRP is scarce, this problem has useful applications especially in the area of supplying humanitarian aid after a natural disaster. In this paper, a two-stage adaptive variable neighbourhood search (AVNS) algorithm that incorporates large neighbourhood search (LNS) as a diversification strategy is proposed. When tested on the benchmark data sets, the results show that the proposed AVNS is highly competitive in producing new best known solutions to more than half of the instances. An alternative but related objective that minimises the maximum arrival time (min-max) is also explored in this study demonstrating the flexibility and the effectiveness of the proposed metaheuristic. To the best of our knowledge, this is the first study that exploits the min-max objective of the CCVRP in addition to providing extensive computational results for a large number of instances for the min-sum. As a by-product of this study, managerial insights for decision making are also presented. |
| first_indexed | 2025-11-15T06:49:20Z |
| format | Article |
| id | unimas-16359 |
| institution | Universiti Malaysia Sarawak |
| institution_category | Local University |
| language | English |
| last_indexed | 2025-11-15T06:49:20Z |
| publishDate | 2017 |
| publisher | Elsevier Ltd |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | unimas-163592022-09-29T03:27:57Z http://ir.unimas.my/id/eprint/16359/ The cumulative capacitated vehicle routing problem with min-sum and min-max objectives: An effective hybridisation of adaptive variable neighbourhood search and large neighbourhood search Jeeu, Fong Sze Said, Salhi Niaz, A. Wassan HE Transportation and Communications T Technology (General) The cumulative capacitated vehicle routing problem (CCVRP) is a relatively new variant of the classical capacitated vehicle routing problem in which the objective is to minimise the sum of arrival times at customers (min-sum) instead of the total route distance. While the literature for the CCVRP is scarce, this problem has useful applications especially in the area of supplying humanitarian aid after a natural disaster. In this paper, a two-stage adaptive variable neighbourhood search (AVNS) algorithm that incorporates large neighbourhood search (LNS) as a diversification strategy is proposed. When tested on the benchmark data sets, the results show that the proposed AVNS is highly competitive in producing new best known solutions to more than half of the instances. An alternative but related objective that minimises the maximum arrival time (min-max) is also explored in this study demonstrating the flexibility and the effectiveness of the proposed metaheuristic. To the best of our knowledge, this is the first study that exploits the min-max objective of the CCVRP in addition to providing extensive computational results for a large number of instances for the min-sum. As a by-product of this study, managerial insights for decision making are also presented. Elsevier Ltd 2017-07-01 Article PeerReviewed text en http://ir.unimas.my/id/eprint/16359/1/The%20cumulative%20capacitated%20vehicle%20routing%20problem%20%28abstract%29.pdf Jeeu, Fong Sze and Said, Salhi and Niaz, A. Wassan (2017) The cumulative capacitated vehicle routing problem with min-sum and min-max objectives: An effective hybridisation of adaptive variable neighbourhood search and large neighbourhood search. Transportation Research Part B: Methodological, 101. pp. 162-184. ISSN 01912615 http://www.sciencedirect.com/science/article/pii/S0191261516308396 DOI: 10.1016/j.trb.2017.04.003 |
| spellingShingle | HE Transportation and Communications T Technology (General) Jeeu, Fong Sze Said, Salhi Niaz, A. Wassan The cumulative capacitated vehicle routing problem with min-sum and min-max objectives: An effective hybridisation of adaptive variable neighbourhood search and large neighbourhood search |
| title | The cumulative capacitated vehicle routing problem with min-sum and min-max objectives: An effective hybridisation of adaptive variable neighbourhood search and large neighbourhood search |
| title_full | The cumulative capacitated vehicle routing problem with min-sum and min-max objectives: An effective hybridisation of adaptive variable neighbourhood search and large neighbourhood search |
| title_fullStr | The cumulative capacitated vehicle routing problem with min-sum and min-max objectives: An effective hybridisation of adaptive variable neighbourhood search and large neighbourhood search |
| title_full_unstemmed | The cumulative capacitated vehicle routing problem with min-sum and min-max objectives: An effective hybridisation of adaptive variable neighbourhood search and large neighbourhood search |
| title_short | The cumulative capacitated vehicle routing problem with min-sum and min-max objectives: An effective hybridisation of adaptive variable neighbourhood search and large neighbourhood search |
| title_sort | cumulative capacitated vehicle routing problem with min-sum and min-max objectives: an effective hybridisation of adaptive variable neighbourhood search and large neighbourhood search |
| topic | HE Transportation and Communications T Technology (General) |
| url | http://ir.unimas.my/id/eprint/16359/ http://ir.unimas.my/id/eprint/16359/ http://ir.unimas.my/id/eprint/16359/ http://ir.unimas.my/id/eprint/16359/1/The%20cumulative%20capacitated%20vehicle%20routing%20problem%20%28abstract%29.pdf |