Capacitated multi-trip vehicle routing problems with time windows (CMTVRPTW) is the extension of the well-known vehicle routing problem (VRP) by allowing many drivers to perform multiple trips to serve a set of customers on a single workday. There has been much attention given to this topic recently because it is crucial for many real-world delivery applications in which vehicle capacity, trip duration, or the number of drivers are limited. However, the added trip scheduling factor significantly increases the complexity of finding the final solution. Through this thesis, we introduce crowd-shipping transportation systems, in which companies can make deliveries by using their fleet composed of their vehicles and occasional drivers (ODs). This problem defines as capacitated multi-trip vehicle routing problem with time windows and occasional drivers (CMTVRPTWOD). It could lower delivery costs and assure benefits even if the customer's demand is higher than what their vehicles can execute on that day. Numerical results are collected on Solomon benchmarks for vehicle routing problems with time windows (VRPTW). For this problem, we formulate it as a mixed-integer programming (MIP) problem and develop a mathematical model which can be solved by the CPLEX solver for small and medium instances. A hybrid meta-heuristic algorithm for large-scale problems is designed, combining Adaptive Large Neighborhood Search (ALNS) with Variable Neighborhood Search (VNS) in a framework of Simulated Annealing (SA) to solve efficiently. This study generally indicates ODs' benefits to the business model, especially for small and medium-sized enterprises.

