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 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

[img]
Preview
PDF
The cumulative capacitated vehicle routing problem (abstract).pdf

Download (191kB) | Preview

Abstract

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.

Item Type: Article
Uncontrolled Keywords: Metaheuristics; Cumulative capacitated vehicle routing; OR in disaster relief; Min-max; CCVRP managerial insights; Adaptive variable neighbourhood search, unimas, university, universiti, Borneo, Malaysia, Sarawak, Kuching, Samarahan, ipta, education, research, Universiti Malaysia Sarawak
Subjects: H Social Sciences > HE Transportation and Communications
T Technology > T Technology (General)
Divisions: Academic Faculties, Institutes and Centres > Faculty of Computer Science and Information Technology
Depositing User: Ibrahim
Date Deposited: 24 May 2017 06:16
Last Modified: 24 May 2017 06:16
URI: http://ir.unimas.my/id/eprint/16359

Actions (For repository members only: login required)

View Item View Item