tailieunhanh - An efficient general variable neighborhood search for large travelling salesman problem with time windows

General Variable Neighborhood Search (GVNS) is shown to be a powerful and robust methodology for solving travelling salesman and vehicle routing problems. However, its efficient implementation may play a significant role in solving large size instances. In this paper we suggest new GVNS heuristic for solving Travelling salesman problem with time windows. | Yugoslav Journal of Operations Research 23 (2013), Number 1, 19-30 DOI: AN EFFICIENT GENERAL VARIABLE NEIGHBORHOOD SEARCH FOR LARGE TRAVELLING SALESMAN PROBLEM WITH TIME WINDOWS Nenad MLADENOVIĆ School of Mathematics, Brunel University-West London, UK, Raca TODOSIJEVIĆ Mathematical Institute, Serbian Academy of Science and Arts, Serbia, racatodosijevic@ Dragan UROŠEVIĆ Mathematical Institute, Serbian Academy of Science and Arts, Serbia, Received: Маy 2012 / Accepted: August 2012 Abstract: General Variable Neighborhood Search (GVNS) is shown to be a powerful and robust methodology for solving travelling salesman and vehicle routing problems. However, its efficient implementation may play a significant role in solving large size instances. In this paper we suggest new GVNS heuristic for solving Travelling salesman problem with time windows. It uses different set of neighborhoods, new feasibility checking procedure and a more efficient data structure than the recent GVNS method that can be considered as a state-of-the-art heuristic. As a result, our GVNS is much faster and more effective than the previous GVNS. It is able to improve 14 out of 25 best known solutions for large test instances from the literature. Keywords: Travelling Salesman Problem, Time windows, Variable Neighborhood Search. MSC: 90C59, 90B06. 20 N. Mladenović, R. Todosijević and D. Urošević / An Efficient General Variable 1. INTRODUCTION The Travelling Salesman Problem with Time Windows (TSPTW) is a variant of the well-known Travelling Salesman Problem (TSP). Suppose that a depot, a set of customers, service time (., the time that must be spent at the customer), and a time window (. its ready time and due date) are given. The TSPTW problem consists of finding a minimum cost tour starting and ending at a given depot, after each customer is visited only once before its due date. The travelling salesman