A Comparative Approach to Capacitated Vehicle Routing Problem with Stochastic Demand

Abstract

In this study, stochastic vehicle routing problem (SVRP), which is one of the most important combinatorial optimization problems studied in the literature, is discussed. As it is known, the capacities of the vehicles and the demands of the customers are known in the classical vehicle routing problem, so the problem is deterministic. Since the problem parameters in real life problems vary according to the different situations, it is rare to know the exact values of the parameters. Therefore, there is a need to formulate the classical vehicle routing problem under uncertainty conditions. In this study, the vehicle routing problem is analyzed, and the demands are stochastically evaluated for the cases where customer demands are uncertain. In order to examine the variable demand conditions, the effects of these distributions on the solutions of the problem are investigated by using three different distributions, which are uniform, exponential, and Poisson. The GAMS software is used for computational results and the results of the stochastic and deterministic models of the problem are compared at the final part of the study.

Keywords

• Vehicle Routing Problem
• Uniform Distribution
• Exponential Distribution
• Poisson Distribution

Stokastik Talepli Kapasite Kısıtlı Araç Rotalama Problemine Yönelik Karşılaştırmalı Bir Yaklaşım

Abstract

Bu çalışmada literatürde çalışılan en önemli kombinatoryal eniyileme problemlerinden biri olan stokastik araç rotalama problemi (SARP) ele alınmıştır. Bilindiği üzere klasik araç rotalama probleminde, araçların kapasiteleri ve müşterilerin talepleri bilinmektedir yani problem deterministiktir. Gerçek hayat problemlerinde problem parametreleri farklı durumlara göre değişkenlik gösterdiğinden, parametrelerin kesin değerlerinin bilinmesine az rastlanmaktadır. Bu yüzden belirtilen klasik araç rotalama probleminin belirsizlik koşulları altında formüle edilmesine ihtiyaç duyulmaktadır. Ele alınan çalışmada, müşteri taleplerinin belirsiz olduğu durumlar için, araç rotalama problemi analiz edilmiştir ve talepler stokastik olarak modelde değerlendirilmiştir. Değişken talep durumlarını incelemek için düzgün, üstel ve Poisson olmak üzere 3 farklı dağılım kullanılarak, bu dağılımların problemin çözümleri üzerindeki etkileri incelenmiştir. Hesaplama sonuçları için GAMS yazılımı kullanılmıştır ve çalışmanın sonunda ele alınan problemin stokastik ve deterministik modellerinin sonuçları kıyaslanmıştır.

Keywords

• Araç Rotalama Problemi
• Düzgün Dağılım
• Üstel Dağılım
• Poisson Dağılım

References

1. Dantzig, G.B.,& Ramser, J.H. (1959). The Truck Dispatching Problem. Informs, 6, 80-91.
2. Toth, P., & Vigo, D. (2002).The Vehicle Routing Problem, Bologna, SIAM.
3. Dror M., & Trudeau, P.. (1989). Savings by Split Delivery Routing. Transportation Science, 23, 141–145.
4. Laporte, G., Louveaux, F., & Mercure, H., (1989). Models and exact solutions for a class of stochastic locationrouting problems. European Journal of Operational Research, 39, 71–78.
5. Yang, W-H., Kamlesh M., & Ronald, B.H. (2000). Stochastic vehicle routing problem with restocking. Transportation Science, 34, 99–112.
6. Smith, S.L., Pavone, M., Bullos, F., & Frazzoli, E. (2010). Dynamic vehicle routing with priority classes of stochastic demands. IAM Journal on Control and Optimization, 48(5), 3224–3245.
7. Bertsimas, D. (1991). A vehicle routing problem with stochastic demand. Journal of Operations Research, 40(3), 554–585.
8. Tripathi, M., Kuriger, G., Wan, H. (2009). An ant based simulation optimization for vehicle problem with stochastic demands. 2009 Winter Simulation Conference, December 13-16, Austin, USA.

9. Erera, A.L., Morales, C.J., & Savelsbergh, M. (2010). The vehicle routing problem with stochastic demand and duration constraints. Report, The Supply Chain and Logistics Institute, Georgia Institute of Technology School of Industrial and Systems Engineering Atlanta, GA.
10. Moghaddam F.B., Babak, R.R., & Sadjadi J.S. (2012). Vehicle routing problem with uncertain demands: An advanced particle swarm algorithm. Computers and Industrial Engineering, 62, 306–317.
11. Kenyon, S.A., & Morton, P.D. (2003). Stochastic vehicle routing with random travel times. Journal of Transportation Science, 37(1), 69–82.
12. Goodson, J.C., Ohlmann, J.W., & Thomas, B.W. (2012). Cyclic-order neighborhoods with application to the vehicle routing problem with stochastic demand. European Journal of Operational Research, 217(2), 312–323.
13. Bertsimas, D. (1992). A vehicle routing problem with stochastic demand. Operations Research, 40, 574–585.
14. Gendreau, M., Laporte, G., & Sèguin, R. (1996). Stochastic vehicle routing. European Journal of Operational Research, 88, 3–12.
15. Campbell, M.A., Gendreau M., & Thomas, B.W. (2011). The orienteering problem with stochastic travel and service Times. Annals of Operations Research, 186, 61–81.
16. Laporte, G. (1992). The vehicle routing problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 59, 345–358.
17. Guo, Z., Mak, K.L. (2004). A heuristic algorithm for the stochastic vehicle routing problems with soft time windows. Proceedings of the 2004 Congress on Evolutionary Computation, IEEE, 19-23 June, Portland, USA.
18. Dinh, T., Fukasawa, R., Luadtka, J. (2018). Exact algorithms for the chanceconstrained vehicle routing problem, Mathematical Programming, 172(1- 2), 105-138.
19. Calvet, L., Bernaus, A.P., Travessat-Baro, O., Juan, A.A. (2016). A Simheuristic for the heterogeneous site-dependent asymetric VRP with stochastic demands, Advances in Artificial Intelligence, 408-417.
20. Calvet, L.,Wang, D., Juan, A., Bove, L. (2019). Solving the multidepot vehicle routing problem with limited depot capacity and stochastic demands, International Transactions in Operational Research, 26, 459-484.
21. Berhan, E., Beshah, B., Kitaw, D., & Abraham, A. (2014). Stochastic vehicle routing problem: a literature survey. Journal of Information and Knowledge Management, 13 (3), 1450022:1-12.
22. Miller, C. E., Tucker, A. W., & Zemlin, R. A. (1960). Integer programming formulation of traveling salesman problems, Journal of the ACM, 7 (4), 326-329.
23. Christofides, N., Mingozzi, A., & Paolo, T. (1981). Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations. Mathemtical Programming, 20 (1), 255-282.