A neural network approach for the solution of Traveling Salesman and basic vehicle routing problems

Persistent Link:
http://hdl.handle.net/10150/282498
Title:
A neural network approach for the solution of Traveling Salesman and basic vehicle routing problems
Author:
Ghamasaee, Rahman, 1953-
Issue Date:
1997
Publisher:
The University of Arizona.
Rights:
Copyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.
Abstract:
Easy to explain and difficult to solve, the traveling salesman problem, TSP, is to find the minimum distance Hamiltonian circuit on a network of n cities. The problem cannot be solved in polynomial time, that is, the maximum number of computational steps needed to find the optimum solution grows with n faster than any power of n. Very good combinatoric solution approaches including heuristics with worst case lower bounds, exist. Neural network approaches for solving TSP have been proposed recently. In the elastic net approach, the algorithm begins from m nodes on a small circle centered on the centroid of the distribution of cities. Each node is represented by the coordinates of the related point in the plane. By successive recalculation of the position of nodes, the ring is gradually deformed, and finally it describes a tour around the cities. In another approach, the self organizing feature map, SOFM, which is based on Kohonen's idea of winner takes all, fewer than m nodes are updated at each iteration. In this dissertation I have integrated these two ideas to design a hybrid method with faster convergence to a good solution. On each iteration of the original elastic net method two nx m matrices of connection weights and inter node-city distances must be calculated. In our hybrid method this has been reduced to the calculation of one row and one column of each matrix, thus, If the computational complexity of the elastic net is O(n x m) then the complexity of the hybrid method is O(n+m). The hybrid method then is used to solve the basic vehicle routing problem, VRP, which is the problem of routing vehicles between customers so that the capacity of each vehicle is not violated. A two phase approach is used. In the first phase clusters of customers that satisfy the capacity constrain are formed by using a SOFM network, then in the second phase the above hybrid algorithm is used to solve the corresponding TSP. Our improved method is much faster than the elastic net method. Statistical comparison of the TSP tours shows no difference between the two methods. Our computational results for VRP indicate that our heuristic outperforms existing methods by producing a shorter total tour length.
Type:
text; Dissertation-Reproduction (electronic)
Keywords:
Applied Mechanics.; Engineering, Industrial.; Operations Research.
Degree Name:
Ph.D.
Degree Level:
doctoral
Degree Program:
Graduate College; Applied Mathematics
Degree Grantor:
University of Arizona
Advisor:
Goldberg, Jeffrey B.

Full metadata record

DC FieldValue Language
dc.language.isoen_USen_US
dc.titleA neural network approach for the solution of Traveling Salesman and basic vehicle routing problemsen_US
dc.creatorGhamasaee, Rahman, 1953-en_US
dc.contributor.authorGhamasaee, Rahman, 1953-en_US
dc.date.issued1997en_US
dc.publisherThe University of Arizona.en_US
dc.rightsCopyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.en_US
dc.description.abstractEasy to explain and difficult to solve, the traveling salesman problem, TSP, is to find the minimum distance Hamiltonian circuit on a network of n cities. The problem cannot be solved in polynomial time, that is, the maximum number of computational steps needed to find the optimum solution grows with n faster than any power of n. Very good combinatoric solution approaches including heuristics with worst case lower bounds, exist. Neural network approaches for solving TSP have been proposed recently. In the elastic net approach, the algorithm begins from m nodes on a small circle centered on the centroid of the distribution of cities. Each node is represented by the coordinates of the related point in the plane. By successive recalculation of the position of nodes, the ring is gradually deformed, and finally it describes a tour around the cities. In another approach, the self organizing feature map, SOFM, which is based on Kohonen's idea of winner takes all, fewer than m nodes are updated at each iteration. In this dissertation I have integrated these two ideas to design a hybrid method with faster convergence to a good solution. On each iteration of the original elastic net method two nx m matrices of connection weights and inter node-city distances must be calculated. In our hybrid method this has been reduced to the calculation of one row and one column of each matrix, thus, If the computational complexity of the elastic net is O(n x m) then the complexity of the hybrid method is O(n+m). The hybrid method then is used to solve the basic vehicle routing problem, VRP, which is the problem of routing vehicles between customers so that the capacity of each vehicle is not violated. A two phase approach is used. In the first phase clusters of customers that satisfy the capacity constrain are formed by using a SOFM network, then in the second phase the above hybrid algorithm is used to solve the corresponding TSP. Our improved method is much faster than the elastic net method. Statistical comparison of the TSP tours shows no difference between the two methods. Our computational results for VRP indicate that our heuristic outperforms existing methods by producing a shorter total tour length.en_US
dc.typetexten_US
dc.typeDissertation-Reproduction (electronic)en_US
dc.subjectApplied Mechanics.en_US
dc.subjectEngineering, Industrial.en_US
dc.subjectOperations Research.en_US
thesis.degree.namePh.D.en_US
thesis.degree.leveldoctoralen_US
thesis.degree.disciplineGraduate Collegeen_US
thesis.degree.disciplineApplied Mathematicsen_US
thesis.degree.grantorUniversity of Arizonaen_US
dc.contributor.advisorGoldberg, Jeffrey B.en_US
dc.identifier.proquest9814384en_US
dc.identifier.bibrecord.b37741950en_US
All Items in UA Campus Repository are protected by copyright, with all rights reserved, unless otherwise indicated.