Arşiv ve Dokümantasyon Merkezi
Dijital Arşivi

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

Basit öğe kaydını göster

dc.contributor Graduate Program in Industrial Engineering.
dc.contributor.advisor Ulusoy, Gündüz.
dc.contributor.author Tovya, Yasef.
dc.date.accessioned 2023-03-16T10:28:17Z
dc.date.available 2023-03-16T10:28:17Z
dc.date.issued 1983.
dc.identifier.other IE 1983 T64
dc.identifier.uri http://digitalarchive.boun.edu.tr/handle/123456789/13265
dc.description.abstract This 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.extent 30 cm.
dc.publisher Thesis (M.S.) - Bogazici University. Institute for Graduate Studies in Science and Engineering, 1983.
dc.relation Includes appendices.
dc.relation Includes appendices.
dc.subject.lcsh Traveling-salesman problem.
dc.subject.lcsh Heuristic programming.
dc.subject.lcsh Algorithms.
dc.title Four heuristic solution procedures to the travelling salesman problem and an application to the multi-depot vehicle routing problem
dc.format.pages xiv, 210 leaves;


Bu öğenin dosyaları

Bu öğe aşağıdaki koleksiyon(lar)da görünmektedir.

Basit öğe kaydını göster

Dijital Arşivde Ara


Göz at

Hesabım