Machine learning algorithms for the problem of optimizing the distribution of parcels in time-dependent networks: the case study

Zbigniew Tarapata; Wojciech Kulas; Ryszard Antkiewicz

doi:10.5604/01.3001.0015.8269

Authors

Zbigniew Tarapata Military University of Technology, Faculty of Cybernetics, Warsaw Author https://orcid.org/0000-0001-8143-7869
Wojciech Kulas Military University of Technology, Faculty of Cybernetics, Warsaw Author https://orcid.org/0000-0001-6749-6563
Ryszard Antkiewicz Military University of Technology, Faculty of Cybernetics, Warsaw Author https://orcid.org/0000-0003-1489-4407

DOI:

https://doi.org/10.5604/01.3001.0015.8269

Keywords:

parcel distribution, optimization, machine learning algorithms, time-dependent networks

Abstract

In the paper we present machine learning algorithms for the problem of optimizing the distribution of parcels in stochastic time-dependent networks, which have been built as a part of some Distribution Optimization System. The problem solved was a modified VRPTW (Vehicle Routing Problem with Time Windows) with many warehouses, a heterogeneous fleet, travel times depending on the time of departure (stochastic time-dependent network) and an extensive cost function as an optimization criterion. To solve the problem a modified simulated annealing (SATM) algorithm has been proposed. The paper presents the results of the algorithm learning process: the calibration of input parameters and the study of the impact of parameters on the quality of the solution (calculation time, transport cost function value) depending on the type of input data. The idea is to divide the input data into classes according to a proposed classification rule and to propose several strategies for selecting the optimal set of calibration parameters. These strategies consist in solving some multi-criteria optimization tasks in which four criterion functions are used: the length of the designated routes, the computation time, the number of epochs used in the algorithm, the number of designated routes. The subproblem was building a network model of travel times that is used in constructed SATM algorithm to determine the travel time between recipients, depending on the time of departure from the start location. An attempt has been made to verify the research hypothesis that the time between two points can be estimated with sufficient accuracy depending on their geographical location and the time of departure (without reference to the micro-scale, i.e. the detailed structure of the road network). The research was conducted on two types of data for Warsaw: from transport companies and one of the Internet traffic data providers. Learning the network model of travel times has produced very promising results, which will be described in the paper.

References

Afifi, S., Dang, D-C., Moukrim, A., (2013). A Simulated Annealing Algorithm for the Vehicle Routing Problem with Time Windows and Synchronization Constraints. 7th International Conference, Learning and Intelligent Optimization (LION 7), Catania, Italy, 259-265.

Bertsimas, D., Delarue, A., Jaillet, P., Martin, S., (2019). Travel Time Estimation in the Age of Big Data, Operations Research, vol.67 (2), 498-515.

Bräysy, O., Gendreau, M., (2005). Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms, Transportation Science, 39(1), 104–118.

Chen, B.Y., Li, Q., Lam, W., Shaw, S-L., Yan, K., (2014). Map-matching algorithm for large-scale low-frequency floating car data, International Journal of Geographical Information Science, 28(1), 22-38.

Chowdhury, M., Apon, A., Dey, K., (2017). Data Analytics for Intelligent Transportation Systems, Elsevier, Amsterdam.

Cordeau, J.F., Desaulniers, G., Desrosiers, J., Solomon, M. M., Soumis, F., (2002). The VRP with time windows, in: P. Toth D. Vigo (eds.), The Vehicle Routing Problem, SIAM Monographs on Discrete Mathematics and Applications, SIAM, 157-194.

Czech, Z., Czarnas, P., (2002). Parallel simulated annealing for the vehicle routing problem with time windows, in Proceedings 10th Euromicro Workshop on Parallel, Distributed and Network-based Processing, Canary Islands, Spain.

Development and research of new methods and techniques for optimization of goods and services distribution processes - selected research problems and results obtained during the project (in Polish: Opracowanie i badanie własności nowych metod i technik optymalizacji procesów dystrybucji towarów i usług - wybrane problemy badawcze i wyniki uzyskane w trakcie projektu), Technical Report of the project POIR.01.01.01-00-1146/17, Track-Mate, Warsaw, 2020 (in Polish).

