Kapalı-açık araç rotalama problemi için model ve metasezgisel çözüm önerileri
A model and metaheuristic solution approaches for close-open vehicle routing problem
Yazar: ABDURRAHMAN YILDIZ
Danışman: YRD. DOÇ. DR. RİFAT AYKUT ARAPOĞLU
Eskişehir Osmangazi Üniversitesi / Fen Bilimleri Enstitüsü / Endüstri Mühendisliği Ana Bilim Dalı / Yöneylem Araştırması Bilim Dalı
Derece: Doktora, 2016
Konu: Endüstri ve Endüstri Mühendisliği = Industrial and Industrial Engineering

Özet:
Klasik Araç Rotalama Probleminde (ARP) araçların tümünün faaliyetlerini tamamladıktan sonra depoya dönmeleri gerekir. Açık Araç Rotalama probleminde ise, araçlar depoya geri dönmezler. Rotalar döngü olmayıp, depodan başlayan yollardır. Kendisine ait bir araç filosu olan şirketler için dağıtım/toplama faaliyetleri ARP olarak modellenebilirken, kendisine ait bir araç filosu olmayan ve dağıtım/toplama faaliyetlerini şirket dışından satın alan firmalar için Açık ARP daha gerçekçi bir modeldir.

Bu çalışmada, belirli sayıda (K) araca sahip olan ancak tüm müşterilerin talebinin karşılanamadığı durumlarda dışarıdan da araç teminine izin veren parametrik bir tamsayılı programlama modeli önerilmiştir. Böylece elde edilen model "Kapalı-Açık Araç Rotalama Problemi" olarak isimlendirilmiştir. Model uzaklık temelli olup amaç, araçların kat ettiği toplam mesafeyi enküçüklemektir. Eğer modelde, K parametresi sıfır alınırsa problem bir Açık ARP halini alır. Eğer K tüm müşterilerin talebini karşılayacak kadar alınırsa, bu sefer problem klasik ARP'ye dönüşür. Kapalı Açık ARP her iki problemi de özel durum olarak içermektedir ve bu nedenle iki problemden daha genel bir problemdir. Kapalı-Açık ARP için geliştirilen model ile küçük boyutlu test problemlerinde GAMS ile en iyi çözüm bulunmuş, daha büyük boyutlu problemlerde daha hızlı ve etkin çözüm bulabilmek amacıyla genetik algoritma ve tavlama benzetiminden oluşan bütünsel bir metasezgisel geliştirilmiştir.

Abstract:
In classical Vehicle Routing Problem (VRP) all vehicles must return to depot after completing their service activities. In Open Vehicle Routing problem, however, vehicles are not required to return to depot. Routes are not tours but paths all starting at the depot. While companies that own their vehicles can be modeled as a VRP, other companies that do not own a fleet of its own, may consider the distribution/collection activities as an Open VRP which is a more realistic model.

In this study, a parametric integer programming model is proposed which allows outsourced vehicles when companies having a certain number (K) of vehicles, yet, cannot meet all customers' demand. Thus, the model called "Close-Open Vehicle Routing Problem" is obtained. As it is a distance based model, it aims to minimize the total distance travelled by all vehicles. If parameter K takes the value zero, the problem becomes an Open VRP. If K takes a value so as to meet the demand of all customers, it turns out to be a classical VRP. Note that Close-Open VRP includes both problems as special cases and hence, is a generalization of the two problems. The model developed for small sized problems, are solved using GAMS software to obtain optimal solutions to the Close-Open VRP.  An integrated metaheuristic consisting of genetic algorithm and modified simulated annealing, is developed to find more efficient solutions to larger sized problems.