An iterated local search for the Traveling Salesman Problem with release dates and completion time minimization. (October 2018)

• Record Type: Journal Article
• Authors: Archetti, Claudia; Feillet, Dominique; Mor, Andrea; Speranza, M. Grazia
• Is Part Of: Computers & operations research. Volume 98(2018)
• Page Start: 24
• Page End: 37
• Publication Date: 2018-10
• Subjects: Traveling Salesman Problem with release dates -- Heuristics -- Matheuristics -- Iterated local search; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2018.05.001
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: We consider the TSP with release date and completion time minimization. We devise some properties of the problem and describe an approximation algorithm. We propose a mathematical programming formulation and present a heuristic approach. The mathematical formulation has allowed us to solve to optimality instances with up to 20 customers. Using MILP models as a repair operator has not turned out to be beneficial for the solution of the problem. Abstract: In the Traveling Salesman Problem (TSP) with release dates and completion time minimization an uncapacitated vehicle delivers to customers goods which arrive at the depot over time. A customer cannot be served before the demanded goods arrive at the depot. A release date is associated with each customer which represents the time at which the goods requested by the customer arrive at the depot. The vehicle may perform multiple routes, all starting and ending at the depot. The release dates of the customers served in each route must be not larger than the time at which the route starts. The objective of the problem is to minimize the total time needed to serve all customers, given by the sum of the traveling time and the waiting time at the depot. The waiting time is due to the fact that the vehicle has to wait at the depot until the latest release date of the customers it is going to serve in the next route. We introduce some properties, propose a mathematical programming formulation and present a heuristic approach based on an iterated local search where the perturbation is performed by means of a destroy-and-repair method. Two alternative repair operators, one simple and fast and the other based on a mathematical programming model, are proposed, which give rise to two variants of the heuristic. The mathematical formulation is used to find the optimal solution on instances with up to 20 customers, built from benchmark instances for the classical TSP. Comparison with optimal solutions shows that both algorithms provide high-quality solutions. Tests are also made on larger instances to compare the performance of the two variants of the heuristic.