Cluster-based approach for successful solving real-world vehicle routing problems

• Autorzy: Žunić Emir , Đonko Dženana , Šupić Haris , Delalić Sead

Identyfikatory

DOI

10.15439/2020F184

• Konferencja: Federated Conference on Computer Science and Information Systems (15 ; 06-09.09.2020 ; Sofia, Bulgaria)
• Języki publikacji: EN

Abstrakty

EN

Vehicle routing problem as the generalization of the Travelling Salesman Problem (TSP) is one of the most studied optimization problems. Industry itself pays special attention to this problem, since transportation is one of the most crucial segments in supplying goods. This paper presents an innovative cluster-based approach for the successful solving of real-world vehicle routing problems that can involve extremely complex VRP problems with many customers needing to be served. The validation of the entire approach was based on the real data of a distribution company, with transport savings being in a range of 10-20 %. At the same time, the transportation routes are completely feasible, satisfying all the realistic constraints and conditions.

Słowa kluczowe

EN

clustering; transport; vehicle routing problem; feasible solution; multi-phase approach

PL

grupowanie; transport; wyznaczanie trasy; wykonalne rozwiązanie; podejście wielofazowe

• Wydawca: Polskie Towarzystwo Informatyczne
• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2020
• Tom: Vol. 21
• Strony: 619--626
• Opis fizyczny: Bibliogr. 17 poz., rys., wz., tab.

Twórcy

autor

Žunić Emir

• Info Studio d.o.o. Sarajevo and Faculty of Electrical Engineering, University of Sarajevo, B&H

autor

Đonko Dženana

• Faculty of Electrical Engineering, University of Sarajevo, Bosnia and Herzegovina

autor

Šupić Haris

• Faculty of Electrical Engineering, University of Sarajevo, Bosnia and Herzegovina

autor

Delalić Sead

• Faculty of Science, University of Sarajevo and Info Studio d.o.o. Sarajevo, B&H

Bibliografia

• 1. Dantzig, G. B., and Ramser, J. H. (1959). The truck dispatching problem. Management science, Vol. 6(1), 80-91. http://dx.doi.org/10.1287/mnsc.6.1.80
• 2. Hall, R. (2006). On the road to integration. OR/MS Today 33(3), 50–57.
• 3. Grosso, R., Munuzuri, J., Escudero-Santana, A., and Barbadilla-Martín, E. (2018). Mathematical Formulation and Comparison of Solution Approaches for the Vehicle Routing Problem with Access Time Windows. Complexity. http://dx.doi.org/10.1155/2018/4621694
• 4. Nalepa, J., and Blocho, M. (2016). Adaptive memetic algorithm for minimizing distance in the vehicle routing problem with time windows. Soft Computing, Vol. 20 (6), 2309–2327. http://dx.doi.org/10.1007/s00500-015-1642-4
• 5. Dixit, A., Mishra, A., and Shukla, A. (2019). Vehicle Routing Problem with Time Windows Using Meta-Heuristic Algorithms: A Survey. In: Yadav N., Yadav A., Bansal J., Deep K., Kim J. (eds) Harmony Search and Nature Inspired Optimization Algorithms. Advances in Intelligent Systems and Computing, Vol. 741, 539-546. http://dx.doi.org/10.1007/978-981-13-0761-4_52
• 6. Goel, R., and Maini, R. (2018). A hybrid of ant colony and firefly algorithms (HAFA) for solving vehicle routing problems. Journal of Computational Science, Vol. 25, 28-37. http://dx.doi.org/10.1016/j.jocs.2017.12.012
• 7. Mahmudy, W. F. (2014). Improved Simulated Annealing for Optimization of Vehicle Routing Problem With Time Windows (VRPTW). Kursor, Vol. 7(3). http://dx.doi.org/10.21107/KURSOR.V7I3.1092
• 8. Osaba, E., Yang, X. S., and Del Ser, J. (2020). Is the Vehicle Routing Problem Dead? An Overview Through Bioinspired Perspective and a Prospect of Opportunities. In: Yang XS., Zhao YX. (eds) Nature- Inspired Computation in Navigation and Routing Problems. Springer Tracts in Nature-Inspired Computing. Springer, Singapore, http://dx.doi.org/10.1007/978-981-15-1842-3_3
• 9. Dondo, R., and Cerdá, J. (2007). A cluster-based optimization approach for the multi-depot heterogeneous fleet vehicle routing problem with time windows. European Journal of Operational Research, Vol. 176(3), 1478-1507. http://dx.doi.org/10.1016/j.ejor.2004.07.077
• 10. Žunić, E., Đonko, D., and Buza., E. (2020). An adaptive data-driven approach to solve real-world vehicle routing problems in logistics. Complexity. http://dx.doi.org/10.1155/2020/7386701
• 11. Žunić, E., Hindija, H., Beširević, A., Hodžić, K., and Delalić, S. (2018). Improving Performance of Vehicle Routing Algorithms using GPS Data. 14th Symposium on Neural Networks and Applications (NEUREL), Belgrade, Serbia, 2018, 1-4. http://dx.doi.org/10.1109/NEUREL.2018.8586982
• 12. Žunić, E., Djedović, A., and Đonko, D. (2017). Cluster-based analysis and time-series prediction model for reducing the number of traffic accidents. International Symposium ELMAR, 25-29. http://dx.doi.org/10.23919/ELMAR.2017.8124427
• 13. Žunić, E., and Đonko, D. (2019). Parameter setting problem in the case of practical vehicle routing problems with realistic constraints. 2019 Federated Conference on Computer Science and Information Systems (FedCSIS), 755-759. http://dx.doi.org/10.15439/2019F194
• 14. Žunić, E., Delalić, S., Hodžić, K., Beširević, A., and Hindija, H. (2018). Smart warehouse management system concept with implementation. 14th Symposium on Neural Networks and Applications (NEUREL), 1-5. http://dx.doi.org/10.1109/NEUREL.2018.8587004
• 15. Zunic, E., Besirevic, A., Delalic, S., Hodzic, K., and Hasic, H. (2018). A generic approach for order picking optimization process in different warehouse layouts. in 2018 41st International Convention on Information and Communication Technology, Electronics and Microelectronics (MIPRO). http://dx.doi.org/10.23919/MIPRO.2018.8400183
• 16. Žunić, E., Djedović, A., and Đonko, D. (2016). Application of Big Data and text mining methods and technologies in modern business analyzing social networks data about traffic tracking. XI International Symposium on Telecommunications (BIHTEL), 1-6. http://dx.doi.org/10.1109/BIHTEL.2016.7775717
• 17. Žunić, E. (Emir). (2018). Real-world VRP benchmark data with realistic non-standard constraints - input data and results. 4TU.Centre for Research Data. Dataset. https://doi.org/10.4121/uuid:598b19d1-df64-493e-991a-d8d655dac3ea

Uwagi

1. Track 4: Information Systems and Technology

2. Technical Session: 26th Conference on Knowledge Acquisition and Management

3. Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).