Fulton, R., (2015). Estimating Delivery Times. A Case Study In Practical Machine Learning, https://blog.postmates.com/estimating-delivery-times-a-case-study-in-practicalmachine-learning-e70f677e736c.

GoogleMaps API Website (2021): https://developers.google.com/maps/documentation/directions/, last accessed 2021/05/10.

He, P., Li, J., (2018). Vehicle routing problem with partly simultaneous pickup and delivery for the cluster of small and medium enterprises, Archives of Transport, 45(1), 35-42.

Juhász, M., Mátrai, T., Koren, C., (2017). Forecasting travel time reliability in urban road transport, Archives of Transport, 43 (3), 53-67.

Karurukan, V.I., Nugraha, I., Kumiawan, N., (2018). The Estimation Model of Travel Time Between Point of Interest for Tourist Travel Recommendations with Regression Analysis, in 2018 International Conference on Information Technology Systems and Innovation (ICITSI), DOI:10.1109/ICITSI.2018.8696070.

Kim, S., Yu, H., Yeo, H., (2021). A Study on Travel Time Estimation of Diverging Traffic Stream on Highways Based on Timestamp Data, Journal of Advanced Transportation, 2021, 1-13.

Kulas, W., Tarapata, Z., (2021). Simulated Annealing Algorithm for Solving Modified VRPTW Problem in Time-Dependent Net works: A Case Study, Proceedings of the 37th International Business Information Manage ment Association Conference (IBIMA), 30-31 May, Cordoba, Spain, ISBN: 978-0-99985516-4, ISSN: 2767-9640, 7351-7360.

Lan, W., Xu, Y., Zhao, B., (2019). Travel Time Estimation without Road Networks: An Urban Morphological Layout Representation Approach, IJCAI, 2019, 1772-1778.

Shi, Ch., Chen, B.Y., Li, Q., (2017). Estimation of Travel Time Distributions in Urban Road Networks Using Low-Frequency Floating Car Data, ISPRS International Journal of Geo-In-formation, 6, 253.

Solomon, M. M., (1987). Algorithms for the Vehicle Routing and Scheduling with Time Windows Constraints, Operating Research, 35(2), 254-265.

Tan, K.C., Lee, L.H., Zhu, Q. L., Ou, K., (2001). Heuristic methods for vehicle routing problem with time windows, Artificial Intelligence in Engineering, 15, 281-295.

Tarapata, Z., Nowicki, T., Antkiewicz, R., Dudziński, J., Janik, K. (2020). Data-Driven Machine Learning System for Optimization of Processes Supporting the Distribution of Goods and Services – a case study, Procedia Manufacturing, 44C, 60-67.

Tarapata, Z., Antkiewicz, R. (2021). Selected Distribution Network Optimisation Problems and Solving Methods, Proceedings of the 37th International Business Information Management Association Conference (IBIMA), 30-31 May, Cordoba, Spain, ISBN: 978-0-9998551-6-4, ISSN: 2767-9640, 4165-4173.

Vidal, T., Marinelli, R., Pham, T.A., Ha, M.H., (2020). Arc Routing with Time-Dependent Travel Times and Paths, Technical Report, PUC-Rio, 29 April.

VRPTW benchmarks files: https://www.sintef.no/projectweb/top/vrptw/, last accessed 2021/05/10.

Wieczorek, B., (2011). Parallel Independent Simulated Annealing Searches to Solve the VRPTW. In: Czachórski T., Kozielski S., Stańczyk U. (eds) Man-Machine Interactions 2. Advances in Intelligent and Soft Computing, 103, Springer, Berlin, Heidelberg.

Woch, M., Łebkowski, P., (2009). Sequential Simulated Annealing for the Vehicle Routing Problem with Time Windows, Decision Making in Manufacturing and Services, 3(1/2), 87-100.