Abstract
Abstract
This study aims to find a solution for both the Multi-Traveling Salesman Problem
(M-TSP) and Multi Agent Path Finding Problem with Multiple Delivery Locations
(MAPF-MD). Within these problems, 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 kinds of 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 (finding a solution
with N-k salesmen instead of N salesmen). Our proposed method easily 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 the elapsed time until
the solution is found.
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
clustering, 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.