A Mixed-Integer Linear Programming Model for the Multi-Trip Multi-Period Vehicle Routing Problem with Hard Time Windows
##plugins.themes.academic_pro.article.sidebar##
Available on-line since
Oct 30, 2026
Download
Statistic
Read Counter : 7
Download : 0
Download : 0
##plugins.themes.academic_pro.article.main##
Abstract
Distributors that serve many customers with strict delivery time windows over several days must decide which vehicle serves each customer, on which trip, and on which day. This study formulates a mixed-integer linear programming (MILP) model for the multi-trip multi-period vehicle routing problem with hard time windows (MTMPVRPTW) by integrating multi-trip and multi-period formulations to minimize transportation cost under vehicle-capacity, route-duration, and time-window constraints. The model was validated conceptually against the operations of a snack distributor in Padang, Indonesia, verified through dimensional analysis, and tested in LINGO on three reduced instances with five, eight, and ten customers served by two 50-bale vehicles. It generated one route in one day, three routes including a second trip within one day, and four routes over two days, respectively, with every route within capacity. Computation time rose from 2 s to 30 min 11 s, indicating that larger instances require heuristic solution approaches.
##plugins.themes.academic_pro.article.details##
License and Copyright
This work is licensed under a Creative Commons Attribution 4.0 International License.
Copyright (c): Eri Wirdianto (2026)
How to Cite
Wirdianto, E. (2026). A Mixed-Integer Linear Programming Model for the Multi-Trip Multi-Period Vehicle Routing Problem with Hard Time Windows. MOTIVECTION : Journal of Mechanical, Electrical and Industrial Engineering, 8(3), 263 - 276. https://doi.org/10.46574/motivection.v8i2.643
References
[1] S. Chopra and P. Meindl, Supply Chain Management: Strategy, Planning, and Operation, 6th ed. Boston, MA, USA: Pearson, 2016.
[2] Q. Fu, A. A. A. Rahman, H. Jiang, J. Abba, and U. Comite, “Sustainable supply chain and business performance: The impact of strategy, network design, information systems, and organizational structure,” Sustainability, vol. 14, no. 3, Art. no. 1080, 2022, doi: 10.3390/su14031080.
[3] A. F. S. Billa, N. I. Saragih, and P. S. Muttaqin, “Product delivery distribution route design at UD. XYZ use the saving matrix method to minimize distribution costs,” MOTIVECTION: J. Mech. Electr. Ind. Eng., vol. 4, no. 3, pp. 305–318, 2022, doi: 10.46574/motivection.v4i3.164.
[4] A. A. Kharisma, “Konsep, tantangan dan strategi alihmoda angkutan logistik nasional,” Badan Kebijakan Transportasi, Kementerian Perhubungan Republik Indonesia, 2023. [Online]. Available: https://baketrans.kemenhub.go.id/berita/konsep-tantangan-dan-strategi-alihmoda-angkutan-logistik-nasional (accessed Jan. 15, 2026).
[5] T. T. Sang, N. M. Thu, T. H. Khoi, N. T. K. Huong, L. T. N. Lan, and N. V. Thanh, “The optimization of transportation costs in logistics enterprises during the COVID-19 pandemic,” ARRUS J. Math. Appl. Sci., vol. 1, no. 2, pp. 62–71, 2021, doi: 10.35877/mathscience567.
[6] M. A. Rahman, A.-A. Hossain, B. Debnath, Z. M. Zefat, M. S. Morshed, and Z. H. Adnan, “Intelligent vehicle scheduling and routing for a chain of retail stores: A case study of Dhaka, Bangladesh,” Logistics, vol. 5, no. 3, Art. no. 63, 2021, doi: 10.3390/logistics5030063.
[7] K. Zhang, F. He, Z. Zhang, X. Lin, and M. Li, “Multi-vehicle routing problems with soft time windows: A multi-agent reinforcement learning approach,” Transp. Res. Part C Emerg. Technol., vol. 121, Art. no. 102861, 2020, doi: 10.1016/j.trc.2020.102861.
[8] R. Pérez-Rodríguez and A. Hernández-Aguirre, “A hybrid estimation of distribution algorithm for the vehicle routing problem with time windows,” Comput. Ind. Eng., vol. 130, pp. 75–96, 2019, doi: 10.1016/j.cie.2019.02.017.
[9] W. Zhang, D. Yang, G. Zhang, and M. Gen, “Hybrid multiobjective evolutionary algorithm with fast sampling strategy-based global search and route sequence difference-based local search for VRPTW,” Expert Syst. Appl., vol. 145, Art. no. 113151, 2020, doi: 10.1016/j.eswa.2019.113151.
[10] R. Xu, S. Li, and J. Wu, “Multi-trip vehicle routing problem with time windows and resource synchronization on heterogeneous facilities,” Systems, vol. 11, no. 8, Art. no. 412, 2023, doi: 10.3390/systems11080412.
[11] M. E. H. Sadati, B. Çatay, and D. Aksen, “An efficient variable neighborhood search with tabu shaking for a class of multi-depot vehicle routing problems,” Comput. Oper. Res., vol. 133, Art. no. 105269, 2021, doi: 10.1016/j.cor.2021.105269.
[12] A. B. Pratiwi, A. Sasmito, Q. S. Istiqomah, M. R. Kurniawan, and H. Suprajitno, “Metaheuristic algorithms for solving multiple-trips vehicle routing problem with time windows (MTVRPTW),” J. Phys.: Conf. Ser., vol. 1306, no. 1, Art. no. 012021, 2019, doi: 10.1088/1742-6596/1306/1/012021.
[13] B. Pan, Z. Zhang, and A. Lim, “Multi-trip time-dependent vehicle routing problem with time windows,” Eur. J. Oper. Res., vol. 291, no. 1, pp. 218–231, 2021, doi: 10.1016/j.ejor.2020.09.022.
[14] R. Paradiso, R. Roberti, D. Laganá, and W. Dullaert, “An exact solution framework for multitrip vehicle-routing problems with time windows,” Oper. Res., vol. 68, no. 1, pp. 180–198, 2020, doi: 10.1287/opre.2019.1874.
[15] E. B. Tirkolaee, I. Mahdavi, M. M. S. Esfahani, and G.-W. Weber, “A hybrid augmented ant colony optimization for the multi-trip capacitated arc routing problem under fuzzy demands for urban solid waste management,” Waste Manag. Res., vol. 38, no. 2, pp. 156–172, 2020, doi: 10.1177/0734242X19865782.
[16] J. Zhang, Y. Zhu, T. Wang, W. Wang, R. Wang, and X. Li, “An improved intelligent auction mechanism for emergency material delivery,” Mathematics, vol. 10, no. 13, Art. no. 2184, 2022, doi: 10.3390/math10132184.
[17] L. Janinhoff, R. Klein, and D. Scholz, “Multitrip vehicle routing with delivery options: A data-driven application to the parcel industry,” OR Spectr., vol. 46, no. 2, pp. 241–294, 2024, doi: 10.1007/s00291-023-00710-6.
[18] D. Wu and C. Wu, “Research on the time-dependent split delivery green vehicle routing problem for fresh agricultural products with multiple time windows,” Agriculture, vol. 12, no. 6, Art. no. 793, 2022, doi: 10.3390/agriculture12060793.
[19] A. Paul, R. S. Kumar, C. Rout, and A. Goswami, “Designing a multi-depot multi-period vehicle routing problem with time window: Hybridization of tabu search and variable neighbourhood search algorithm,” Sādhanā, vol. 46, no. 3, Art. no. 183, 2021, doi: 10.1007/s12046-021-01693-2.
[20] M. Keskin, J. Branke, V. Deineko, and A. K. Strauss, “Dynamic multi-period vehicle routing with touting,” Eur. J. Oper. Res., vol. 310, no. 1, pp. 168–184, 2023, doi: 10.1016/j.ejor.2023.02.037.
[21] S. Fazi, S. K. Choudhary, and J.-X. Dong, “The multi-trip container drayage problem with synchronization for efficient empty containers re-usage,” Eur. J. Oper. Res., vol. 310, no. 1, pp. 343–359, 2023, doi: 10.1016/j.ejor.2023.02.041.
[22] T. Calamoneri, F. Corò, and S. Mancini, “Management of a post-disaster emergency scenario through unmanned aerial vehicles: Multi-depot multi-trip vehicle routing with total completion time minimization,” Expert Syst. Appl., vol. 251, Art. no. 123766, 2024, doi: 10.1016/j.eswa.2024.123766.
[23] A. Mor and M. G. Speranza, “Vehicle routing problems over time: A survey,” Ann. Oper. Res., vol. 314, pp. 255–275, 2022, doi: 10.1007/s10479-021-04488-0.
[24] J. S. Azuero-Ortiz, M. A. Gaviria-Hernández, V. M. Jiménez-Rodríguez, E. J. Vale-Santiago, and E. M. González-Neira, “Design of a hybridization between tabu search and PAES algorithms to solve a multi-depot, multi-product green vehicle routing problem,” Decis. Sci. Lett., vol. 12, no. 2, pp. 441–456, 2023, doi: 10.5267/j.dsl.2022.11.004.
[25] K. Huang and M. Xu, “Optimization models for the vehicle routing problem under disruptions,” Mathematics, vol. 11, no. 16, Art. no. 3521, 2023, doi: 10.3390/math11163521.
[26] M. A. Gökçe and E. Ercan, “Multi-period vehicle routing & replenishment problem of neighbourhood disaster stations for pre-disaster humanitarian relief logistics,” IFAC-PapersOnLine, vol. 52, no. 13, pp. 2614–2619, 2019, doi: 10.1016/j.ifacol.2019.11.601.
[27] F. Hernandez, D. Feillet, R. Giroudeau, and O. Naud, “A new exact algorithm to solve the multi-trip vehicle routing problem with time windows and limited duration,” 4OR, vol. 12, no. 3, pp. 235–259, 2014, doi: 10.1007/s10288-013-0238-z.
[28] V. L. Azzahra and M. Fauzi, “Determination of the shortest route for inorganic waste transportation using the Clarke and Wright saving algorithm,” MOTIVECTION: J. Mech. Electr. Ind. Eng., vol. 5, no. 2, pp. 195–204, 2023, doi: 10.46574/motivection.v5i2.217.
[29] E. Wirdianto, M. G. Bintang, and F. Azhari, “Determination of optimal route for distribution of rice food assistance in City X using the cuckoo search algorithm,” MOTIVECTION: J. Mech. Electr. Ind. Eng., vol. 8, no. 1, pp. 13–22, 2026, doi: 10.46574/motivection.v8i1.528.
[30] T. Jastrzab, M. Myller, L. Tulczyjew, M. Blocho, M. Kawulok, A. Czornik, and J. Nalepa, “Standardized validation of vehicle routing algorithms,” Appl. Intell., vol. 54, no. 2, pp. 1335–1364, 2024, doi: 10.1007/s10489-023-05212-0.
[2] Q. Fu, A. A. A. Rahman, H. Jiang, J. Abba, and U. Comite, “Sustainable supply chain and business performance: The impact of strategy, network design, information systems, and organizational structure,” Sustainability, vol. 14, no. 3, Art. no. 1080, 2022, doi: 10.3390/su14031080.
[3] A. F. S. Billa, N. I. Saragih, and P. S. Muttaqin, “Product delivery distribution route design at UD. XYZ use the saving matrix method to minimize distribution costs,” MOTIVECTION: J. Mech. Electr. Ind. Eng., vol. 4, no. 3, pp. 305–318, 2022, doi: 10.46574/motivection.v4i3.164.
[4] A. A. Kharisma, “Konsep, tantangan dan strategi alihmoda angkutan logistik nasional,” Badan Kebijakan Transportasi, Kementerian Perhubungan Republik Indonesia, 2023. [Online]. Available: https://baketrans.kemenhub.go.id/berita/konsep-tantangan-dan-strategi-alihmoda-angkutan-logistik-nasional (accessed Jan. 15, 2026).
[5] T. T. Sang, N. M. Thu, T. H. Khoi, N. T. K. Huong, L. T. N. Lan, and N. V. Thanh, “The optimization of transportation costs in logistics enterprises during the COVID-19 pandemic,” ARRUS J. Math. Appl. Sci., vol. 1, no. 2, pp. 62–71, 2021, doi: 10.35877/mathscience567.
[6] M. A. Rahman, A.-A. Hossain, B. Debnath, Z. M. Zefat, M. S. Morshed, and Z. H. Adnan, “Intelligent vehicle scheduling and routing for a chain of retail stores: A case study of Dhaka, Bangladesh,” Logistics, vol. 5, no. 3, Art. no. 63, 2021, doi: 10.3390/logistics5030063.
[7] K. Zhang, F. He, Z. Zhang, X. Lin, and M. Li, “Multi-vehicle routing problems with soft time windows: A multi-agent reinforcement learning approach,” Transp. Res. Part C Emerg. Technol., vol. 121, Art. no. 102861, 2020, doi: 10.1016/j.trc.2020.102861.
[8] R. Pérez-Rodríguez and A. Hernández-Aguirre, “A hybrid estimation of distribution algorithm for the vehicle routing problem with time windows,” Comput. Ind. Eng., vol. 130, pp. 75–96, 2019, doi: 10.1016/j.cie.2019.02.017.
[9] W. Zhang, D. Yang, G. Zhang, and M. Gen, “Hybrid multiobjective evolutionary algorithm with fast sampling strategy-based global search and route sequence difference-based local search for VRPTW,” Expert Syst. Appl., vol. 145, Art. no. 113151, 2020, doi: 10.1016/j.eswa.2019.113151.
[10] R. Xu, S. Li, and J. Wu, “Multi-trip vehicle routing problem with time windows and resource synchronization on heterogeneous facilities,” Systems, vol. 11, no. 8, Art. no. 412, 2023, doi: 10.3390/systems11080412.
[11] M. E. H. Sadati, B. Çatay, and D. Aksen, “An efficient variable neighborhood search with tabu shaking for a class of multi-depot vehicle routing problems,” Comput. Oper. Res., vol. 133, Art. no. 105269, 2021, doi: 10.1016/j.cor.2021.105269.
[12] A. B. Pratiwi, A. Sasmito, Q. S. Istiqomah, M. R. Kurniawan, and H. Suprajitno, “Metaheuristic algorithms for solving multiple-trips vehicle routing problem with time windows (MTVRPTW),” J. Phys.: Conf. Ser., vol. 1306, no. 1, Art. no. 012021, 2019, doi: 10.1088/1742-6596/1306/1/012021.
[13] B. Pan, Z. Zhang, and A. Lim, “Multi-trip time-dependent vehicle routing problem with time windows,” Eur. J. Oper. Res., vol. 291, no. 1, pp. 218–231, 2021, doi: 10.1016/j.ejor.2020.09.022.
[14] R. Paradiso, R. Roberti, D. Laganá, and W. Dullaert, “An exact solution framework for multitrip vehicle-routing problems with time windows,” Oper. Res., vol. 68, no. 1, pp. 180–198, 2020, doi: 10.1287/opre.2019.1874.
[15] E. B. Tirkolaee, I. Mahdavi, M. M. S. Esfahani, and G.-W. Weber, “A hybrid augmented ant colony optimization for the multi-trip capacitated arc routing problem under fuzzy demands for urban solid waste management,” Waste Manag. Res., vol. 38, no. 2, pp. 156–172, 2020, doi: 10.1177/0734242X19865782.
[16] J. Zhang, Y. Zhu, T. Wang, W. Wang, R. Wang, and X. Li, “An improved intelligent auction mechanism for emergency material delivery,” Mathematics, vol. 10, no. 13, Art. no. 2184, 2022, doi: 10.3390/math10132184.
[17] L. Janinhoff, R. Klein, and D. Scholz, “Multitrip vehicle routing with delivery options: A data-driven application to the parcel industry,” OR Spectr., vol. 46, no. 2, pp. 241–294, 2024, doi: 10.1007/s00291-023-00710-6.
[18] D. Wu and C. Wu, “Research on the time-dependent split delivery green vehicle routing problem for fresh agricultural products with multiple time windows,” Agriculture, vol. 12, no. 6, Art. no. 793, 2022, doi: 10.3390/agriculture12060793.
[19] A. Paul, R. S. Kumar, C. Rout, and A. Goswami, “Designing a multi-depot multi-period vehicle routing problem with time window: Hybridization of tabu search and variable neighbourhood search algorithm,” Sādhanā, vol. 46, no. 3, Art. no. 183, 2021, doi: 10.1007/s12046-021-01693-2.
[20] M. Keskin, J. Branke, V. Deineko, and A. K. Strauss, “Dynamic multi-period vehicle routing with touting,” Eur. J. Oper. Res., vol. 310, no. 1, pp. 168–184, 2023, doi: 10.1016/j.ejor.2023.02.037.
[21] S. Fazi, S. K. Choudhary, and J.-X. Dong, “The multi-trip container drayage problem with synchronization for efficient empty containers re-usage,” Eur. J. Oper. Res., vol. 310, no. 1, pp. 343–359, 2023, doi: 10.1016/j.ejor.2023.02.041.
[22] T. Calamoneri, F. Corò, and S. Mancini, “Management of a post-disaster emergency scenario through unmanned aerial vehicles: Multi-depot multi-trip vehicle routing with total completion time minimization,” Expert Syst. Appl., vol. 251, Art. no. 123766, 2024, doi: 10.1016/j.eswa.2024.123766.
[23] A. Mor and M. G. Speranza, “Vehicle routing problems over time: A survey,” Ann. Oper. Res., vol. 314, pp. 255–275, 2022, doi: 10.1007/s10479-021-04488-0.
[24] J. S. Azuero-Ortiz, M. A. Gaviria-Hernández, V. M. Jiménez-Rodríguez, E. J. Vale-Santiago, and E. M. González-Neira, “Design of a hybridization between tabu search and PAES algorithms to solve a multi-depot, multi-product green vehicle routing problem,” Decis. Sci. Lett., vol. 12, no. 2, pp. 441–456, 2023, doi: 10.5267/j.dsl.2022.11.004.
[25] K. Huang and M. Xu, “Optimization models for the vehicle routing problem under disruptions,” Mathematics, vol. 11, no. 16, Art. no. 3521, 2023, doi: 10.3390/math11163521.
[26] M. A. Gökçe and E. Ercan, “Multi-period vehicle routing & replenishment problem of neighbourhood disaster stations for pre-disaster humanitarian relief logistics,” IFAC-PapersOnLine, vol. 52, no. 13, pp. 2614–2619, 2019, doi: 10.1016/j.ifacol.2019.11.601.
[27] F. Hernandez, D. Feillet, R. Giroudeau, and O. Naud, “A new exact algorithm to solve the multi-trip vehicle routing problem with time windows and limited duration,” 4OR, vol. 12, no. 3, pp. 235–259, 2014, doi: 10.1007/s10288-013-0238-z.
[28] V. L. Azzahra and M. Fauzi, “Determination of the shortest route for inorganic waste transportation using the Clarke and Wright saving algorithm,” MOTIVECTION: J. Mech. Electr. Ind. Eng., vol. 5, no. 2, pp. 195–204, 2023, doi: 10.46574/motivection.v5i2.217.
[29] E. Wirdianto, M. G. Bintang, and F. Azhari, “Determination of optimal route for distribution of rice food assistance in City X using the cuckoo search algorithm,” MOTIVECTION: J. Mech. Electr. Ind. Eng., vol. 8, no. 1, pp. 13–22, 2026, doi: 10.46574/motivection.v8i1.528.
[30] T. Jastrzab, M. Myller, L. Tulczyjew, M. Blocho, M. Kawulok, A. Czornik, and J. Nalepa, “Standardized validation of vehicle routing algorithms,” Appl. Intell., vol. 54, no. 2, pp. 1335–1364, 2024, doi: 10.1007/s10489-023-05212-0.