A variable neighborhood search for the capacitated vehicle routing problem with two-dimensional loading constraints

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review

89 Scopus Citations
View graph of relations

Author(s)

  • Lijun Wei
  • Zhenzhen Zhang
  • Defu Zhang
  • Andrew Lim

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)798-814
Journal / PublicationEuropean Journal of Operational Research
Volume243
Issue number3
Online published6 Jun 2015
Publication statusPublished - 16 Jun 2015

Abstract

This paper addresses the capacitated vehicle routing problem with two-dimensional loading constraints (2L-CVRP), which is a generalized capacitated vehicle routing problem in which customer demand is a set of two-dimensional, rectangular, weighted items. The objective is to design the route set of minimum cost for a homogenous fleet of vehicles, starting and terminating at a central depot, to serve all the customers. All the items packed in one vehicle must satisfy the two-dimensional orthogonal packing constraints. A variable neighborhood search is proposed to address the routing aspect, and a skyline heuristic is adapted to examine the loading constraints. To speed up the search process, an efficient data structure (Trie) is utilized to record the loading feasibility information of routes, but also to control the computational effort of the skyline spending on the same route. The effectiveness of our approach is verified through experiments on widely used benchmark instances involving two distinct versions of loading constraints (unrestricted and sequential versions). Numerical experiments show that the proposed method outperforms all existing methods and improves or matches the majority of best known solutions for both problem versions.

Research Area(s)

  • 2L-CVRP, Packing, Routing, Skyline heuristic, Variable neighborhood search

Citation Format(s)

A variable neighborhood search for the capacitated vehicle routing problem with two-dimensional loading constraints. / Wei, Lijun; Zhang, Zhenzhen; Zhang, Defu et al.
In: European Journal of Operational Research, Vol. 243, No. 3, 16.06.2015, p. 798-814.

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review