Çok gezginli en küçük gecikme problemi için yeni karar modelleri

Abstract

En küçük Gecikme Problemi (EGP) rotalama problemlerinin temelini oluşturan Gezgin Satıcı Probleminin (GSP) bir türü olmaktadır. EGP, bir başlangıç düğümünden başlayarak, tüm düğümlere uğradıktan sonra başlangıç noktasında veya verilen bir düğümde sona eren Hamilton turunu veya yolunu araştırmaktadır. GSP bütün müşterilere uğramak için gerekli olan toplam zamanı en küçük yapmayı amaçlamakta, EGP ise tüm müşterilerin toplam gecikme zamanını en küçük yapmayı amaçlamaktadır. EGP'nin en önemli özel durumu olarak görülen çok gezginli uzantısı için kaynaklardaki yapılan çalışmalar incelendiğinde polinom sayıda ve üstel sayıda kısıta sahip iki farklı matematiksel model olduğu ancak bu modellere bakıldığında kısa sürede çözüme ulaşma açısından verimli olmadığı belirlenmiştir. Bu nedenle yeni karar modellerine ihtiyaç olduğu görülmüştür. Bu çalışma kapsamında ise, temel konu olarak ele alınan çok gezginli EGP için yapılacak çalışmanın altyapısını oluşturması amacıyla öncelikle EGP modelleri kaynaklarda bulunan kıyaslama problemi verileri kullanılarak sayısal analizlere tabi tutulmuştur. İşlem süresi (CPU) ve doğrusal programlama (LP) gevşetme değerleri yönüyle en iyi performans gösteren model belirlenmiştir. Çok gezginli EGP için üç tanesi yeni model bir tanesi kaynaklarda yer alan bir model olmak üzere toplam dört model ele alınıp kaynaklardaki farklı düğüm sayısına sahip kıyaslama problemleri ve gezgin sayıları için çözdürülerek en iyi performans gösteren model önerilmiştir. Yapılan bu karşılaştırmalı analizler sonucunda problem boyutu ve CPU süresi arasındaki ilişki ve gezgin sayısı ile CPU süresi arasındaki ilişki ile ilgili çıkarımlar da elde edilmiştir. Bu çalışmanın en önemli sonucu çok gezginli EGP için yeni bir modelin bilime katkı olarak sunulmasıdır.

The Minimum Latency Problem (MLP) is a kind of Traveling Salesman Problem (TSP) which is the basis of the routing problems. MLP investigates the Hamilton tour or path, which starts from an initial node, after visiting all nodes, it ends at the starting or any given node. While TSP aims to make the smallest total time required to visit all customers, MLP aims to minimize total delay time of customers. When we review the literatüre, MLP with multiple traveler which is regarded as the most important exception of MLP, is modeled in two different ways: one with polynomial and the other with exponential number of constraints. However, both models are not efficient in terms of reaching a solution in a short time. Therefore the need for a new decision model is obvious. In this study, firstly MLP models are subjected to several quantitative analysis using available benchmarking problems in the literature. The purpose of this analysis is to create an infrastructure for the multiple traveling MLP. The best performing model is determined in terms of processing time (CPU) and linear programming (LP) relaxation values. Four models, one from literature and three new ones, are solved for benchmark problems with different number of nodes and different number of travelers and the best performing model is selected accordingly. As a result of this comparative analysis, we observe the relationship between problem size and CPU time and also the relationship between the number of travelers and CPU time. The most important result of this study is presented as a contribution to science, a new model for multiple traveling MLP.