A multi-start evolutionary local search for the two-dimensional loading capacitated vehicle routing problem
A multi-start evolutionary local search for the two-dimensional loading capacitated vehicle routing problem
复制标题
DOI：
10.1016/j.cor.2010.08.017
复制
发表时间：
2011-03
期刊：
影响因子：
--
通讯作者：
C. Duhamel;P. Lacomme;A. Quilliot;H. Toussaint
中科院分区：
文献类型：
--
作者：
C. Duhamel;P. Lacomme;A. Quilliot;H. Toussaint
本文讨论了扩展的能力约束车辆路径问题，客户需求是由二维加权项目（2L-CVRP）。该目标包括在设计一组行程最小化的总运输成本与同质车队的车辆的基础上的一个仓库节点。每个车辆行程中的物品必须满足二维正交包装约束。提出了一种GRASP×ELS算法，将负荷约束转化为资源约束的项目调度问题（RCPSP）求解。我们把这个放松的问题称为RCPSP-CVRP。该优化框架处理RCPSP-CVRP，最后通过解决一个专用的包装问题将RCPSP-CVRP解决方案转化为2L-CVRP解决方案。通过经典CVRP和2L-CVRP实例的计算实验证明了该方法的有效性。数值实验表明，GRASP×ELS方法的性能优于以往的所有方法.
This paper addresses an extension of the capacitated vehicle routing problem where customer demand is composed of two-dimensional weighted items (2L-CVRP). The objective consists in designing a set of trips minimizing the total transportation cost with a homogenous fleet of vehicles based on a depot node. Items in each vehicle trip must satisfy the two-dimensional orthogonal packing constraints. A GRASP×ELS algorithm is proposed to compute solutions of a simpler problem in which the loading constraints are transformed into resource constrained project scheduling problem (RCPSP) constraints. We denote this relaxed problem RCPSP-CVRP. The optimization framework deals with RCPSP-CVRP and lastly RCPSP-CVRP solutions are transformed into 2L-CVRP solutions by solving a dedicated packing problem. The effectiveness of our approach is demonstrated through computational experiments including both classical CVRP and 2L-CVRP instances. Numerical experiments show that the GRASP×ELS approach outperforms all previously published methods.