An adaptive large neighborhood search algorithm for the heterogeneous pick-up and delivery vehicle routing problem with time windows

Abstract

Bu tezde heterojen araç filolu, eşzamanlı dağıtım ve toplamalı, ve müşterilerin mal kabul saatlerinde zaman pencereleri bulunan bir araç rotalama problemi ele alınmıştır. Ele alınan problemblem gerçek hayatta birçok uygulama alanına sahiptir. Problemi formüle etmek için üç farklı matematiksel model önerilmiştir. Bunlardan ilki Miller-Tucker-Zemlin (1960) kısıtları kullanılarak yazılmıştır. Diğer ikisi ise akış karar değişkenlerinden faydalanılarak yazılmıştır. Bilgimiz dahilinde, tezde ele alınan problem araç rotalama literatüründe henüz çalışılmamıştır. Tezde ayrıca matematiksel modelleri sağladıkları alt sınırlar üzerinden karşılaştırabilmek için yeni test problemleri oluşturulmuştur. Yapılan geniş çaplı sayısal deneyler, en iyi formülasyonun akış değişkenlerinin kullanıldığı formülasyon olduğunu göstermiştir. Matematiksel model ile ancak küçük test problemleri çözülebildiğinden, daha büyük boyutlu gerçek hayat problemlerini çözebilmek amacıyla Adaptif Geniş Komşuluk Arama bazlı bir sezgisel algoritma geliştirilmiştir. Geliştirilen algoritma matematiksel modeller sonucu bulunan çözümler ile karşılaştırıldığında algoritmanın birçok test probleminde optimum sonuç bulduğu ve ortalamada matematiksel model çözümlerinden daha iyi çözümler bulduğu görülmüştür. Büyük veriler üzerinde algoritmayı basit ekleme sezgiseli ile karşılaştırdığımızda ise algoritmanın ekleme sezgiselinden çok daha iyi sonuçlar verdiği, hem çözüm kalitesi açısından oldukça istikrarlı olduğu hem de çözüm süresinin problem boyutuyla çok fazla değişmediği görülmüştür. Önerilen algoritma sevkiyat planlaması yapan firmaların günlük planları için çok hızlı ve yüksek kaliteli sonuçlar üretmede kullanılabilir.

In this thesis, a heterogeneous vehicle routing problem with time windows and simultaneous pick-up and delivery, which has wide application areas, is handled. Three different types of mathematical models are proposed to formulate the problem. The first one is based on Miller-Tucker-Zemlin (1960) constraints. The other two are based on flow decision variables. To the best of our knowledge, the problem has not been studied in the vehicle routing literature. A new set of benchmark instances is also generated to compare lower bounds of mathematical models. The flow variable-based mathematical models provide the best results based on the computational experiments. As the mathematical models can solve only small sized instances, a heuristic algorithm based on Adaptive Large Neighborhood Search is proposed to solve larger real world instances. When the proposed heuristic algorithm and the mathematical models are compared, it is observed that the algorithm finds the optimal solution in most of the test instances. On the average, the algorithm finds better solutions than the mathematical models. The algorithm is also compared with a simple insertion heuristic for large instances, and is found to obtain much better solutions than the simple insertion heuristic. The proposed algorithm is not only stable in terms of solution quality, but also robust in terms of computation time. The proposed heuristic algorithm can be used in everyday logistics operations to obtain very fast and high quality solutions.