Application of large-scale optimization methods in scheduling and routing problems

Abstract

In this thesis, we consider three different applications of large-scale optimization methods. We focus on the blood donation tailoring problem under uncertain demand in the first problem. In the second one, we propose a model for hybrid manufacturing consisting of flexible manufacturing systems and typical manufacturing machines. In the last one, we consider a two-echelon vehicle routing problem for last-mile delivery of groceries. In the first part of the thesis, we propose a stochastic scenario-based reformulation of the blood donation management problem that adopts multicomponent apheresis and utilizes donor pool segmentation as here-and-now and wait-and-see donors. The donation pool segmentation enables more flexible donation schedules than the orthodox donation approach because wait-and-see donors may adjust their donation schedules according to the realized values of demand over time. We propose a column generation approach to solve the associated multi-stage stochastic donation tailoring problem for realistically sized instances. The second part considers a flexible/hybrid manufacturing production setting with typically dedicated machinery to satisfy regular demand and a flexible manufacturing system to handle surged demand. We model the uncertainty in demand using a scenario-based approach and allow the business to make here-and-now and wait-and-see decisions exploiting the cost-effectiveness of the standard production and responsiveness of the flexible manufacturing systems. We propose a branch-and-price algorithm as the solution approach. Our computational analysis shows that this hybrid production setting provides highly robust response to the uncertainty in demand, even with high fluctuations. In the third part, we propose a \textit{two-echelon vehicle routing problem} (2E-VRP) under consideration of a heterogeneous fleet of vehicles and different customer types. In our model, unlike the previous studies in the literature, not only do the large vehicles visit the pre-assigned points, called satellites, to refill the smaller vehicles, but they also deliver items to the customers. On the other hand, smaller vehicles are responsible for the customers with small size demands and can get refilled whether at the depots or satellites. We propose a branch-and-price algorithm as the solution approach and obtain promising results in comprehensive numerical studies that prove its versatility.

Bu tezde, büyük ölçekli optimizasyon yöntemlerinin üç farklı uygulamasını ele alıyoruz. İlk problemde, belirsiz talep altında kan bağışı terzilik problemine odaklanıyoruz. İkincisinde, esnek imalat sistemleri ve tipik imalat makinelerinden oluşan hibrit imalat için bir model öneriyoruz. Sonuncusunda, bakkalların son mil teslimatı için iki kademeli bir araç rotalama problemini ele alıyoruz. Tezin ilk bölümünde, çok bileşenli aferezi benimseyen ve burada-şimdi ve bekle-gör donörleri olarak donör havuzu bölümlemesini kullanan kan bağışı yönetimi probleminin stokastik senaryo tabanlı yeniden formüle edilmesini öneriyoruz. Bağış havuzu segmentasyonu, geleneksel bağış yaklaşımından daha esnek bağış programları sağlar çünkü bekle ve gör bağışçılar bağış programlarını zaman içinde gerçekleşen talep değerlerine göre ayarlayabilirler. Gerçekçi olarak boyutlandırılmış örnekler için ilgili çok aşamalı stokastik bağış uyarlama problemini çözmek için bir sütun oluşturma yaklaşımı öneriyoruz. İkinci bölümde, düzenli talebi karşılamak için tipik olarak tahsis edilmiş makineler ve ani talebi karşılamak için esnek bir üretim sistemi ile esnek/hibrit üretim üretim ayarı ele alınmaktadır. Talepteki belirsizliği senaryo tabanlı bir yaklaşım kullanarak modelliyoruz ve işletmenin standart üretimin maliyet etkinliğinden ve esnek üretim sistemlerinin yanıt verebilirliğinden yararlanarak burada ve şimdi ve bekle-gör kararları almasına izin veriyoruz. Çözüm yaklaşımı olarak sütun oluşturma tabanlı bir algoritma öneriyoruz. Hesaplamalı analizimiz, bu hibrit üretim ayarının, yüksek dalgalanmalarda bile talepteki belirsizliğe son derece sağlam yanıt verdiğini gösteriyor.\\ Üçüncü bölümde, heterojen bir araç filosu ve farklı müşteri tipleri göz önünde bulundurularak \textit{iki kademeli bir araç rotalama problemi} (2K-ARP) önerilmiştir. Modelimizde literatürdeki önceki çalışmalardan farklı olarak büyük araçlar, daha küçük araçları doldurmak için uydu adı verilen önceden belirlenmiş noktaları ziyaret etmekle kalmaz, aynı zamanda müşterilere ürün teslim eder. Daha küçük araçlar ise, küçük boyutlu talepleri olan müşterilerin sorumluluğundadır ve ister depolarda ister uydularda dolum yapabilmektedir. Çözüm yaklaşımı olarak bir dal-ve-fiyat-kes algoritması öneriyoruz ve çok yönlülüğünü kanıtlayan kapsamlı sayısal çalışmalarda umut verici sonuçlar elde ediyoruz.