Danijel Marković, Goran Petrovć, Žarko Ćojbašić, Aleksandar Stanković

DOI Number
First page
Last page


The vehicle routing problem with stochastic demands (VRPSD) is a combinatorial optimization problem. The VRPSD looks for vehicle routes to connect all customers with a depot, so that the total distance is minimized, each customer visited once by one vehicle, every route starts and ends at a depot, and the travelled distance and capacity of each vehicle are less than or equal to the given maximum value. Contrary to the classical VRP, in the VRPSD the demand in a node is known only after a vehicle arrives at the very node. This means that the vehicle routes are designed in uncertain conditions. This paper presents a heuristic and meta-heuristic approach for solving the VRPSD and discusses the real problem of municipal waste collection in the City of Niš.


Vehicle Routing Problem, Stochastic Demands, Municipal Waste, Heuristic and Meta-heuristic

Full Text:



Marković, D., 2018, Development of a logistic model for municipal waste management by applying heuristic methods, (in Serbian), PhD Thesis, University of Niš, Serbia.

Dantzig, G.B., Ramser, J.H., 1959, The truck dispatching problem, Management science, 6(1), pp. 80-91.

Babaee, T.E., Abbasian, P., Soltani, M., Ghaffarian, S.A., 2019, Developing an applied algorithm for multi-trip vehicle routing problem with time windows in urban waste collection: A case study, Waste Management & Research, 37(1), pp.4-13.

Pamučar, D., Ćirović, G., 2018, Vehicle route selection with an adaptive neuro fuzzy inference system in uncertainty conditions, Decision Making: Applications in Management and Engineering, 1(1), pp. 13-37.

Letchford, A.N., Salazar-González, J.J., 2019, The capacitated vehicle routing problem: stronger bounds in pseudo-polynomial time, European Journal of Operational Research, 272(1), pp. 24-31.

Bernal, J., Willmer, J.E., Paz, J.C., Linfati, R., Gatica, G., 2018, A probabilistic granular tabu search for the distance constrained capacitated vehicle routing problem, International Journal of Industrial and Systems Engineering, 29(4), pp. 453-477.

Laporte, G., 2018, Vehicle routing with backhauls, Computers and Operations Research, 91(C), pp. 79-91.

Neves-Moreira, F., da Silva, D.P., Guimarães, L., Amorim, P., Almada-Lobo, B., 2018, The time window assignment vehicle routing problem with product dependent deliveries, Transportation Research Part E: Logistics and Transportation Review, 116, pp.163-183.

Madankumar, S., Rajendran, C., 2018, Mathematical models for green vehicle routing problems with pickup and delivery: A case of semiconductor supply chain, Computers & Operations Research, 89, pp.183-192.

Mohamed, M.K., Lanzon, A., 2012, Design and control of novel tri-rotor UAV, IEEE International Conference on Control (CONTROL) UKACC, pp. 304-309.

Avci, M., Topaloglu, S., 2016, A hybrid metaheuristic algorithm for heterogeneous vehicle routing problem with simultaneous pickup and delivery, Expert Systems with Applications, 53, pp.160-171.

Ritzinger, U., Puchinger, J., Hartl, R.F., 2016, A survey on dynamic and stochastic vehicle routing problems, International Journal of Production Research, 54(1), pp. 215-231.

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), pp.673-690.

Babaee Tirkolaee, E., Alinaghian, M., Bakhshi Sasi, M., Seyyed Esfahani, M.M., 2016, Solving a robust capacitated arc routing problem using a hybrid simulated annealing algorithm: a waste collection application, Journal of Industrial Engineering and Management Studies, 3(1), pp.61-76.

Marinaki, M., Marinakis, Y., 2016, A glowworm swarm optimization algorithm for the vehicle routing problem with stochastic demands, Expert Systems with Applications, 46, pp. 145-163.

Mendoza, J.E., Rousseau, L. M., Villegas, J.G., 2016, A hybrid metaheuristic for the vehicle routing problem with stochastic demand and duration constraints, Journal of Heuristics, 22(4), pp. 539-566.

Mendoza, J.E., Castanier, B., Gué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), pp. 1886-1898.

Shen, Z., Dessouky, M.M., Ordóñez, F., 2009, A two‐stage vehicle routing model for large‐scale bioterrorism emergencies, Networks, 54(4), pp. 255-269.

Peng, Y., Qian, Y.M., 2010, A particle swarm optimization to vehicle routing problem with fuzzy demands, Journal of Convergence Information Technology, 5(6), pp. 112-119.

Waller, S.T., Ziliaskopoulos, A.K., 2006, A chance-constrained based stochastic dynamic traffic assignment model: Analysis, formulation and solution algorithms, Transportation Research Part C: Emerging Technologies, 14(6), pp. 418-427.

Xiangyong, L.,Peng, T., Stephen, C.H.L., 2010, Vehicle routing problem with time windows and stochastic travel and service times, International Journal Production Economics, 125, pp. 137-145.

Liu, B., Iwamura, K., 1998, Chance constrained programming with fuzzy parameters, Fuzzy sets and systems, 94(2), pp.227-237.

Doyuran, T., Çatay, B., 2011, A robust enhancement to the Clarke–Wright savings algorithm, Journal of the Operational Research Society, 62(1), pp. 223-231.

Roy, A., Manna, A., Maity, S., 2019, A novel memetic genetic algorithm for solving traveling salesman problem based on multi-parent crossover technique, Decision Making: Applications in Management and Engineering, 2(2), pp. 100-111.

Radiša, R., Dučić, N., Manasijević, S., Marković, N., Ćojbašić, Ž., 2017, Casting improvement based on metaheuristic optimization and numerical simulation, Facta Universitatis-Series Mechanical Engineering, 15(3), pp. 397 – 411.

Pollaris, H., Braekers, K., Caris, A., Janssens, G.K., Limbourg, S., 2017, Iterated local search for the capacitated vehicle routing problem with sequence‐based pallet loading and axle weight constraints, Networks, 69(3), pp. 304-316.

Wei, L., Zhang, Z., Zhang, D., Leung, S. C., 2018, A simulated annealing algorithm for the capacitated vehicle routing problem with two-dimensional loading constraints, European Journal of Operational Research, 265(3), pp. 843-859.


  • There are currently no refbacks.

ISSN: 0354-2025 (Print)

ISSN: 2335-0164 (Online)

COBISS.SR-ID 98732551

ZDB-ID: 2766459-4