Relative Distances Approach for Multi-Traveling Salesmen Problem

Date

2024-1-15

Author

Ergüven, Emre

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

158
views

193
downloads

Cite This

This study aims to find a solution for the Multi-Traveling Salesman Problem (M-TSP). Within the problem, multiple tasks (e.g cargo delivery, warehouse placement) are executed by multiple agents (e.g traveling salesman, autonomous robots). There are two main objectives for these problems; the first one is minimizing the total path cost, and the second one is minimizing the maximum cost of salesmen (makespan). We mainly focused on minimizing the total cost. But fully focusing on decreasing the total cost mostly results with an increase on the makespan. Our method keeps the makespan in a reasonable range. Due to the combinatorial structure of the problem, finding the cost-optimal solutions is impossible (with current conditions). Solutions must be found quickly in order to be applicable in real-life. So, it can be said that the third objective of the problem is reducing the complexity and time to find the solutions. The MTSP problem is generally tried to be solved in two separate phases. In the first phase, tasks are assigned to salesmen with different approaches (e.g K-Means, DBSCAN). Second phase is finding optimal routes for each salesman. The problem within the second stage is identical to the Traveling Salesman Problem (TSP). Our relative distance model combines these phases within one method with a novel heuristic approach. With our model, tasks can be easily added and removed from the problem space and live-scheduling can be enabled. All of these methods mentioned are implemented on C++ and visualized on Python

Subject Keywords

Traveling Salesman Problem, Multi Traveling Salesman Problem, Combinatorial Optimization, Heuristic Methods, Task Assignment

URI

https://hdl.handle.net/11511/108328

Collections

Graduate School of Natural and Applied Sciences, Thesis