MULTI TRAVELING SALESMAN PROBLEM (M-TSP)

• Main Author: Setiyono, Budi
• Format: Theses
• Language: Indonesia
• Online Access: https://digilib.itb.ac.id/gdl/view/5222
• Institution: Institut Teknologi Bandung

<b>Abstrak :</b><p align="justify">An extension of TSP is the Multi Traveling Salesman Problem (m-TSP), which is TSP with more than one salesman. The m-TSP can be stated follows : there are m salesmen who must visit a set of n cities (clients). Each salesman tour starts and ends at the the base city (node of depots). Each city must be visited only once by one salesman. The problem is a set of m tours must be found so that the sum of involved distances is minimized.<p align="justify"> <br /> In this thesis, a software was developed to solve this m-TSP problem, and called multi Traveling Salesman Solver (mTraSolv).<p align="justify"> <br /> Inputs of mTraSolv are matrix of distance, number of salesman, and node of depots. Matrix of distance can be visualized, so enables user to adjust the position of nodes in the graph editor.<p align="justify"> <br /> The number of sub tours created are the same as the number of salesmen. This process is based on the assignment heuristic method. If the number of salesman exceeds the degree of depot nodes, then as many sub tours are made as the degree of depot nodes.<p align="justify"> <br /> Each sub tour is then checked for the existence of Hamilton circuit. If no Hamilton circuit is found then an edge is added to non-adjacent nodes.<p align="justify"> <br /> After every sub tours has Hamilton circuit, optimization process is carried out to get minimum Hamilton circuit in each sub tour. This process is based on branch and bound method.<p align="justify"> <br /> Outputs of mTraSolv are in the form of text and graph that indicate the route of each salesman.<p align="justify"> <br /> mTraSolv was developed using Borland Delphi 5.