Optimization Using Simulation of the Vehicle Routing Problem

Authors: Nayera E. El-Gharably, Khaled S. El-Kilany, Aziz E. El-Sayed

Abstract:

A key element of many distribution systems is the routing and scheduling of vehicles servicing a set of customers. A wide variety of exact and approximate algorithms have been proposed for solving the vehicle routing problems (VRP). Exact algorithms can only solve relatively small problems of VRP, which is classified as NP-Hard. Several approximate algorithms have proven successful in finding a feasible solution not necessarily optimum. Although different parts of the problem are stochastic in nature; yet, limited work relevant to the application of discrete event system simulation has addressed the problem. Presented here is optimization using simulation of VRP; where, a simplified problem has been developed in the ExtendSimTM simulation environment; where, ExtendSimTM evolutionary optimizer is used to minimize the total transportation cost of the problem. Results obtained from the model are very satisfactory. Further complexities of the problem are proposed for consideration in the future.

Keywords: Discrete event system simulation, optimization using simulation, vehicle routing problem.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1084868

References:

[1] R. Baldacci, P. Toth, and D. Vigo, "Exact algorithms for routing problems under vehicle capacity constraints," Ann Oper Res, vol. 175, pp. 213-245, 2010.
[2] N. Azi, M. Gendreau, and J.-Y. Potvin, "An exact algorithm for a singlevehicle routing problem with time windows and multiple routes," European Journal of operational Research, vol. 178, pp. 755-766, 2007.
[3] R. Baldacci, E. Hadjiconstantinou, and A. Mingozzi, "An Exact Algorithm for the Capacitated Vehicle Routing Problem Based on a Two-Commodity NetworkFlow Formulation," Operations Research, vol. 52, pp. 723-738, 2004.
[4] O. Bräysy and M. Gendreau, "Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms," Transportation science, vol. 39, pp. 104-118, 2005.
[5] O. Bräysy and M. Gendreau, "Vehicle Routing Problem with Time Windows, Part II: Metaheuristics," Transportation science, vol. 39, pp. 119-139, 2005.
[6] U. Derigs and K. Reuter, "A simple and efficient tabu search heuristic for solving the open vehicle routing problem," Journal of the Operational Research Society, vol. 60, pp. 1658-1669, 2009.
[7] M. Desrochers, J. K. Lenstra, and M. W. P. Savelsbergh, "A classification scheme for and scheduling problems vehicle routing," European Journal of operational Research, vol. 46, pp. 322-332, 1990.
[8] R. H. Ballou, Business Logistics/ Supply Chain Management, 5th ed. Pearson, 2004.
[9] S. Ropke, "Heuristics and exact algorithms for vehicle routing problems," Ph.D., Department of Computer Science University of Copenhagen, 2005.
[10] Z. Fu, R. Eglese, and L. Li, "A unified tabu search algorithm for vehicle routing problems with soft time windows," Journal of the Operational Research Society, vol. 59, pp. 663 --673, 2008.
[11] M. M. Solomon and J. Desrosiers, "Time window constrained routing and scheduling Problems," Transportation science, vol. 22, 1988.
[12] W. Maden, R. Eglese, and D. Black, "Vehicle routing and scheduling with time-varying data: A case study," Journal of the Operational Research Society, vol. 61, pp. 515-522, 2010.
[13] F. S. Hillier and G. J. Lieberman, Introduction to Operations Research, 8th ed.: McGraw-Hill, 2005.
[14] P. Toth and D. Vigo, The Vehicle Routing Problem. Philadelphia: SIAM, 2002.
[15] A. M. Campbell and M. Savelsbergh, "Efficient Insertion Heuristics for Vehicle Routing and Scheduling Problems," Transportation science, vol. 38, pp. 369-378, 2004.
[16] G. Laporte, "The Vehicle Routing Problem: An overview of exact and approximate algorithms," European Journal of operational Research, vol. 59, pp. 345-358, 1992.
[17] M. M. Solomon, "Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints," Operations Research, vol. 35, pp. 254-265, 1987.
[18] N. Wassan, "A reactive tabu search for the vehicle routing problem," Journal of the Operational Research Society, vol. 57, pp. 111-116, 2006.
[19] B. M. Baker and M. A. Ayechew, "A genetic algorithm for the vehicle routing problem," Computers & Operations Research, vol. 30, pp. 787- 800, 2003.
[20] S. Zhongyue and G. Zhongliang, "Vehicle Routing Problem Based on Object-oriented Discrete Event Simulation," presented at the International Conference on Advanced Computer Control ICACC, 2010.
[21] J. Faulin, M. Gilibert, A. A. Juan, X. Vilajosana, and R. Ruiz, "SR-1: A Simulation-based Heuristic Algorithm for the Capacitated Vehicle Routing Problem," presented at the The 2008 Winter Simulation Conference, 2008.
[22] D. Feillet, P. Dejax, and M. Gendreau, "Traveling Salesman Problems with Profits," Transportation science, vol. 39, pp. 188-205, 2005.
[23] R. V. Kulkarni and P. R. Bhave, "Integer programming formulations of vehicle routing problems," European Journal of operational Research, vol. 20, pp. 58-67, 1985.
[24] "ExtendSim 8 User Guide," Imagine That Inc.2007.