Zaman Pencereli ve Değişken Başlama Zamanlı Bir Araç Rotalama Problemi için Sütun Türetme Temelli Matsezgiseller

Abstract

In this study, a vehicle routing problem with time windows is investigated, where the costs depend on the total duration of vehicle routes and the starting time from the depot for each vehicle is determined by a decision maker. In order to solve the problem, two column generation based mat-heuristics are developed, where the first one makes use of the iterated local search and the second one uses the variable neighbourhood search. In order to assess the accuracy of the mat-heuristics, they are first compared with an exact algorithm on small instances taken from the literature. Since their performance are quite satisfactory, they are further tested on 87 large instances by running each algorithm 3 times for each instance. The computational results prove that the mat-heuristic using the variable neighbourhood search outperforms the other one. Hence, this enables to obtain a good feasible solution in a very short time when it is not possible to solve large instances with an exact solution method in a reasonable CPU time.

Bu çalışmada, araçların kullanıldıkları süreye bağlı maliyetlerin oluştuğu ve araçların depodan başlama zamanının bir karar verici tarafından belirlendiği zaman pencereli bir araç rotalama problemi ele alınmaktadır. Problemi çözmek için biri yinelemeli yerel arama meta-sezgiselinden, diğeri değişken komşuluk arama meta-sezgiselinden yararlanan iki sütun türetme temelli mat-sezgisel geliştirilmiştir. Geliştirilen mat-sezgiseller ilk önce literatürden alınarak türetilen küçük bir veri kümesi üzerinde problemin eniyi sonucunu bulan kesin bir yöntem ile karşılaştırılarak kaliteli sonuçlar ürettiklerini kanıtlamışlardır. Yöntemlerin ürettikleri sonuçların doğruluk derecesinden emin olunduktan sonra, daha büyük 87 örnek üzerinde her mat-sezgisel her örnekte 3 kere çalıştırılarak test edilmiştir. Bilgisayımsal sonuçlar değişken komşuluk arama meta-sezgiseli kullanan mat-sezgiselin, daha kaliteli ve verimli sonuçlar vererek daha başarılı bir algoritma olduğunu göstermiştir. Bu sayede kesin bir yöntemle makul bir ana işlemci zamanında çözülemeyen büyük ölçülü problemler için çok kısa bir zaman içerisinde iyi bir olurlu çözüm elde etmek mümkün hale gelmiştir.