Four heuristic solution procedures to the travelling salesman problem and an application to the multi-depot vehicle routing problem

Simple item page
dc.contributorGraduate Program in Industrial Engineering.
dc.contributor.advisorUlusoy, Gündüz.
dc.contributor.authorTovya, Yasef.
dc.date.accessioned2023-03-16T10:28:17Z
dc.date.available2023-03-16T10:28:17Z
dc.date.issued1983.
dc.description.abstractThis study consists of two parts. In the first part, four heuristic algorithms for solving the Travelling Salesman Problem (TSP) is developed. Given a graph, the first algorithm forms a subgraph in which the necessary conditions for the existence of a travelling salesman tour are satisfied. In case the subgraph does not contain any travelling salesman tour, Little's bcanch and bound algorithm is partially applied to the resultant cost matrix. The second algorithm, starts with the minimum cost assignment and ranks the assignment solutions in ascending costs by introducing subtour breaking constraints. The third algorithm produces some best achievable n-paths which start from a root node and end at some node incident to the root node. These paths are then completed to travelling salesman tours and the least cost tour is taken as the best achievable solution. A geometric approach to solving the TSP is described in the last algorithm. Starting with a partial tour, the algorithm determines which of the remaining nodes are to be inserted between which consecutive pair of nodes on the subtour and in what order. After all, a summary of computational results regarding both the efficiency and the computational effort of all the algorithms is presented.
dc.format.extent30 cm.
dc.format.pagesxiv, 210 leaves;
dc.identifier.otherIE 1983 T64
dc.identifier.urihttps://digitalarchive.library.bogazici.edu.tr/handle/123456789/13265
dc.publisherThesis (M.S.) - Bogazici University. Institute for Graduate Studies in Science and Engineering, 1983.
dc.relationIncludes appendices.
dc.relationIncludes appendices.
dc.subject.lcshTraveling-salesman problem.
dc.subject.lcshHeuristic programming.
dc.subject.lcshAlgorithms.
dc.titleFour heuristic solution procedures to the travelling salesman problem and an application to the multi-depot vehicle routing problem

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
b1167628.019074.001.PDF
Size:
7.07 MB
Format:
Adobe Portable Document Format
Download

Collections

M.S. Theses