There is growing concern about plastic waste and its impact on the environment, leading to an interest in sustainable living. One solution is the use of home-refill services, which deliver bulk household products to customers' containers rather than traditional retail chains. This study aims to optimize the distribution operations of a home-refill service company that uses motorbikes with multiple compartments (dispensers) to deliver a range of household products. Each motorbike can perform multiple trips in a day. We also take into account the optional customers whose demands are not required to be fulfilled since their priorities are lower than those of mandatory customers. This problem is referred to as the Multi-Vehicle Profitable Tour Problem with Multi-Trip Flexible Discrete Compartment (MV-PTP MT-FDC). We formulate a mathematical programming model for the problem and propose an Adaptive Large Neighborhood Search (ALNS) metaheuristic to solve small and large instances. We conducted extensive computational experiments to analyze the efficiency of ALNS solving the test instance to find the optimal solution.

Archetti, C., Feillet, D., Hertz, A., & Speranza, M. G. (2009). The capacitated team orienteering and profitable tour problems. Journal of the Operational Research Society, 60(6), 831-842. https://doi.org/10.1057/palgrave.jors.2602603
Archetti, C., Speranza, M. G., & Vigo, D. (2014). Chapter 10: Vehicle Routing Problems with Profits. In: Vehicle Routing: Problems, Methods, and Applications, Second Edition, 273–297. Piladelphia, USA: SIAM. https://doi.org/10.1137/1.9781611973594.ch10
Avci, M. G., & Avci, M. (2019). An adaptive large neighborhood search approach for multiple traveling repairman problem with profits. Computers and Operations Research 111, 367–385. https://doi.org/10.1016/j.cor.2019.07.012
Avella, P., Boccia, M., & Sforza, A. (2004). Solving a fuel delivery problem by heuristic and exact approaches. European Journal of Operational Research, 152(1), 170-179. https://doi.org/10.1016/S0377-2217(02)00676-8
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
Brown, G. G., Ellis, C. J., Graves, G. W., & Ronen, D. (1987). Real-Time, Wide Area Dispatch of Mobil Tank Trucks. Interfaces, 17(1), 107-120. https://doi.org/DOI10.1287/inte.17.1.107
Brown, G. G., & Graves, G. W. (1981). Real-Time Dispatch of Petroleum Tank Trucks. Management Science, 27(1), 19-32. http://www.jstor.org/stable/2631140
Cattaruzza, D., Absi, N., & Feillet, D. (2016). Vehicle routing problems with multiple trips. A Quarterly Journal of Operations Research, 223-259. https://doi.org/10.1007/s10288-016-0306-2
Cattaruzza, D., Absi, N., Feillet, D., & Vigo, D. (2014). An iterated local search for the multi-commodity multi-trip vehicle routing problem with time windows. Computers & Operations Research, 51, 257-267. https://doi.org/10.1016/j.cor.2014.06.006
Chbichib, A., Mellouli, R., & Chabchoub, H. (2011). Profitable Vehicle Routing Problem with Multiple Trips: modeling and constructive heuristics. 4th International Conference on Logistics, 500-507. https://doi.org/10.1109/LOGISTIQUA.2011.5939450
Demir, E., Bektas, T., & Laporte, G. (2012). An adaptive large neighborhood search heuristic for the Pollution-Routing Problem. European Journal of Operational Research, 223(2), 346-359. https://doi.org/10.1016/j.ejor.2012.06.044
Derigs, U., Gottlieb, J., Kalkoff, J., Piesche, M., Rothlauf, F., & Vogel, U. (2011). Vehicle routing with compartments: applications, modelling and heuristics. Or Spectrum, 33(4), 885-914. https://doi.org/10.1007/s00291-010-0194-3
El Fallahi, A., Prins, C., & Calvo, R. W. (2008). A memetic algorithm and a tabu search for the multi-compartment vehicle routing problem. Computers & Operations Research, 35(5), 1725-1741. https://doi.org/10.1016/j.cor.2006.10.006
Eshtehadi, R., Demir, E., & Huang, Y. (2020). Solving the vehicle routing problem with multi-compartment vehicles for city logistics. Computers & Operations Research, 115. https://doi.org/ARTN0485910.1016/j.cor.2019.104859
Fleischmann, B. (1990). The vehicle routing problem with multiple use of the vehicles. Ph.D. Thesis, Fachbereich Wirtschaftswissenschaften, Universität Hamburg, Hamburg, Germany.
Francois, V., Arda, Y., & Crama, Y. (2019). Adaptive large neighborhood search for multi-trip vehicle routing. 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
Golden, B. L., Levy, L., & Vohra, R. (1987). The Orienteering Problem. Naval Research Logistics, 34(3), 307-318. https://doi.org/Doi10.1002/1520-6750(198706)34:3<307::Aid-Nav3220340302>3.0.Co;2-D
Hammami, F., Rekik, M., & Coelho, L. C. (2020). A hybrid adaptive large neighborhood search heuristic for the team orienteering problem. Computers & Operations Research, 123, 105034. https://doi.org/ARTN 0503410.1016/j.cor.2020.105034
Handoko, S. D., Gupta, A., Heng, C. K., Lau, H. C., & Ong, Y. S. (2015). Solving multi-vehicle profitable tour problem via knowledge adoption in evolutionary bi-level programming. IEEE International Congress on Evolutionary Computation (CEC), Sendai, Japan, 2713-2720. https://doi.org/10.1109/CEC.2015.7257225
Henke, T., Speranza, M. G., & Wascher, G. (2015). The multi-compartment vehicle routing problem with flexible compartment sizes. European Journal of Operational Research, 246(3), 730-743. https://doi.org/10.1016/j.ejor.2015.05.020
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
Hessler, K. (2021). Exact algorithms for the multi-compartment vehicle routing problem with flexible compartment sizes. European Journal of Operational Research, 294(1), 188-205. https://doi.org/10.1016/j.ejor.2021.01.037
Hubner, A., & Ostermeier, M. (2019). A Multi-Compartment Vehicle Routing Problem with Loading and Unloading Costs. Transportation Science, 53(1), 282-300. https://doi.org/10.1287/trsc.2017.0775
Kabcome, P., & Mouktonglang, T. (2015). Vehicle Routing Problem for Multiple Product Types, Compartments, and Trips with Soft Time Windows. International Journal of Mathematics and Mathematical Sciences, 2015. https://doi.org/10.1155/2015/126754
Koch, H., Henke, T., & Wascher, G. (2016). A genetic algorithm for the multi-compartment vehicle routing problem with flexible compartment sizes. FEMM Working Papers, 04/2016, Magdeburg: Otto-von-Guericke University Magdeburg, Faculty of Economics and Management.
Lahyani, R., Coelho, L. C., Khemakhem, M., Laporte, G., & Semet, F. (2015). A multi-compartment vehicle routing problem arising in the collection of olive oil in Tunisia. Omega-International Journal of Management Science, 51, 1-10. https://doi.org/10.1016/j.omega.2014.08.007
Laporte, G., Ropke, S., & Vidal, T. (2014). Heuristics for the Vehicle Routing Problem. Vehicle Routing: Problems, Methods, and Applications, 2nd Edition, 87-116. https://doi.org/Book_Doi10.1137/1.9781611973594
Lin, S. W., & Yu, V. F. (2017). Solving the team orienteering problem with time windows and mandatory visits by multi-start simulated annealing. Computers & Industrial Engineering, 114, 195-205. https://doi.org/10.1016/j.cie.2017.10.020
Lofthouse, V., & Bhamra, T. (2006). An investigation into consumer perceptions of refills and refillable packaging. Loughborough: Loughborough University, 1-33.
Louis, D., Lombart, C., & Durif, F. (2021). Packaging-free products: A lever of proximity and loyalty between consumers and grocery stores. Journal of Retailing and Consumer Services, 60. https://doi.org/10.1016/j.jretconser.2021.102499
Martins, S., Ostermeier, M., Amorim, P., Huebner, A., & Almada-Lobo, B. (2019). Product-oriented time window assignment for a multi-compartment vehicle routing problem. European Journal of Operational Research, 276(3), 893-909. https://doi.org/10.1016/j.ejor.2019.01.053
Muyldermans, L., & Pang, G. (2010). On the benefits of co-collection: Experiments with a multi-compartment vehicle routing algorithm. European Journal of Operational Research, 206(1), 93-103. https://doi.org/10.1016/j.ejor.2010.02.020
Ostermeier, M., Henke, T., Hubner, A., & Wascher, G. (2021). Multi-compartment vehicle routing problems: State-of-the-art, modeling framework and future directions. European Journal of Operational Research, 292(3), 799-817. https://doi.org/10.1016/j.ejor.2020.11.009
Pan, B., Zhang, Z., & Lim, A. (2021). Multi-trip time-dependent vehicle routing problem with time windows. European Journal of Operational Research 291, 218–231. https://doi.org/10.1016/j.ejor.2020.09.022
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. (1998). Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems. Lecture Notes in Computer Science, 1520, 417–431. https://doi.org/10.1007/3-540-49481-2_30
Taillard, E. D., Laporte, G., & Gendreau, M. (1996). Vehicle routeing with multiple use of vehicles. Journal of the Operational Research Society, 47(8), 1065-1070. https://doi.org/DOI10.1057/palgrave.jors.0470810
Tarantilis, C. D., Stavropoulou, F., & Repoussis, P. P. (2013). The Capacitated Team Orienteering Problem: A Bi-level Filter-and-Fan method. European Journal of Operational Research, 224(1), 65-78. https://doi.org/10.1016/j.ejor.2012.07.032
Tirkolaee, E. B., Abbasian, P., Soltani, M., & Ghaffarian, S. A. (2019). Developing an applied algorithm for multi-trip vehicle routing problem with time windows in urban waste collection: A case study. Waste Management & Research, 37(1). https://doi.org/10.1177/0734242X18807001
Zhen, L., Ma, C. L., Wang, K., Xiao, L. Y., & Zhang, W. (2020). Multi-depot multi-trip vehicle routing problem with time windows and release dates. Transportation Research Part E-Logistics and Transportation Review, 135. https://doi.org/ARTN0186610.1016/j.tre.2020.101866