1. Proceedings
  2. I3M
  3. 2021
  4. MAS
  5. 10.46354/i3m.2021.mas.001

A hybrid heuristic algorithm for solving the Traveling Salesman Problem with Time Windows

  • a Mattia Neroni ,
  • b Letizia Tebaldi 
  • a,b, Department of Engineering and Architecture – University of Parma, Parco Area delle Scienze 181/A, 43124, Parma (Italy)
Cite as
Neroni M., Tebaldi L. (2021). A hybrid heuristic algorithm for solving the Traveling Salesman Problem with Time Windows. Proceedings of the 20th International Conference on Modeling & Applied Simulation (MAS 2021), pp. 1-8. DOI: https://doi.org/10.46354/i3m.2021.mas.001

Abstract

Several issues related to the logistics field can be recognized as applications of the renowned Traveling Salesman Problem with Time Windows (TSPTW); examples of these issues include, among others, instance planning deliveries, managing internal logistics, bank couriers, material handling, but also production scheduling. In the light of such numerous applications, in this paper a hybrid algorithm based on the Divide-And-Conquer (DAC) technique and the Biased Randomized heuristic Algorithm (BRA) for solving the mentioned problem is presented. The aim is to propose a flexible solution suitable for implementation in many contexts where the TSPTW is relevant, thus improving performance and key indicators. The quality and reliability of the tool are validated on several benchmark problems through a comparison with a different algorithm already proposed in literature. In the light of the simulations carried out, it turned out to be effective and efficient when dealing with problems similar to those that characterize real applications, even in terms of computational time efficiency.

