OPEN MULTIPLE TRAVELLING SALESMAN PROBLEM AND A SOLUTION PROPOSAL

Zühal Kartal

Makale detayları

OPEN MULTIPLE TRAVELLING SALESMAN PROBLEM AND A SOLUTION PROPOSAL

Yazarlar:

Zühal Kartal

Yayıncı:

Süleyman Demirel University

Ana Başlıklar:

Bilgisayar Yazılımı | Endüstri Mühendisliği

Dergi:

Mühendislik Bilimleri ve Tasarım Dergisi Vol.11 Issue 4, pp.1517-1528

Belge Tipi:

Makale

Yayın Tarihi:

12/2023

Belge Dili:

Türkçe

Document ID (Org No.):

2001307544

pISSN:

1308-6693

Anahtar kelimeler:

Özet:

 The multiple traveling salesman problem aims to minimize the total cost of m tours while visiting each city only once form sellers who start a tour from a single depot and finish the tour at the same depot. In the open multiple traveling salesman problem, m sellers complete the tour in the city they last visited without returning to the depot. The aim of the problem is to minimize the total travelled distance formed by m sellers. This problem is encountered in the logistics sector, especially in cargo transportation. In this study, a solution is proposed to solve by using open source softwares. First, the cities to be visited by m sellers are determined by the K-Medoids Clustering Algorithm which is an unsupervised machine learning algorithm, and then the routes are formed with the Nearest Neighborhood Algorithm. The performance of the proposed method was tested on datasets with different clustering characteristics such as clustered, random and a hydrid random-clustered dataset from the literature. Its performance was compared with the optimal solutions taken from the Gurobi commercial solver. The results indicate that the proposed method is reasonably successful; however, it exhibits different behaviors on datasets with distinct characteristics.

 The multiple traveling salesman problem aims to minimize the total cost of m tours while visiting each city only once form sellers who start a tour from a single depot and finish the tour at the same depot. In the open multiple traveling salesman problem, m sellers complete the tour in the city they last visited without returning to the depot. The aim of the problem is to minimize the total travelled distance formed by m sellers. This problem is encountered in the logistics sector, especially in cargo transportation. In this study, a solution is proposed to solve by using open source softwares. First, the cities to be visited by m sellers are determined by the K-Medoids Clustering Algorithm which is an unsupervised machine learning algorithm, and then the routes are formed with the Nearest Neighborhood Algorithm. The performance of the proposed method was tested on datasets with different clustering characteristics such as clustered, random and a hydrid random-clustered dataset from the literature. Its performance was compared with the optimal solutions taken from the Gurobi commercial solver. The results indicate that the proposed method is reasonably successful; however, it exhibits different behaviors on datasets with distinct characteristics.

 The multiple traveling salesman problem aims to minimize the total cost of m tours while visiting each city only once form sellers who start a tour from a single depot and finish the tour at the same depot. In the open multiple traveling salesman problem, m sellers complete the tour in the city they last visited without returning to the depot. The aim of the problem is to minimize the total travelled distance formed by m sellers. This problem is encountered in the logistics sector, especially in cargo transportation. In this study, a solution is proposed to solve by using open source softwares. First, the cities to be visited by m sellers are determined by the K-Medoids Clustering Algorithm which is an unsupervised machine learning algorithm, and then the routes are formed with the Nearest Neighborhood Algorithm. The performance of the proposed method was tested on datasets with different clustering characteristics such as clustered, random and a hydrid random-clustered dataset from the literature. Its performance was compared with the optimal solutions taken from the Gurobi commercial solver. The results indicate that the proposed method is reasonably successful; however, it exhibits different behaviors on datasets with distinct characteristics.

 Çoklu gezgin satıcı problemi, bir tura tek bir depodan başlayan ve turu depoda bitiren m adet satıcı için her bir şehrin yalnızca bir kez ziyaret edilmesi kısıtı altında, oluşan m adet turun toplam maliyetini minimize etmeyi amaçlar. Açık uçlu çoklu gezgin satıcı probleminde ise, m adet satıcı depoya geri dönme zorunluluğu olmadan, turu en son ziyaret ettikleri şehirde tamamlarlar. Problemin amacı, m adet satıcının oluşturduğu rotaların toplam mesafesinin en küçüklenmesini sağlamaktır. Bu probleme lojistik sektöründe özellikle kargo taşımacılığında rastlanmaktadır. Bu çalışma ile, açık uçlu çoklu gezgin satıcı problemine açık kaynak kodlu yazılımlar kullanılarak bir çözüm önerisinde bulunulmuştur. İlk olarak m adet satıcının gezeceği şehirler denetimsiz makine öğrenmesi algoritmalarından K-Medoids Kümeleme Algoritmasıyla belirlenmiş, ardından En Yakın Komşuluk Algoritması ile rotalar oluşturulmuştur. Önerilen yöntemin başarısı literatürden kümelenmiş, rassal ve hibrid rassal-kümelenmiş olarak sunulmuş özellikler gösteren veri setleri üzerindeki denenerek, performansı Gurobi ticari çözücüsünden alınan optimal çözümlerle karşılaştırılmıştır. Sonuç olarak, önerilen yöntemin kabul edilebilir seviyede başarılı olduğunu ancak, farklı özellikler taşıyan veri setlerinde farklı davranışlar sergilediğini göstermektedir.

Makale detayları

OPEN MULTIPLE TRAVELLING SALESMAN PROBLEM AND A SOLUTION PROPOSAL

Yazarlar:

Zühal Kartal

Yayıncı:

Süleyman Demirel University

Ana Başlıklar:

Bilgisayar Yazılımı | Endüstri Mühendisliği

Dergi:

Mühendislik Bilimleri ve Tasarım Dergisi Vol.11 Issue 4, pp.1517-1528

Belge Tipi:

Makale

Yayın Tarihi:

12/2023

Belge Dili:

Türkçe

Document ID (Org No.):

2001307544

pISSN:

1308-6693

Open Multiple Travelling Salesman Problem

Machine Learning

K-Medoids Algorithm

Nearest Neighborhood Algorithm.Açık Uçlu Gezgin Satıcı Problemi

Makine Öğrenmesi

K-Medoids Algoritması

En Yakın Komşuluk Araması Algoritması.

Sayı

Makale detayları

Yazarlar: Zühal Kartal

Yayıncı: Süleyman Demirel University

Ana Başlıklar: Bilgisayar Yazılımı | Endüstri Mühendisliği

Dergi: Mühendislik Bilimleri ve Tasarım Dergisi Vol.11 Issue 4, pp.1517-1528

Belge Tipi: Makale

Yayın Tarihi: 12/2023

Belge Dili: Türkçe

Document ID (Org No.): 2001307544

pISSN: 1308-6693

Sayı

Yazarlar:

Zühal Kartal

Yayıncı:

Süleyman Demirel University

Ana Başlıklar:

Bilgisayar Yazılımı | Endüstri Mühendisliği

Dergi:

Mühendislik Bilimleri ve Tasarım Dergisi Vol.11 Issue 4, pp.1517-1528

Belge Tipi:

Makale

Yayın Tarihi:

12/2023

Belge Dili:

Türkçe

Document ID (Org No.):

2001307544

pISSN:

1308-6693