Capacitated Vehicle Routing Problem (CVRP) with Sweep and Nearest Neighbor Algorithm
DOI:
https://doi.org/10.61194/sijl.v2i1.187Keywords:
CVRP, Sweep Algorithm, Neirest Neighbour, OptimizationAbstract
The Capacitated Vehicle Routing Problem (CVRP) presents significant challenges in shipping route optimization and logistics management. These challenges include balancing vehicle capacity, minimizing travel distance, and efficiently grouping delivery points, all of which are crucial for enhancing operational efficiency and reducing costs. This research aims to apply a combination of the Sweep and Nearest Neighbor algorithms to address the CVRP, seeking to improve route efficiency and manage vehicle capacity effectively. The Sweep algorithm is employed to cluster pickup points based on their polar angle from the depot, facilitating efficient grouping and optimal vehicle capacity management. Within each cluster, the Nearest Neighbor algorithm is implemented to optimize the sequence of visits, minimizing total travel distance by sequentially selecting the next closest point. The Haversine Distance is used to calculate the distances between points, ensuring geographical accuracy compared to the Euclidean method. Experimental results demonstrate that this hybrid approach yields shorter routes. Quantitative analysis shows a significant reduction 13% in total travel distance when using this combination of algorithms, highlighting its effectiveness in solving the CVRP. This research demonstrates that combining the Sweep and Nearest Neighbor algorithms provides an efficient solution to the CVRP, improving route optimization and vehicle capacity management. The findings contribute valuable insights to logistics management, with practical implications for enhancing shipping route efficiency.
References
Akhand, M. A. H., Peya, Z. J., Sultana, T., & Rahman, M. M. H. (2017). Solving capacitated vehicle routing problem using variant sweep and swarm intelligence. Journal of Applied Science and Engineering, 20(4), 511–524. https://doi.org/10.6180/jase.2017.20.4.13
Ali, A. M., Ngadi, M. A., Sham, R., & Al_Barazanchi, I. I. (2023). Enhanced QoS Routing Protocol for an Unmanned Ground Vehicle, Based on the ACO Approach. Sensors, 23(3). https://doi.org/10.3390/s23031431
Avraham, E., Raviv, T., & Khmelnitsky, E. (2017). The decentralized field service routing problem. Transportation Research Part B: Methodological, 104, 290–316. https://doi.org/10.1016/j.trb.2017.07.005
Bertrand, J. T., Mangani, N., & Mansilu, M. (1986). Strategies for family planning service delivery in Bas Zaire. International Family Planning Perspectives, 12(4), 108–115. https://doi.org/10.2307/2947981
Das, P. (2016). Uncharted waters: Navigating new configurations for urban service delivery in India. Environment and Planning A, 48(7), 1354–1373. https://doi.org/10.1177/0308518X16640529
Evans, E., Anglin, M. D., Urada, D., & Yang, J. (2011). Promising practices for delivery of court-supervised substance abuse treatment: Perspectives from six high-performing California counties operating Proposition 36. Evaluation and Program Planning, 34(2), 124–134. https://doi.org/10.1016/j.evalprogplan.2010.09.001
Fischetti, M., Toth, P., & Vigo, D. (1994). A Branch-And-Bound Algorithm for the Capacitated Vehicle Routing Problem on Directed Graphs Author ( s ): Matteo Fischetti , Paolo Toth and Daniele Vigo Published by : INFORMS Stable URL : http://www.jstor.org/stable/171544 REFERENCES Linked references ar. Operations Research, 42(5), 846–859.
Ghannadpour, S. F., Noori, S., Tavakkoli-Moghaddam, R., & Ghoseiri, K. (2014). A multi-objective dynamic vehicle routing problem with fuzzy time windows: Model, solution and application. Applied Soft Computing Journal, 14(PART C), 504–527. https://doi.org/10.1016/j.asoc.2013.08.015
Konstantakopoulos, G. D., Gayialis, S. P., & Kechagias, E. P. (2022). Vehicle routing problem and related algorithms for logistics distribution: a literature review and classification. Operational Research, 22(3), 2033–2062. https://doi.org/10.1007/s12351-020-00600-7
Laganà, D., Longo, F., & Santoro, F. (2015). Multi-product inventory-routing problem in the supermarket distribution industry. International Journal of Food Engineering, 11(6), 747–766. https://doi.org/10.1515/ijfe-2015-0052
Liu, G.-S., & Lin, K.-P. (2019). A decision support system of green inventory-routing problem. Industrial Management and Data Systems, 119(1), 89–110. https://doi.org/10.1108/IMDS-11-2017-0533
Mahajan, N., Hegyi, A., Hoogendoorn, S. P., & van Arem, B. (2019). Design analysis of a decentralized equilibrium-routing strategy for intelligent vehicles. Transportation Research Part C: Emerging Technologies, 103, 308–327. https://doi.org/10.1016/j.trc.2019.03.028
McDaniel, E. L., Akwafuo, S., Urbanovsky, J., & Mikler, A. R. (2023). Benchmarking a fast, satisficing vehicle routing algorithm for public health emergency planning and response: “Good Enough for Jazz.” PeerJ Computer Science, 9. https://doi.org/10.7717/peerj-cs.1541
Mengash, H. A., Alqahtani, H., Maray, M., Nour, M. K., Marzouk, R., Al-Hagery, M. A., Mohsen, H., & Duhayyim, M. A. (2023). Coati Optimization-Based Energy Efficient Routing Protocol for Unmanned Aerial Vehicle Communication. Computers, Materials and Continua, 75(3), 4805–4820. https://doi.org/10.32604/cmc.2023.037810
Peya, Z. J., Akhand, M. A. H., Sultana, T., & Hafizur Rahman, M. M. (2019). Distance based Sweep Nearest algorithm to solve Capacitated Vehicle Routing Problem. International Journal of Advanced Computer Science and Applications, 10(10), 259–264. https://doi.org/10.14569/ijacsa.2019.0101036
Prajapati, D., Chan, F. T. S., Daultani, Y., & Pratap, S. (2022). Sustainable vehicle routing of agro-food grains in the e-commerce industry. International Journal of Production Research, 60(24), 7319–7344. https://doi.org/10.1080/00207543.2022.2034192
Prasetya, D. A., Nguyen, P. T., Faizullin, R., Iswanto, I., & Armay, E. F. (2020). Resolving the shortest path problem using the haversine algorithm. Journal of Critical Reviews, 7(1), 62–64. https://doi.org/10.22159/jcr.07.01.11
Rojas-Cuevas, I.-D., Caballero-Morales, S.-O., Martinez-Flores, J.-L., & Mendoza-Vazquez, J.-R. (2018). Capacitated vehicle routing problem model for carriers. Journal of Transport and Supply Chain Management, 12(July), 0–9. https://doi.org/10.4102/jtscm.v12i0.345
Rosyida, E. E., Santosa, B., & Pujawan, I. N. (2020). Freight route planning in intermodal transportation network to deal with combinational disruptions. Cogent Engineering, 7(1). https://doi.org/10.1080/23311916.2020.1805156
Roudo, M., Campbell, A., & Delay, S. (2018). Is decentralisation compatible with the application of performance management? The impacts of minimum service standards on the motivation of local government to improve service delivery in the indonesian decentralised system. Journal of Regional and City Planning, 29(2), 135–155. https://doi.org/10.5614/jrcp.2018.29.2.5
Scharpff, J., Schraven, D., Volker, L., Spaan, M. T. J., & de Weerdt, M. M. (2021). Can multiple contractors self-regulate their joint service delivery? A serious gaming experiment on road maintenance planning. Construction Management and Economics, 39(2), 99–116. https://doi.org/10.1080/01446193.2020.1806336
Seifbarghy, M., & Samadi, Z. (2014). A tabu search-based heuristic for a new capacitated cyclic inventory routing problem. International Journal of Mathematics in Operational Research, 6(4), 491–504. https://doi.org/10.1504/IJMOR.2014.063159
Wang, Y., Peng, S., Assogba, K., Liu, Y., Wang, H., Xu, M., & Wang, Y. (2018). Implementation of cooperation for recycling vehicle routing optimization in two-echelon reverse logistics networks. Sustainability (Switzerland), 10(5). https://doi.org/10.3390/su10051358
Winarno, E., Hadikurniawati, W., & Rosso, R. N. (2017). Location based service for presence system using haversine method. Proceedings - 2017 International Conference on Innovative and Creative Information Technology: Computational Intelligence and IoT, ICITech 2017, 2018-January, 1–4. https://doi.org/10.1109/INNOCIT.2017.8319153
Zhao, P., Liu, F., Guo, Y., Duan, X., & Zhang, Y. (2021). Bi-Objective Optimization for Vehicle Routing Problems with a Mixed Fleet of Conventional and Electric Vehicles and Soft Time Windows. Journal of Advanced Transportation, 2021. https://doi.org/10.1155/2021/9086229
Zhou, W., Oyegoke, A. S., & Sun, M. (2019). Service planning and delivery outcomes of home adaptations for ageing in the UK. Journal of Housing and the Built Environment, 34(2), 365–383. https://doi.org/10.1007/s10901-017-9580-3
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2024 Erly Ekayanti, Sugianto, Imaduddin Bachtiar Efendi
This work is licensed under a Creative Commons Attribution 4.0 International License.