References

  1. Ahmadov, Y. and Helo, P. (2018). A cloud based job sequencing with sequence-dependent setup for sheet metal manufacturing. Ann. Oper. Res., 270:5-24.
  2. Arcus, A. L. (1965). A computer method of sequencing operations for assembly lines. Int. J. Prod. Res., 4:259-277.
  3. Briant, O., Cambazard, H., Cattaruzza, D., Catusse, N., Ladier, A.-L. and Ogier, M. (2020). An efficient and general approach for the joint order batching and picker routing problem. Eur. J. Oper. Res., 285:497-512.
  4. Bontempi, G., & Birattari, M. (2005). From linearization to lazy learning: A survey of divide-and-conquer techniques for nonlinear control. International Journal of Computational Cognition, 3(1).
  5. Bychkov, I. and Batsyn, M. (2018). A Hybrid Approach for the Capacitated Vehicle Routing Problem with Time Windows. Proceedings of the School-Seminar on Optimization Problems and their Applications (OPTA-SCL 2018).
  6. Chen, Z. and Zhang, R. (2018). A capital flow-constrained lot-sizing problem with trade credit. Sci. Iran., 25:2775-27
  7. Cheng, W., Maimai, Z. and Jian, L. (2008). Solving traveling salesman problems with time windows by genetic particle swarm optimization. 2008 IEEE Congress on Evolutionary Computation (IEEE World Congress on Computational Intelligence),1752-1755.
  8. Colorni, A., Dorigo, M., and Maniezzo, V. (1991). Distributed optimization by ant colonies. In Proceedings of the first European conference on artificial life, 142:134-142.
  9. Dekker, R., Bloemhof, J. and Mallidis, I. (2012). Operations Research for green logistics – An overview of aspects, issues, contributions and challenges. Eur. J. Oper. Res.,, 219:671-679.
  10. El-Sherbeny. (2010). Vehicle routing with time windows: An overview of exact, heuristic and metaheuristic methods. J. King Saud Univ. Sci., 22:123-131.
  11. Eshtehadi, R., Demir, E. and Huang, Y. (2020). Solving the vehicle routing problem with multi-compartment vehicles for city logistics. Comput. Oper. Res., 115, A.N. 104859.
  12. Eurostat, (2020). Statistics Explained, Freight Transportation Statistics – modal split. https://ec.europa.eu/eurostat/statistics-explained/pdfscache/1142.pdf [Accessed January 2021].
  13. Ferreira da Silva, R. and Urrutia, S. (2010). A General VNS heuristic for the traveling salesman problem with time windows. Discrete Optim., 7:203-211.
  14. Foo, Y. S., & Szu, H. (1989). ‘Solving large-scale optimization problems by divide-and-conquer neural networks’. IEEE International Joint Conference on Neural Networks, Vol. 1, pp. 507-511.
  15. Gendreau, M., Hertz, A., Laporte, G. and Stan, M. (1998). A generalized insertion heuristic for the traveling salesman problem with time windows. Oper. Res., 46:330-335.
  16. Grasas, A., Juan, A. A., Faulin, J., de Armas, J. and Ramalhinho, H. (2017). Biased randomization of heuristics using skewed probability distributions: a survey and some applications. Comput. Ind. Eng., 110:216-228.
  17. Juan, A. A., Faulin, J., Ruiz, R., Barrios, B. and Caballé, S. (2010). The SR-GCWS hybrid algorithm for solving the capacitated vehicle routing problem. Appl. Soft Comput., 10: 215-224.
  18. Juan, A. A., Lourenço, H. R., Mateo, M., Luo, R., & Castella, Q. (2014). Using iterated local search for solving the flow‐shop problem: parallelization, parametrization, and randomization issues. International Transactions in Operational Research, 21(1), 103-126.
  19. Juan, A. A., Pascual, I., Guimarans, D. and Barrios, B. (2015). Combining biased randomization with iterated local search for solving the multi-depot vehicle routing problem. Int. T. Oper. Res., 22:647-667.
  20. Karunanithy, K. and Velusamy, B. (2020). Energy efficient cluster and travelling salesman problem based data collection using WSNs for Intelligent water irrigation and fertigation. Measurement: Journal of the International Measurement Confederation, 161:107835.
  21. Kulak, O., Sahin, Y. and Egement Taner, M. (2012). Joint order batching and picker routing in single and multiple-cross-aisle warehouses using cluster- based tabu search algorithms. Flex. Serv. Manuf. J., 24:52-80.
  22. Mei, Y., Omidvar, M. N., Li, X., & Yao, X. (2016). A competitive divide-and-conquer algorithm for unconstrained large-scale black-box optimization. ACM Transactions on Mathematical Software (TOMS), 42(2), 1-24.
  23. Meuth, R. J., & Wunsch, D. C. (2008). Divide and conquer evolutionary TSP solution for vehicle path planning, IEEE Congress on Evolutionary Computation, pp. 676-681.
  24. Mulder, S. A., & Wunsch D. C. (2003). Million city traveling salesman problem solution by divide and conquer clustering with adaptive resonance neural networks. Neural Networks, 16(5-6): 827-832.
  25. Ohlmann, J.W. and Thomas, B.W. (2007). A compressed-annealing heuristic for the traveling salesman problem with time windows. INFORMS J. Comput., 19(1).
  26. Öztürkoğlu, Ö. (2020). A bi-objective mathematical model for product allocation in block stacking warehouses. Int. T. Oper. Res., 27:2184-2210.
  27. Penteado M., M. and Chicarelli A., R. (2016). Logistics activities in supply chain business process. Int. J. Logist. Manag., 27:6-30.
  28. Selvi, L., Joelianto, E. and Leksono, E. (2019). Time Optimization Analysis Using Hybrid Simulated Annealing and Genetics Algorithm for CNC Punching Machine. 2nd International Conference on Mechanical, Electronics, Computer, and Industrial Technology, MECnIT 2018, 1230. 
  29. Silva, A., Coelho, L.C., Darvish, M. and Renaud, J. (2020). Integrating storage location and order picking problems in warehouse planning. Transp. Res. Part E, 140:102003.
  30. Tonge, F. M. (1965). Assembly line balancing using probabilistic combinations of heuristics. Manag. Sci., 11:727-735.
  31. Yang, P., Tang, K., & Yao, X. (2019). A parallel divide-and-conquer-based evolutionary algorithm for large-scale optimization. IEEE Access, 7, 163105-163118.
  32. Zhang, G. Q. and Lai, K. K. (2006). Combining path relinking and genetic algorithms for the multiple-level warehouse layout problem. Eur. J. Oper. Res., 169:413-425.