A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service
A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service
复制标题
DOI：
10.1016/j.cor.2004.07.009
复制
发表时间：
2006-03
期刊：
影响因子：
--
通讯作者：
Fermín Alfredo Tang Montané;R. D. Galvão
中科院分区：
文献类型：
--
作者：
Fermín Alfredo Tang Montané;R. D. Galvão
同时取货和送货的车辆路径问题（VRP_SPD）是经典车辆路径问题（VRP）的一个变种，客户需要同时取货和送货服务。在车辆服务开始时，从一个仓库提供货物，而在服务结束时，将货物运送到同一个仓库。该问题的一个重要特征是，车辆在任何给定路线上的载荷是拾取载荷和递送载荷的混合。本文提出了一种禁忌搜索算法来求解VRP_SPD。该算法使用三种类型的运动来获得路线间的相邻解：重新定位，交换和交叉运动。一个2-opt程序是用来获得替代路由内的解决方案。实施了四种类型的街区，其中三种是通过使用每一种单一的路线间移动来定义的，第四种是通过使用这些移动的组合来定义的。采用两种不同的搜索策略来选择下一个运动：第一允许运动和最佳允许运动。通过频率惩罚实现了搜索的强化和多样化。计算结果报告了一组87个测试问题与50和400个客户端之间。
The vehicle routing problem with simultaneous pick-up and delivery (VRP_SPD) is a variant of the classical vehicle routing problem (VRP) where clients require simultaneous pick-up and delivery service. Deliveries are supplied from a single depot at the beginning of the vehicle's service, while pick-up loads are taken to the same depot at the conclusion of the service. One important characteristic of this problem is that a vehicle's load in any given route is a mix of pick-up and delivery loads. In this paper we develop a tabu search algorithm to solve VRP_SPD. This algorithm uses three types of movements to obtain inter-route adjacent solutions: the relocation, interchange and crossover movements. A 2-opt procedure is used to obtain alternative intra-route solutions. Four types of neighbourhoods were implemented, three of them defined by the use of each of the single inter-route movements and the fourth by using a combination of these movements. Two different search strategies were implemented for selecting the next movement: first admissible movement and best admissible movement. Intensification and diversification of the search were achieved through frequency penalization. Computational results are reported for a set of 87 test problems with between 50 and 400 clients.