Geri Dön

Araç rotalama için kümeleme yaklaşımı

Clustering approach for vehicle routing

PDF İndir

  1. Tez No: 947260
  2. Yazar: ÇAĞLA EBRU BİLİR
  3. Danışmanlar: PROF. DR. ÖZER UYGUN
  4. Tez Türü: Yüksek Lisans
  5. Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2024
  8. Dil: Türkçe
  9. Üniversite: Sakarya Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Endüstri Mühendisliği Bilim Dalı
  13. Sayfa Sayısı: 107

Ö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.

Özet (Çeviri)

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.

Benzer Tezler

  1. Tez No

    808822

    Zaman pencereli araç rotalama problemi için kümeleme destekli metasezgisel çözüm önerisi

    A clustering approach for the metaheuristic solution of vehicle routing problem with time window

    TUĞBA GÜL YANTUR

    Yüksek Lisans

    Türkçe

    Türkçe

    2023

    Endüstri ve Endüstri MühendisliğiSakarya Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    DOÇ. DR. ÖZER UYGUN

  2. Tez No

    860425

    Makine öğrenmesi ile araç rotalama problemi için önce-kümele sonra-rotala yöntemlerinin incelenmesi

    Investigation of cluster-first route-second methods for vehicle routing problem using machine learning

    SEDAT GÜZELŞEMME

    Yüksek Lisans

    Türkçe

    Türkçe

    2024

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolMunzur Üniversitesi

    Mühendislik Yönetimi Ana Bilim Dalı

    DOÇ. DR. FARUK SERİN

  3. Tez No

    455447

    Transportation planning for the relief items distribution during an emergency

    Acil durumda yardım malzemelerinin dağıtımı için ulaşım planlaması

    EMRE ÇANKAYA

    Yüksek Lisans

    İngilizce

    İngilizce

    2017

    Endüstri ve Endüstri MühendisliğiÖzyeğin Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    DOÇ. DR. OKAN ÖRSAN ÖZENER

    DOÇ. DR. ALİ EKİCİ

  4. Tez No

    518821

    Routing and inventory loading problem for heterogeneous vehicle fleet with compartments

    Çok kompartmanlı heterojen araç filosu için envanter yükleme ve rotalama problemi

    TÜRKAY UMUT YILMAZ

    Yüksek Lisans

    İngilizce

    İngilizce

    2018

    Endüstri ve Endüstri MühendisliğiÖzyeğin Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    DOÇ. DR. ALİ EKİCİ

  5. Tez No

    748566

    Deniz yolu üzerinde göçmen sayısı tahmini ve devriye botu rotalaması

    Forecasting the number of immigrants on the maritime line and patrol boat routing

    FATMA ÇARMAN ÇEVİK

    Doktora

    Türkçe

    Türkçe

    2021

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolTOBB Ekonomi ve Teknoloji Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    PROF. DR. TAHİR HANALİOĞLU

Geri Dön