The capacitated team orienteering problem with time windows (CTOPTW) is a NP-hard combinatorial optimization problem. In the CTOPTW, a set of customers is given each with a profit, a demand, a service time and a time window. A homogeneous fleet of vehicles is available for serving customers and collecting their associated profits. Each vehicle is constrained by a maximum tour duration and a limited capacity. The CTOPTW is concerned with the determination of a preset number of vehicle tours that begin and end at a depot, visit each customer no more than once while satisfying the time duration, time window and vehicle capacity constraints on each tour. The objective is to maximize the total profit collected. In this study we propose an iterated local search (ILS) algorithm to deal with the CTOPTW. ILS is a single solution based meta-heuristic that successively invokes a local search procedure to explore the solution space. A perturbation operator is used to modify the current local optimum solution in order to provide a starting solution for the local search procedure. As different problems and instances have different characteristics, the success of the ILS is highly dependent on the local search procedure, the perturbation operator(s) and the perturbation strength. The basic ILS uses a single perturbation operator and the perturbation strength remains the same during the optimization process. To address these issues, we use three different perturbation operators and a varying perturbation strength which changes as the algorithm progresses. The idea is to assign a larger perturbation strength in the early stages of the search in order to focus on exploring the search space. The perturbation strength is gradually decreased so that we focus more on exploitation. The computational results show that the proposed ILS algorithm is able to generate high quality solutions on the CTOPTW benchmark instances taken from the scientific literature, demonstrating its efficiency in terms of both the solution quality and computational time. Moreover, the proposed ILS produces 21 best known results and 5 new best solutions.

This paper presents a cooperative parallel tabu search meta-heuristic for the vehicle routing problem with time windows. It is based on the scheme in which several search threads cooperate by asynchronously exchanging information on the best solutions identified. The exchanges are performed through a mechanism called adaptive memory which holds and manages a pool of solutions. This enforces the asynchronous strategy of information exchanges and ensures the independence of the individual search threads. Each of these independent threads implements a tabu search meta-heuristic. Comprehensive computational experiments and comparisons to best known solutions show that the proposed cooperative parallel tabu search algorithm is able to achieve 48 new best solutions on VRPTW benchmark instances.