The vehicle routing problem with traffic conditions

Abstract

Araç rotalama problemi (ARP), belirli bir talebi minimum maliyet ile başlangıç ve bitiş noktası depo olan rota boyunca müşterilere ulaştırmayı amaçlar. Temel bir araç rotalama problemi, kapasiteleri belirli araçlar ile tüm müşterilerin memnuniyetini sağlayan, minimum taşıma maliyetli rotaların oluşturulması için kullanılır. Müşteri memnuniyetini sağlayabilmek için taşımanın doğru miktarda ve istenilen zamanda yapılması önemlidir. Bu durum malzeme taşınmasında ve ürün dağıtımında doğru rotanın seçilmesinin önemini arttırmaktadır. Araç rotalama problemi NP-zor bir problemdir. Bu nedenle, matematiksel çözüm yöntemleri ile kabul edilebilir sürelerde sadece küçük boyutlu problemlerin çözümü yapılabilmektedir. Müşteri ve araç sayısı, kapasite ve zaman kısıtları arttıkça problemin çözümü zorlaşmaktadır. Araştırmada gerçek hayat koşullarına uygun bir araç rotalama problemi ele alınmıştır. Rotanın en iyi şekilde oluşturulabilmesi için de kat edilen toplam mesafe dışında, müşteri memnuniyeti bağlamında zamanın da dikkate alınması gerekmektedir. Seçilen rota üzerindeki araç trafiği, rota üzerinde harcanan zamanı etkileyeceğinden, rota belirlenmesinde önemli bir rol oynamaktadır. Dolayısıyla, bu çalışmada araç rotalama probleminin çözümünde alternatif yollar üzerindeki trafik koşulları da dikkate alınmış olup, bu çalışma ile pratik hayata ve literatüre katkı yapılması hedeflenmiştir. Problemin formülasyonu ve çözümü için öncelikle literatür araştırması yapılmıştır. Literatür araştırmasını takiben, belirlenen araç rotalama probleminin tamsayılı doğrusal programlama ile matematiksel formülasyonu oluşturulmuştur ve Genetik Algoritma, Lin-Kernighan Algoritması ve 2-opt algoritmasının birleşiminden oluşan metasezgisel bir metot geliştirilmiştir.

The Vehicle Routing Problem (VRP) is a combinatorial optimization and integer programming problem seeking to service a number of customers with a fleet of vehicles. The classical VRP aims to find a set of routes at a minimal cost for beginning and ending points of the route at the depot, so that the known demands of all customers are fulfilled. Each customer is visited only once, by only one vehicle, and each vehicle has a limited capacity. It is important that the right amount of product should be transported at the right time to ensure customer satisfaction. So, choosing the right route is very critical for transportation systems. The vehicle routing problem is an NP-Hard problem. When number of customers and vehicles, constraints of capacity, and time increases, the solution of the problem becomes more difficult.In this study, a vehicle routing problem, which is suitable for real-life situation is discussed. In order to establish the best route apart from the traveled total distance, time must be taken into account for customer satisfaction. Traffic volume on the selected route will affect the time which is spent on the route. So, traffic plays an important role in determining the route. In this study, traffic conditions on alternative ways are taken into account to solve VRP. To achieve this aim, literature review is conducted, then integer linear programing formulation and metaheuristic method which is a combination of Genetic Algorithm, Lin-Kernighan Algorithm and 2-opt Algorithm, is developed.