Optimal vehicle route schedules in picking up and delivering cargo containers considering time windows in logistics distribution networks: A case study

• Autorzy: Le Thi Diem Chau , Nguyen Duy Duc , Oláh Judit , Pakurár Miklós

Identyfikatory

DOI

10.30657/pea.2020.26.31

• Języki publikacji: EN

Abstrakty

EN

This study describes a pickup and delivery vehicle routing problem, considering time windows in reality. The problem of tractor truck routes is formulated by a mixed integer programming model. Besides this, three algorithms - a guided local search, a tabu search, and simulated annealing - are proposed as solutions. The aims of our study are to optimize the number of internal tractor trucks used, and create optimal routes in order to minimize total logistics costs, including the fixed and variable costs of an internal vehicle group and the renting cost of external vehicles. Besides, our study also evaluates both the quality of solutions and the time to find optimal solutions to select the best suitable algorithm for the real problem mentioned above. A novel mathematical model is formulated by OR tools for Python. Compared to the current solution, our results reduced total costs by 18%, increased the proportion of orders completed by internal vehicles (84%), and the proportion of orders delivered on time (100%). Our study provides a mathematical model with time constraints and large job volumes for a complex distribution network in reality. The proposed mathematical model provides effective solutions for making decisions at logistics companies. Furthermore, our study emphasizes that simulated annealing is a more suitable algorithm than the two others for this vehicle routing problem.

Słowa kluczowe

EN

vehicle routing problem; logistics distribution network; time window; guided local search; tabu search; simulated annealing

PL

problem trasowania pojazdów; sieć dystrybucji; okno czasowe; wyszukiwanie lokalne; symulowane wyżarzanie

• Wydawca: Oficyna Wydawnicza Stowarzyszenia Menedżerów Jakości i Produkcji
• Czasopismo: Production Engineering Archives
• Rocznik: 2020
• Tom: Vol. 26, Iss. 4
• Strony: 174--184
• Opis fizyczny: Bibliogr. 41 poz., rys., tab.

Twórcy

autor

Le Thi Diem Chau

• Faculty of Economics and Business, Institute of Applied Informatics and Logistics, University of Debrecen, 4028 Debrecen, Hungary
• Ho Chi Minh City University of Technology-VNU, Ho Chi Minh City, Vietnam

autor

Nguyen Duy Duc

• School of Management Technology, Sirindhorn International Institute of Technology, Thammasat University, Pathum Thani 12120, Thailand

autor

Oláh Judit

• Faculty of Economics and Business, Institute of Applied Informatics and Logistics, University of Debrecen, 4028 Debrecen, Hungary
• TRADE Research Entity, North-West University, Vanderbijlpark 1900, South Africa

autor

Pakurár Miklós

• Faculty of Economics and Business, Institute of Applied Informatics and Logistics, University of Debrecen, 4028 Debrecen, Hungary

Bibliografia

