A Modified Genetic Algorithm for solving uncertain Constrained Solid Travelling Salesman Problems

doi:10.1016/j.cie.2015.02.023

Return

A Modified Genetic Algorithm for solving uncertain Constrained Solid Travelling Salesman Problems

2015-05-01

PRE

Samir Maity *

Arindam Roy

Manoranjan Maiti

DOI：10.1016/j.cie.2015.02.023

Original

Original request for help

Save

Abstract

En 中文

In this paper, a Modified Genetic Algorithm (MGA) is developed to solve Constrained Solid Travelling Salesman Problems (CSTSPs) in crisp, fuzzy, random, random-fuzzy, fuzzy-random and bi-random environments. In the proposed MGA, for the first time, a new 'probabilistic selection' technique and a 'comparison crossover' are used along with conventional random mutation. A Solid Travelling Salesman Problem (STSP) is a Travelling Salesman Problem (TSP) in which, at each station, there are a number of conveyances available to travel to another station. Thus STSP is a generalization of classical TSP and CSTSP is a STSP with constraints. In CSTSP, along each route, there may be some risk/discomfort in reaching the destination and the salesman desires to have the total risk/discomfort for the entire tour less than a desired value. Here we-model the CSTSP with traveling costs and route risk/discomfort factors as crisp, fuzzy, random, random-fuzzy, fuzzy-random and bi-random in nature. A number of benchmark problems from standard data set, TSPLIB are tested against the existing Genetic Algorithm (with Roulette Wheel Selection (RWS), cyclic crossover and random mutation) and the proposed algorithm and hence the efficiency of the new algorithm is established. In this paper, CSTSPs are illustrated numerically by some empirical data using this algorithm. In each environment, some sensitivity studies due to different risk/discomfort factors and other system parameters are presented. (c) 2015 Elsevier Ltd. All rights reserved.

Keywords:

STSP

CSTSP

Probabilistic selection

Comparison crossover

Modified Genetic Algorithm (MGA)

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.