A Clustering Algorithm For The Capacitated Vehicle Routing Problems With Stochastic Demands

Abstract

In today’s world, logistics problems are crucial for the supply chain management. The vehicle routing problems are one of the most studied combinatorial optimization problems in the logistics literature. In real life applications, all of the parameters of the problem may not be known. In this paper, we considered the capacitated vehicle routing problem with stochastic demands. Uniform and normal distributions were analyzed on customer demands to observe the stochastic nature of the problem. These methods were compared by using GAMS with different test problems which were taken from the literature. The clustering analysis including the K-means algorithm also applied on large-sized test problems. All of the obtained results were presented in detail.

Keywords

• Clustering Analysis
• K-Means
• Modelling
• Stochastic Demand
• VRP

Stokastik Talepli Kapasite Kısıtlı Araç Rotalama Problemleri için Bir Kümeleme Algoritması

Abstract

Günümüz dünyasında, tedarik zinciri yönetimi için lojistik problemler çok kritiktir. Araç rotalama problemi, lojistik literatüründe en çok çalışılan kombinatoryal optimizasyon problemlerinden biridir. Gerçek hayat uygulamalarında problemin tüm parametreleri bilinmeyebilir. Bu çalışmada, stokastik talepli kapasite kısıtlı araç rotalama problemi ele alınmıştır. Problemin stokastik yapısını gözlemlemek için müşteri talepleri düzgün ve normal dağılımlar ile analiz edilmiştir. Bu yöntemler, literatürden alınan farklı test problemleri ile GAMS kullanılarak karşılaştırılmıştır. Büyük boyutlu test problemleri için k-ortalamalar algoritmasını içeren kümeleme analizi uygulanmıştır. Elde edilen tüm sonuçlar ayrıntılı olarak gösterilmiştir.

Keywords

• Kümeleme Analizi
• K-Ortalamalar
• Modelleme
• Stokastik Talep
• ARP

References

1. [1] Dantzig G.B., Ramser, J.H. The Truck Dispatching Problem, Informs, 6 80-91, 1959.
2. [2] Dror M., Trudeau P. Savings by Split Delivery Routing, Transportation Science, 23 141–145, 1989.
3. [3] Laporte G., Louveaux F., Mercure H. Models and exact solutions for a class of stochastic location routing problems, European Journal of Operational Research, 39 71–78, 1989.
4. [4] Smith S.L., Pavone M., Bullos F., Frazzoli E. Dynamic vehicle routing with priority classes of stochastic demands, IAM Journal on Control and Optimization, 48:5 3224–3245, 2010.
5. [5] Tripathi M., Kuriger G. An ant based simulation optimization for vehicle routing problem with stochastic demands, IEEE Winter Simulation Conference (WSC 2009), December, 2009.
6. [6] Erera A.L., Morales J.C., Savelsbergh M. The vehicle routing problem with stochastic demand and duration constraints, Transportation Science, 44:4 474-492, 2010.
7. [7] Moghaddam F.B., Babak R.R., Sadjadi J.S. Vehicle routing problem with uncertain demands: An advanced particle swarm algorithm, Computers and Industrial Engineering, 62 306–317, 2012.
8. [8] Goodson J.C., Ohlmann J.W., Thomas B.W. Cyclic-order neighborhoods with application to the vehicle routing problem with stochastic demand, European Journal of Operational Research, 217:2 312–323, 2012.

9. [9] Niu Y., Kong D., Wen R., Cao Z., Xiao J. An improved learnable evolution model for solving multi-objective vehicle routing problem with stochastic demand, Knowledge-Based Systems, 230 107378, 2021.
10. [10] Florio A.M., Hartl R.F., Minner S., Salazar-González J. J.A branch-and-price algorithm for the vehicle routing problem with stochastic demands and probabilistic duration constraints, Transportation Science, 55:1 122-138, 2021.
11. [11] Gaur D.R., Mudgal A., Singh R.R. Improved approximation algorithms for cumulative VRP with stochastic demands, Discrete Applied Mathematics, 280 133-143, 2020.
12. [12] Xia X., Liao W., Zhang Y., Peng X. A discrete spider monkey optimization for the vehicle routing problem with stochastic demands, Applied Soft Computing, 111 107676, 2021.
13. [13] Salavati-Khoshghalb M., Gendreau M., Jabali O., Rei W. An exact algorithm to solve the vehicle routing problem with stochastic demands under an optimal restocking policy, European Journal of Operational Research, 273:1 175-189, 2019.
14. [14] Islam M.A., Gajpal Y., El-Mekkawy T.Y. Mixed fleet based green clustered logistics problem under carbon emission cap, Sustainable Cities and Society, 72 103074, 2021.
15. [15] Durak P. Personel servisi rotalama probleminin optimizasyonu, Yüksek lisans tezi, Eskişehir Teknik Üniversitesi, 2021.
16. [16] Bruwer F. Petal-shaped Clustering for the Capacitated Vehicle Routing Problem, Doctoral dissertation, University of the Witwatersrand, Faculty of Engineering and the Built Environment, School of Mechanical, Industrial and Aeronautical Engineering, 2018.
17. [17] Comert S.E., Yazgan H.R., Kır S., Yener F. A cluster first-route second approach for a capacitated vehicle routing problem: a case study, International Journal of Procurement Management, 11:4 399-419, 2018.
18. [18] Alpaslan Takan, M., Agayeva C. On Some Vehicle Routing Problems With Random Demand. International Conference on Multidisciplinary, Science, Engineering and Technology Conference (IMESET 2018), 25-27 October, Dubai, 2018.
19. [19] Toth P., Vigo D. The vehicle routing problem, SIAM, 2002.
20. [20] Miller C.E., Tucker A.W., Zemlin R.A. Integer programming formulations and traveling salesman problems, Journal of the Association for Computing Machinery, 7 326–329, 1960.
21. [21] Agayeva C., Alpaslan Takan M. Stokastik talepli kapasite kısıtlı araç rotalama problemine yönelik karşılaştırmalı bir yaklaşım, Bilecik Şeyh Edebali Üniversitesi Fen Bilimleri Dergisi, 7:2 971-979, 2020.
22. [22] Augerat P., Belenguer J.M., Benavent E., Corberán A., Naddef D., Rinaldi G. Computational results with a branch and cut code for the capacitated vehicle routing problem, Technical Report R, 495 1995.
23. [23] Christofides N., Mingozzi A., Toth P. The Vehicle Routing Problem, Combinatorial Optimization, Wiley, Chichester, 1979.
24. [24] Agayeva C., Alpaslan Takan M. Condition of Optimality for Stochastic Switching Linear Systems with Variable Time Delay on State. International Conference on Multidisciplinary, Science, Engineering and Technology Conference (IMESET 2018), 25-27 October, Dubai, 2018.