Archetti, C., Guerriero, F., & Macrina, G. (2021). The online vehicle routing problem with occasional drivers. Computers & Operations Research, 127, 105144. https://doi.org/10.1016/j.cor.2020.105144
Archetti, C., Savelsbergh, M., & Speranza, M. G. (2016). The vehicle routing problem with occasional drivers. European Journal of Operational Research, 254(2), 472-480. https://doi.org/10.1016/j.ejor.2016.03.049
Azi, N., Gendreau, M., & Potvin, J. Y. (2007). An exact algorithm for a single-vehicle routing problem with time windows and multiple routes. European Journal of Operational Research, 178(3), 755-766. https://doi.org/10.1016/j.ejor.2006.02.019
Azi, N., Gendreau, M., & Potvin, J. Y. (2010). An exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles. European Journal of Operational Research, 202(3), 756-763. https://doi.org/10.1016/j.ejor.2009.06.034
Azi, N., Gendreau, M., & Potvin, J. Y. (2014). An adaptive large neighborhood search for a vehicle routing problem with multiple routes. Computers & Operations Research, 41(1), 167-173. https://doi.org/10.1016/j.cor.2013.08.016
Ball, M. O., Golden, B., Assad, A., & Bodin, L. (1983). Planning for truck fleet size in the presence of a common‐carrier option. Decision Sciences, 14(1), 103-120. https://doi.org/10.1111/j.1540-5915.1983.tb00172.x
Battarra, M., Monaci, M., & Vigo, D. (2009). An adaptive guidance approach for the heuristic solution of a minimum multiple trip vehicle routing problem. Computers & Operations Research, 36(11), 3041-3050. https://doi.org/10.1016/j.cor.2009.02.008
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. https://doi.org/10.1287/trsc.2015.0608
Cattaruzza, D., Absi, N., & Feillet, D. (2018). Vehicle routing problems with multiple trips. Annals of Operations Research, 271(1), 127-159. https://doi.org/10.1007/s10479-018- 2988-7
Cattaruzza, D., Absi, N., Feillet, D., & Vidal, T. (2014). A memetic algorithm for the Multi Trip Vehicle Routing Problem. European Journal of Operational Research, 236(3), 833-848. https://doi.org/10.1016/j.ejor.2013.06.012
Dahle, L., Andersson, H., & Christiansen, M. (2017). The vehicle routing problem with dynamic occasional drivers. Computational Logistics ICCL 2017, 10572, 49-63. https://doi.org/10.1007/978-3-319-68496-3_4
Dahle, L., Andersson, H., Christiansen, M., & Speranza, M. G. (2019). The pickup and delivery problem with time windows and occasional drivers. Computers & Operations Research, 109, 122-133. https://doi.org/10.1016/j.cor.2019.04.023
Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management science, 6(1), 80-91. https://doi.org/10.1287/mnsc.6.1.80
Fleischmann, B. (1990). The vehicle routing problem with multiple use of vehicles. Fachbereich Wirtschaftswissenschaften, Universität Hamburg.
Francois, V., Arda, Y., & Crama, Y. (2019). Adaptive large neighborhood search for multitrip vehicle routing with time windows. Transportation Science, 53(6), 1706-1730. https://doi.org/10.1287/trsc.2019.0909
Francois, V., Arda, Y., Crama, Y., & Laporte, G. (2016). Large neighborhood search for multi-trip vehicle routing. European Journal of Operational Research, 255(2), 422-441.
https://doi.org/10.1016/j.ejor.2016.04.065
Gahm, C., Brabander, C., & Tuma, A. (2017). Vehicle routing with private fleet, multiple common carriers offering volume discounts, and rental options. Transportation Research Part E-Logistics and Transportation Review, 97, 192-216. https://doi.org/10.1016/j.tre.2016.10.010
Hernandez, F., Feillet, D., Giroudeau, R., & Naud, O. (2014). A new exact algorithm to solve the multi-trip vehicle routing problem with time windows and limited duration. 4or-a Quarterly Journal of Operations Research, 12(3), 235-259. https://doi.org/10.1007/s10288-013-0238-z
Hernandez, F., Feillet, D., Giroudeau, R., & Naud, O. (2016). Branch-and-price algorithms for the solution of the multi-trip vehicle routing problem with time windows. European Journal of Operational Research, 249(2), 551-559. https://doi.org/10.1016/j.ejor.2015.08.040
Kafle, N., Zou, B., & Lin, J. (2017). Design and modeling of a crowdsource-enabled system for urban parcel relay and delivery. Transportation Research Part B-Methodological, 99, 62-82. https://doi.org/10.1016/j.trb.2016.12.022
Lin, S. W., Yu, V. F., & Chou, S. Y. (2009). Solving the truck and trailer routing problem based on a simulated annealing heuristic. Computers & Operations Research, 36(5), 1683-1692. https://doi.org/10.1016/j.cor.2008.04.005
Macedo, R., Alves, C., de Carvalho, J. M. V., Clautiaux, F., & Hanafi, S. (2011). Solving the vehicle routing problem with time windows and multiple routes exactly using a pseudo- polynomial model. European Journal of Operational Research, 214(3), 536-545. https://doi.org/10.1016/j.ejor.2011.04.037
Macrina, G., Di Puglia Pugliese, L., & Guerriero, F. (2020a). A variable neighborhood search for the vehicle routing problem with occasional drivers and time windows. ICORES, 1,
270-277. https://doi.org/10.5220/0009193302700277
Macrina, G., Di Puglia Pugliese, L., Guerriero, F., & Laganà, D. (2017). The vehicle routing problem with occasional drivers and time windows (A. Sforza & C. Sterle, Eds. Vol. 217). Springer International Publishing. https://doi.org/10.1007/978-3-319-67308- 0_58
Macrina, G., & Guerriero, F. (2018). The green vehicle routing problem with occasional drivers. New Trends in Emerging Complex Real Life Problems: ODS, Taormina, Italy, September 10–13, 2018, 1, 357-366. https://doi.org/10.1007/978-3-030-00473-6_38
Macrina, G., Pugliese, L., Guerriero, F., & Laporte, G. (2020b). Crowd-shipping with time windows and transshipment nodes. Computers & Operations Research, 113, 104806. https://doi.org/10.1016/j.cor.2019.104806
Mladenović, N., & Hansen, P. (1997). Variable neighborhood search. Computers & Operations Research, 24(11), 1097-1100. https://doi.org/10.1016/S0305-0548(97)00031-2 Olivera, A., & Viera, O. (2007). Adaptive memory programming for the vehicle routing
problem with multiple trips. Computers & Operations Research, 34(1), 28-47.
https://doi.org/10.1016/j.cor.2005.02.044
Pan, B. B., Zhang, Z. Z., & Lim, A. (2021). Multi-trip time-dependent vehicle routing problem with time windows. European Journal of Operational Research, 291(1), 218-231. https://doi.org/10.1016/j.ejor.2020.09.022
Paradiso, R., Roberti, R., Lagana, D., & Dullaert, W. (2020). An exact solution framework for multitrip vehicle-routing problems with time windows. Operations Research, 68(1), 180-198. https://doi.org/10.1287/opre.2019.1874
Pugliese, L. D., Ferone, D., Festa, P., Guerriero, F., & Macrina, G. (2022). Solution approaches for the vehicle routing problem with occasional drivers and time windows. Optimization Methods & Software, 37(4), 1384-1414.
https://doi.org/10.1080/10556788.2021.2022142
Pugliese, L. D., Ferone, D., Macrina, G., Festa, P., & Guerriero, F. (2023). The crowd-shipping with penalty cost function and uncertain travel times. Omega-International Journal of Management Science, 115, 102776. https://doi.org/10.1016/j.omega.2022.102776
Ropke, S., & Pisinger, D. (2006). An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation Science, 40(4), 455- 472. https://doi.org/10.1287/trsc.1050.0135
Shaw, P. (1997). A new local search algorithm providing high quality solutions to vehicle routing problems. APES Group, Dept of Computer Science, University of Strathclyde, Glasgow, Scotland, UK, 46.
Solomon, M. M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research, 35(2), 254-265. https://doi.org/10.1287/opre.35.2.254
Taillard, E. D., Laporte, G., & Gendreau, M. (1996). Vehicle routing with multiple use of vehicles. Journal of the Operational Research Society, 47(8), 1065-1070. https://doi.org/10.1057/jors.1996.133
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. https://doi.org/10.1016/j.cie.2015.02.005
Wang, Z., Liang, W., & Hu, X. (2014). A metaheuristic based on a pool of routes for the vehicle routing problem with multiple trips and time windows. Journal of the Operational Research Society, 65(1), 37-48. https://doi.org/10.1057/jors.2013.4
Yang, Y. (2022). An exact price-cut-and-enumerate method for the capacitated multitrip
vehicle routing problem with time windows. Transportation Science.
https://doi.org/10.1287/trsc.2022.1161
Yu, V. F., Aloina, G., Jodiawan, P., Gunawan, A., & Huang, T.-C. (2023). The vehicle routing problem with simultaneous pickup and delivery and occasional drivers. Expert Systems with Applications, 214, 119118. https://doi.org/10.1016/j.eswa.2022.119118
Yu, V. F., Jodiawan, P., Hou, M. L., & Gunawan, A. (2021). Design of a two-echelon freight distribution system in last-mile logistics considering covering locations and occasional drivers. Transportation Research Part E-Logistics and Transportation Review, 154, 102461. https://doi.org/10.1016/j.tre.2021.102461
Yu, V. F., Jodiawan, P., & Redi, A. A. N. P. (2022). Crowd-shipping problem with time windows, transshipment nodes, and delivery options. Transportation Research Part E- Logistics and Transportation Review, 157, 102545. https://doi.org/10.1016/j.tre.2021.102545
Yu, V. F., Redi, A. A. N. P., Hidayat, Y. A., & Wibowo, O. J. (2017). A simulated annealing heuristic for the hybrid vehicle routing problem. Applied Soft Computing, 53, 119-132. https://doi.org/10.1016/j.asoc.2016.12.027