Araç rotalama için kümeleme yaklaşımı
Clustering approach for vehicle routing
Yazar: ÇAĞLA EBRU BİLİR
Danışman: PROF. DR. ÖZER UYGUN
Sakarya Üniversitesi / Fen Bilimleri Enstitüsü / Endüstri Mühendisliği Ana Bilim Dalı / Endüstri Mühendisliği Bilim Dalı
Derece: Yüksek Lisans, 2024
Konu: Endüstri ve Endüstri Mühendisliği = Industrial and Industrial Engineering

Özet:
Günümüzde işletmelerin en önemli amaçlarından biri ürünlerin müşterilere zamanında
teslim edilebilmesidir. Ürünlerin müşteriye teslim sürecinde dağıtım yapacak araç
sayısı, müşteriler ve dağıtım merkezleri arası mesafeler, teslimat zamanlaması, doğru
ürününün doğru miktarda teslimi, ürünlerin araç içi yerleştirilmeleri, vb. çok fazla
kriter dikkate alınmaktadır. Araç Rotalama Problemleri tüm bu kriterleri dikkate alarak
hem müşteri memnuniyetini sağlanmasında hem de sürecin maliyetlerinin minimize
edilmesinde kullanılmaktadır. Bu nedenle araç rotalama problemleri hem literatürde
hem de uygulamada oldukça sıklıkla çalışılmaktadır.
Rotalama yapılırken kapasite, mesafe, depo sayısı vb kısıtlara bağlı olarak kapasite
kısıtlı, mesafe kısıtlı, çok depolu önce dağıt sonra topla, eşzamanlı ve karışık topladağıt, zaman pencereli vb farklı teknikler kullanılmaktadır. Bu tekniklerin ortak
amaçları: sevkiyatta maliyetlerin azaltılması, en az sefer sayısı ile en fazla teslimatı
yapacak rotanın belirlenmesi ve bunları sağlarken teslimat ve hizmet kalitesinin
arttırılmasıdır. Rotalamada faydalanılan yaklaşımlardan biri dağıtım yapılacak
merkezleri gruplandırmak için kullanılan kümeleme yaklaşımıdır. K-means
Kümeleme Algoritması, Hiyerarşik Kümeleme Algoritması, Model Tabanlı
Kümeleme metotları, Grid Temelli metotlar, Yoğunluk Temelli metotlar vb.
kümeleme algoritmaları kullanılabilir.
Bu çalışmada beyaz eşya sektöründe faaliyet gösteren bir imalat işletmesinin nihai
ürünlerinin bayilere doğru ve verimli şekilde sevkiyatı için araç rotalama uygulaması
anlatılmaktadır. Problemin çözümünde teslimatların yapılacağı bayilerin
rotalanmasında "önce kümele sonra rotala" yaklaşımı kullanılmıştır.
Öncelikle bayi konumları, sipariş hacimleri ve bilgileri gibi veriler elde edilmiştir.
Bayilerin ana depoya olan uzaklıkları dikkate alınarak Google Maps uygulaması
aracılığı ile mesafe matrisi oluşturulmuştur. Önce kümele sonra rotala yaklaşımına
dayanarak bayilerin kümelemesinde K-means ve Bulanık c-means olmak üzere iki
farklı kümeleme algoritması kullanılmıştır. Her iki algoritma ile belirlenen kümeler
üzerinden Yapay Arı Kolonisi Algoritması ve Ateş Böceği Algoritması olmak üzere
iki farklı sezgisel algoritma ile rotalama yapılmıştır. Sonuç olarak K-means ve Yapay
Arı Kolonisi, K-means ve Ateş Böceği, Bulanık c-means ve Yapay Arı Kolonisi,
Bulanık c-means ve Ateş Böceği eşleştirmeleri ile dört farklı rota elde edilmiştir. Hem
kümeleme hem de rotalama için kullanılan tüm algoritmalara ait kodlar Phyton
programında çalıştırılmıştır. Bu rotalar: araç sayısı, kat edilen toplam mesafe, araç
kapasitelerinin dolulukları açısından kıyaslanmıştır. Çözümler arasından en uygun
yöntem belirlenmiştir.

