A variable neighborhood search for the capacitated vehicle routing problem with two-dimensional loading constraints
A variable neighborhood search for the capacitated vehicle routing problem with two-dimensional loading constraints
复制标题
DOI：
10.1016/j.ejor.2014.12.048
复制
发表时间：
2015-06
期刊：
影响因子：
--
通讯作者：
Lijun Wei;Zhenzhen Zhang;Defu Zhang;A. Lim
中科院分区：
文献类型：
--
作者：
Lijun Wei;Zhenzhen Zhang;Defu Zhang;A. Lim
本文解决了具有二维负载约束的有能力车辆路径问题（2L-CVRP），这是一个广义的有能力车辆路径问题，其中客户需求是一组二维、矩形、加权项目。目标是为同质车队设计成本最低的路线集，在中央停车场出发和终止，为所有客户提供服务。一辆车内包装的所有物品必须满足二维正交包装约束。提出了可变邻域搜索来解决路由方面的问题，并采用天际线启发式来检查负载约束。为了加快搜索过程，利用高效的数据结构（Trie）来记录路线的加载可行性信息，同时也控制同一路线上天际线花费的计算量。通过对广泛使用的基准实例进行实验验证了我们方法的有效性，其中涉及两个不同版本的加载约束（无限制版本和顺序版本）。数值实验表明，所提出的方法优于所有现有方法，并改进或匹配两个问题版本的大多数最著名的解决方案。
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 (unrestrictedandsequentialversions). 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.