Construction of the subtour

Abstract

oz GEZGİN SATICI PROBLEMİNİN ALT TUR ENGELLEME KISITLARININ OLUŞTURULMASI VE UZANTILARI Tolga Bektaş ENDÜSTRİ MÜHENDİSLİĞİ ANABİLİM DALI YÜKSEK LİSANS TEZİ Ankara, 2000 Kombinatoryel optimizasyon alanının en tanınmış ve en övülen problemi, şüphesiz Gezgin Satıcı Problemi'dir (GSP). GSP, temel olarak bir şehirden başlayıp tekrar aynı şehire dönmek zorunda olan bir gezgin için, her şehiri bir kere ziyaret etmesini sağlayacak eniyi turun bulunması olarak tanımlanabilir. GSP'nin önemli bir uzantısı, bir yerine m adet gezgin içeren, Çok Gezgin Satıcılı Problem'dir (m-GSP). GSP ve m-GSP 'deki en büyük problem, alt turların engellenmesidir. GSP ve m- GSP'nin kesin çözüm yöntemleri, alt tur engelleme kısıtlarına dayalı, atama tabanlı tamsayılı doğrusal programlama modellerini kullanırlar. GSP için ilk defa alt tur engelleme kısıtlarını öneren, 1954'da Dantzig, Fulkerson ve Johnson olmuştur. Daha sonra, Miller, Tucker ve Zemlin (1960) (MTZ), yeni değişkenler kullanarak alternatif başka bir grup kısıt önermişlerdir. Bunu takiben, Desrochers ve Laporte (1991) (DL), MTZ alt tur engelleme kısıtlarının daha da sıkılaştınlarak iyileştirilebileceklerini göstermişlerdir. m-GSP için bu alandaki çalışmalar daha kısıtlıdır ve bu problem için alt tur engelleme kısıtlan, sadece Svestka ve Huckfeldt (1976) ve Sipahioğlu (1996) tarafından önerilmiştir. Bilgisayar yazılım ve donanım teknolojisindeki hızlı gelişme, matematiksel modellerin kesin çözümlerinin kolay ve etkin bir şekilde bulunmasına imkan vermiştir. Bu bağlamda, bu çalışma GSP ve m-GSP 'nin atama tabanlı tamsayılı doğrusal karar modellerinin bir optimizasyon paket programı kullanarak, doğrudan çözümlerinin mbulunmasını esas almaktadır. Çalışmada, GSP ve m-GSP'nin modelleme metodolojisine ağırlık verilerek, alt tur engelleme problemine mantıksal bir yaklaşım uygulanmıştır. Alt tur problemi çerçevesinde, alt turların oluşmasını engelleyen kısıtlan türetmek için zayıf ve kuvvetli mantıksal kısıtlamalar kullanılmıştır. Sözkonusu kısıtlamalar, TSP ve m-GSP için kullanılmış ve sonuç olarak her durum için alt tur engelleme kısıtlan oluşturulmuştur. Zayıf mantıksal kısıtlamalann GSP üzerinde uygulanması sonucunda elde edilen kısıtlann, önceden deneysel olarak elde edilen MTZ kısıtlanyla aynı olduğu görülmüştür. Kuvvetli mantıksal kısıtlamalann GSP üzerinde uygulanmasıyla ise, DL kısıtlarına erişilmiştir. Bu çalışma, bir yönüyle, ilgili kaynaklarda önerilen alt tur engelleme kısıtlannın doğrudan türetilme metodolojisini göstermektedir. Bu yaklaşım, aynı zamanda m-GSP üzerinde de uygulanmış ve sonuç olarak m-GSP için dört yeni model önerilmiştir. Bunlardan ilk üçü, düğüm potansiyeli ile yeni tanımlanan ve tur potansiyeli adı verilen değişkene dayanan modeller, sonuncusu ise önceden GSP için önerilmiş bir modelin m-GSP' ine uzantısıdır. Önerilen yeni m-GSP modelleri, varolanlarla birlikte, optimizasyon paket programı CPLEX 6.0 kullanılarak karşılaştırmalı analize tabi tutulmuştur. Analiz sonuçlan, problemdeki gezgin sayısı arttıkça önerilen modelin diğerlerine olan üstünlüğünün arttığını göstermektedir. Anahtar kelimeler. Gezgin satıcı problemi, çok gezgin satıcılı problem, Alt tur engelleme kısıtlan, tamsayılı doğrusal karar modeli, kesin çözüm. iv

ABSTRACT CONSTRUCTION OF THE SUBTOUR ELIMINATION CONSTRAINTS OF THE TRAVELING SALESMAN PROBLEM AND ITS EXTENSIONS Tolga Bektaş MASTER THESIS DEPARTMENT OF INDUSTRIAL ENGINEERING Ankara, 2000 The most famous and celebrated problem of the field of combinatorial optimization is with no doubt, the traveling salesman problem (TSP). The TSP is basically finding the shortest path for a salesman who has to visit each city exactly once and turn back to the city from which he starts. An important extension of TSP is the multiple traveling salesman problem (m-TSP), which considers m salesmen instead of one. The main problem for the TSP and the m-TSP is the subtour elimination. The exact solution methods of the TSP and the m-TSP mainly utilize assignment based integer linear programming (ILP) formulations which are based on subtour elimination constraints (SECs), i.e. constraints used to prevent the formation of subtours. Dantzig, Fulkerson and Johnson are one of the first to propose subtour elimination constraints in 1954 for the TSP. Later on, Miller, Tucker and Zemlin (1960) (MTZ) proposed an alternative formulation by introducing new variables. Following this, Desrochers and Laporte (1991) (DL) showed that the MTZ SECs could be strengthened using a lifting technique. The research on m-TSP is more limited and the subtour elimination constraints proposed for this problem are only due to Svestka and Huckfeldt (1976) and Sipahioğlu(1996). The rapid development in computer software and hardware technology has given the opportunity to easily and effectively use exact solution methods for the solution of mathematical models. In this respect, this research considers assignment based ILPformulations of both TSP and m-TSP to be used for obtaining the solution of the problems directly, by means of optimization software. This work emphasizes on the modelling methodology of the TSP and the m-TSP by using a logical approach on the subtour elimination problem. Weak and strong logical restrictions on the subtour problem are imposed to derive tight constraints prohibiting the formation of subtours. Each restriction is imposed on both the TSP and m-TSP and as a result, SECs are constructed for each case. The SECs obtained as a result of a weak logical restriction imposed on the TSP are observed to be the same as the MTZ SECs. In the case of strong logical restriction on the TSP, the previously proposed DL SECs are obtained. Part of this research demonstrates, in a sense, the way to directly derive the previously proposed SECs in the literature. The same logical approach is applied to the m-TSP as well and consequently, four new formulations for the m-TSP are proposed. The first three of the proposed formulations are based on node potentials and newly defined variables, called tour potentials. The last one is an extension of an ILP formulation previously proposed for the TSP. The new m-TSP formulations are compared with the existing ones using an optimization software CPLEX 6.0, in terms of computational efficiency. The results of the analysis show that the proposed formulation becomes superior to the existing ones as the number of salesman increase in the problem. Keywords: Traveling salesman problem, multiple traveling salesman problem, subtour elimination constraints, integer linear programming formulation, exact solution. 11