A heuristic framework for solving time dependent vehicle routing problem with time windows

Abstract

Araç rotalama problemde, çoğu çözüm yaklaşımı iki talep noktası arasındaki seyahat süresini sabit kabul eder. Seyahat hızının değişkenliği, şehirlerarası ulaşım gibi uzun mesafelerde görmezden gelinebilirken kısa mesafelerde ve yüksek trafik yoğunluğundan etkilenen problemler için önemlidir.GPS teknolojisinin son on yılda sivil kullanım için yaygınlaşması ile aracında bir GPS uygulaması taşıyan ve bunu bir coğrafi veri tabanı ile paylaşan sürücülerin anlık trafik verilerini toplamak mümkün olmuştur.Bu teknolojik gelişmeler pek çok araştırmacıyı zaman bağımlı hız ve zaman pencereli dağıtım gibi daha gerçekçi problemlere yönlendirmiştir. Bu çalışma Zaman Bağımlı ve Zaman Pencereli Araç Rotalama Problemi için MetaOpt tarafından yönlendirilen bir Tabu Arama yaklaşımı önerir. Önemli bir değişken olan başlangıç zamanının değiştirilmesi literatürde rotalar belirli olduktan sonra ikinci bir çalışma ile çözülmeye çalışılmaktadır. Bu çalışma sıfırdan farklı başlangıç zamanlarını tabu arama algoritması devam ederken araştırmayı amaçlamaktadır.

In vehicle routing problem, most of the solution approaches deals with problems that the travel time between two demand points is assumed constant. While dealing with long distances like intercity transportation, variation in travel speed is negligible, it is essential when it comes to short distances and high traffic density. However as GPS technology got more common for civilian use in the last decade; it became possible to collect instant traffic data from drivers who carry a GPS application in their vehicle and share it with a geospatial database. These technological developments intrigued researchers to study with more real-life problems such as time-dependent vehicle routing problem with time windows which is assuming the travel speed is perfectly correlated with time of the day and customers want their demand is satisfied within a predefined time period. This study suggests a Tabu Search algorithm guided by MetaOpt framework for TDVRPTW problems. Optimizing departure times in vehicle routes are considered with diversification. Though some approaches are developed and introduced, they all focus on post-processing of the main problem. This study is aimed to search different-than-zero departure time in tabu search is processing.