Recombination Operators in Permutation-Based Evolutionary Algorithms for the Travelling Salesman Problem

Recombination Operators in Permutation-Based Evolutionary Algorithms for the Travelling Salesman Problem

Camelia Chira (Babes-Bolyai University, Romania) and Anca Gog (Babes-Bolyai University, Romania)
DOI: 10.4018/978-1-4666-0297-7.ch010
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

The Travelling Salesman Problem (TSP) is one of the most widely studied optimization problems due to its many applications in domains such as logistics, planning, routing, and scheduling. Approximation algorithms to address this NP-hard problem include genetic algorithms, ant colony systems, and simulated annealing. This chapter concentrates on the evolutionary approaches to TSP based on permutation encoded individuals. A comparative analysis of several recombination operators is presented based on computational experiments for TSP instances and a generalized version of TSP. Numerical results emphasize a good performance of two proposed crossover schemes: best-worst recombination and best order recombination which take into account information from the global best and/or worst individuals besides the genetic material from parents.
Chapter Preview
Top

2. The Travelling Salesman Problem

Given a list of cities and a starting point, a travelling salesman has to visit every city exactly once and then return to the starting city. A set of k points in a plane is given, corresponding to the location of k cities. The objective is to find the shortest route for the travelling salesman. The number of possible tours for k cities is (k-1)!/2 which represents a very large search space.

The Travelling Salesman Problem (TSP) can be formalized as follows. A set of k citiesis given. For each pair

Letbe the distance between the city and the city

Complete Chapter List

Search this Book:
Reset