A New Heuristic Algorithm for the Traveling Salesman Problem

Abstract

The Traveling Salesman Problem (TSP) is one of the most prominent problems in combinatorial optimization. Although the problem has stimulated many efforts to find an efficient algorithm, no current algorithms are available which can solve the optimal solution for this problem in polynomial time. the aim of this paper is to present a new heuristic method for the TSP, which applies a constructive scheme and a local search procedure to improve the initial solution. the constructive scheme creates subroutes based on a minimum ratio test, and continues to pair locations until a feasible route is obtained. with this initial solution, a pairwise exchange heuristics improves the route until no exchanges yield an improvement. Numerical results illustrated that the heuristic method is an efficient algorithm for application to a variety of problems, such as the Vehicle Routing Problem (VRP) and Inventory Routing Problem (IRP).

Department(s)

Engineering Management and Systems Engineering

Keywords and Phrases

Heuristic algorithm; Improvement algorithm; IRP; Traveling salesman problem; VRP

Document Type

Article - Conference proceedings

Document Version

Citation

File Type

text

Language(s)

English

Rights

© 2024 Scimago Journal & Country Rank, All rights reserved.

Publication Date

01 Dec 2005

This document is currently not available here.

Share

 
COinS