Periodic vehicle routing problem with two types of visits

Abstract

Araç rotalama problemi 1950'li yıllardan beri çalışılan modern bir konudur. Son yıllarda, günümüzün rekabetçi ortamında, tedarik zinciri yönetimi ve dağıtım kanallarının önemi ciddi bir biçimde artmıştır. Araç rotalama problemi, bir aracın bir veya daha fazla depodan ayrılıp tüm müşterileri ziyaret ederek tekrar depo veya depolara dönüş yapmasını amaçlayan problemdir. Genellikle, araç rotalama probleminin amacı toplam kat edilen mesafeyi en azlayarak taşıma maliyetini düşürmektir. Periyodik araç rotalama problemi, klasik araç rotalama probleminin bir varyantıdır. Periyodik araç rotalama problemi, planlama periyodu içerisinde bulunan birden fazla günde müşterileri ziyaret sıklıklarına göre bir veya birden fazla ziyaret edilmesi üzerine kurulu bir problemdir. Problem her bir gün için ziyaret edilecek müşterilere ve bu müşterilerin ziyaret edilmesi için en uygun rotaya karar verir. Genellikle, ana amaç müşteri ziyaretleri için belirlenen rotaları en küçüklemektir. Müşterilerin ziyaret günlerini organize etmek, taşıma maliyetini ve araç sayısını düşürmek için önemli bir avantaj sağlar. Periyodik araç rotalama problemi 2 farklı ziyaret tipi, birbirini takip eden günlerde ziyaret edilmesi zorunlu olan iki farklı amaçlı ziyaret içermektedir. İlk ziyaret, talep bilgisini edinmek ve ürünlerin mağazadaki görünürlüğünü arttırmak üzere yapılan çalışmaları yapabilmek amaçlarıyla yapılmaktadır. Bu ziyaretler, görece küçük, hızlı araçlarla yapılmaktadır ve zaman kapasitesine sahiptir. Diğer taraftan, ikinci tip araçlar görece büyük, yavaş ve fiziksel kapasiteye sahiptir. Bu araçların ziyaret amacı ise ürünlerin müşteriye teslim edilmesidir. Daha önce de belirtilmiş olduğu gibi eğer bir müşteri herhangi bir küçük araç ile ziyaret edilmiş ise takip eden günde büyük araç ile ziyaret edilmeli ve ürünler müşteriye teslim edilmelidir. Bu sebeple, kapasite ve özellikleri farklı bu araçlarla birbirini takip eden günlerde aynı rotaları kullanarak ziyaretlerin gerçekleştirilmesi mümkün olmayabilir. Bu çalışmada, yeni bir alt sınır algoritması ve sezgisel yöntem algoritması geliştirilmiştir. Literatürde sıkça kullanılan örnek problemler üzerinde geliştirilen yöntemler test edilmiş ve sonuçları gösterilmiştir. Bu araştırma, Türkiye Bilimsel ve Teknolojik Araştırma Kurumu (TÜBİTAK) tarafından 1001 araştırma geliştirme programı kapsamında, 213M425 numaralı proje olarak desteklenmektedir.

Vehicle routing problem is a contemporary topic and it has been studied since 1950's. In last decades, the importance of supply chain management and distribution channels has increased for today's competitive environment. Vehicle routing problem (VRP) is the problem in which vehicles departure from one or more depot(s), visit customers and finally return to the depot(s). Generally, VRP aims to minimize the total distance of the vehicles' routes and therefore decrease transportation costs. Periodic vehicle routing problem (PVRP) is a variant of the classical vehicle routing problem. PVRP is based on visiting customers once or more during a planning horizon with multiple days. The problem decides the customers to be visited and the routes for each day. In general, the goal is to minimize the total length of the routes. Organizing the visit days properly provides an important advantage to decrease delivery costs and the number of vehicles. PVRP with two types of visits (PVRP2TV) involves two types of visits that must be made on consecutive days in PVRP setting. The first type visit to the customer is for collecting demand information and increasing the visibility of the products at the store, the second type of visit is for delivering the goods. The first type visits take place with small and fast vehicles with time capacity constraints. On the other hand, the second type visits realized with relatively large scale, slow and physical capacitated vehicles. Hence using the same routes for the consecutive days might not be feasible. In this thesis, we develop a mathematical programming model and a special lower bound algorithm We also propose a heuristic algorithm based on variable neighborhood search (VNS) and conduct computational tests on the modified versions of the widely used test instances. This thesis is funded by The Scientific And Technological Research Council of Turkey (TÜB TAK) as TÜB TAK 1001 research and development program with grant number 213M425.