Skip to main content

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

Sze, Jeeu Fong, Salhi, Said, Wassan, Niaz (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 0191-2615. (doi:10.1016/j.trb.2017.04.003) (KAR id:61598)

PDF Author's Accepted Manuscript
Language: English
Download (741kB) Preview
[img]
Preview
Official URL
http://dx.doi.org/10.1016/j.trb.2017.04.003

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
DOI/Identification number: 10.1016/j.trb.2017.04.003
Uncontrolled keywords: Metaheuristics; Cumulative capacitated vehicle routing; OR in disaster relief; Min-max; CCVRP managerial insights; Adaptive variable neighbourhood search
Subjects: Q Science > Operations Research - Theory
Divisions: Faculties > Social Sciences > Kent Business School > Centre for Logistics and Heuristic Organisation (CLHO)
Depositing User: Said Salhi
Date Deposited: 03 May 2017 09:24 UTC
Last Modified: 06 Feb 2020 09:45 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/61598 (The current URI for this page, for reference purposes)
Salhi, Said: https://orcid.org/0000-0002-3384-5240
Wassan, Niaz: https://orcid.org/0000-0003-0153-7646
  • Depositors only (login required):

Downloads

Downloads per month over past year