Algorithmic innovations and robust solutions for time windows and stochastic demands in vehicle routing
DOI:
https://doi.org/10.35335/emod.v16i2.59Keywords:
Algorithmic Innovations, Robust Solutions, Stochastic Demands, Time Windows, Vehicle RoutingAbstract
This research addresses time windows and stochastic demands in vehicle routing using algorithmic improvements and robust solutions. Optimizing delivery operations requires managing routes and schedules while considering demand uncertainty and severe time frame limits. The research starts with a mathematical formulation that includes consumer locations, stochastic demands, time windows, and costs. Algorithms are added to handle uncertain requests and severe time window restrictions. Demand forecasting, route optimization, and uncertainty-based decision-making are used in the suggested strategy. The proposed routing method models stochastic requests using historical demand data and probability distributions. To create effective delivery plans, it analyzes client visit sequencing, vehicle capabilities, and time window limits. Numerical examples and case studies validate the proposed approach. Numerical examples show how the mathematical theory and algorithm address vehicle routing issues with time windows and stochastic demands. Case studies demonstrate how algorithmic advances and robust solutions benefit logistics firms in real-world circumstances. The proposed approach improves efficiency, cost savings, and customer satisfaction. Optimized routes and timetables help handle uncertain demand patterns, resource use, and time slots. Discussing the solutions' scalability and adaptability sheds light on their application and future research. This research provides algorithmic breakthroughs and robust solutions for vehicle routing time windows and stochastic needs. Logistics companies can increase operational efficiency and customer service with the findings. The proposed method optimizes delivery operations under uncertainty and time restrictions, helping logistics organizations compete in a changing business environment.
References
Akbarpour, N., Salehi-Amiri, A., Hajiaghaei-Keshteli, M., & Oliva, D. (2021). An innovative waste management system in a smart city under stochastic optimization using vehicle routing problem. Soft Computing, 25, 6707–6727.
Alamatsaz, K., Ahmadi, A., & Mirzapour Al-e-hashem, S. M. J. (2022). A multiobjective model for the green capacitated location-routing problem considering drivers’ satisfaction and time window with uncertain demand. Environmental Science and Pollution Research, 29(4), 5052–5071.
Bac, U., & Erdem, M. (2021). Optimization of electric vehicle recharge schedule and routing problem with time windows and partial recharge: A comparative study for an urban logistics fleet. Sustainable Cities and Society, 70, 102883.
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.
Baykasoğlu, A., & Ozsoydan, F. B. (2018). Dynamic scheduling of parallel heat treatment furnaces: A case study at a manufacturing system. Journal of Manufacturing Systems, 46, 152–162.
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.
Bochtis, D. D., & Sørensen, C. G. (2009). The vehicle routing problem in field logistics part I. Biosystems Engineering, 104(4), 447–457.
Boujlil, M., & Elhaq, S. L. (2020). The vehicle routing problem with Time Window and Stochastic Demands (VRPTW-SD). 2020 IEEE 13th International Colloquium of Logistics and Supply Chain Management (LOGISTIQUA), 1–6.
Bousdekis, A., Lepenioti, K., Apostolou, D., & Mentzas, G. (2021). A review of data-driven decision-making methods for industry 4.0 maintenance applications. Electronics, 10(7), 828.
Bozorgi-Amiri, A., & Khorsi, M. (2016). A dynamic multi-objective location–routing model for relief logistic planning under uncertainty on demand, travel time, and cost parameters. The International Journal of Advanced Manufacturing Technology, 85, 1633–1648.
Cacchiani, V., Qi, J., & Yang, L. (2020). Robust optimization models for integrated train stop planning and timetabling with passenger demand uncertainty. Transportation Research Part B: Methodological, 136, 1–29.
Calvet, L., Armas, J. de, Masip, D., & Juan, A. A. (2017). Learnheuristics: hybridizing metaheuristics with machine learning for optimization with dynamic inputs. Open Mathematics, 15(1), 261–280.
Calvet, L., Wang, D., Juan, A., & Bové, L. (2019). Solving the multidepot vehicle routing problem with limited depot capacity and stochastic demands. International Transactions in Operational Research, 26(2), 458–484.
Cao, Z., Guo, H., Song, W., Gao, K., Chen, Z., Zhang, L., & Zhang, X. (2020). Using reinforcement learning to minimize the probability of delay occurrence in transportation. IEEE Transactions on Vehicular Technology, 69(3), 2424–2436.
Chen, B., Qu, R., Bai, R., & Laesanklang, W. (2018). A hyper-heuristic with two guidance indicators for bi-objective mixed-shift vehicle routing problem with time windows. Applied Intelligence, 48, 4937–4959.
de Armas, J., & Melián-Batista, B. (2015). Variable neighborhood search for a dynamic rich vehicle routing problem with time windows. Computers & Industrial Engineering, 85, 120–131.
De La Vega, J., Munari, P., & Morabito, R. (2019). Robust optimization for the vehicle routing problem with multiple deliverymen. Central European Journal of Operations Research, 27, 905–936.
Dias, L. S., & Ierapetritou, M. G. (2016). Integration of scheduling and control under uncertainties: Review and challenges. Chemical Engineering Research and Design, 116, 98–113.
Durana, P., Perkins, N., & Valaskova, K. (2021). Artificial intelligence data-driven internet of things systems, real-time advanced analytics, and cyber-physical production networks in sustainable smart manufacturing. Econ. Manag. Financ. Mark, 16, 20–30.
Erten, H. I., Deveci, H. A., & Artem, H. S. (2020). Stochastic optimization methods. In Designing engineering structures using stochastic optimization methods (pp. 10–23). CRC Press.
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.
Goel, R., Maini, R., & Bansal, S. (2019). Vehicle routing problem with time windows having stochastic customers demands and stochastic service times: Modelling and solution. Journal of Computational Science, 34, 1–10.
Golden, B. L., Raghavan, S., & Wasil, E. A. (2008). The vehicle routing problem: latest advances and new challenges (Vol. 43). Springer.
Guimarans, D., Dominguez, O., Panadero, J., & Juan, A. A. (2018). A simheuristic approach for the two-dimensional vehicle routing problem with stochastic travel times. Simulation Modelling Practice and Theory, 89, 1–14.
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.
Hwang, I., & Jang, Y. J. (2020). Q (λ) learning-based dynamic route guidance algorithm for overhead hoist transport systems in semiconductor fabs. International Journal of Production Research, 58(4), 1199–1221.
Ivanov, D., Dolgui, A., Das, A., & Sokolov, B. (2019). Digital supply chain twins: Managing the ripple effect, resilience, and disruption risks by data-driven optimization, simulation, and visibility. Handbook of Ripple Effects in the Supply Chain, 309–332.
Karimi-Mamaghan, M., Mohammadi, M., Meyer, P., Karimi-Mamaghan, A. M., & Talbi, E.-G. (2022). Machine learning at the service of meta-heuristics for solving combinatorial optimization problems: A state-of-the-art. European Journal of Operational Research, 296(2), 393–422.
Kheiri, A., Dragomir, A. G., Mueller, D., Gromicho, J., Jagtenberg, C., & van Hoorn, J. J. (2019). Tackling a VRP challenge to redistribute scarce equipment within time windows using metaheuristic algorithms. EURO Journal on Transportation and Logistics, 8(5), 561–595.
Konstantakopoulos, G. D., Gayialis, S. P., & Kechagias, E. P. (2020). Vehicle routing problem and related algorithms for logistics distribution: a literature review and classification. Operational Research, 1–30.
Li, H., Li, Z., Cao, L., Wang, R., & Ren, M. (2020). Research on optimization of electric vehicle routing problem with time window. IEEE Access, 8, 146707–146718.
Li, Y., & Chung, S. H. (2019). Disaster relief routing under uncertainty: A robust optimization approach. Iise Transactions, 51(8), 869–886.
Maghfiroh, M. F. N., & Hanaoka, S. (2018). Dynamic truck and trailer routing problem for last mile distribution in disaster response. Journal of Humanitarian Logistics and Supply Chain Management.
Munari, P., Moreno, A., De La Vega, J., Alem, D., Gondzio, J., & Morabito, R. (2019). The robust vehicle routing problem with time windows: compact formulation and branch-price-and-cut method. Transportation Science, 53(4), 1043–1066.
Nasri, M., Metrane, A., Hafidi, I., & Jamali, A. (2020). A robust approach for solving a vehicle routing problem with time windows with uncertain service and travel times. International Journal of Industrial Engineering Computations, 11(1), 1–16.
Osaba, E., Carballedo, R., Yang, X.-S., Fister Jr, I., Lopez-Garcia, P., & Del Ser, J. (2018). On efficiently solving the vehicle routing problem with time windows using the bat algorithm with random reinsertion operators. Nature-Inspired Algorithms and Applied Optimization, 69–89.
Osaba, E., Yang, X.-S., Diaz, F., Onieva, E., Masegosa, A. D., & Perallos, A. (2017). A discrete firefly algorithm to solve a rich vehicle routing problem modelling a newspaper distribution system with recycling policy. Soft Computing, 21, 5295–5308.
Pasha, J., Dulebenets, M. A., Kavoosi, M., Abioye, O. F., Wang, H., & Guo, W. (2020). An optimization model and solution algorithms for the vehicle routing problem with a “factory-in-a-box.” Ieee Access, 8, 134743–134763.
Psaraftis, H. N., Wen, M., & Kontovas, C. A. (2016). Dynamic vehicle routing problems: Three decades and counting. Networks, 67(1), 3–31.
Rizzoli, A. E., Montemanni, R., Lucibello, E., & Gambardella, L. M. (2007). Ant colony optimization for real-world vehicle routing problems: from theory to applications. Swarm Intelligence, 1, 135–151.
Shahparvari, S., & Abbasi, B. (2017). Robust stochastic vehicle routing and scheduling for bushfire emergency evacuation: An Australian case study. Transportation Research Part A: Policy and Practice, 104, 32–49.
Shehadeh, K. S., & Padman, R. (2022). Stochastic optimization approaches for elective surgery scheduling with downstream capacity constraints: Models, challenges, and opportunities. Computers & Operations Research, 137, 105523.
Shi, Y., Boudouh, T., & Grunder, O. (2017). A hybrid genetic algorithm for a home health care routing problem with time window and fuzzy demand. Expert Systems with Applications, 72, 160–176.
Shi, Y., Boudouh, T., & Grunder, O. (2019). A robust optimization for a home health care routing and scheduling problem with consideration of uncertain travel and service times. Transportation Research Part E: Logistics and Transportation Review, 128, 52–95.
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.
Solomon, M. M., & Desrosiers, J. (1988). Survey paper—time window constrained routing and scheduling problems. Transportation Science, 22(1), 1–13.
Sultana, N. N., Baniwal, V., Basumatary, A., Mittal, P., Ghosh, S., & Khadilkar, H. (2021). Fast approximate solutions using reinforcement learning for dynamic capacitated vehicle routing with time windows. ArXiv Preprint ArXiv:2102.12088.
Sun, S., Duan, Z., & Yang, D. (2015). Urban freight management with stochastic time-dependent travel times and application to large-scale transportation networks. Discrete Dynamics in Nature and Society, 2015.
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.
Ulmer, M. W., Goodson, J. C., Mattfeld, D. C., & Thomas, B. W. (2020). On modeling stochastic dynamic vehicle routing problems. EURO Journal on Transportation and Logistics, 9(2), 100008.
Vahdani, B., Veysmoradi, D., Noori, F., & Mansour, F. (2018). Two-stage multi-objective location-routing-inventory model for humanitarian logistics network design under uncertainty. International Journal of Disaster Risk Reduction, 27, 290–306.
Wang, D., Zhu, J., Wei, X., Cheng, T. C. E., Yin, Y., & Wang, Y. (2019). Integrated production and multiple trips vehicle routing with time windows and uncertain travel times. Computers & Operations Research, 103, 1–12.
Wang, Y., Assogba, K., Fan, J., Xu, M., Liu, Y., & Wang, H. (2019). Multi-depot green vehicle routing problem with shared transportation resource: Integration of time-dependent speed and piecewise penalty cost. Journal of Cleaner Production, 232, 12–29.
Wang, Y., Assogba, K., Liu, Y., Ma, X., Xu, M., & Wang, Y. (2018). Two-echelon location-routing optimization with time windows based on customer clustering. Expert Systems with Applications, 104, 244–260.
Williams, A., Suler, P., & Vrbka, J. (2020). Business process optimization, cognitive decision-making algorithms, and artificial intelligence data-driven internet of things systems in sustainable smart manufacturing. Journal of Self-Governance and Management Economics, 8(4), 39–48.
Xu, X., Lin, Z., Li, X., Shang, C., & Shen, Q. (2022). Multi-objective robust optimisation model for MDVRPLS in refined oil distribution. International Journal of Production Research, 60(22), 6772–6792.
Yang, Z., van Osta, J.-P., van Veen, B., van Krevelen, R., van Klaveren, R., Stam, A., Kok, J., Bäck, T., & Emmerich, M. (2017). Dynamic vehicle routing with time windows in theory and practice. Natural Computing, 16, 119–134.
Yao, Y., Zhu, X., Dong, H., Wu, S., Wu, H., Tong, L. C., & Zhou, X. (2019). ADMM-based problem decomposition scheme for vehicle routing problem with time windows. Transportation Research Part B: Methodological, 129, 156–174.
Ye, C., He, W., & Chen, H. (2022). Electric vehicle routing models and solution algorithms in logistics distribution: A systematic review. Environmental Science and Pollution Research, 29(38), 57067–57090.
Zarandi, M. H. F., Hemmati, A., Davari, S., & Turksen, I. B. (2013). Capacitated location-routing problem with time windows under uncertainty. Knowledge-Based Systems, 37, 480–489.
Zarouk, Y., Mahdavi, I., Rezaeian, J., & Santos-Arteaga, F. J. (2022). A novel multi-objective green vehicle routing and scheduling model with stochastic demand, supply, and variable travel times. Computers & Operations Research, 141, 105698.
Zong, Z., Feng, T., Xia, T., Jin, D., & Li, Y. (2021). Deep Reinforcement Learning for Demand Driven Services in Logistics and Transportation Systems: A Survey. ArXiv Preprint ArXiv:2108.04462.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2022 Desrosiers Goel Zarouk, Chung Wang Xu, Erten Wang Cacchiani
This work is licensed under a Creative Commons Attribution 4.0 International License.
