Document Type : Original Article


1 Department of Industrial Engineering, Ayandegan Institute of Higher Education, Tonekabon, Iran

2 Department of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran

3 Department of Industrial Engineering, Iran University of Science and Technology, Tehran, Iran


Purpose: In the real world, the vehicles should return to the depot after serving the last customer's location because of decreased related costs. This paper investigates the problem of increasing service time by using the stochastic time for each tour such that the total travelling time of the vehicles is limited to a specific limit based on a defined probability.
Methodology: It is proven that classic models in vehicle routing problems (VRPs) belong to the class of NP-hard ones; thus, due to its complexity using exact methods in large-scale problems, a meta-heuristic-based differential evolution (DE) algorithm is proposed.
Findings: The obtained results indicate the efficiency of the proposed DE algorithm.
Originality/Value: The total travel time is limited to a definite probability per cent, and other constraints (e.g., capacity and time distribution restrictions) are considered. In contrast, the total cost of the transportation is minimized.


Chiang, W. C., & Russell, R. A. (1996). Simulated annealing metaheuristics for the vehicle routing problem with time windows. Annals of operations research, 63(1), 3-27.
Christofides, N., Mingozzi, A., & Toth, P. (1979). The vehicle routing problem. Combinatorial optimization. Chichester, Wiley, pp 315–338
Cordeau, J. F., & Maischberger, M. (2012). A parallel iterated tabu search heuristic for vehicle routing problems. Computers & operations research39(9), 2033-205.
Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management science6(1), 80-91.
Das, S., & Suganthan, P. N. (2010). Differential evolution: a survey of the state-of-the-art. IEEE transactions on evolutionary computation15(1), 4-31.
Erera, A. L., Morales, J. C., & Savelsbergh, M. (2010). The vehicle routing problem with stochastic demand and duration constraints. Transportation science44(4), 474-492.
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 research217(2), 312-323.
Jozefowiez, N., Semet, F., & Talbi, E. G. (2009). An evolutionary algorithm for the vehicle routing problem with route balancing. European journal of operational research195(3), 761-769.
Kunnapapdeelert, S., & Kachitvichyanukul, V. (2015). Modified DE algorithms for solving multi-depot vehicle routing problem with multiple pickup and delivery requests. In Toward sustainable operations of supply chain and logistics systems (pp. 361-373). Springer, Cham.
Lee, T., & Ueng, J. (2001). A study of vehicle routing problems with load balancing. International journal of physical distribution and logistics management, 29, 646–658.
Lenstra, J. K., & Kan, A. R. (1981). Complexity of vehicle routing and scheduling problems. Networks11(2), 221-227.
Lin, S. W., Vincent, F. Y., & Chou, S. Y. (2009). Solving the truck and trailer routing problem based on a simulated annealing heuristic. Computers & operations research36(5), 1683-1692.
Maden, W., Eglese, R., & Black, D. (2010). Vehicle routing and scheduling with time-varying data: a case study. Journal of the operational research society61(3), 515-522.
Novoa, C., & Storer, R. (2009). An approximate dynamic programming approach for the vehicle routing problem with stochastic demands. European journal of operational research196(2), 509-515.
Qin, A. K., & Suganthan, P. N. (2005, September). Self-adaptive differential evolution algorithm for numerical optimization. In 2005 IEEE congress on evolutionary computation, (pp. 1785-1791).
Reimann, M., Stummer, M., & Doerner, K. (2002). A savings-based ant system for the vehicle routing problem. In proceedings of the 4th annual conference on genetic and evolutionary computation, (pp. 1317-1326).
Ribeiro, R., & Ramalhinho Dias Lourenço, H. (2001). A multi-objective model for a multi-period distribution management proble. SSRN electronic journal, 1, 97–102.
Storn, R., & Price, K. (1997). Differential evolution–a simple and efficient heuristic for global optimization over continuous spaces. Journal of global optimization11(4), 341-359.
Tasan, A. S., & Gen, M. (2012). A genetic algorithm-based approach to vehicle routing problem with simultaneous pick-up and deliveries. Computers & industrial engineering62(3), 755-761.