• 1.An, H., Li, W. 2011. Synthetically improved genetic algorithm on the traveling salesman problem in material transportation, In Proceedings of 2011 International Conference on Electronic & Mechanical Engineering and Information Technology, 7, IEEE, 3368-3371.
• 2.Afifi, S., Dang, D.C., Moukrim, A., 2016. Heuristic solutions for the vehicle routing problem with time windows and synchronized visits, Optimization Letters, 10(3), 511-525.
• 3.Aggarwal, D., Kumar, V., 2019. Mixed integer programming for vehicle routing problem with time windows, International Journal of Intelligent Systems Technologies and Applications, 18(1-2), 4-19.
• 4.Alsheddy, A., 2011. Empowerment scheduling: a multi-objective optimization approach using guided local search, Doctoral dissertation, University of Essex.
• 5.Archetti, C., Speranza, M.G., Hertz, A., 2006. A tabu search algorithm for the split delivery vehicle routing problem, Transportation science, 40(1), 64-73.
• 6.Barbarosoglu, G., Ozgur, D., 1999. A tabu search algorithm for the vehicle routing problem, Computers Operations Research, 26(3), 255-270.
• 7.Bent, R., & Van Hentenryck, P. (2006). A two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows. Computers & Operations Research, 33(4), 875-893.
• 8.Birim, Ş., 2016. Vehicle routing problem with cross docking: A simulated annealing approach, Procedia-Social and Behavioral Sciences, 235(Supplement C), 149-158.
• 9.Busetti, F., 2003. Simulated annealing overview, World Wide Web URL, www. geocities. com/francorbusetti/saweb. pdf, 4.
• 10.Cao, W., Yang, W., 2017. A survey of vehicle routing problem, In MATEC Web of Conferences, 100, EDP Sciences,01006.
• 11.Connor, A. M., Shea, K., 2000. A comparison of semi-deterministic and stochastic search techniques, In Evolutionary Design and Manufacture, Springer, London, 287-298.
• 12.Chen, Q., Li, K., & Liu, Z. (2014). Model and algorithm for an unpaired pickup and delivery vehicle routing problem with split loads. Transportation Research Part E: Logistics and Transportation Review, 69, 218-235.
• 13.Dantzig, G. B., Ramser, J. H., 1959. The truck dispatching problem, Management science, 6(1), 80-91.
• 14.Dongyang, X., Kunpeng, L., Jiehui, Y., Ligang, C., 2020. A multicommodity unpaired pickup and delivery vehicle routing problem with split loads and unloads, Industrial Management & Data Systems.
• 15.Gan, X., Wang, Y., Li, S., Niu, B., 2012. Vehicle routing problem with time windows and simultaneous delivery and pick-up service based on MCPSO, Mathematical Problems in Engineering, 2012.
• 16.Gunawan, A., Widjaja, A. T., Gan, B., Yu, V. F., Jodiawan, P., 2020. Vehicle routing problem for multi-product cross-docking.
• 17.Huang, M., Yang, J., Ma, T., Li, X., Wang, T., 2017. The modeling of milkrun vehicle routing problem based on improved CW algorithm that joined time window, Transp. Res. Procedia, 25, 716-728.
• 18.Rodrigue J.P., 2020, New York: Routledge, ISBN 978-0-367-36463-2, 456.
• 19.Kantawong, K., Pravesjit, S., 2020. An Enhanced ABC algorithm to Solve the Vehicle Routing Problem with Time Windows, ECTI Transactions on Computer and Information Technology (ECTI-CIT), 14(1), 46-52.
• 20.Kilby, P., Prosser, P., Shaw, P., 1999. Guided local search for the vehicle routing problem with time windows, In Meta-heuristics, Springer, Boston, MA, 473-486.
• 21.Kuo, Y., 2010. Using simulated annealing to minimize fuel consumption for the time-dependent vehicle routing problem, Computers Industrial Engineering, 59(1), 157-165.
• 22.Masmoudi, M., Mellouli, R. 2014. MILP for synchronized-mTSPTW: application to home healthCare scheduling, In 2014 International Conference on Control, Decision and Information Technologies (CoDIT), IEEE, 297- 302.
• 23.Mohammed, M.A., Abd Ghani, M.K., Hamed, R.I., Mostafa, S.A., Ahmad, M.S., Ibrahim, D.A., 2017. Solving vehicle routing problem by using improved genetic algorithm for optimal solution, Journal of computational science, 21, 255-262.
• 24.Londoño, J.C., Tordecilla, R.D., Martins, L.D.C., Juan, A.A., 2020. A biasedrandomized iterated local search for the vehicle routing problem with optional backhauls, TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, 1-30.
• 25.Pérez-Rodríguez, R., Hernández-Aguirre, A., 2019. A hybrid estimation of distribution algorithm for the vehicle routing problem with time windows, Computers & Industrial Engineering, 130, 75-96.
• 26.Qi, C., Hu, L., 2020. Optimization of vehicle routing problem for emergency cold chain logistics based on minimum loss, Physical Communication, 101085.
• 27.Ruiz, E., Soto-Mendoza, V., Barbosa, A.E.R., Reyes, R., 2019. Solving the open vehicle routing problem with capacity and distance constraints with a biased random key genetic algorithm, Computers & Industrial Engineering, 133, 207-219.
• 28.Setamanit, S.-O. 2019. Improving transportation contract management using simulation, Polish Journal of Management Studies, 20 (2), 466-477.
• 29.Shuai, Y., Yunfeng, S., Kai, Z., 2019. An effective method for solving multiple travelling salesman problem based on NSGA-II, Systems Science & Control Engineering, 7(2), 108-116.
• 30.Straka, M., Rosová, A., Lenort, R., Besta, P., & Šaderová, J. 2018. Principles of computer simulation design for the needs of improvement of the raw materials combined transport system. Acta Montanistica Slovaca, 23(2), 163-174.
• 31.Tasar, B., Türsel Eliiyi, D., Kandiller, L., 2019. Vehicle Routing with Compartments Under Product Incompatibility Constraints, Promet-Traffic&Transportation, 31(1), 25-36.
• 32.Toth, P., & Vigo, D. (Eds.). (2014). Vehicle routing: problems, methods, and applications. Society for Industrial and Applied Mathematics.
• 33.Van Brummelen, G., 2012. Heavenly mathematics: The forgotten art of spherical trigonometry, Princeton University Press.
• 34.Vincent, F.Y., Jewpanya, P., Redi, A.P., 2016. Open vehicle routing problem with cross-docking, Computers & Industrial Engineering, 94, 6-17.
• 35.Voudouris, C., Tsang, E. P., 2003. Guided local search, In Handbook of metaheuristics, Springer, Boston, MA, 185-218.
• 36.Spliet, R., Desaulniers, G., 2015. The discrete time window assignment vehicle routing problem, European Journal of Operational Research, 244(2), 379-391.
• 37.Wang, C., Mu, D., Zhao, F., Sutherland, J. W., 2015. A parallel simulated annealing method for the vehicle routing problem with simultaneous pickup–delivery and time windows, Computers & Industrial Engineering, 83, 111-122.
• 38.Wei, L., Zhang, Z., Zhang, D., Leung, S.C., 2018. A simulated annealing algorithm for the capacitated vehicle routing problem with two-dimensional loading constraints, European Journal of Operational Research, 265(3), 843-859.
• 39.Xu, X., Yuan, H., Liptrott, M., & Trovati, M. (2018). Two phase heuristic algorithm for the multiple-travelling salesman problem. Soft Computing, 22(19), 6567-6581.
• 40.Zhang, D., Cai, S., Ye, F., Si, Y. W., Nguyen, T.T., 2017. A hybrid algorithm for a vehicle routing problem with realistic constraints, Information Sciences, 394, 167-182.
• 41.Zhu, L., Hu, D., 2019. Study on the vehicle routing problem considering congestion and emission factors, International Journal of Production Research, 57(19), 6115-6129.

Uwagi

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