An Efficient Tabu Search based Procedure for Simultaneous Delivery and Pick-up Problem with Time Window

摘要

In this paper, we propose an Efficient Tabu Search based Procedure (ETSP) to solve the Vehicle Routing Problem with Simultaneous Delivery and Pick-up with Time Window (VRPSDPTW). We are given a set of identical vehicles (each having a capacity), a depot, and a set of customers with deterministic delivery and pick-up demands and time windows. The objective is to minimize the number of used vehicles and the total traveling costs related to the performed routes. ETSP is composed of two types of tabu search strategies, which are called TS I and TS II respectively. TS I only considers recording the shifted customers between the different vehicles by a two-dimensional tabu list. This strategy benefits a fast decreasing of the objective searching, but easily traps into the local optimum. On the other hand, TS II utilizes a three-dimensional array to record the detailed movement of each customer. This strategy is quite slow but easy to get rid of local optima. The search is performed by shifting between TS I and TS II. These two strategies complement each other's strengths and weaknesses, and the algorithm terminates when the two search methods cannot further improve the objective values. Computational experiments on benchmark instances from the literature show that the proposed algorithm can produce several better solutions than the previously published methods.