Selective and periodic inventory routing problem for collection of end-of-life products

Abstract

Bu çalışmada, restoran ve hastane gibi büyük miktarda atık üreten ve şehre yayılmış kaynak noktalarından atık bitkisel yağ toplayan İstanbul'daki bir biyodizel üretim tesisini inceliyoruz. Bu üretim tesisi, toplanan atık yağları biyodizel üretiminde hammadde olarak kullanmakta. Üretim tesisinin yöneticisi mevcut kaynak noktalarından hangilerini atık toplama programına dahil etmesi gerektiğine; hangilerinin her gün ziyaret edilmesi gerektiğine; sonsuz süre zarfında hangi periyodik rotalama çizelgesinin tekrarlanması gerektiğine, üretim gereksinimleri ile operasyonel kısıtlar altında toplama, envanter ve satın alma maliyetlerin toplamını minimize etmek için kaç tane araç kullanılması gerektiğine karar vermelidir. Bu seçici ve periyodik envanter rotalama problemi için ilk olarak akış tabanlı bir doğrusal tamsayılı programlama (DTP) modeli geliştirdik ve bu modeli 36 gerçek problem senaryosu ile test ettik. Kısmi doğrusal gevşetme modeli kullanarak alt limitleri oluşturduk ve modelin çözümlerine baktığımızda ortalamada 3.28% uygunluk düzeyi sağladığını gözlemledik. Duyarlılık analizleri ile müşteri seçimi, rotalama ve üretim kararları ile ilgili çeşitli gözlemler ile elde ettik. İkinci olarak, değişik formülasyonlar içeren alternatif modeller geliştirdik ve bu modelleri seçilen 6 senaryo üzerinde test ettik. Burada müşteri envanteri tutan (DTP), ziyaret çizelgesini eniyilemek için uç alternatifi karşılaştırdık ve birinci olarak sunmuş olduğumuz DTP modelinin en iyi sonuçları sağladığını gözlemledik. Üçüncü ve son olarak da, tek araçlı problemler için Lagrange Gevşetme yaklaşımını uyguladık. Gevşetme modeli, biri ziyaret çizelgesini, diğeri ise her bir periyot için toplama rotasını eniyileyen olmak üzere iki adet karışık tamsayı programlama modeline ayrılır. Bu çözüm yaklaşımının performansını test ettik ve önceden belirlenen bir zaman limiti dahilinde, Lagrange gevşetme metodu ile elde edilen alt limitler ile önerilen DTP model ile elde edilen alt limitleri karşılaştırıldı ve metodun az miktarda geliştirme elde ettiğini gözlemledik.

Our study is motivated from a biodiesel production facility in Istanbul that collects waste vegetable oils from source points such as restaurants and hospitals that generate waste in large amounts and are dispersed throughout the city. The production facility uses the collected waste oil as raw material for biodiesel production. The manager of this facility needs to decide which of the present source points to include in the collection program, which of them to visit on each day, which periodic routing schedule to repeat over an infinite horizon and how many vehicles to operate such that the total collection, inventory and purchasing costs are minimized while the production requirements and operational constraints are met. For this selective and periodic inventory routing problem: First, we propose a ow-based mixed integer linear programming (MILP) formulation and test it on a real-world problem with 36 scenarios. We generate lower bounds using a partial linear relaxation model, and observe that the solutions obtained through our model are within 3:28% of optimality on the average. Several insights regarding the customer selection, routing and production decisions are acquired with further sensitivity analysis. Secondly, we compare alternative formulations and test them on six scenarios. Here, we compare three alternatives to optimize the visiting schedule and observe that our first proposed MILP model yields the best solutions. Thirdly, we propose a Lagrangian Relaxation approach for the solution of single vehicle problems. The relaxed model decomposes into two mixed integer programming models that optimize the visit schedule and the collection route in each period separately. We test the performance of this solution approach and compare the lower bounds obtained by the Lagrangian relaxation method to the ones obtained by solving the proposed MILP model within a pre-specified time limit.