A Hybrid Approach for Simultaneous Effective Automobile Navigation with DE and PSO
DOI:
https://doi.org/10.21015/vtcs.v12i2.1914Abstract
Automobile Navigation is fundamentally an optimization challenge focused on transportation logistics between a depot and various clients. In this paper, we specifically address the complex variant of Automobile Navigation that involves simultaneous pickup and delivery tasks, which must be executed concurrently at clients' locations. This dual requirement introduces significant complexity, as traditional exact approaches struggle to rapidly identify near-optimal solutions due to the problem's NP-hardness. Therefore, the objective of this research is to develop a novel hybrid algorithm that integrates Differential Evolution (DE) and Particle Swarm Optimization (PSO) to effectively solve the Automobile Navigation problem with simultaneous pickup and delivery. The proposed method uses the nearest neighbor heuristic to initially produce results. It is based on the iterated local search paradigm. Variable neighborhood descent is used to improve the search process by adding random sequences to the neighborhood structures for improved search space intensification. Furthermore, exploration across various sections of the search space is made possible by the perturbation process. This method solves the problem of different truck loads on every client visit because it does the pickup and delivery at the same time, which makes the Navigation strategy more effective.
References
A. Ait-Saadi, Y. Meraihi, A. Soukane, A. Ramdane-Cherif, and A. B. Gabis, "A novel hybrid chaotic aquila optimization algorithm with simulated annealing for unmanned aerial vehicles path planning," Computers and Electrical Engineering, vol. 104, p. 108461, 2022.
J. Zhao, M. Mao, X. Zhao, and J. Zou, "A hybrid of deep reinforcement learning and local search for the vehicle routing problems," IEEE Transactions on Intelligent Transportation Systems, vol. 22, no. 11, pp. 7208–7218, 2020.
P. Sun, L. P. Veelenturf, M. Hewitt, and T. Van Woensel, "Adaptive large neighborhood search for the time-dependent profitable pickup and delivery problem with time windows," Transportation Research Part E: Logistics and Transportation Review, vol. 138, p. 101942, 2020.
Z. H. Ahmed and M. Yousefikhoshbakht, "An improved tabu search algorithm for solving heterogeneous fixed fleet open vehicle routing problem with time windows," Alexandria Engineering Journal, vol. 64, pp. 349–363, 2023.
M. Ibrahim, F. Nurhakiki, D. Utama, and A. Rizaki, "Optimised genetic algorithm crossover and mutation stage for vehicle routing problem pick-up and delivery with time windows," in IOP Conference Series: Materials Science and Engineering, vol. 1071, no. 1, p. 012025, 2021.
W. Zhang, D. Yang, G. Zhang, and M. Gen, "Hybrid multiobjective evolutionary algorithm with fast sampling strategy-based global search and route sequence difference-based local search for vrptw," Expert Systems with Applications, vol. 145, p. 113151, 2020.
T. Stadtler, S. Nita, and J. Dünnweber, "A parallel hybrid genetic search for the capacitated vrp with pickup and delivery," in 34th International Workshop, LCPC 2021, Newark, DE, USA, October 13–14, 2021, 2023.
P. Li, C. Zhi, and W. Li, "An algorithm to solve heterogeneous vehicle routing problem with second trip," IEEE Access, vol. 9, pp. 12241–12255, 2021.
F. R. Dorcheh and M. Rahbari, "Greenhouse gas emissions optimization for distribution and vehicle routing problem in a poultry meat supply chain in two phases: a case study in iran," Process Integration and Optimization for Sustainability, vol. 7, no. 5, pp. 1289–1317, 2023.
R. Prakash and S. Pushkar, "Green vehicle routing problem: Metaheuristic solution with time window," Expert Systems, vol. 41, no. 6, p. e13007, 2024.
D. A. Albalawneh and M. Mohamed, "A new federated genetic algorithm-based optimization technique for multi-criteria vehicle route planning using arcgis network analyst," International Journal of Pervasive Computing and Communications, vol. 20, no. 2, pp. 206–227, 2024.
R. M. A. Baracho, M. J. M. Vidigal, M. F. Porto, and B. Couto, "Interdisciplinarity in smart systems applied to rural school transport in brazil," Journal of Systemics, Cybernetics and Informatics, vol. 22, no. 4, pp. 52–59, 2024.
A. Mohammadi, B. Kiani, H. Mahmoudzadeh, and R. Bergquist, "Pedestrian road traffic accidents in metropolitan areas: Gis-based prediction modelling of cases in mashhad, iran," Sustainability, vol. 15, no. 13, p. 10576, 2023.
A. Amini and M. Haughton, "A mathematical optimization model for cluster-based single-depot location-routing e-commerce logistics problems," Supply Chain Analytics, vol. 3, p. 100019, 2023.
A. Bokhare and P. Metkewar, "Identifying best goalkeepers problem is a np-hard?" in World Conference on Information Systems for Business Management. Springer, 2023, pp. 415–421.
S. Liu, J. G. Cavalcanti Costa, Y. Mei, and M. Zhang, "Gpgls: Genetic programming guided local search for large-scale vehicle routing problems," in International Conference on Parallel Problem Solving from Nature. Springer, 2024, pp. 36–51.
Y. Ma, Z. Cao, and Y. M. Chee, "Learning to search feasible and infeasible regions of routing problems with flexible neural k-opt," Advances in Neural Information Processing Systems, vol. 36, 2024.
W. Zhang, D. Yang, G. Zhang, and M. Gen, "Hybrid multiobjective evolutionary algorithm with fast sampling strategy-based global search and route sequence difference-based local search for vrptw," Expert Systems with Applications, vol. 145, p. 113151, 2020.
J. G. C. Costa, Y. Mei, and M. Zhang, "An evolutionary hyper-heuristic approach to the large scale vehicle routing problem," in 2021 IEEE Congress on Evolutionary Computation (CEC), IEEE, 2021, pp. 2109–2116.
A. N. Jasim and L. C. Fourati, "Guided genetic algorithm for solving capacitated vehicle routing problem with unmanned-aerial-vehicles," IEEE Access, 2024.
J. G. C. Costa, Y. Mei, and M. Zhang, "An evolutionary hyper-heuristic approach to the large scale vehicle routing problem," in 2021 IEEE Congress on Evolutionary Computation (CEC), IEEE, 2021, pp. 2109–2116.
M. Sánchez, J. M. Cruz-Duarte, J. Carlos Ortíz-Bayliss, H. Ceballos, H. Terashima-Marin, and I. Amaya, "A systematic review of hyper-heuristics on combinatorial optimization problems," IEEE Access, vol. 8, pp. 128068–128095, 2020.
A. A. Laghari, A. K. Jumani, R. A. Laghari, H. Li, S. Karim, and A. A. Khan, "Cognitive robotics," Cognitive Robotics, 2024.
J. G. C. Costa, Y. Mei, and M. Zhang, "An evolutionary hyper-heuristic approach to the large scale vehicle routing problem," in 2021 IEEE Congress on Evolutionary Computation (CEC), IEEE, 2021, pp. 2109–2116.
A. A. Abro, A. A. Khan, M. S. H. Talpur, I. Kayijuka, and E. Yaşar, "Machine learning classifiers: a brief primer," University of Sindh Journal of Information and Communication Technology, vol. 5, no. 2, pp. 63–68, 2021.
Z. Li and V. Tam, "Adaguide: An adaptive and guided differential evolution for continuous optimization problems," Applied Intelligence, pp. 1–79, 2024.
J. G. C. Costa, Y. Mei, and M. Zhang, "Learning penalisation criterion of guided local search for large scale vehicle routing problem," in 2021 IEEE Symposium Series on Computational Intelligence (SSCI), IEEE, 2021, pp. 1–8.
A. A. Laghari, A. K. Jumani, R. A. Laghari, H. Li, S. Karim, and A. A. Khan, "Unmanned aerial vehicles advances in object detection and communication security review," Cognitive Robotics, 2024.
A. A. Abro, "Identifying the machine learning techniques for classification of target datasets," Computer Science-Artificial Intelligence, 2020.
T. Li, A. Rezaeipanah, and E. M. T. El Din, "An ensemble agglomerative hierarchical clustering algorithm based on clusters clustering technique and the novel similarity measurement," Journal of King Saud University-Computer and Information Sciences, vol. 34, no. 6, pp. 3828–3842, 2022.
M. Z. Ghawy, G. A. Amran, H. AlSalman, E. Ghaleb, J. Khan, A. A. Al-Bakhrani, A. M. Alziadi, A. Ali, and S. S. Ullah, "An effective wireless sensor network routing protocol based on particle swarm optimization algorithm," Wireless Communications and Mobile Computing, vol. 2022, no. 1, p. 8455065, 2022.
B. T. Tezel and A. Mert, "A cooperative hybrid firefly algorithm for the capacitated vehicle routing problem," Journal of the Operational Research Society, vol. 74, no. 8, pp. 1691–1712, 2023.
Downloads
Published
How to Cite
Issue
Section
License
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License (CC-By) that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
This work is licensed under a Creative Commons Attribution License CC BY
