An Exact Approach for the Vehicle Routing Problem with Two-Dimensional Loading Constraints
An Exact Approach for the Vehicle Routing Problem with Two-Dimensional Loading Constraints
复制标题
DOI：
10.1287/trsc.1060.0165
复制
发表时间：
2007-05
期刊：
影响因子：
--
通讯作者：
M. Iori;Juan José SALAZAR-GONZÁLEZ;D. Vigo
中科院分区：
文献类型：
--
作者：
M. Iori;Juan José SALAZAR-GONZÁLEZ;D. Vigo
我们考虑了对称有能力车辆路径问题的一个特例，其中K辆相同的车辆必须为n个客户服务，每个客户都有一个给定的需求，包括一组矩形二维加权项目。车辆具有二维加载面和最大重量容量。其目的是将客户划分为总成本最小的路线，这样，对于每辆车，重量容量都被考虑在内，并且存在一个可行的将物品分配到装载面中的二维分配。该问题在货物运输中有几个实际应用，是强意义上的np困难问题。我们提出了一种精确的方法，基于分支切断算法，迭代调用分支定界算法来检查负载的可行性，以最小化路由成本。启发式也用于提高算法的整体性能。计算结果表明了该方法的有效性。
We consider a special case of the symmetric capacitated vehicle routing problem, in which a fleet of K identical vehicles must serve n customers, each with a given demand consisting in a set of rectangular two-dimensional weighted items. The vehicles have a two-dimensional loading surface and a maximum weight capacity. The aim is to find a partition of the customers into routes of minimum total cost such that, for each vehicle, the weight capacity is taken into account and a feasible two-dimensional allocation of the items into the loading surface exists. The problem has several practical applications in freight transportation, and it is NP-hard in the strong sense. We propose an exact approach, based on a branch-and-cut algorithm, for the minimization of the routing cost that iteratively calls a branch-and-bound algorithm for checking the feasibility of the loadings. Heuristics are also used to improve the overall performance of the algorithm. The effectiveness of the approach is shown by means of computational results.