Abstract:
One of the primary objectives of businesses today is to ensure the timely delivery of
products to customers. In the product delivery process, numerous criteria must be
considered, such as the number of vehicles available for distribution, distances
between customers and distribution centers, delivery timing, accurate delivery of the
correct quantity of products, and the internal arrangement of products within vehicles.
Vehicle Routing Problems (VRPs) are utilized to address these criteria, aiming to
enhance customer satisfaction while minimizing operational costs. Consequently,
VRPs are widely studied both in the academic literature and in practice.
Vehicle Routing Problems are the problems of determining the optimum number of
distribution/collection routes for a given number of vehicles to distribute/collect
products from at least one main warehouse (or more than one warehouse) to a set of
customers or dealers who are scattered in different physical locations and have known
demand. In solving vehicle routing problems, the following objectives are taken into
consideration: minimizing total transportation costs by taking into account the total
travel time of the vehicles and their fixed costs, minimizing the number of vehicles to
be used by ensuring that no customer/dealer is left without receiving products/services,
balancing the determined routes in terms of vehicle load and distance traveled, and
preventing partial distribution of orders to customers/dealers. Depending on the nature
of the problem, it may sometimes be necessary to create a model to achieve more than
one and/or conflicting objectives. Vehicle Routing Problems, for which many different
exact methods and many general heuristic methods can be used, are integrated
optimization problems that have remained popular for many years. Many different
types of Vehicle Routing Problems, which have been studied frequently both in
literature and in practical applications since the 1950s, have been introduced by adding
new constraints, and many mixed models and algorithms have been developed for
these problem types.
The main objective in Vehicle Routing Problems is to provide all the desired
constraints depending on the structure of the problem, keep the number of vehicles to
a minimum, keep the total travel time and/or distance to a minimum and at the same
time minimize the cost function. While all these basic objectives are provided in
Vehicle Routing Problems, the secondary objective that needs to be provided is to keep
customer satisfaction at the maximum level. In order to achieve all these goals,
businesses produce solutions based on their past experiences without using
mathematical models, which results in high distribution costs (such as labor, vehicles,
time), and ineffective/inefficient distribution routes can create extra costs for
businesses. In addition, inefficient vehicle routes can affect delivery time and delivery
accuracy, thus reducing customer satisfaction.
During the routing process, various techniques are employed depending on constraints
such as vehicle capacity, distance, and the number of depots. These techniques include
capacitated, distance-constrained, multi-depot, delivery-then-pickup, simultaneous pickup and delivery, and time-windowed routing methods. The common objectives of
these techniques are to reduce distribution costs, determine routes that maximize
deliveries with the fewest trips, and enhance delivery and service quality.
One of the approaches employed in routing is clustering, used to group delivery points
effectively. Clustering algorithms such as K-means Clustering Algorithm,
Hierarchical Clustering Algorithm, Model-Based Clustering methods, Grid-Based
methods, and Density-Based methods are among the techniques that can be utilized.
In this study, a vehicle routing application is presented for a manufacturing company
operating in the white goods sector, aiming to ensure the accurate and efficient
shipment of final products to its dealers. The "cluster first, route second" approach was
adopted for solving the routing of dealers. Initially, data such as dealer locations, order
volumes, and order details were collected. A distance matrix was then created using
Google Maps, taking into account the distances between the dealers and the main
depot. Based on the "cluster first, route second" approach, two different clustering
algorithms — K-means and Fuzzy C-means — were applied to cluster the dealers.
Subsequently, two different metaheuristic algorithms — Artificial Bee Colony (ABC)
Algorithm and Firefly Algorithm — were employed to perform routing based on the
clusters formed by each clustering method. As a result, four different routing solutions
were obtained by pairing the clustering and routing algorithms: (1) K-means & ABC,
(2) K-means & Firefly, (3) Fuzzy C-means & ABC, and (4) Fuzzy C-means & Firefly.
All algorithms were coded and executed using Python.
The resulting routes were compared in terms of the number of vehicles used, total
distance traveled, and vehicle load capacities.
When clustering was performed using the K-means algorithm, the optimum number
of clusters was determined as four based on the Elbow Method. Since Cluster 2
contained a volume of products exceeding the capacity of a single vehicle, five
vehicles were assigned to Cluster 2. Consequently, a total of eight vehicles were used
in each routing solution based on K-means clustering. Therefore, when comparing the
two routing solutions derived from K-means, the primary comparison criterion is the
total distance traveled.
When clustering was performed using the Fuzzy C-means algorithm, the optimum
number of clusters was found to be ten. In the routing solution using the Firefly
Algorithm, Clusters 2 and 3 exceeded the capacity of a single vehicle, thus requiring
two vehicles each. Therefore, a total of twelve vehicles were used in the routing
solution combining Fuzzy C-means clustering and the Firefly Algorithm. Thus, when
comparing the two routing solutions derived from Fuzzy C-means, both the number of
vehicles and the total distance traveled must be considered.
Upon examining the results of all solutions, it was observed that the combination of
K-means clustering and Firefly routing provided the optimum solution, achieving both
the minimum number of vehicles (eight) and the shortest total distance traveled
(1886.98 km).
In the current distribution practice of the white goods company under study, product
deliveries to dealers are planned based on the sales personnel's knowledge and
experience. Since clustering is not applied during distribution planning, orders from
geographically distant dealers may be loaded onto the same vehicles. Furthermore, due
to the absence of a systematic routing method, the number of vehicles used and the
total distances traveled are substantially higher.
The proposed solution, utilizing K-means clustering and Firefly routing, achieved
significant improvements in both the number of vehicles required and the total distance
traveled.