A fast two-level variable neighborhood search for the clustered vehicle routing problem. (July 2017)

• Record Type: Journal Article
• Authors: Defryn, Christof; Sörensen, Kenneth
• Is Part Of: Computers & operations research. Volume 83(2017)
• Page Start: 78
• Page End: 94
• Publication Date: 2017-07
• Subjects: Clustered vehicle routing problem -- Variable neighborhood search -- Metaheuristic; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2017.02.007
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: We propose a two-level variable neighborhood search algorithm for tackling the Clustered Vehicle Routing Problem. High quality solutions and new upper bounds are obtained in very short computing times. The solution approach does not require the distances to be Euclidean. A new variant of the problem (the Clustered Vehicle Routing Problem with weak cluster constraints) is formally introduced. Abstract: In this paper, we present an improved two-level heuristic to solve the clustered vehicle routing problem (CluVRP ). TheCluVRP is a generalization of the classical capacitated vehicle routing problem (CVRP ) in which customers are grouped into predefined clusters, and all customers in a cluster must be served consecutively by the same vehicle. This paper contributes to the literature in the following ways: (i) new upper bounds are presented for multiple benchmark instances, (ii) good heuristic solutions are provided in much smaller computing times than existing approaches, (iii) theCluVRP is reduced to its cluster level without assuming Euclidean coordinates or distances, and (iv) a new variant of theCluVRP, theCluVRP with weak cluster constraints, is introduced. In this variant, clusters are allocated to vehicles in their entirety, but all corresponding customers can be visited by the vehicle in any order. The proposed heuristic solves theCluVRP by combining two variable neighborhood search algorithms, that explore the solution space at the cluster level and the individual customer level respectively. The algorithm is tested on different benchmark instances from the literature with up to 484 nodes, obtaining high quality solutions while requiring only a limited calculation time.