A clustering based heuristic for location routing problems

Abstract

Bu tezde lokasyon rotalama problemleri (LRP) uzerinde durulmustur. Problemin 56zumu i5in kumeleme temelli sezgisel bir yontem onerilmistir. LRP iki zor problem olan lokasyon tahsisi ve arac rotalama problemlerinin birlesmesiyle olusmaktadir. LRP ile bu iki probleme es zamanh 56zum uretilmektedir. Ama5 fonksiyonu rotalama, ara5 kullanma ve depo maliyetinden olusmaktadir ve enazlanmaya cahsilmaktadir. Literaturde genellikle sabit depo acihm maliyeti kullamlmaktadir. Bu tezde depo acma maliyeti kapasite belli degerlerin uzerine 5iktiginda artmaktadir ve genelden farkhdir. Maliyet fonksiyonunun bu yapisi ve LRP nin icsel kompleksligi birlestiginde problemin coziimii zorlasmaktadir. Onerdigimiz sezgisel yonteme gore arac kapasitelerine gore kumeler olusturmustur ve her kume i5inde gezgin satici problem! cozulmustiir. Yerel tarama yontemleri uygulanarak 56zum iyilestirilmistir. Son olarak olusturulan kumeler uygun depolara atanmistir.Anahtar Kelimeler: Arac Rotalama, Lokasyon Dagitim, Lokasyon Rotalama, SezgiselYontemler

In this thesis we address the location routing roblem (LRP) in which vehicle routing and warehouse location/allocation decisions are made simultaneously. LRP deals with determining the optimal number of warehouses as well as their locations while assigning customers to warehouses so that the shortest vehicle routes are achieved. The objective is to minimize total vehicle related costs (fixed vehicle cost and route cost) and the cost of operating the warehouses. To solve this NP-hard roblem, we ropose a clustering based heuristic aproach which consists of three arts. Firstly, we determine the customer clusters based on vehicle capacities, i.e. all customers in the cluster are serviced by the same vehicle. Secondly, we solve a traveling salesman roblem for each cluster. Thirdly, we attempt to improve the routes by using local search techniques. Finally, the routed clusters are assigned to warehouses.Keywords: Clustering, Heuristics, Location-allocation, Location-routing, Vehicle routing