Kapasite kısıtlı yerleştirme rotalama probleminin bir melez karınca kolonisi algoritması ile çözümü

Abstract

Bu çalışmada, varsayımsal bir e-ticaret firması için kapasite kısıtlı yerleştirme rotalama problemi (capacitated location routing problem-CLRP) çözülmüştür. Literatürde yer alan karışık tam sayılı programlama (KTP) modeline yeni bir amaç fonksiyonu eklenerek yeni bir matematiksel model sunulmuştur. Problem NP-zor sınıfında olduğundan, depo yerlerini ve araç rotalarını eş zamanlı olarak belirlemek amacıyla melez karınca kolonisi algoritması (KKA) önerilmiştir. Melez yapıda, KKA ve yerel arama (YA) algoritmaları birlikte çalışmaktadır. Melez algoritmanın adımları sırasıyla KKA ile eş zamanlı olarak depo yerleri ve araç rotalarının belirlenmesi, elde edilen çözüm üzerinde tanımlanan komşuluk yapısına göre YA algoritması ile depo yerlerinin hizmet vereceği yeni talep noktalarının belirlenmesi, depolardan talep noktalarına hizmet verecek araç rotalarının KKA ile belirlenmesi şeklindedir. Problemin amaç fonksiyonu bir kilometrede karşılanan talep miktarının en çok yapılması olarak belirlenmiştir. Tüm talep noktaları depo yeri olmaya adaydır. Önerilen melez algoritmanın, depo yerlerini ve araç rotalarını belirlemedeki etkinliğini göstermek için farklı taleplere göre dört senaryo üretilmiştir. Problemin çözümünde kullanılan talep verileri, normal dağılıma uygun olarak üretilen varsayımsal verilerdir. Tüm veriler üzerinde normallik testi yapılmış ve verilerin %95 güven aralığında normal dağılıma uygun olduğu gösterilmiştir. Algoritmanın senaryolara göre ürettiği sonuçlar paylaşılmıştır. Sonuçlar melez KKA'nın talebe göre ihtiyacı karşılayacak sayıda depo açma ve farklı talepleri karşılayabilme potansiyeline sahip olduğunu göstermektedir. Literatürdeki çalışmalarda LRP genellikle yerleştirme ve rotalama problemi olmak üzere iki alt probleme bölünmüştür. Bu iki problemin çözümü içinse genellikle kademeli veya kümeleme temelli yöntemler kullanılmıştır ancak LRP, yerleştirme ve rotalama probleminin eş zamanlı olarak çözülmesi gerektiği bütünleşik bir problemdir. Bu çalışma, literatürdeki birçok çalışmadan farklı olarak, yerleştirme ve rotalama problemi aynı anda (eş zamanlı) değerlendirerek büyük boyutlu LRP için çözüm sunmaktadır. Çalışma bu yönüyle hem literatürdeki çalışmalardan ayrılmakta hem de eş zamanlı ele alınmasıyla LRP literatürüne katkı sağlamaktadır. Anahtar kelimeler: Kapasite kısıtlı yerleştirme rotalama problemi (CLRP), karışık tam sayılı programlama (KTP), karınca kolonisi algoritması (KKA), yerel arama algoritması (YA)

In this study, the capacitated location routing problem (CLRP) was solved for a hypothetical e-commerce company. A new mathematical model is presented by adding a new objective function to the mixed integer programming (MILP) model in the literature. Since the problem is in the NP-Hard class, a new hybrid ant colony algorithm (ACA) was proposed to determine the depot locations and vehicle routes simultaneously. In the hybrid algorithm, ACA and local search (LS) algorithm run together. The steps of the hybrid algorithm are, respectively, the determination of warehouse locations and vehicle routes simultaneously with the ACA, determining the new demand points to be served by the warehouse locations with the LS algorithm according to the neighborhood structure defined on the solution obtained, and the determination of the vehicle routes that will serve the demand points from the warehouses with ACA. The objective of the problem is to maximize the number of demands per kilometer. All demand points were candidates for depot location. Four scenarios were produced according to the different demands to demonstrate the effectiveness of the proposed hybrid algorithm to determine depot locations and vehicle routes. The demand data used were determined as a hypothetical data based on a normal distribution. A normality test was performed on all data and it was shown that the data were suitable to normal distribution at a 95% confidence interval. The results produced by the algorithm according to the scenarios were presented. The results showed that the hybrid ACA had the potential to open enough depots to meet the demand changing. In the studies in the literature, LRP is generally divided into two sub-problems as location and routing problems. To solve these two problems, phased or clustering-based methods are generally used, but LRP is an integraed problem where the location and routing problem must be solved simultneously. This study offers a solution for large-scale LRP by simultaneously evaluating the location and routing problem. In this respect, the study both differs from the studies in the literature and contributes to the LRP literature by considering it simultaneously. Keywords: Capacitated location routing problem (CLRP), mixed integer programming (MILP), ant colony algorithm (ACA), local search algorithm (LS)