TY - JOUR
T1 - A fast two-level variable neighborhood search for the clustered vehicle routing problem
AU - Defryn, Christof
AU - Sorensen, Kenneth
N1 - data source:
* GVRPθ3 instances (Battarra et al. 2014)
* variant of Golden instances (Expósito-Izquierdo et al. 2016)
* variant of Golden instances (Vidal et al. 2015)
Battarra, M. , Erdogan, G. , Vigo, D. ,2014. Exact algorithms for the clustered vehicle routing problem. Oper. Res. 62 (1), 58–71
Expósito-Izquierdo, C. , Rossi, A. , Sevaux, M. ,2016. A two-level solution approach to solve the clustered capacitated vehicle routing problem. Comput. Ind. Eng. 91, 274–289 .
Vidal, T. , Battarra, M. , Subramanian, A. , Erdogan, G. ,2015. Hybrid metaheuristics for the clustered vehicle routing problem. Comput. Oper. Res. 58, 87–99 .
PY - 2017/7
Y1 - 2017/7
N2 - In this paper, we present an improved two-level heuristic to solve the clustered vehicle routing problem (cluvrp). The cluvrp 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) the cluvrp is reduced to its cluster level without assuming euclidean coordinates or distances, and (iv) a new variant of the cluvrp, the cluvrpwith 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 the cluvrp 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.
AB - In this paper, we present an improved two-level heuristic to solve the clustered vehicle routing problem (cluvrp). The cluvrp 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) the cluvrp is reduced to its cluster level without assuming euclidean coordinates or distances, and (iv) a new variant of the cluvrp, the cluvrpwith 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 the cluvrp 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.
KW - Clustered vehicle routing problem
KW - Variable neighborhood search
KW - Metaheuristic
U2 - 10.1016/j.cor.2017.02.007
DO - 10.1016/j.cor.2017.02.007
M3 - Article
SN - 0305-0548
VL - 83
SP - 78
EP - 94
JO - Computers & Operations Research
JF - Computers & Operations Research
ER -