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

Abstract

Araç rotalama problemleri, başta lojistik ve dağıtım sektörleri olmak üzere literatürde üzerine oldukça çalışılmış ve çeşitli kısıt ve parametrelerden oluşan gerçek hayat problemlerinden biridir. Ana amacı maliyet enküçüklemesi olan araç rotalama problemleri içeriği kapsamında sezgisel ya da metasezgisel yöntemlerle çözümlenmektedir. Bu çalışmada, bir lojistik firmasına ait beyaz eşya ana dağıtım deposundan Ankara ve çevre illerdeki ev ya da bayilere yapılacak olan teslimatların, teslimat saat aralığı kısıtı altında rotasının planlanmasıdır. Firma Ankara'da yer alan ana dağıtım deposundan Ankara ve çevre illerdeki 75 adet bayiye 20 dakika servis süresi ile teslimat yapmaktadır. Her bayinin kendine ait teslimat zaman aralıkları bulunmaktadır. Müşteri gereksinimi olarak bayiler için belirlenen saat aralığında teslimat yapılması en önemli kısıttır. Zaman penceresinden önce ya da sonra teslimat yapılabilir ancak geç kalınması durumunda ceza maliyeti olarak maliyeti artıracaktır, incelenen problem bu nedenle "Esnek zaman pencereli araç rotalama" problemleri sınıfında yer almaktadır. Problem mevcut depoda gerçek zamanlı bir problem olmakla birlikte, sevkiyatlar planlama personelinin deneyim ve görüşlerine dayanarak planlanmakta, sistemsel bir rotalama çalışması bulunmamaktadır. Hedeflenen, sevkiyatlarda maliyetlerin azaltılması, minimum sefer sayısı ile maksimum teslimat yapılmasıdır. Sevkiyat ve hizmet kalitesinin artırılması ve planlamada oluşan hataların minimuma indirilmesi hedeflenmektedir. Sevkiyat planlama personelinin yapmış olduğu planlama sistemi incelenerek sistematik hale getirilecek çıkarımlar analiz edilmiştir. Elde edilen verilere göre bayi konumları, teslimat saat aralıkları, sipariş hacimleri sınıflandırılmıştır, müşteriye ve sevkiyata ait kısıtlar analiz edilmiştir. Önce kümele sonra rotala yaklaşımına dayanan iki aşamalı yöntem önerilmiştir. Teslimat adresleri kapasite kısıtı altında MATLAB R2022a programı kullanılarak kümelenmiştir. Siparişlerin düzenli olarak Ankara bölgesinde yoğunluk göstermesi nedeniyle yoğunluk bazlı bir kümeleme gerektirmesi, küme sayısının başlangıçta bilinememesi ve gürültü noktalarına karşı toleranslı bir kümeleme algoritması olması nedeniyle DBSCAN algoritmasının uygun bir yöntem olduğuna ulaşılır. Kümelenen her bir rota için MATLAB R2022a programı kullanılarak metasezgisel yöntemlerden biri olan Karınca Kolonisi Algoritması yaklaşımı ile zaman pencereler kısıtı altında araç rotalaması yapılmıştır. Her bayi için zaman pencereleri dışında geç ziyaret etme durumlarında ceza maliyeti eklenmiştir. Analiz sonucu elde edilen veriler ile daha önce yapılmış olan planlama verileri mali ve operasyonel olarak karşılaştırılmıştır.

Vehicle routing problems are one of the real-life problems that have been studied extensively in the literature, especially in the logistics and distribution sectors, and consist of various constraints and parameters. Vehicle routing problems, the main purpose of which is cost minimization, are solved with heuristic or metaheuristic methods within the scope of their content. In this study, the problem is to plan the routes for delivering goods from a white goods main distribution warehouse of a logistics company to homes or dealers in Ankara and surrounding cities, considering the delivery time window constraint. The company delivers goods to 75 dealers located in Ankara and surrounding cities with a 20-minute service time. Each dealer has their own delivery time window. The most important constraint is to make deliveries within the specified time window for each dealer. Deliveries can be made before or after the time window, but if there is a delay, it will incur penalty costs. Therefore, the problem examined is in the class of "Vehicle routing with flexible time windows" problems. Although the problem is a real-time problem in the existing warehouse, shipments are planned based on the experience and opinions of the planning personnel, and there is no systematic approach. The aim is to reduce costs in shipments, achieve maximum deliveries with minimum trips, improve shipment and service quality, and minimize planning errors. The inferences to be systematized were analyzed by examining the planning system made by the shipping planning personnel. According to the data obtained, dealer locations, delivery time intervals, order volumes were classified, and customer and shipment constraints were analyzed. A two-stage method based on "cluster first and then route" approach has been proposed. Due to the regular density of orders in the Ankara region, requiring a density-based clustering approach, the unknown number of clusters at the beginning, and the tolerance towards noise points, it is concluded that the DBSCAN algorithm is a suitable method. For each clustered route, vehicle routing was carried out under the time window constraint with the Ant Colony Algorithm approach, which is one of the metaheuristic methods, using the MATLAB R2022a program. Penalty costs are added for visits outside of time windows for each dealer. The data obtained as a result of the analysis and the previous planning data were compared financially and operationally.