A Comparative Study of Meta-heuristic Algorithms for dynamic vehicle routing problem in order to provide efficiency of transportation systems

Subject Areas : Business Management

Nazila Mosayebzadeh ¹ , Farzin Modarres khiyabani ²

1 - Department of Mathematics, Tabriz Branch, Islamic Azad University, Tabriz, Iran
2 - Department of Mathematics, Tabriz Branch, Islamic Azad University, Tabriz, Iran

Received: 2016-02-16 Accepted : 2016-12-16 Published : 2017-05-22

Keywords: Genetic Algorithm, Meta-heuristic Algorithm, Productivity, Vehicle Routing Problem,

Abstract :

Vehicle Routing Problem (VRP) wasone of the mostpopularoptimization problems that hadmany usages for productivity andefficiency of transportation systems in recent decades.The VehicleRouting Problem with Simultaneous pick-up and deliveries (VRP/SPD),which considers simultaneous distribution and collection of goodsfrom/to customers (VRP/SDP/SDC) was a variant of the classical vehiclerouting problem where customers require simultaneous pick-up anddelivery at their locations to be completed within a specified time.Applications of the SPD and its related variants are commonly comeacross in every day transportation and optimizing logistic planning. Thispaper had used Meta-heuristic to this end. The proposed method wasapplied for solving capacitated vehicle routing problem (CVRP) toimprove the distribution efficiency and productivity with an objective ofminimizing the total distance covered in each route, while consideringthe capacity of different routes. This problemwas essentially an NP-Hardin nature, so there was no known optimal solution method withpolynomial time. To solve this NP-hard VRP a hybrid genetic basedalgorithm was developed. The proposed geneticalgorithm was tested onsome standardproblem with respect to computational efficiency andsolution quality. The presented method was implemented and itsperformance was further investigated by comparing it against existingheuristics for the same problem. Theresults showed that the success ofthe proposed approach in handling the difficult problem constraints anddevising simple and robust solution mechanisms that can be integratedwith routing optimization tools and used in real world applications.

References:

Blanton, J. L., & Wainwright, R. L. (1993). Multiple vehicle routing with time and capacity constraints using Genetic Algorithms in Forrest. Proceedings of the 5^th International Conference on Genetic Algorithms, Morgan Kaufmann, San Mateo, CA, 452-9.

Christophides, N., & Beasley, J. (1984). The period routing problem. Networks, 14, 237-256.

Davis, L. (1991). Handbook of Genetic Algorithms, New York: Van Nostrand Reinhold.

Falkenauer, E. (1998). Genetic Algorithms and Grouping Problems, Wiley: Chichester.

Fisher, M. L. (1995). Vehicle routing. Handbooks Oper Res Manage Sci 8.

Fleischmann, B., Gnutzmann, S., & Sandvob, E. (2004). Dynamic vehicle routing based on online traffic information. Transportation Science, 38(4), 420-433.

Gendreau, M., & Potvin, J. Y. (1998). Dynamic vehicle routing and dispatching. Translate  by: T. G. Crainic, & G. Laporte, Boston: Fleet Management and Logistics, Kluwer.  

Ghiani, G., Guerriero, F., Laporte, G., & Musmanno, R. (2003). Real-time vehicle routing: Solution concepts, algorithms and parallel computing strategies. Research Report, Center of Excellence for High Performance Computing, University of Calabria, Arcavacata di Rende.

Glover, F. (1990). Tabu search-part II. Orsaj Comput, 2(1), 4-32.

Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley.

Hanshar F.T., & Ombuki-Berman. B.M. (2007).  Dynamic vehicle routing using genetic algorithms. Appl. Intell. 27, 89-99.

Holland, J. H. (1992). Adaptation in natural and artificial systems university of michigan press Second Edition. MIT Press.

Holland, J. H. (1975). Adaptation in Natural and Artificial Systems-An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence, The University of Michigan Press, Ann Arbor, MI.

Jaw, J. J., Odoni, A. R., Psaraftis, H. N., and Wilson, N. H. M. (1986). A heuristic algorithm for the multi-vehicle advance request dial-a-ride problem with time windows. Transportation Research, 20(2), 243-57.

Kilby P, Prosser P, Shaw, P. (1998). Dynamic VRPs: astudy of scenarios. Technical Report APES-0-1998, University of Strathclyde.

Kopfer, H., Pankratz, G., & Erkens, E. (1994). Die entwicklung eines hybriden genetischen algorithmus fu¨r das tourenplanungsproblem. OR Spektrum, 16, 21-32.

Li, H., & Lim, A. (2001). A metaheuristic for solving the pickup and delivery problem with time windows, in IEEE Computer Society (Ed.), Proceedings of the 13th IEEE International Conference on Tools with Artificial Intelligence (ICTAI), IEEE Computer Society, Los Alamitos.

Mitchell, M. (1996). Anintroduction to genetic algorithms. MIT Press.

Montemanni, R., Gambardella L. M., Rizzoli A. E., & Donati, A. V. (2005). A new algorithm for a dynamic vehicle routing problem based on Ant colony system. Jcomb Optim, 10, 327–343.

Pankratz, G. (2005). A grouping genetic algorithm for the pickup and delivery problem with time windows. Operations Research Spectrum, 27, 21-41.

Pankratz, G. (2005). Dynamic vehicle routing by means of a genetic algorithm. International Journal of Physical Distribution & Logistics Management 35(5), 362-383.

Psaraftis, H. N. (1988). Dynamic vehicle routing problems, North-Holland, Amsterdam.

Savelsbergh, M. W. P., & Sol, M. (1995). The general pickup and delivery problem. Transportation Science, 29, 17-29.

Taillard, E. D. (1994). Parallel iterative search methods for vehicle routing problems. Networks, 23(8), 661-673.

Yang, J., Jaillet, P., & Mahmassani, H. S. (2004). Study of a real-time multi-vehicle truckload pickup-and-delivery problem. Transportation Science, 38(2).