Solving Multiple Routes Travelling Salesman Problem Using Modified Genetic Algorithm

Muhammad Ridwan Andi Purnomo; Mohammad Iqbal; Mila Faila Sufa

doi:10.4028/www.scientific.net/AMR.576.718

Paper Titles

Productivity Study and Line Balancing of GGMG & CALICO Production Line
p.700

Workforce Assignment into Large-Sized Virtual Cells Using Learning Vector Quantization (LVQ) Approach
p.705

Optimization of Forecasting Moving Average Error in Probabilistic Demand Using Genetic Algorithm Based Fuzzy Logic
p.710

The Study on Production Performances of Part Transporter in Flexible Manufacturing System by Using Simulation Method
p.714

Solving Multiple Routes Travelling Salesman Problem Using Modified Genetic Algorithm
p.718

Economic Scenario of Cellulase Enzyme Production Using Palm Oil Mill Effluent (POME)
p.723

Applying Value Stream Mapping for Productivity Improvement of a Metal Stamping Industry
p.727

The Implementation of Lean Manufacturing in Malaysian Automotive Industry
p.731

Reducing Non-Value Added Process for an Automotive Component Using Finite Element Modeling
p.737

HomeAdvanced Materials ResearchAdvanced Materials Research Vol. 576Solving Multiple Routes Travelling Salesman...

Solving Multiple Routes Travelling Salesman Problem Using Modified Genetic Algorithm

Abstract:

The multiple routes travelling salesman problem (mrTSP) is an extension of the well-known travelling salesman problem (TSP), where there are several points clusters to be visited by salesman. The problem to be solved is how to define the best route in every cluster and initial position of each routes as interconnection points for the salesman. In this paper, modified genetic algorithm (mGA) is proposed in order to solve the mrTSP problem. In the proposed mGA, new heuristic algorithm for crossover and mutation operator based on local shortest path algorithm is proposed in order to assist the mGA to improve 'best solution so far'. Numerical examples are also given to test the performance of proposed mGA when solving mrTSP. The result of the study shows that the mGA is superior compared to conventional GA.

You might also be interested in these eBooks

Advances in Manufacturing and Materials Engineering (ICAMME)

View Preview

Info:

Periodical:

Advanced Materials Research (Volume 576)

Pages:

718-722

DOI:

https://doi.org/10.4028/www.scientific.net/AMR.576.718

Citation:

Cite this paper

Online since:

October 2012

Authors:

Muhammad Ridwan Andi Purnomo, Mohammad Iqbal, Mila Faila Sufa

Keywords:

Heuristic Crossover, Heuristic Mutation, Modified GA, Multiple Routes, TSP

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

Citation:

References

[1] Cheng, C.H., Gupta, Y.P., Lee, W.H. & Wong K.F. A TSP-based heuristic for forming machine groups and part families. International Journal of Production Research, 36 (1998) 1325-1337.

DOI: 10.1080/002075498193345

Google Scholar

[2] Phillips, J.M., Punnen, A.P. & Kabadi, S.N. A linear time algorithm for the bottleneck travelling salesman problem on a Halin graph. Information Processing Letters, 67 (1998) 105-110.

DOI: 10.1016/s0020-0190(98)00094-5

Google Scholar

[3] Ozgur, C.O. & Brown, J.R. A two-stage travelling salesman procedure for the single machine sequence-dependent scheduling problem. Omega, Int. J. Mgmt. Sci, 23 (1995) 205-219.

DOI: 10.1016/0305-0483(94)00057-h

Google Scholar

[4] Schneider, J. J & Kirkpatrick, S. Stochastic optimization. Springer-Verlag Berlin Heidelberg-Jerman, (2006).

Google Scholar

[5] Paletta, G. The period traveling salesman problem: a new heuristic algorithm. Computer & Operation Research, 29 (2002) 1343-1352.

DOI: 10.1016/s0305-0548(01)00035-1

Google Scholar

[6] Chao, D., Ye, C. & Miao, H. Two-level genetic algorithm for clustered traveling salesman problem with application in large-scale TSPs. Tsinghua Science and Technology, 12 (2007) 459-465.

DOI: 10.1016/s1007-0214(07)70068-8

Google Scholar

[7] Ghafurian, S. & Jafarian, N. An ant colony algorithm for solving fixed destination multi-depot multi traveling salesman problem. Applied Soft Computing, 11 (2007) 1256-1262.

DOI: 10.1016/j.asoc.2010.03.002

Google Scholar

[8] Liu, Y.H. A hybrid scatter search for the probabilistic traveling salesman problem. Computer & Operation Research, 34 (2007) 2949-2963.

DOI: 10.1016/j.cor.2005.11.008

Google Scholar

[9] Liu, Y.H. Different initial solution generators in genetic algorithms for solving the probabilistic traveling salesman problem. Applied Mathematics and Computation, 216 (2010) 125-137.

DOI: 10.1016/j.amc.2010.01.021

Google Scholar

[10] Hui, W. Comparison of several intelligent algorithms for solving TSP problem in industrial engineering. System Engineering Procedia, 4 (2012) 226-235.

DOI: 10.1016/j.sepro.2011.11.070

Google Scholar