Tackling uncertainty in vehicle routing: Advancements in time windows and stochastic demands optimization
DOI:
https://doi.org/10.35335/emod.v16i2.60Keywords:
Optimization, Stochastic Demands, Uncertainty, Time Windows, Vehicle RoutingAbstract
This research focuses ons addresses vehicle routing uncertainty in time windows and stochastic needs. The project intends to increase vehicle routing efficiency, adaptability, and robustness by developing optimization approaches. Traffic congestion, unanticipated events, and changing client expectations can greatly impact truck routing solutions. Traditional methods presume fixed time frames and deterministic needs, resulting in suboptimal or infeasible paths. This paper presents a mathematical model that includes time window uncertainty and stochastic needs into the vehicle routing issue to address these restrictions. The formulation incorporates arrival times, delivery amounts, and route decisions to minimize transportation costs and ensure timely deliveries and resource efficiency. Advanced algorithms and solvers tackle the optimization challenge. Integer programming, flow conservation constraints, and temporal window constraints are used to identify optimal or near-optimal solutions to uncertainty and dynamic changes. Numerical examples and case studies demonstrate the approach's efficacy. Numerical examples demonstrate the mathematical formulation, while the case study shows the practical consequences and benefits for a dynamic delivery service organization. The research shows that the proposed approach can handle temporal window uncertainties and stochastic demands. These innovations can optimize vehicle routing, reduce transportation costs, boost customer happiness, and increase resource utilization. Addressing time window uncertainty and stochastic demands advances vehicle routing. The proposed approach helps logistics and transportation industries overcome dynamic and uncertain operating environments, boosting operational efficiency and competitiveness.
References
Afzalan, M., & Jazizadeh, F. (2019). Residential loads flexibility potential for demand response using energy consumption patterns and user segments. Applied Energy, 254, 113693.
Bashiri, M., Nikzad, E., Eberhard, A., Hearne, J., & Oliveira, F. (2021). A two stage stochastic programming for asset protection routing and a solution algorithm based on the Progressive Hedging algorithm. Omega, 104, 102480.
Basso, R., Kulcsár, B., Sanchez-Diaz, I., & Qu, X. (2022). Dynamic stochastic electric vehicle routing with safe reinforcement learning. Transportation Research Part E: Logistics and Transportation Review, 157, 102496.
Bernardo, M., Du, B., & Pannek, J. (2021). A simulation-based solution approach for the robust capacitated vehicle routing problem with uncertain demands. Transportation Letters, 13(9), 664–673.
Bernardo, M., & Pannek, J. (2018). Robust solution approach for the dynamic and stochastic vehicle routing problem. Journal of Advanced Transportation, 2018.
Bocewicz, G., Banaszak, Z., Rudnik, K., Witczak, M., Smutnicki, C., & Wikarek, J. (2020). Milk-run routing and scheduling subject to fuzzy pickup and delivery time constraints: An ordered fuzzy numbers approach. 2020 IEEE International Conference on Fuzzy Systems (FUZZ-IEEE), 1–10.
Brandstätter, G., Kahr, M., & Leitner, M. (2017). Determining optimal locations for charging stations of electric car-sharing systems under stochastic demand. Transportation Research Part B: Methodological, 104, 17–35.
Campelo, P., Neves-Moreira, F., Amorim, P., & Almada-Lobo, B. (2019). Consistent vehicle routing problem with service level agreements: A case study in the pharmaceutical distribution sector. European Journal of Operational Research, 273(1), 131–145.
Cattaruzza, D., Absi, N., & Feillet, D. (2016). The multi-trip vehicle routing problem with time windows and release dates. Transportation Science, 50(2), 676–693.
Chang, T.-S., Wan, Y., & Ooi, W. T. (2009). A stochastic dynamic traveling salesman problem with hard time windows. European Journal of Operational Research, 198(3), 748–759.
Chen, J., & Shi, J. (2019). A multi-compartment vehicle routing problem with time windows for urban distribution–A comparison study on particle swarm optimization algorithms. Computers & Industrial Engineering, 133, 95–106.
D’Ariano, A. (2008). Improving real-time train dispatching: models, algorithms and applications.
Dimiduk, D. M., Holm, E. A., & Niezgoda, S. R. (2018). Perspectives on the impact of machine learning, deep learning, and artificial intelligence on materials, processes, and structures engineering. Integrating Materials and Manufacturing Innovation, 7, 157–172.
Errico, F., Desaulniers, G., Gendreau, M., Rei, W., & Rousseau, L.-M. (2018). The vehicle routing problem with hard time windows and stochastic service times. EURO Journal on Transportation and Logistics, 7, 223–251.
Escribano Macias, J., Goldbeck, N., Hsu, P.-Y., Angeloudis, P., & Ochieng, W. (2020). Endogenous stochastic optimisation for relief distribution assisted with unmanned aerial vehicles. OR Spectrum, 42, 1089–1125.
Ezugwu, A. E., Olusanya, M. O., & Govender, P. (2019). Mathematical model formulation and hybrid metaheuristic optimization approach for near-optimal blood assignment in a blood bank system. Expert Systems with Applications, 137, 74–99.
Fattahi, M., Govindan, K., & Keyvanshokooh, E. (2017). Responsive and resilient supply chain network design under operational and disruption risks with delivery lead-time sensitive customers. Transportation Research Part E: Logistics and Transportation Review, 101, 176–200.
Fazayeli, S., Eydi, A., & Kamalabadi, I. N. (2018). Location-routing problem in multimodal transportation network with time windows and fuzzy demands: Presenting a two-part genetic algorithm. Computers & Industrial Engineering, 119, 233–246.
Giaglis, G. M., Minis, I., Tatarakis, A., & Zeimpekis, V. (2004). Minimizing logistics risk through real‐time vehicle routing and mobile technologies: Research to date and future trends. International Journal of Physical Distribution & Logistics Management, 34(9), 749–764.
Gong, J., Garcia, D. J., & You, F. (2016). Unraveling optimal biomass processing routes from bioconversion product and process networks under uncertainty: an adaptive robust optimization approach. ACS Sustainable Chemistry & Engineering, 4(6), 3160–3173.
Govindan, K., Fattahi, M., & Keyvanshokooh, E. (2017). Supply chain network design under uncertainty: A comprehensive review and future research directions. European Journal of Operational Research, 263(1), 108–141.
Gu, Z., & Saberi, M. (2021). Simulation-based optimization of toll pricing in large-scale urban networks using the network fundamental diagram: A cross-comparison of methods. Transportation Research Part C: Emerging Technologies, 122, 102894.
Haghani, A., & Jung, S. (2005). A dynamic vehicle routing problem with time-dependent travel times. Computers & Operations Research, 32(11), 2959–2986.
Helo, P., & Hao, Y. (2022). Artificial intelligence in operations management and supply chain management: An exploratory case study. Production Planning & Control, 33(16), 1573–1590.
Hu, C., Lu, J., Liu, X., & Zhang, G. (2018). Robust vehicle routing problem with hard time windows under demand and travel time uncertainty. Computers & Operations Research, 94, 139–153.
Ide, J., & Schöbel, A. (2016). Robustness for uncertain multi-objective optimization: a survey and analysis of different concepts. OR Spectrum, 38(1), 235–271.
Irawan, C. A., Eskandarpour, M., Ouelhadj, D., & Jones, D. (2021). Simulation-based optimisation for stochastic maintenance routing in an offshore wind farm. European Journal of Operational Research, 289(3), 912–926.
James, J. Q., Yu, W., & Gu, J. (2019). Online vehicle routing with neural combinatorial optimization and deep reinforcement learning. IEEE Transactions on Intelligent Transportation Systems, 20(10), 3806–3817.
Juan, A. A., Faulin, J., Grasman, S. E., Rabe, M., & Figueira, G. (2015). A review of simheuristics: Extending metaheuristics to deal with stochastic combinatorial optimization problems. Operations Research Perspectives, 2, 62–72.
Keyvanshokooh, E., Ryan, S. M., & Kabir, E. (2016). Hybrid robust and stochastic optimization for closed-loop supply chain network design using accelerated Benders decomposition. European Journal of Operational Research, 249(1), 76–92.
Kontogiannis, T., & Malakis, S. (2013). Strategies in controlling, coordinating and adapting performance in air traffic control: modelling ‘loss of control’events. Cognition, Technology & Work, 15, 153–169.
Ksciuk, J., Kuhlemann, S., Tierney, K., & Koberstein, A. (2022). Uncertainty in Maritime Ship Routing and Scheduling: A Literature Review. European Journal of Operational Research.
Laña, I., Sanchez-Medina, J. J., Vlahogianni, E. I., & Del Ser, J. (2021). From data to actions in intelligent transportation systems: A prescription of functional requirements for model actionability. Sensors, 21(4), 1121.
Lidberg, S., Aslam, T., Pehrsson, L., & Ng, A. H. C. (2020). Optimizing real-world factory flows using aggregated discrete event simulation modelling: Creating decision-support through simulation-based optimization and knowledge-extraction. Flexible Services and Manufacturing Journal, 32(4), 888–912.
Liu, R., Tao, Y., Hu, Q., & Xie, X. (2017). Simulation-based optimisation approach for the stochastic two-echelon logistics problem. International Journal of Production Research, 55(1), 187–201.
Liu, Y. (2019). An optimization-driven dynamic vehicle routing algorithm for on-demand meal delivery using drones. Computers & Operations Research, 111, 1–20.
Manju, A., Kalaiselvi, K., Dhananjayan, V., Palanivel, M., Banupriya, G. S., Vidhya, M. H., Panjakumar, K., & Ravichandran, B. (2018). Spatio-seasonal variation in ambient air pollutants and influence of meteorological factors in Coimbatore, Southern India. Air Quality, Atmosphere & Health, 11, 1179–1189.
Mazzuco, D. E., Oliveira, D. L., & Frazzon, E. M. (2017). State of the art in simulation-based optimization approaches for vehicle routing problems along manufacturing supply chains. 24th International Conference on Production Research (ICPR 2017), 574–579.
Quang Tran, D., & Bae, S.-H. (2020). Proximal policy optimization through a deep reinforcement learning framework for multiple autonomous vehicles at a non-signalized intersection. Applied Sciences, 10(16), 5722.
Ramachandranpillai, R., & Arock, M. (2021). A solution to dynamic green vehicle routing problems with time windows using spiking neural P systems with modified rules and learning. The Journal of Supercomputing, 1–32.
Rincon-Garcia, N., Waterson, B. J., & Cherrett, T. J. (2018). Requirements from vehicle routing software: Perspectives from literature, developers and the freight industry. Transport Reviews, 38(1), 117–138.
Rougé, C., & Tilmant, A. (2016). Using stochastic dual dynamic programming in problems with multiple near‐optimal solutions. Water Resources Research, 52(5), 4151–4163.
Saint-Guillain, M., Paquay, C., & Limbourg, S. (2021). Time-dependent stochastic vehicle routing problem with random requests: Application to online police patrol management in Brussels. European Journal of Operational Research, 292(3), 869–885.
Salcedo-Sanz, S., García-Herrera, R., Camacho-Gómez, C., Alexandre, E., Carro-Calvo, L., & Jaume-Santero, F. (2019). Near-optimal selection of representative measuring points for robust temperature field reconstruction with the CRO-SL and analogue methods. Global and Planetary Change, 178, 15–34.
Shakibayifar, M., Sheikholeslami, A., & Corman, F. (2018). A simulation-based optimization approach to reschedule train traffic in uncertain conditions during disruptions. Scientia Iranica, 25(2), 646–662.
Shi, Y., Zhou, Y., Ye, W., & Zhao, Q. Q. (2020). A relative robust optimization for a vehicle routing problem with time-window and synchronized visits considering greenhouse gas emissions. Journal of Cleaner Production, 275, 124112.
Soeffker, N., Ulmer, M. W., & Mattfeld, D. C. (2022). Stochastic dynamic vehicle routing in the light of prescriptive analytics: A review. European Journal of Operational Research, 298(3), 801–820.
Su, Y., & Fan, Q.-M. (2019). The green vehicle routing problem from a smart logistics perspective. IEEE Access, 8, 839–846.
Tordecilla, R. D., Juan, A. A., Montoya-Torres, J. R., Quintero-Araujo, C. L., & Panadero, J. (2021). Simulation-optimization methods for designing and assessing resilient supply chain networks under uncertainty scenarios: A review. Simulation Modelling Practice and Theory, 106, 102166.
van Lent, G. P. T. (2018). Using column generation for the time dependent vehicle routing problem with soft time windows and stochastic travel times.
Vidal, T., Crainic, T. G., Gendreau, M., & Prins, C. (2015). Time-window relaxations in vehicle routing heuristics. Journal of Heuristics, 21, 329–358.
Wang, A., Subramanyam, A., & Gounaris, C. E. (2021). Robust vehicle routing under uncertainty via branch-price-and-cut. Optimization and Engineering, 1–54.
Wang, Y., Yuan, Y., Guan, X., Xu, M., Wang, L., Wang, H., & Liu, Y. (2020). Collaborative two-echelon multicenter vehicle routing optimization based on state–space–time network representation. Journal of Cleaner Production, 258, 120590.
Wang, Y., Zhang, J., Assogba, K., Liu, Y., Xu, M., & Wang, Y. (2018). Collaboration and transportation resource sharing in multiple centers vehicle routing optimization with delivery and pickup. Knowledge-Based Systems, 160, 296–310.
Wilbur, M., Kadir, S. U., Kim, Y., Pettet, G., Mukhopadhyay, A., Pugliese, P., Samaranayake, S., Laszka, A., & Dubey, A. (2022). An online approach to solve the dynamic vehicle routing problem with stochastic trip requests for paratransit services. 2022 ACM/IEEE 13th International Conference on Cyber-Physical Systems (ICCPS), 147–158.
Yang, T., Asanjan, A. A., Faridzad, M., Hayatbini, N., Gao, X., & Sorooshian, S. (2017). An enhanced artificial neural network with a shuffled complex evolutionary global optimization with principal component analysis. Information Sciences, 418, 302–316.
Yin, F., & Zhao, Y. (2021). Optimizing vehicle routing via Stackelberg game framework and distributionally robust equilibrium optimization method. Information Sciences, 557, 84–107.
Yuan, B., Liu, R., & Jiang, Z. (2015). A branch-and-price algorithm for the home health care scheduling and routing problem with stochastic service times and skill requirements. International Journal of Production Research, 53(24), 7450–7464.
Zhang, H., Zhang, Q., Ma, L., Zhang, Z., & Liu, Y. (2019). A hybrid ant colony optimization algorithm for a multi-objective vehicle routing problem with flexible time windows. Information Sciences, 490, 166–190.
Zhang, S., Ohlmann, J. W., & Thomas, B. W. (2014). A priori orienteering with time windows and stochastic wait times at customers. European Journal of Operational Research, 239(1), 70–79.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2022 Fristi Riandari, Demita Sihotang, Hamed Huckle Schubert
This work is licensed under a Creative Commons Attribution 4.0 International License.
