Literature Review for Vehicle Routing Problem with Stochastic Demands
Yıl 2019,
Cilt: 18 Sayı: 36, 181 - 222, 06.11.2019
Beste Desticioğlu
,
Bahar Özyörük
Öz
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.
Kaynakça
- Kitaplar
- Jaillet, P. ve Odoni, A. (1988). The Probabilistic Vehicle Routing Problem in Vehicle Routing: Methods and Studies, B. L. Golden and A. A. Assad (eds.), North-Holland, Amsterdam.
- Makaleler
- Ak, A., Erera, A.L., (2007). A Paired-Vehicle Recourse Strategy for the Vehicle-Routing Problem with Stochastic Demands, Transportation Science, 41, 222 –237.
Arvianto, A., Saptadi, S. Budiawan, W., Nartadhi, R.L. (2019). Vehicle routing problem model and simulation with probabilistic demand and sequential insertion, AIP Conference Proceedings.
Balaprakash, P. Birattari, M., Stützle, T., Dorigo, M. (2015), Estimation-based metaheuristics for the single vehicle routing problem with stochastic demands and customers, Computational Optimization and Applications, 61(2), 463-487.
Bastian, C., Kan, R., (1992). The stochastic vehicle routing problem revisited, European Journal Of Operational Research, 56, 407-412.
Berhan, E. (2016), Stochastic vehicle routing problems with real simultaneous pickup and delivery services, Journal of Optimization in Industrial Engineering, 19, 1-7.
Bertazzi, L., Secomandi, N. (2018). Faster rollout search for the vehicle routing problem with stochastic demands and restocking, European Journal Of Operational Research, 270(2018), 487-497.
Bertsimas, D. J., (1992). A vehicle routing problem with stochastic demand, Operations Research, 40 (3) , 574–585.
Bertsimas, D. J., Chervi, P., Peterson, M., (1995). Computational approaches to stochastic vehicle routing problems, Transportation Science, 29 (4), 342–352.
Bianchi, L., Birattari, M., Manfrin, M., Mastorolilli, M., Paquete, L., Rossi-Doria, O., Schiavinotto, T. (2004). Metaheuristics for the vehicle routing problem with stochastic demands, In International conference on parallel problem solving from nature 450-460, Springer Berlin Heidelberg,
Bianchi, L., Birattari, M., Manfrin, M., Mastrolilli, M., Paquete, L., Rossi-Doria, O., Schiavinotto, T., (2006). Hybrid Metaheuristics for the Vehicle Routing Problem with Stochastic Demand, Journal of Mathematical Modelling and Algorithms, 5, 91-110.
Biesinger, B., Hu., B., Raidl, G.R. (2015). A variable neighborhood search for the generalized vehicle routing problem with stochastic demands, Evolutionary Computation in Combinatorial Optimization, 48-60.
Biesinger, B., Hu., B., Raidl, G.R. (2016). An integer L-Shaped method for the generalized vehicle routing problem with stochastic demands, Electronic Notes in Discrete Mathematics,52, 245-252.
Biesinger, B., Hu., B., Raidl, G.R. (2018). A genetic algorithm in combination with a solution archive for solving the generalized vehicle routing problem with stochastic demands, Transportation Science, 52(3), 497-.
Calvet, L., Juan, A.A., Schefers, N. (2015). Solving the Multi-Depot Vehicle Routing Problem considering Uncertainty and Risk Factors, Proceedings of the ICRA6/Risk International Conference, Barcelona, Spain.
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.
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(2019), 459-484.
Chan, Y. , Carter, W. B. , Burnes, M. D. (2001). A multiple-depot, multiple-vehicle, location-routing problem with stochastically processed demands, Computers & Operations Research, 28(8), 803-826.
Chang, M.S. (2005). A vehicle routing problem with time windows and stochastic demands, Journal of the Chienese Institute of Engineering, 28(5),783–794.
Desticioğlu, B. ve Özyörük, B. (2019). Dinamik ARP, Çok Depolu ARP ve Eş Zamanlı Topla Dağıt ARP İçin Literatür Taraması, MAS International Conference on Mathematics-Engineering and Natural&Medical Sciences-III, 345-363.
Dimitrakos, T.D. ve Kyriakidis, E.G. (2015). A single vehicle routing problem with pickups and deliveries continous random demands and predefined customer order, European Journal of Operational Research, 244(3), 990-993.
Dinh, T., Fukasawa, R., Luadtka, J. (2018). Exact algorithms for the chance-constrained vehicle routing problem, Mathematical Programming, 172(1-2), 105-138.
Dror, M., Laporte, G., Trudeau, P., (1989).Vehicle routing with stochastic demands; Properties and solution frameworks, Transportation Science, 23 (3), 166-176.
Dror, M., Trudeau, P., (1986). Stochastic vehicle routing with modified savings algorithm, European Journal of Operational Research, 23, 228-235.
Dror, M., (1993). Modeling Vehicle Routing with Uncertain Demands as a Stochastic Program: Properties of the Corresponding Solution, European Journal of Operational Research, 64, 432–441.
Dror, M., Laporte, G., Louveaux, F.V. (1993). Vehicle routing with stochastic demands and restricted failures, ZOR Zeitschrift für Operations Research Methods and Models of Operation Research 37(3), 273-283.
Dror, M. (2016). Vehicle routing with stochastic demands: Models & computational methods, International Series in Operations Research and Management Science, 46, 425-449.
Erera, A.L., Savelsbergh, M., Uyar, E. (2009). Fixed routes with backup vehicles for stochastic vehicle routing problems with time constraints, Networks, 54(4), 270–283.
Erera, A.L., Morales, J.C., Savelsbergh, M. (2010). The vehicle routing problem with stochastic demand and duration constraints, Transportation Science, 44(4), 474–492.
Festa, P., Pastore, T., Ferore, D., Juan, A.A., Bayliss, C. (2018). Integrating Biased-randomized GRASP with Monte Carlo simulation for solving the vehicle routing problem with stochastic demands, 2018 Winter Simulation Conference, 2989-3000.
Gauvin, C., Desaulniers, G., Gendreau, M. (2014). A branch-cut-and-price algorithm for the vehicle routing problem with stochastic demands, Computers & Operations Research, 50, 141–153.
Gee, S.B., Arokiasami, W.A., Jiang, J., Tan, K.C. (2016), Decomposition-based multi-objective evolutionary algortihm for vehicle routing problem with stochastic demands, Soft Computing, 20(9), 3443-3453.
Gendreau, M., Laporte, G., Seguin, R. (1995). An exact algorithm for the vehicle routing problem with stochastic demands and customers, Transportation Science, 29(2), 143-155.
Gendreau, M., Laporte, G., Guo, B. (1996). Stochastic vehicle routing: Invited review, European Journal of Operational Research, 88, 3-12.
Ghilas, V., Demir, E. ve Woensel, T.V. (2016). A scenerai-based planning for the pickup and delivery problem with time windows, scheduled lines and stochastic demands, Transportation Research Part B: Methodological, 91, 34-51.
Goel, R., Maini, R., Bansal, S. (2019), Vehicle routing problem with time windows having stochastic customer demands and stochastic service times: Modeling and solution, Journal of Computational Science, 34, 1-10.
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.
Goodson, J.C. (2015). A priori policy evaluation and cyclic-order-based simulated annealing for the multicompartment vehicle routing problem with stochastic demands, European Journal of Operational Research, 241(2), 361–369.
Goodson, J.C., Thomas, B.W., Ohlmann, J.W. (2015). Restocking-based rollout policies for the vehicle routing problem with stockhastic demand and duration limits, Transportation Science, 50(2), 363-370.
Gounaris, C.E., Wiesemann, W., Floudas, C.A. (2013). The robust capacitated vehicle routing problem under demand uncertainty, Operations Research, 61(3), 677–693.
Gutierrez, A. Dieulle, L., Labadie, N. ve Velasco, N. (2018). A hybrid metaheuristic algorithm for the vehicle routing problem with stockhastic demands, Computers & Operations Research, 99, 135-147.
Haugland, D., Ho, S.C., Laporte, G. (2007). Designing delivery districts for the vehicle routing problem with stochastic demands, European Journal of Operational Research, 180(3), 997–1010.
Hernandez, F., Gendreau, M., Jabali, O. ve Rei, W. (2019). A local branching metaheuristic for the multi-vehicle routing problem with stochastic demands, Journal of Heuristics, 25(2),215-245.
Hjorring, C., Holt, J. (1999). New optimality cuts for a single-vehicle stochastic routing problem, Annals of Operations Research, 86, 569–584.
Hou, L., Hou, Z. (2013). A novel discrete differential evolution algorithm, Telkomnika, 11(4), 1883-1888.
Hou L., Zhou, H., (2010). Stochastic vehicle routing problem with uncertain demand and travel time and simultaneous pickups and delivery, Third International Joint Conference on Computational science and Optimization, 32-35.
Hou, L., Zhou, H., Zhao, J., (2010). A novel discrete differential evolution algorithm for stochastic VRPSPD, Journal of Computational Information Systems, 6(8), 2483-2491.
Hu, C., Lu, J., Liu, X. Ve Zhang, G. (2018). Robust vehicle routing problem with hard time windows under demand and travel time uncertainty, Computational Optimization and Applications, 61(2), 463-487.
Ismail, Z. Ve Irhamah, I. (2008). Solving the vehicle routing problem with stochastic demands via hybrid genetic algorithm- tabu search, Journal of Mathematics and Statistics, 4(3), 161-167.
Jabali, O., Rei, W., Gendreau, M., Laporte, G. (2014). Partial-route inequalities for the multi-vehicle routing problem with stochastic demands, Discrete Applied Mathematics, 177, 121-136.
Juan, A., Faulin, J., Grasman, S., Riera , D., Marull, J., Mendez, C. (2011) Using safety stocks and simulation tosolve the vehicle routing problem with stochastic demands, Transportation Research Part C:EmergencyTechnology, 19(5), 751–765, Freight Transportation and Logistics.
Juan, A., Faulin, J., Jorba, J., Cacares, J., Marques, J.M. (2013) Using parallel & distributed computing solving real time vehicle routing problems with stochastic demands, Annals of Operations Research, 207(1), 43-65.
Kyriakidis, E.G. ve Dimitrakos, T.D. (2015). Single vehicle routing problem with a predefined customer sequence, stochastic demands and partial satisfaction of demands, Operations Research Proceedings, 157-164.
Laporte, G., Louveaux, F., Mercure, H. (1989). Models and exact solutions for a class of stochastic location-routing problems, European Journal of Operational Research, 39(1), 71-78.
Laporte, G., Louveaux, F., (1990). Formulations and Bounds for Stochastic Vehicle Routing Problem with Uncertain Supplies in Economic Decision-Making: Games, Econometrics, and Optimization, J. J. Gabzewicz, J. F. Richard, and L. A. Wolsey (eds.), North-Holland, Amsterdam.
Laporte, G., Louveaux, F.V., Hamme, L.V. (2002). An integer L-shaped algorithm for the capacitated vehicle routing problem with stochastic demands, Operational Research, 50(3), 415–423.
Lee, C., Lee, K., Park, S. (2012). Robust vehicle routing problem with deadlines and travel time/demand uncertainty, Journal of Operational Research Society, 63(9), 1294–1306.
Lei, H. , Laporte, G. ,Guo, B. (2011). The capacitated vehicle routing problem with stochastic demands and time windows, Computers & Operations Research, 38(12), 1775-1783.
Liu, C., Kou, G., Huang, F. (2016). Vehicle coordinated strategy for vehicle routing problem with fuzzy demands, Mathematical Problems in Engineering, 2016, 1-10.
Louveaux, F.V. ve Salazar-Gonzalez, J.J. (2018). Exact approach for the vehicle routing problem with stockhastic demands and preventive returns, Transportation Science, 52(6), 1297-
Luo, Z., Qin, H., Zhang, D. Ve Lim, A. (2016). New exact algorthm and solution properties for the vehicle routing problem with stochastic demands and weight-related cost, Transportation Research Part E: Logistics and Transportation Review, 85, 69-89.
Marinaki, M. ve Marinakis, Y. (2016). A glowworm swarm optimization algorithm for the vehicle routing problem with stockhastic demands, Expert Systems with Applications, 46, 145-163.
Marinakis, Y., Iordanidou, G.R., Marinaki, M. (2013). Particle swarm optimization for the vehicle routing problem with stochastic demands, Applied Soft Computing, 13(4), 1693-1704.
Marinakis, Y., Marinaki, M. ve Spanou, P. (2015). A memetic differantial evolution algorthm for the vehicle routing problem with stochastic demands, Adaptation and Hybridization in Computational Intelligence, 18, 185-204.
Mendoza, J.E., Castanier, B., Gue´ret, C., Medaglia, A.L., Velasco, N. (2010). A memetic algorithm for the multi compartment vehicle routing problem with stochastic demands. Computers & Operations Research, 37(11), 1886–1898.
Mendoza, J.E., Villegas, J.G. (2013). A multi-space sampling heuristic for the vehicle routing problem with stochastic demands, Optimization Letters, 7(7), 1503–1516.
Mendoza, J.E., Rousseau, L.M. ve Villegas, J.G. (2016). A hybrid metaheuristics for the vehicle routing problem with stochastic demand and duration constraints, Journal of Heuristics, 22(4), 539-566.
Minis, I., Tatarakis, A. (2011). Stochastic single vehicle routing with pick up and a predefined customer sequence, European Journal of Operational Research, 213, 37-51.
Moghaddam, B.F. , Ruiz, R., Sadjadi, S.J. (2012). Vehicle routing problem with uncertain demands: An advanced particle swarm algorithm, Computers & Industrial Engineering, 62(1), 306-317.
Novoa, C., Storer, R. (2009). An approximate dynamic programming approach for the vehicle routing problem with stochastic demands, European Journal of Operational Research, 196(2), 509-515.
Ong, H.L., Ang, B.W., Goh, T.N., Deny, C.C.(1997). A vehicle routing and scheduling problem with time windows and stochastic demand constraints, Asia-Pacific Journal of Operational Research, 14, 1-17.
Oyola, J., Arntzen, H., Woodruff, D.L., (2018) The stochastic vehicle routing problem a literature review, part I: models, EURO J Trasp Logist, 7, 193-221.
Pasha, U., Hoff, A., Hvattum, L.M. (2017). The multi-period fleet size and mix vehicle routing problem with stochastic demands, Computational Methods and Models for Transport, 121-146.
Qin, J., Ye, Y., Cheng, B. Zhao, X. Ve Ni, L. (2017). The emergency vehicle routing problem with uncertain demand under sustainability environments, Sustainability, 9(2), 288-
Rei, W., Gendreau, M., Soriano, P. (2010). A hybrid monte carlo local branching algorithm for the single vehicle routing problem with stochastic demands, Transportation Science, 44(1), 136–146.
Ritzinger, U., Punchinger, J., Hartl, R.F. (2016). A survey on dynamic and stochastic vehicle routing problems, International Journal of Production Research, 54(1), 215-231.
Saint-Guillian, M., Solnon, C., Deville, Y. (2017)., The static and stochastic VRP with time windows and both random customers and reveal times, Applications of Evolutionary Computation, 110-127.
Salavati-Khosghalb, M., Gendreau, M., Jabali, O., ve Rei, W. (2019a). A rule-based recourse for the vehicle routing problem with stockhastic demands, Transportation Science
Salavati-Khosghalb, M., Gendreau, M., Jabali, O., ve Rei, W. (2019b). An exact algorithm to solve the vehicle routing problem with stockhastic demands under an optimal restocking policy, European Journal of Operational Research, 273(1), 175-189.
Salavati-Khosghalb, M., Gendreau, M., Jabali, O., ve Rei, W. (2019c). A hybrid recourse policy for the vehicle routing problem with stockhastic demands, Euro Journal on Transportation and Logistics, 8(3), 269-298.
Sarasola, B. Doerner, K.F., Schmid, V., Alba, E. (2016). Variable neighborhood search for the stochastic and dynamic vehicle routing problem, Annals o Operations Search,236(2), 425-461.
Secomandi, N., (2000). Comparing neuro-dynamic programming algorithms for the vehicle routing problem with stochastic demands, Computers and Operations Research, 27 (5), 1171–1200.
Secomandi, N., (2001). A rollout policy for the vehicle routing problem with stochastic demands, Operations Research, 49 (5), 796–802.
Secomandi, N., Margot, F. (2009). Reoptimization approaches for the vehicle-routing problem with stochastic demands, Operational Research, 57(1), 214–230.
Soonpracha, K., Mungwattana, A., Manisri, T. (2015). A re-constructed meta-heuristic algorithm for robust fleet size and mix the vehicle routing problem with time windows under uncertain demands, Evolutionary Systems, 2, 347-361.
Stewart, W., R., Golden, B., L., (1983). Stochastic vehicle routing : A comprehensive approach, European Journal Of Operational Research, 14, 371-385.
Sungur, I, Ordo´nez, F., Dessouky, M. (2008). A robust optimization approach for the capacitated vehicle routing problem with demand uncertainty, IIE Transactions, 40, 509–523.
Sun, L. ve Wang, B. (2018). A goal-robust-optimization approach for solving open vehicle routing problem with demand uncertainty, Wireless Personal Communications, 103(1), 1059-1075.
Tan, K. C., Cheong, C. Y., Goh, C. K. (2007). Solving multiobjective vehicle routing problem with stochastic demand via evolutionary computation, European Journal of Operational Research, 177(2), 813-839.
Tatarakis, A. ve Minis, I. (2009). Stochastic single vehicle routing with a predefined customer sequence and multiple depot returns, European Journal of Operational Research, 197(2), 557-571.
Teng, S., Ong, H.L., Huang, H.C., (2003). A comparative study of metaheurıstıcs for vehıcle routıng problem wıth stochastıc demands, Asia-Pacific Journal of Operational Research, 20, 103-119.
Teodorovi´c, D., Pavkovi´c, G., (1992).A simulated annealing technique approach to the vehicle routing problem in the case of stochastic demand, Transportation Planning and Technology, 16, 261–273.
Tillman, F. A. (1969).The multiple terminal delivery problem with probabilistic demands. Transportation Science, 3(3), 192-204.
Ulmer, M.W., Mattfeld, D.C., Hennig, M. Ve Goodson, J.C. (2015). A rollout algorithm for vehicle routing with stockhastic customer requests, Logistic Management, 217-227.
Uslu, A., Çetinkaya, C., İşleyen, S.K., (2017). Vehicle routing problem in post-disaster humanitarian relief logistics: A case study in Ankara, Sigma Journal of Engineering and Natural Science, 35(3), 481-499.
Wang, C., Qiu, Y. (2011). Vehicle routing problem with stochastic demands and simultaneous delivery and pickup based on the cross-entropy method, Advances in Automation and Robotics, 2, 55-60.
Wang, K., Lan, S. ve Zhao, Y. (2017). A genetic-algorithm-based approach to the two echelon capacited vehicle routing problem with stochastic demands in logistics service, Journal of the Operational Research Society, 68(11), 1409-1421.
Xaingguo, M., Manying, W. (2015). Optimization model of the vehicle routing of cold chain logistics based on stochastic demands, Journal of Applied Science and Engineering Innovation, 2(9), 356-362.
Yang, W., Mathur, K., Ballou, R. H., (2000). Stochastic vehicle routing problem with restocking, Transportation Science, 34 (1), 99–112.
Zhang, J., Lam, W.H.K., Chen, B.W. (2016). On-time delivery probabilistic models for the vehicle routing problem with stochastic demands and time windows, European Journal of Operational Research, 249(1), 144-154.
Zhang, C., Delleart, N.P., Zhao, L., Van Woenseş, T., Sever, D. (2013), Single vehicle routing problem with stochastic demands: Approximate dynamic programming, Eindhoven University of Technology, 425, 1-29.
Zhu, L., Rousseau, L-M., Rei, W., Li, B. (2014). Paired cooperative reoptimization strategy for the vehicle routing problem with stochastic demands. Computers & Operations Research, 50, 1–13.
Zhu, L. ve Sheu, J.B. (2018). Failure-specific cooperative recourse strategy for simultaneous pick up and delivery problem with stochastic demands, European Journal of Operational Research, 271(3), 896-912.
Zuhori, S.T., Peya, Z.J., Mahmud, F. (2013). A novel three-phase approachfor solving multi-depot vehicle routing problem with stochastic demand, Algorithms Research, 1(4), 15-19.
- Tezler
- Gültepe, A. (2011). “Stokastik eş zamanlı topla-dağıt araç rotalama problemi için melez yaklaşım: Diferansiyel evrim algoritması”, Yüksek Lisans Tezi, Başkent Üniversitesi Fen Bilimleri Enstitüsü, Ankara.
İşleyen, S.K. (2008). “Lojistik yönetim sistemlerinde stokastik talepli araç rotalama problemi”, Yüksek Lisans Tezi, Gazi Üniversitesi Fen Bilimleri Enstitüsü, Ankara.
Kızıloğlu, K. (2017). “Stokastik talepli çok depolu araç rotalama problemi için sezgisel bir çözüm yaklaşımı”, Yüksek Lisans Tezi, Gazi Üniversitesi Fen Bilimleri Enstitüsü, Ankara.
Uslu, A. (2016). “Afet Sonrası İnsani Yardım Lojistiğinde Stokastik Talepli Çok Depolu Araç Rotalama Problemi: Ankara İli Örneği”, Yüksek Lisans Tezi, Gazi Üniversitesi Fen Bilimleri Enstitüsü, Ankara.
Yang, W.H., (1996). Stochastic Vehicle Routing with Optimal Restocking, PhD thesis, Case Western Reserve University, Cleveland, OH, U.S.A. 16-18.
- İnternet Kaynakları
- Christiansen, C.H., Eglese, R.W., Letchford, A.N., Lysgaard, J. (2016). A Branch-and-Cut-and-Price algorithm for the Multi-Depot Capacitated Vehicle Routing Problem with Stochastic Demands, https://www.researchgate.net/publication/229169058_A_branch-and-cut-and-price_algorithm_for_the_multi-depot_heterogeneous_vehicle_routing_ problem_with_time_windows, Son erişim tarihi:26.08.2019.
Florio, A., Hartl, R., Minner, S. (2018), New exact algorithm and solution properties fort he vehicle routing problem with stachastic demands, https://arxiv.org/abs/1806.08549, Son Erişim Tarihi: 28.08.2019.
Florio, A., Hartl, R., Minner, S. (2018), Optimal a priori tour and restocking policy for the single vehicle routing problem with stochastic demands, https://www.sciencedirect.com/science/article/abs/pii/S0377221718309135 Son Erişim Tarihi: 30.08.2019.
Subramanyam, A., Repoussis, P.P., Gounaris, C.E. (2018). Robust optimization of broad class of heterogeneous vehicle routing problems under demand uncertainty, 1-54, https://arxiv.org/abs/1810.04348, Son Erişim Tarihi: 08.09.2019.
Stokastik Talepli Araç Rotalama Problemi İçin Literatür Taraması
Yıl 2019,
Cilt: 18 Sayı: 36, 181 - 222, 06.11.2019
Beste Desticioğlu
,
Bahar Özyörük
Öz
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.
Kaynakça
- Kitaplar
- Jaillet, P. ve Odoni, A. (1988). The Probabilistic Vehicle Routing Problem in Vehicle Routing: Methods and Studies, B. L. Golden and A. A. Assad (eds.), North-Holland, Amsterdam.
- Makaleler
- Ak, A., Erera, A.L., (2007). A Paired-Vehicle Recourse Strategy for the Vehicle-Routing Problem with Stochastic Demands, Transportation Science, 41, 222 –237.
Arvianto, A., Saptadi, S. Budiawan, W., Nartadhi, R.L. (2019). Vehicle routing problem model and simulation with probabilistic demand and sequential insertion, AIP Conference Proceedings.
Balaprakash, P. Birattari, M., Stützle, T., Dorigo, M. (2015), Estimation-based metaheuristics for the single vehicle routing problem with stochastic demands and customers, Computational Optimization and Applications, 61(2), 463-487.
Bastian, C., Kan, R., (1992). The stochastic vehicle routing problem revisited, European Journal Of Operational Research, 56, 407-412.
Berhan, E. (2016), Stochastic vehicle routing problems with real simultaneous pickup and delivery services, Journal of Optimization in Industrial Engineering, 19, 1-7.
Bertazzi, L., Secomandi, N. (2018). Faster rollout search for the vehicle routing problem with stochastic demands and restocking, European Journal Of Operational Research, 270(2018), 487-497.
Bertsimas, D. J., (1992). A vehicle routing problem with stochastic demand, Operations Research, 40 (3) , 574–585.
Bertsimas, D. J., Chervi, P., Peterson, M., (1995). Computational approaches to stochastic vehicle routing problems, Transportation Science, 29 (4), 342–352.
Bianchi, L., Birattari, M., Manfrin, M., Mastorolilli, M., Paquete, L., Rossi-Doria, O., Schiavinotto, T. (2004). Metaheuristics for the vehicle routing problem with stochastic demands, In International conference on parallel problem solving from nature 450-460, Springer Berlin Heidelberg,
Bianchi, L., Birattari, M., Manfrin, M., Mastrolilli, M., Paquete, L., Rossi-Doria, O., Schiavinotto, T., (2006). Hybrid Metaheuristics for the Vehicle Routing Problem with Stochastic Demand, Journal of Mathematical Modelling and Algorithms, 5, 91-110.
Biesinger, B., Hu., B., Raidl, G.R. (2015). A variable neighborhood search for the generalized vehicle routing problem with stochastic demands, Evolutionary Computation in Combinatorial Optimization, 48-60.
Biesinger, B., Hu., B., Raidl, G.R. (2016). An integer L-Shaped method for the generalized vehicle routing problem with stochastic demands, Electronic Notes in Discrete Mathematics,52, 245-252.
Biesinger, B., Hu., B., Raidl, G.R. (2018). A genetic algorithm in combination with a solution archive for solving the generalized vehicle routing problem with stochastic demands, Transportation Science, 52(3), 497-.
Calvet, L., Juan, A.A., Schefers, N. (2015). Solving the Multi-Depot Vehicle Routing Problem considering Uncertainty and Risk Factors, Proceedings of the ICRA6/Risk International Conference, Barcelona, Spain.
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.
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(2019), 459-484.
Chan, Y. , Carter, W. B. , Burnes, M. D. (2001). A multiple-depot, multiple-vehicle, location-routing problem with stochastically processed demands, Computers & Operations Research, 28(8), 803-826.
Chang, M.S. (2005). A vehicle routing problem with time windows and stochastic demands, Journal of the Chienese Institute of Engineering, 28(5),783–794.
Desticioğlu, B. ve Özyörük, B. (2019). Dinamik ARP, Çok Depolu ARP ve Eş Zamanlı Topla Dağıt ARP İçin Literatür Taraması, MAS International Conference on Mathematics-Engineering and Natural&Medical Sciences-III, 345-363.
Dimitrakos, T.D. ve Kyriakidis, E.G. (2015). A single vehicle routing problem with pickups and deliveries continous random demands and predefined customer order, European Journal of Operational Research, 244(3), 990-993.
Dinh, T., Fukasawa, R., Luadtka, J. (2018). Exact algorithms for the chance-constrained vehicle routing problem, Mathematical Programming, 172(1-2), 105-138.
Dror, M., Laporte, G., Trudeau, P., (1989).Vehicle routing with stochastic demands; Properties and solution frameworks, Transportation Science, 23 (3), 166-176.
Dror, M., Trudeau, P., (1986). Stochastic vehicle routing with modified savings algorithm, European Journal of Operational Research, 23, 228-235.
Dror, M., (1993). Modeling Vehicle Routing with Uncertain Demands as a Stochastic Program: Properties of the Corresponding Solution, European Journal of Operational Research, 64, 432–441.
Dror, M., Laporte, G., Louveaux, F.V. (1993). Vehicle routing with stochastic demands and restricted failures, ZOR Zeitschrift für Operations Research Methods and Models of Operation Research 37(3), 273-283.
Dror, M. (2016). Vehicle routing with stochastic demands: Models & computational methods, International Series in Operations Research and Management Science, 46, 425-449.
Erera, A.L., Savelsbergh, M., Uyar, E. (2009). Fixed routes with backup vehicles for stochastic vehicle routing problems with time constraints, Networks, 54(4), 270–283.
Erera, A.L., Morales, J.C., Savelsbergh, M. (2010). The vehicle routing problem with stochastic demand and duration constraints, Transportation Science, 44(4), 474–492.
Festa, P., Pastore, T., Ferore, D., Juan, A.A., Bayliss, C. (2018). Integrating Biased-randomized GRASP with Monte Carlo simulation for solving the vehicle routing problem with stochastic demands, 2018 Winter Simulation Conference, 2989-3000.
Gauvin, C., Desaulniers, G., Gendreau, M. (2014). A branch-cut-and-price algorithm for the vehicle routing problem with stochastic demands, Computers & Operations Research, 50, 141–153.
Gee, S.B., Arokiasami, W.A., Jiang, J., Tan, K.C. (2016), Decomposition-based multi-objective evolutionary algortihm for vehicle routing problem with stochastic demands, Soft Computing, 20(9), 3443-3453.
Gendreau, M., Laporte, G., Seguin, R. (1995). An exact algorithm for the vehicle routing problem with stochastic demands and customers, Transportation Science, 29(2), 143-155.
Gendreau, M., Laporte, G., Guo, B. (1996). Stochastic vehicle routing: Invited review, European Journal of Operational Research, 88, 3-12.
Ghilas, V., Demir, E. ve Woensel, T.V. (2016). A scenerai-based planning for the pickup and delivery problem with time windows, scheduled lines and stochastic demands, Transportation Research Part B: Methodological, 91, 34-51.
Goel, R., Maini, R., Bansal, S. (2019), Vehicle routing problem with time windows having stochastic customer demands and stochastic service times: Modeling and solution, Journal of Computational Science, 34, 1-10.
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.
Goodson, J.C. (2015). A priori policy evaluation and cyclic-order-based simulated annealing for the multicompartment vehicle routing problem with stochastic demands, European Journal of Operational Research, 241(2), 361–369.
Goodson, J.C., Thomas, B.W., Ohlmann, J.W. (2015). Restocking-based rollout policies for the vehicle routing problem with stockhastic demand and duration limits, Transportation Science, 50(2), 363-370.
Gounaris, C.E., Wiesemann, W., Floudas, C.A. (2013). The robust capacitated vehicle routing problem under demand uncertainty, Operations Research, 61(3), 677–693.
Gutierrez, A. Dieulle, L., Labadie, N. ve Velasco, N. (2018). A hybrid metaheuristic algorithm for the vehicle routing problem with stockhastic demands, Computers & Operations Research, 99, 135-147.
Haugland, D., Ho, S.C., Laporte, G. (2007). Designing delivery districts for the vehicle routing problem with stochastic demands, European Journal of Operational Research, 180(3), 997–1010.
Hernandez, F., Gendreau, M., Jabali, O. ve Rei, W. (2019). A local branching metaheuristic for the multi-vehicle routing problem with stochastic demands, Journal of Heuristics, 25(2),215-245.
Hjorring, C., Holt, J. (1999). New optimality cuts for a single-vehicle stochastic routing problem, Annals of Operations Research, 86, 569–584.
Hou, L., Hou, Z. (2013). A novel discrete differential evolution algorithm, Telkomnika, 11(4), 1883-1888.
Hou L., Zhou, H., (2010). Stochastic vehicle routing problem with uncertain demand and travel time and simultaneous pickups and delivery, Third International Joint Conference on Computational science and Optimization, 32-35.
Hou, L., Zhou, H., Zhao, J., (2010). A novel discrete differential evolution algorithm for stochastic VRPSPD, Journal of Computational Information Systems, 6(8), 2483-2491.
Hu, C., Lu, J., Liu, X. Ve Zhang, G. (2018). Robust vehicle routing problem with hard time windows under demand and travel time uncertainty, Computational Optimization and Applications, 61(2), 463-487.
Ismail, Z. Ve Irhamah, I. (2008). Solving the vehicle routing problem with stochastic demands via hybrid genetic algorithm- tabu search, Journal of Mathematics and Statistics, 4(3), 161-167.
Jabali, O., Rei, W., Gendreau, M., Laporte, G. (2014). Partial-route inequalities for the multi-vehicle routing problem with stochastic demands, Discrete Applied Mathematics, 177, 121-136.
Juan, A., Faulin, J., Grasman, S., Riera , D., Marull, J., Mendez, C. (2011) Using safety stocks and simulation tosolve the vehicle routing problem with stochastic demands, Transportation Research Part C:EmergencyTechnology, 19(5), 751–765, Freight Transportation and Logistics.
Juan, A., Faulin, J., Jorba, J., Cacares, J., Marques, J.M. (2013) Using parallel & distributed computing solving real time vehicle routing problems with stochastic demands, Annals of Operations Research, 207(1), 43-65.
Kyriakidis, E.G. ve Dimitrakos, T.D. (2015). Single vehicle routing problem with a predefined customer sequence, stochastic demands and partial satisfaction of demands, Operations Research Proceedings, 157-164.
Laporte, G., Louveaux, F., Mercure, H. (1989). Models and exact solutions for a class of stochastic location-routing problems, European Journal of Operational Research, 39(1), 71-78.
Laporte, G., Louveaux, F., (1990). Formulations and Bounds for Stochastic Vehicle Routing Problem with Uncertain Supplies in Economic Decision-Making: Games, Econometrics, and Optimization, J. J. Gabzewicz, J. F. Richard, and L. A. Wolsey (eds.), North-Holland, Amsterdam.
Laporte, G., Louveaux, F.V., Hamme, L.V. (2002). An integer L-shaped algorithm for the capacitated vehicle routing problem with stochastic demands, Operational Research, 50(3), 415–423.
Lee, C., Lee, K., Park, S. (2012). Robust vehicle routing problem with deadlines and travel time/demand uncertainty, Journal of Operational Research Society, 63(9), 1294–1306.
Lei, H. , Laporte, G. ,Guo, B. (2011). The capacitated vehicle routing problem with stochastic demands and time windows, Computers & Operations Research, 38(12), 1775-1783.
Liu, C., Kou, G., Huang, F. (2016). Vehicle coordinated strategy for vehicle routing problem with fuzzy demands, Mathematical Problems in Engineering, 2016, 1-10.
Louveaux, F.V. ve Salazar-Gonzalez, J.J. (2018). Exact approach for the vehicle routing problem with stockhastic demands and preventive returns, Transportation Science, 52(6), 1297-
Luo, Z., Qin, H., Zhang, D. Ve Lim, A. (2016). New exact algorthm and solution properties for the vehicle routing problem with stochastic demands and weight-related cost, Transportation Research Part E: Logistics and Transportation Review, 85, 69-89.
Marinaki, M. ve Marinakis, Y. (2016). A glowworm swarm optimization algorithm for the vehicle routing problem with stockhastic demands, Expert Systems with Applications, 46, 145-163.
Marinakis, Y., Iordanidou, G.R., Marinaki, M. (2013). Particle swarm optimization for the vehicle routing problem with stochastic demands, Applied Soft Computing, 13(4), 1693-1704.
Marinakis, Y., Marinaki, M. ve Spanou, P. (2015). A memetic differantial evolution algorthm for the vehicle routing problem with stochastic demands, Adaptation and Hybridization in Computational Intelligence, 18, 185-204.
Mendoza, J.E., Castanier, B., Gue´ret, C., Medaglia, A.L., Velasco, N. (2010). A memetic algorithm for the multi compartment vehicle routing problem with stochastic demands. Computers & Operations Research, 37(11), 1886–1898.
Mendoza, J.E., Villegas, J.G. (2013). A multi-space sampling heuristic for the vehicle routing problem with stochastic demands, Optimization Letters, 7(7), 1503–1516.
Mendoza, J.E., Rousseau, L.M. ve Villegas, J.G. (2016). A hybrid metaheuristics for the vehicle routing problem with stochastic demand and duration constraints, Journal of Heuristics, 22(4), 539-566.
Minis, I., Tatarakis, A. (2011). Stochastic single vehicle routing with pick up and a predefined customer sequence, European Journal of Operational Research, 213, 37-51.
Moghaddam, B.F. , Ruiz, R., Sadjadi, S.J. (2012). Vehicle routing problem with uncertain demands: An advanced particle swarm algorithm, Computers & Industrial Engineering, 62(1), 306-317.
Novoa, C., Storer, R. (2009). An approximate dynamic programming approach for the vehicle routing problem with stochastic demands, European Journal of Operational Research, 196(2), 509-515.
Ong, H.L., Ang, B.W., Goh, T.N., Deny, C.C.(1997). A vehicle routing and scheduling problem with time windows and stochastic demand constraints, Asia-Pacific Journal of Operational Research, 14, 1-17.
Oyola, J., Arntzen, H., Woodruff, D.L., (2018) The stochastic vehicle routing problem a literature review, part I: models, EURO J Trasp Logist, 7, 193-221.
Pasha, U., Hoff, A., Hvattum, L.M. (2017). The multi-period fleet size and mix vehicle routing problem with stochastic demands, Computational Methods and Models for Transport, 121-146.
Qin, J., Ye, Y., Cheng, B. Zhao, X. Ve Ni, L. (2017). The emergency vehicle routing problem with uncertain demand under sustainability environments, Sustainability, 9(2), 288-
Rei, W., Gendreau, M., Soriano, P. (2010). A hybrid monte carlo local branching algorithm for the single vehicle routing problem with stochastic demands, Transportation Science, 44(1), 136–146.
Ritzinger, U., Punchinger, J., Hartl, R.F. (2016). A survey on dynamic and stochastic vehicle routing problems, International Journal of Production Research, 54(1), 215-231.
Saint-Guillian, M., Solnon, C., Deville, Y. (2017)., The static and stochastic VRP with time windows and both random customers and reveal times, Applications of Evolutionary Computation, 110-127.
Salavati-Khosghalb, M., Gendreau, M., Jabali, O., ve Rei, W. (2019a). A rule-based recourse for the vehicle routing problem with stockhastic demands, Transportation Science
Salavati-Khosghalb, M., Gendreau, M., Jabali, O., ve Rei, W. (2019b). An exact algorithm to solve the vehicle routing problem with stockhastic demands under an optimal restocking policy, European Journal of Operational Research, 273(1), 175-189.
Salavati-Khosghalb, M., Gendreau, M., Jabali, O., ve Rei, W. (2019c). A hybrid recourse policy for the vehicle routing problem with stockhastic demands, Euro Journal on Transportation and Logistics, 8(3), 269-298.
Sarasola, B. Doerner, K.F., Schmid, V., Alba, E. (2016). Variable neighborhood search for the stochastic and dynamic vehicle routing problem, Annals o Operations Search,236(2), 425-461.
Secomandi, N., (2000). Comparing neuro-dynamic programming algorithms for the vehicle routing problem with stochastic demands, Computers and Operations Research, 27 (5), 1171–1200.
Secomandi, N., (2001). A rollout policy for the vehicle routing problem with stochastic demands, Operations Research, 49 (5), 796–802.
Secomandi, N., Margot, F. (2009). Reoptimization approaches for the vehicle-routing problem with stochastic demands, Operational Research, 57(1), 214–230.
Soonpracha, K., Mungwattana, A., Manisri, T. (2015). A re-constructed meta-heuristic algorithm for robust fleet size and mix the vehicle routing problem with time windows under uncertain demands, Evolutionary Systems, 2, 347-361.
Stewart, W., R., Golden, B., L., (1983). Stochastic vehicle routing : A comprehensive approach, European Journal Of Operational Research, 14, 371-385.
Sungur, I, Ordo´nez, F., Dessouky, M. (2008). A robust optimization approach for the capacitated vehicle routing problem with demand uncertainty, IIE Transactions, 40, 509–523.
Sun, L. ve Wang, B. (2018). A goal-robust-optimization approach for solving open vehicle routing problem with demand uncertainty, Wireless Personal Communications, 103(1), 1059-1075.
Tan, K. C., Cheong, C. Y., Goh, C. K. (2007). Solving multiobjective vehicle routing problem with stochastic demand via evolutionary computation, European Journal of Operational Research, 177(2), 813-839.
Tatarakis, A. ve Minis, I. (2009). Stochastic single vehicle routing with a predefined customer sequence and multiple depot returns, European Journal of Operational Research, 197(2), 557-571.
Teng, S., Ong, H.L., Huang, H.C., (2003). A comparative study of metaheurıstıcs for vehıcle routıng problem wıth stochastıc demands, Asia-Pacific Journal of Operational Research, 20, 103-119.
Teodorovi´c, D., Pavkovi´c, G., (1992).A simulated annealing technique approach to the vehicle routing problem in the case of stochastic demand, Transportation Planning and Technology, 16, 261–273.
Tillman, F. A. (1969).The multiple terminal delivery problem with probabilistic demands. Transportation Science, 3(3), 192-204.
Ulmer, M.W., Mattfeld, D.C., Hennig, M. Ve Goodson, J.C. (2015). A rollout algorithm for vehicle routing with stockhastic customer requests, Logistic Management, 217-227.
Uslu, A., Çetinkaya, C., İşleyen, S.K., (2017). Vehicle routing problem in post-disaster humanitarian relief logistics: A case study in Ankara, Sigma Journal of Engineering and Natural Science, 35(3), 481-499.
Wang, C., Qiu, Y. (2011). Vehicle routing problem with stochastic demands and simultaneous delivery and pickup based on the cross-entropy method, Advances in Automation and Robotics, 2, 55-60.
Wang, K., Lan, S. ve Zhao, Y. (2017). A genetic-algorithm-based approach to the two echelon capacited vehicle routing problem with stochastic demands in logistics service, Journal of the Operational Research Society, 68(11), 1409-1421.
Xaingguo, M., Manying, W. (2015). Optimization model of the vehicle routing of cold chain logistics based on stochastic demands, Journal of Applied Science and Engineering Innovation, 2(9), 356-362.
Yang, W., Mathur, K., Ballou, R. H., (2000). Stochastic vehicle routing problem with restocking, Transportation Science, 34 (1), 99–112.
Zhang, J., Lam, W.H.K., Chen, B.W. (2016). On-time delivery probabilistic models for the vehicle routing problem with stochastic demands and time windows, European Journal of Operational Research, 249(1), 144-154.
Zhang, C., Delleart, N.P., Zhao, L., Van Woenseş, T., Sever, D. (2013), Single vehicle routing problem with stochastic demands: Approximate dynamic programming, Eindhoven University of Technology, 425, 1-29.
Zhu, L., Rousseau, L-M., Rei, W., Li, B. (2014). Paired cooperative reoptimization strategy for the vehicle routing problem with stochastic demands. Computers & Operations Research, 50, 1–13.
Zhu, L. ve Sheu, J.B. (2018). Failure-specific cooperative recourse strategy for simultaneous pick up and delivery problem with stochastic demands, European Journal of Operational Research, 271(3), 896-912.
Zuhori, S.T., Peya, Z.J., Mahmud, F. (2013). A novel three-phase approachfor solving multi-depot vehicle routing problem with stochastic demand, Algorithms Research, 1(4), 15-19.
- Tezler
- Gültepe, A. (2011). “Stokastik eş zamanlı topla-dağıt araç rotalama problemi için melez yaklaşım: Diferansiyel evrim algoritması”, Yüksek Lisans Tezi, Başkent Üniversitesi Fen Bilimleri Enstitüsü, Ankara.
İşleyen, S.K. (2008). “Lojistik yönetim sistemlerinde stokastik talepli araç rotalama problemi”, Yüksek Lisans Tezi, Gazi Üniversitesi Fen Bilimleri Enstitüsü, Ankara.
Kızıloğlu, K. (2017). “Stokastik talepli çok depolu araç rotalama problemi için sezgisel bir çözüm yaklaşımı”, Yüksek Lisans Tezi, Gazi Üniversitesi Fen Bilimleri Enstitüsü, Ankara.
Uslu, A. (2016). “Afet Sonrası İnsani Yardım Lojistiğinde Stokastik Talepli Çok Depolu Araç Rotalama Problemi: Ankara İli Örneği”, Yüksek Lisans Tezi, Gazi Üniversitesi Fen Bilimleri Enstitüsü, Ankara.
Yang, W.H., (1996). Stochastic Vehicle Routing with Optimal Restocking, PhD thesis, Case Western Reserve University, Cleveland, OH, U.S.A. 16-18.
- İnternet Kaynakları
- Christiansen, C.H., Eglese, R.W., Letchford, A.N., Lysgaard, J. (2016). A Branch-and-Cut-and-Price algorithm for the Multi-Depot Capacitated Vehicle Routing Problem with Stochastic Demands, https://www.researchgate.net/publication/229169058_A_branch-and-cut-and-price_algorithm_for_the_multi-depot_heterogeneous_vehicle_routing_ problem_with_time_windows, Son erişim tarihi:26.08.2019.
Florio, A., Hartl, R., Minner, S. (2018), New exact algorithm and solution properties fort he vehicle routing problem with stachastic demands, https://arxiv.org/abs/1806.08549, Son Erişim Tarihi: 28.08.2019.
Florio, A., Hartl, R., Minner, S. (2018), Optimal a priori tour and restocking policy for the single vehicle routing problem with stochastic demands, https://www.sciencedirect.com/science/article/abs/pii/S0377221718309135 Son Erişim Tarihi: 30.08.2019.
Subramanyam, A., Repoussis, P.P., Gounaris, C.E. (2018). Robust optimization of broad class of heterogeneous vehicle routing problems under demand uncertainty, 1-54, https://arxiv.org/abs/1810.04348, Son Erişim Tarihi: 08.09.2019.