13May 2018

SOLVE THE CAPACITANCE VEHICLE ROUTING PROBLEM ( CVRP) USING THE TABU SEARCH ALGORITHM (TS) AND THE PARTICLE SWARM OPTIMIZATION WITH PRACTICAL APPLICATION.

  • Assistant Professor of Statistics at the University of Baghdad, College of Management and Economics.
  • Master Operations Research, University of Baghdad, College of Management and Economics.
Crossref Cited-by Linking logo
  • Abstract
  • Keywords
  • References
  • Cite This Article as
  • Corresponding Author

In this paper we examine the vehicle routing problem (VRP) which is classified as a problem (NP-HARD). This problem addresses the design of tracks for a group of vehicles that equip a number of customers deployed in different locations. The objective of this problem is to reduce the total cost of delivery, taking into account the limitations of the problem, and also to design the optimal distribution of the tracks within the specified vehicle capacity limits. The study includes the most important methods used to solve the problem, the use of the tabu search algorithm (TS) and particle swarm optimization(pso) and the hybridization of a new algorithm that adopts the characteristics of tabu search with particle swarm optimization ( TS-PSO) in solving problem Issues. The performance and efficiency of the algorithms are compared by solving known issues of the problem. The results show that the tabu search algorithm (TS) is efficient in finding solutions to the problem. The ability to reach the mean deviation about (1.764) from the standard solutions for the set of standard issues. However, the TS-PSO is able to produce results that overcame the results of the tabu search algorithm as well as the particle swarm algorithm, although the hybrid algorithm requires double and large computational times compared to the two individually designed algorithms. The method of the problem has been applied in the General Company for the manufacture of grain distribution process from one of the mills to a group of agents deployed geographically The method was able to reach to draw and design the best possible paths for vehicles available at the least distance cut and the lowest number of vehicles.

  1. Ai, J. and V. Kachitvichyanukul. A study on adaptive particle swarm optimization for solving vehicle routing problems. in The 9th Asia Pacific? industrial engineering and management systems conference. 2008
  2. Belenguer, J.M. and E. Benavent, A cutting plane algorithm for the capacitated arc routing problem. Computers & Operations Research, 2003. 30(5): p. 705-728
  3. Choi, E. and D.-W. Tcha, A column generation approach to the heterogeneous fleet vehicle routing problem.Computers & Operations Research, 2007. 34(7): p 2080-2095
  4. Christofides, N., The vehicle routing problem. Revue fran?aise d'automatique, informatique, recherche op?rationnelle. Recherche op?rationnelle, 1976. 10(V1): p. 55-70.
  5. Clarke, G. and J.W. Wright, Scheduling of vehicles from a central depot to a number of delivery points. Operations research, 1964. 12(4): p. 568-581
  6. Dantzig, G.B. and J.H. Ramser, The truck dispatching problem.Management science, 6(1): p. 80-91
  7. Du, L. and R. He, Combining nearest neighbor search with tabu search for large- scale vehicle routing problem. Physics Procedia, 2012. 25: p. 1536-1546
  8. Fosin, J., T. Carić, and E. Ivanjko, Vehicle Routing Optimization Using Multiple Local Search Improvements. automatika, 2014. 55(2): p. 124-132
  9. Fukasawa, R., et al., Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Mathematical programming, 2006. 106(3): p. 491-511
  10. Gendreau, M. and J.-Y. Potvin, Metaheuristics in combinatorial optimization. Annals of Operations Research, 2005. 140(1): p. 189-213
  11. Glover, F., Future paths for integer programming and links to artificial intelligence Computers & operations research, 1986. 13(5): p. 533-549
  12. Glover, F.W. and G.A. Kochenberger, Handbook of metaheuristics. Vol. 57. 2006: Springer Science & Business Media http://vrp.atd-lab.inf.puc-rio.br/index.php/en/instances?view=vrp
  13. Huang, S.-H., Solving the multi-compartment capacitated location routing problem with pickup?delivery routes and stochastic demands. Computers & Industrial? Engineering, 2015. 87: p. 104-113.
  14. Jaziri, W., Local search techniques: focus on tabu search. Published by In-The in September, 2008.???????? Kachitvichyanukul, V., Particle swarm optimization and two solution representations for solving the capacitated vehicle routing problem.Computers & Industrial Engineering, 2009. 56(1): p. 380-387
  15. Kok, A.L., et al., A dynamic programming heuristic for the vehicle routing problem with time windows and European Community social legislation Transportation Science, 2010. 44(4): p. 442-454
  16. Kokash, N., An introduction to heuristic algorithms. Department of Informatics and Telecommunications, 2005: p. 1-8
  17. Laporte, G., et al., Classical and modern heuristics for the vehicle routing problem. International transactions in operational research, 2000. 7(4-5):p. 285-300
  18. Lin, S.-W., et al., Applying hybrid meta-heuristics for capacitated vehicle routing problem. Expert Systems with Applications, 2009. 36(2):p. 1505-1512.
  19. Naddef, D. and G. Rinaldi, Branch-and-cut algorithms for the capacitated VRP, in The vehicle routing problem. 2002, SIAM. p. 53-84
  20. Osman, I.H., Metastrategy? simulated?? annealing and tabu search algorithms for the vehicle routing problem. Annals of operation? research,1993. 41(4): p. 421-451
  21. Peterson, B., et al., Flexible milk-runs for stochastic vehicle routing. 2010
  22. Ray , S., Revisiting The Evolution and Application of Assignment Problem Industrial Engineering Letters, 2016. 6(10): p. 16-38
  23. Ruttanateerawichien, K., W. Kurutach, and T. Pichpibul. A new efficient and effective golden-ball-based technique for the capacitated vehicle routing problem. in Computer and Information Science (ICIS), 2016 IEEE/ACIS 15th International Conference on. IEEE
  24. Toth, P. and D. Vigo, Branch-and-bound algorithms for the capacitated VRP, in The vehicle routing problem. 2002, SIAM. p. 29-51
  25. Zhang, Y., et al., Analysis of an Automated Vehicle Routing Problem in Logistics considering Path Interruption. Journal of Advanced Transportation, 2017. 2017.

[Abdul-Jabbar Khadr Bakhit and Ali ghani noori. (2018); SOLVE THE CAPACITANCE VEHICLE ROUTING PROBLEM ( CVRP) USING THE TABU SEARCH ALGORITHM (TS) AND THE PARTICLE SWARM OPTIMIZATION WITH PRACTICAL APPLICATION. Int. J. of Adv. Res. 6 (May). 129-139] (ISSN 2320-5407). www.journalijar.com

Ali Ghani Noori

DOI:

Article DOI: 10.21474/IJAR01/7016      
DOI URL: http://dx.doi.org/10.21474/IJAR01/7016

Download Full Paper

Download PDF No. of Downloads: 68 | No. of Views: 271