Relative Distances Approach for Multi-Traveling Salesmen Problem

Abstract

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

Alternate abstract:

Bu çalışma, Çoklu Gezgin Satıcı Problemini çözmeyi amaçlamaktadır. Bu problemlerde, görevler (kargo teslimatı, depo yerleştirimi) birden çok etmen (gezgin satıcı, otonom robot) tarafından tamamlanmaya çalışılır. Bu gibi problemlerde iki ana hedef vardır; birincisi toplam kat edilen mesafeyi minimize etmektir, ikincisi de bir etmen tarafından kat edilen maksimum mesafeyi minimize etmektir.

Bu çözümdeki ana öncelik toplam kat edilen mesafeyi minimize etmektir. Fakat tamamen toplam kat edilen mesafeyi minimize etmeye odaklanmak, bir etmen tarafından kat edilen maksimum mesafeyi artırabilir. Bu çalışmada sunulan yöntem, bir etmen tarafından kat edilen maksimum mesafeyi de makul bir seviyede tutmaktadır. Problemin kombinatoryal yapıda olması sebebiyle maliyeti minmize eden bir çözümü bulmak imkansızdır (günümüz koşullarında). Gerçek hayatta uygulanabilirlik için çözümün hızlı bir şekilde bulunması gerekmektedir. Yani, şu söylenebilir ki; problemin üçüncü hedefi, çözüm bulunana kadarki karmaşıklığı ve harcanan zamanı düşürmektir.

Çoklu gezgin satıcı problemi, genellikle iki ayrı aşamada çözülmeye çalışılır. İlk aşamada görevler kullanıcılara farklı yaklaşımlarla verilir (k-ortalamalar kümesi, yoğunluk tabanlı mekansal uygulamaların gürültüyle kümelenmesi). İkinci aşama ise her gezgin için verilen görevlerin optimal sıralamasıdır. İkinci aşamadaki problem gezgin satıcı problemiyle aynıdır. Göreli Mesafe modelimiz bu fazları tek bir yöntemde özgün bir keşifsel yaklaşımla birleştirir. Modelimiz sayesinde görevler kolayca iptal edilebilir veya yeni görevler eklenebilir ve canlı planlama sağlanabilir.

Yukarıda belirtilen tüm metodlar C++'da çalıştırılmış ve Python'da görselleştirilmiştir.