Competitive Vehicle Routing Problem with Time Windows and Stochastic Demands

Document Type: Research note


School of Industrial Engineering, Islamic Azad University, South Tehran Branch, Tehran, Iran


The competitive vehicle routing problem is one of the important issues in transportation area. In this paper a new method for competitive VRP with time windows and stochastic demand is introduced. In the presented method a three time bounds are given and the probability of arrival time between each time bound is assumed to be uniform. The demands of each customer are different in each time window. Therefore, revenue given in each time window is different. In this paper a project with two companies in a city with eight customers is considered and the best routing with maximum revenue is obtained.


Main Subjects

Bent R, Van Hentenryck P (2004) Scenario-based planning for partially dynamic vehicle routing with stochastic customers. Operations Research 52(6):977–987
Bianchi L, Birattari M, Chiarandini M, Manfrin M, Mastrolilli M, Paquete L, Rossi-Doria O, Schiavinotto T (2004) Metaheuristics for the vehicle routing problem with stochastic demands. In: Parallel Problem Solving from Nature - PPSN VIII, Lecture Notes in Computer Science, Springer Berlin, Heidelberg, pp 450–460
Braysy O, Gendreau M. (2005) Vehicle routing problem with time windows, part I: route construction and local search algorithms. Transportation Science;39:104–18.
Cordeau JF, Desaulniers G, Desrosiers J, Solomon MM, Soumis F, (2002) The VRP with time windows. In: Toth P, Vigo D, editors. The vehicle routing problem, SIAM Monographs on Discrete Mathematics and Applications, Vol. 9, Philadelphia, PA; p. 157–194.
Geiger MJ. Multi-criteria und Fuzzy Systeme in Theorie und Praxis. In: A computational study of genetic crossover operators for multi-objective vehicle routing problem with soft time windows. Deutscher Universities-Verlag; 2003. p. 191–207.
Golden B, Laporte G, Taillard E. (1999) An adaptive memory heuristic for a class of vehicle routing problems with minmax objective. Computers and Operations Research;24:445–52.
Haugland D, Ho S, Laporte G (2007) Designing delivery districts for the vehicle routing problem with stochastic demands. European Journal of Operational Research 180(3):997–1010
J.E. Mendoza, B. Castaniera, C. Guereta, A.L. Medagliab, N. Velascob, (2010)  A memetic algorithm for the multi-compartment vehicle routing problem with stochastic demands, Computers and Operations Research 37, 1886–1898.
Laporte G, Louveaux F, Van Hamme L (2002) An integer L-shaped algorithm for the capacitated vehicle routing problem with stochastic demands. Operations Research 50(3):415–423
Marinakis, Y. and M. Marinaki, (2013). Particle Swarm Optimization with Expanding Neighborhood Topology for the Permutation Flowshop Scheduling Problem, Soft Computing, (accepted), DOI:10.1007/s00500-013-0992-z
Mendoza JE, Castanier B, Gu´eret C, Medaglia AL, Velasco N (2010) A memetic algorithm for the multi-compartment vehicle routing problem with stochastic demands. Computers & Operations Research 37(11):1886–1898
Mendoza JE, Castanier B, Gu´eret C, Medaglia AL, Velasco N (2011) Constructive heuristics for the multicompartment vehicle routing problem with stochastic demands. Transportation Science 45(3):335–345
Qureshi AG, Taniguchi E, Yamada T. (2009E) An exact solution approach for vehicle routing and scheduling problems with soft time windows. Transportation Research;45(9), 60–77.
Secomandi N, Margot F (2009) Reoptimization approaches for the vehicle-routing problem with stochastic demands. Operations Research 57(1):214–230
Solomon MM, Desrosiers J. (1988) Time window constrained routing and scheduling problems. Transportation Science; 22(1):1–13.
Solomon MM. (1987) Algorithms for the vehicle routing and scheduling problem with time windows constraints. Operations Research; 35:254– 65.
Taillard ED. (1999) A heuristic column generation method for the heterogeneous fleet VRP. Rairo OR;33(1):1–14.
Tavakkoli-Moghaddam R, Saremi AR, Ziaee MS. (2006) A memetic algorithm for a vehicle routing problem with backhauls. Applied Mathematics and Computation;181:1049–60.
Tavakkoli-Moghaddam R, Safaei N, Gholipour Y. (2006) A hybrid simulated annealing for capacitated vehicle routing problems with the independent route length. Applied Mathematics and Computation;176:445–54.
Yang, W. H., Mathur, K., Ballou, R. H. (2000). Stochastic vehicle routing problem with restocking, Transportation Science, 34, 99-112.