An adaptive large neighborhood search algorithm for selective and periodic inventory routing problem

Abstract

Bu çalışmada, tersine lojistik alanında karşımıza çıkan seçici ve periyodik envanter rotalama problemi için literatürdeki ilk sezgisel methodu geliştiriyoruz. Bu problemde, restoran ve otel gibi büyük miktarda bitkisel yağ tüketimi yapan ve ?stanbul?un anadolu tarafına yayılmış bu kaynak noktalarından atık bitkisel yağ toplayan bir biyodizel üretim tesisini inceliyoruz. Toplanan atık yağlar bu tesiste biyodizel üretmek için hammadde olarak kullanılmaktadır. Üretim tesisinin yöneticisi mevcut kaynak noktalarından hangilerini atık toplama programına dahil edilmesi gerektiğine; hangilerinin her gün ziyaret edilmesi gerektiğine; sonsuz süre zarfında hangi periyodik rotalama çizelgesinin tekrarlanması gerektiğine karar vererek, üretim gereksinimleri ile operasyonel kısıtlar altında araç kullanımı, rotalama, envanter ve satın alma maliyetlerin toplamını minimize etmeyi amaçlamaktadır. Bu seçici ve periyodik envanter rotalama problemi için yakın geçmişte ilk olarak akış tabanlı bir doğrusal tamsayılı programlama (DTP) modeli geliştirildi ve 40 kaynak noktasına kadar gerçek hayat problemleri üzerinde test edildi. Kaynak nokta sayısı 25?i aştığında, bu modelin 3 saat limitli çözümlerinin uygunluk düzeyinin %10?u aştığı belirtildi. Bu problemi daha fazla kaynak sayısı ile uygun zaman limitleriyle daha etkili çözebilmek için 11 farklı komşu yapısından oluşan bir uyarlanmış geniş komşu arama sezgisel algoritması geliştirdik. Bazı komşu yapıları kaynak noktasının ziyaret programını ve araçların rotalamasını modifiye ederken, diğerleri ziyaret edilen kaynak nokta listesini de değiştirebiliyor. Algoritmamızın sonuçlarını DTP modeli ile karşılaştırdığımızda, bizim methodumuzun birkaç saniye içinde bulduğu çözümü DTP modelinin bir kaç saate bulduğunu gördük. Kaynak nokta sayısı 30?u geçtiğinde bizim algoritmamız, DTP modelinden daha iyi sonuçlar vermektedir. Aynı zamanda, algoritmamızı 100 kaynak noktasına kadar büyük problemlerde de test ettik. 50 ile 100 arasında kaynak noktasına sahip problemlerin çözümlerini hesapladığımız alt limitlerle karşılaştırdığımızda, algoritmamızın bu problemleri ortalama %10.7 uygunluk düzeyinde çözdüğünü gözlemledik.

In this thesis we develop the first metaheuristic method for a selective and periodic inventory routing problem (SPIRP) that arises in reverse logistics. The problem concerns a biodiesel production company collecting used vegetable oil from restaurants and hotels which are the source nodes using and wasting vegetable oil in considerable amounts. The production facility reuses the waste oil as raw material to produce biodiesel and meets the raw material requirement for each day from daily collection, inventory and by purchasing oil. The manager needs to decide which of the present source nodes to include in the collection program, and which periodic routing schedule to repeat in every planning horizon to visit these nodes accumulating vegetable oil. His objective is to minimize the total collection, inventory and purchasing costs while the production requirements and operational constraints are met. Recently, a flow-based mixed integer linear programming (MILP) formulation was proposed for this problem, and solved on a real-world case with up to 40 source nodes. However, it was observed that the average optimality gap attained by the commercial MILP solver in three hours exceeds 10% when there are more than 25 nodes present. In order to solve large sized instances of SPIRP more effectively in a reasonable time, we develop an Adaptive Large Neighborhood Search (ALNS) algorithm by using a rich neighborhood structure comprised of 11 distinct moves. Some of these moves modify the visiting schedule and vehicle routes, while others change also the subset of visited source nodes. We test our algorithm on small size instances and compare the results with the MILP model. While our algorithm solves the small instances in several seconds, the MILP model runs for hours to find similar results. When the number of source nodes is 30 and more, our algorithm outperforms the MILP model. We also test our algorithm on larger instances with up to 100 nodes and present the related computational results. For the instances with 50 to 100 nodes, the problem is solved with around 10.7% gap.