Please use this identifier to cite or link to this item: https://hdl.handle.net/20.500.13087/3136
Title: Machine learning and mathematical programming based hybrid solution proposal for capacitated vehicle routing problem
Other Titles: Kapasiteli araç rotalama problemi için makine öğrenmesi ve matematiksel programlama temelli hibrid bir çözüm önerisi
Authors: Kartal, Zühal
Sanlı, Özgür
Keywords: Endüstri ve Endüstri Mühendisliği
Industrial and Industrial Engineering
Issue Date: 2022
Publisher: Eskişehir Teknik Üniversitesi
Abstract: Bu çalışmada, kapasiteli araç rotalama probleminin (KARP) çözümü için makine öğrenmesi teknikleri ile matematiksel programlama formülasyonlarını hibritleştiren üç aşamalı bir yaklaşım önerilmiştir. KARP'ın çözümü için ilk aşamada makine öğrenmesi algoritmaları ile düğümlerin hangi araçlara atanacağına karar verildikten sonra ikinci aşamada ortaya çıkan kümelerin toplam talep miktarının her bir aracın kapasitesini aşmaması kapasite dengeleme algoritması adı verilen bir metot tarafından garantilenmiştir. Üçüncü aşamada ise, her bir araç depodan tur oluşturmak için başlar ve gezgin satıcı problemi (GSP) matematiksel modelini kullanarak en kısa kat edilen mesafeyi bulmak için atanan tüm düğümleri ziyaret eder. KARP 'ın nihai çözümü, tüm TSP rotalarının birleştirilmesiyle oluşturulmuştur. Bu çalışmada kullanılan makine öğrenmesi algoritmaları denetimli öğrenme kategorisi altında; K-En yakın Komşuluk algoritması (K-NN) ve lojistik regresyon (LR) algoritmalarıyken; denetimsiz öğrenme kategorisi için, K-Ortalamalar (K-Means) algoritmasıdır. Önerilen yaklaşım için, farklı araç sayıları ile literatürden farklı veri setleri kullanılarak duyarlılık analizleri gerçekleştirilmiştir. Sonuç olarak önerilen hibrit yaklaşımın test problemlerinin çoğunda KARP'ın matematiksel modelinin çözümüne göre daha iyi sonuçlar verdiği gösterilmiştir.
In this study, a three-stage approach which hybridizes machine learning techniques and mathematical programming formulations, is proposed for the solution of capacitated vehicle routing problem (CVRP). In order to solve CVRP, in the first stage, it was decided the nodes to be assigned to which vehicles via machine learning algorithms, then in the second stage it was ensured that the resulting clusters' total demand amount do not exceed the vehicle capacity using a method, which is called capacity balancing algorithm. In the third stage, the vehicle started from the depot and visits all the assigned nodes to find the shortest (minimum as an alternative) travelled distance by using the traveling salesman problem (TSP) mathematical model. The final solution of the CVRP has been formed by combining all TSP routes. The machine learning algorithms that are used in this study are for supervised learning category; K-Nearest Neighborhood (K-NN) and Logistic Regression (LR) algorithms and for unsupervised learning category; K-Means algorithm. For the proposed approach, sensitivity analyzes were carried out using different datasets from the literature with a different number of vehicles. As a result, it has been shown that the proposed hybrid approach gives better results in most of the test problems than the solution of the mathematical model of CVRP.
URI: https://tez.yok.gov.tr/UlusalTezMerkezi/TezGoster?key=sELqxhTlFGAjsbjOuuiyCFnS1CRb7TFSmJKK_9WbFcHTSiSYvgGTvlyKQQ6tPRks
https://hdl.handle.net/20.500.13087/3136
Appears in Collections:Tez Koleksiyonu

Show full item record

CORE Recommender

Google ScholarTM

Check


Items in GCRIS Repository are protected by copyright, with all rights reserved, unless otherwise indicated.