Literature Review for Vehicle Routing Problem with Stochastic Demands

Abstract

Vehicle Routing Problem (VRP) is the problem of identifying suitable routes in a way that minimizes the cost in order to serve customers in different locations from one or more depots by one or more vehicles. However, in real life problems, Stochastic Vehicle Routing Problem (SVRP) with stochastic information appears more than deterministic problems in which all parameters are known in advance. When the studies on SVRP in the literature are examined, it is found that the researchers study the most about vehicle routing problem with stochastic demand (VRPSD) in which stochastic demand takes place. In this study, a situation was examined in such a way that customer demands are not known exactly until the vehicle reaches the customer location. In VRPSD, it is accepted that the demands from customers consist of random variables with a certain probability distribution. Studies on VRPSD in the literature have been examined in detail and a classification has been made under the specified constraints. Studies on VRPSD are evaluated according to this classification, mathematical models developed for VRPSD and the proposed solution approaches for solving the problem are laid out and an effort is made to determine which problem the researchers concentrated on the most.

Özet

Araç Rotalama Problemi (ARP), bir işletmenin farklı konumlarda yer alan müşterilerine bir veya birden fazla depodan, tek veya çok araçla hizmet verebilmek için maliyeti minimize edecek şekilde uygun rotaların belirlenmesi problemidir. Ancak gerçek hayat problemlerinde bütün parametrelerin önceden bilindiği deterministik problemlerden çok, olasılıklı bilgilerin yer aldığı Stokastik Araç Rotalama Problemi (SARP) ile karşılaşılmaktadır. Literatürde SARP konusunda yapılan çalışmalar incelendiğinde, araştırmacıların en çok stokastik talebin yer aldığı stokastik talepli araç rotalama problemini (STARP) inceledikleri tespit edilmiştir. Bu çalışmada da müşteri taleplerinin araç müşteri lokasyonuna gidene kadar kesin olarak bilinmediği, ancak müşteri lokasyonuna varıldığında öğrenildiği durum incelenmiştir. STARP’da müşterilerden gelen taleplerin belirli bir olasılık dağılımına sahip rassal değişkenlerden oluştuğu kabul edilmektedir. STARP konusunda literatürde yapılan çalışmalar ayrıntılı olarak incelenmiş ve belirlenen kısıtlar altında bir sınıflandırma yapılmıştır. STARP konusunda yapılan çalışmalar bu sınıflandırmaya göre değerlendirilmiş, STARP için geliştirilen matematiksel modeller ile problemin çözümü için önerilen çözüm yaklaşımları hakkında bilgi verilmiş ve araştırmacıların en çok hangi problem üzerinde yoğunlaştıkları belirlenmeye çalışılmıştır.

Keywords: Araç Rotalama Problemi, Stokastik Talepli Araç Rotalama Problemi, Yardımcı Eylemli Stokastik Programlama, Şans Kısıtlı Stokastik Programlama