Seçici gezgin satıcı problemi için yeni matematiksel modeller

Abstract

Gezgin Satıcı Problemi (GSP), araç rotalama, çizelgeleme vb. pek çok gerçek hayat problemlerinin temelini oluşturur. Kaynaklardaki çalışmalara bakıldığında, GSP ve uzantılarında amaç olarak genellikle, toplam maliyetin, toplam kat edilen yolun veya toplam harcanan sürenin enküçüklenmesi esas alına gelmiştir. Son yıllarda, serimdeki tüm düğümlere uğrama kısıtı gevşetilerek, verilen bir bütçe veya seyahat süresi kısıtı altında, gezginin uğrayabileceği düğümlerden elde edilecek kar, kazanç vb. getiriler toplamının enbüyük olması istenen problemler de araştırmacıların ilgi odağı olmuştur. Kaynaklarda `Orienteering problemi veya Seçici GSP (The Selective TSP)`, `Getiri Toplamalı GSP-(The Price Collecting TSP)` veya `Karlı Tur Problemi (Profitable Tour Problem)` olarak isimlendirilen bu tür problemler, `Getiri Yönlü GSP (Traveling Salesman Problems with Profits)` başlığı altında toplanmaktadır. Farklı isimlendirmeler olmakla birlikte, bu tür problemlerde, aynı kısıtlar altında farklı amaç fonksiyonlarının ele alındığı görülmektedir. GSP ve uzantılarında olduğu gibi, getiri yönlü problemlerin çözüm yaklaşımlarının da öncelikle sezgiseller veya özel algoritmalar üzerine yoğunlaştığı, matematiksel modellere yeterince önem verilmediği görülmektedir. Söz konusu durum göz önüne alınarak, bu çalışmada ilk olarak, getiri yönlü GSP'nin kaynaklarda var olan modelleri incelenmiş, sonra getiri yönlü GSP'lerin benzer matematiksel yapısı nedeniyle bu problemlerden biri olan Seçici GSP, diğer adıyla Orienteering problemi için bir düğüm tabanlı bir de ayrıt tabanlı iki yeni karar modeli önerilmiştir. Önerilen modeller, kısıt ve tamsayı değişken sayısı itibariyle polinom büyüklüktedir ve tamsayılı karar modellerini çözen herhangi bir paket programla doğrudan kullanılabilecek özelliktedir. Önerilen modellerin performanslarını görmek amacıyla, kaynaklarda yer alan karşılaştırma problemleri Vansteenwegen-Souffriau-Oudheusden modeli ve yeni modellerle, CPLEX 12.5 paket programı kullanılarak çözülmüştür. Elde edilen sonuçlar, çözüm süreleri ve doğrusal programlama gevşetme değerleri yönleriyle analiz edilmiş ve önerilen yeni modellerin çok üstün olduğu görülmüştür. Ayrıca, matematiksel karar modelleri ile bulunan eniyi değerlerin, kaynaklarda sezgisel algoritmalarla bulunan bilinen eniyi değerlerin çoğundan daha büyük olduğu tespit edilmiştir.

Travelling Salesman Problem (TSP) is the basis of many real-life problems as vehicle routing, scheduling etc. The objective of TSP and its extensions is usually to minimize the total cost or the total amount of time spent or the total distance travelled. In recent years, researchers take an interest in problems which aim to maximize the profit such as revenue, income etc. by relaxation of the constraint which ensures to visit all nodes in the network, under the given budget or travel time constraint. In the literature, these problems are named as `The Selective TSP or Orienteering Problem `, `The Prize-collecting TSP ` and `The Profitable Tour Problem`. These problems are gathered under the common name of `TSP with Profits`. Just as TSP and its extensions, it is clear that heuristic methods or special algorithms are primarily preferred as solution approaches of TSP with profits, therefore mathematical models don't attract enough attention. In the scope of this study, two new mathematical models (node-based and edge-based) have been presented for the Selective TSP which is the most popular problem of TSP with profits. Size of the new models is polynomial according to the numbers of its constraints and binary decision variables so that they can be solved by an integer-programming solver. Some of Orienteering Problem benchmark instances are solved with new models by using CPLEX 12.5 software. The results are compared to an existing model in literature and it is found that the new models are superior to the existing model. Besides, it has been detected that some of the optimal solutions of mathematical models are larger than the solutions of heuristics in the literature.