{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T10:20:30Z","timestamp":1775816430266,"version":"3.50.1"},"reference-count":46,"publisher":"MDPI AG","issue":"11","license":[{"start":{"date-parts":[[2022,11,4]],"date-time":"2022-11-04T00:00:00Z","timestamp":1667520000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"NSERC, Canada"},{"name":"Compute Canada"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Motivated by the transportation needs of modern-day retailers, we consider a variant of the vehicle routing problem with time windows in which each truck has a variable capacity. In our model, each vehicle can bring one or more wagons. The clients are visited within specified time windows, and the vehicles can also make multiple trips. We give a mathematical programming formulation for the problem, and a branch and price algorithm is developed to solve the model. In each iteration of branch and price, column generation is used. Different subproblems are created based on the different capacities to find the best column. We use CPLEX to solve the problem computationally and extend Solomon\u2019s instances to evaluate our approach. To our knowledge, ours is the first such study in this field.<\/jats:p>","DOI":"10.3390\/a15110412","type":"journal-article","created":{"date-parts":[[2022,11,7]],"date-time":"2022-11-07T02:43:51Z","timestamp":1667789031000},"page":"412","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Branch and Price Algorithm for Multi-Trip Vehicle Routing with a Variable Number of Wagons and Time Windows"],"prefix":"10.3390","volume":"15","author":[{"given":"Leila","family":"Karimi","sequence":"first","affiliation":[{"name":"Department of Mathematics and Computer Science, University of Lethbridge, Lethbridge, AB T1K 3M4, Canada"}]},{"given":"Chowdhury","family":"Nawrin Ferdous","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computer Science, University of Lethbridge, Lethbridge, AB T1K 3M4, Canada"}]}],"member":"1968","published-online":{"date-parts":[[2022,11,4]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1287\/mnsc.6.1.80","article-title":"The Truck Dispatching Problem","volume":"6","author":"Dantzig","year":"1959","journal-title":"Manag. Sci."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Caric, T., and Gold, H. (2008). Vehicle Routing Problem, InTech.","DOI":"10.5772\/64"},{"key":"ref_3","first-page":"366","article-title":"An exact method to solve the multitrip vehicle routing problem with time windows and limited duration","volume":"7","author":"Hernandez","year":"2010","journal-title":"TRISTAN"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"756","DOI":"10.1016\/j.ejor.2009.06.034","article-title":"An exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles","volume":"202","author":"Azi","year":"2010","journal-title":"Eur. J. Oper. Res."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/S0166-218X(03)00434-7","article-title":"A multi-phase constructive heuristic for the vehicle routing problem with multiple trips","volume":"133","author":"Petch","year":"2003","journal-title":"Discret. Appl. Math."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1287\/opre.35.2.254","article-title":"Algorithms for the vehicle routing and scheduling problems with time window constraints","volume":"35","author":"Solomon","year":"1987","journal-title":"Oper. Res."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1007\/s13676-014-0074-0","article-title":"Vehicle routing problems for city logistics","volume":"6","author":"Cattaruzza","year":"2017","journal-title":"EURO J. Transp. Logist."},{"key":"ref_8","unstructured":"Fleischmann, B. (1990). The Vehicle Routing Problem with Multiple Use of Vehicles. [Ph.D. Thesis, Fachbereich Wirtschaftswissenschaften, Universit\u00e4t Hamburg]."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1065","DOI":"10.1057\/jors.1996.133","article-title":"Vehicle routeing with multiple use of vehicles","volume":"47","author":"Taillard","year":"1996","journal-title":"J. Oper. Res. Soc."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1016\/S0377-2217(97)00010-6","article-title":"A tabu search algorithm for the multi-trip vehicle routing and scheduling problem","volume":"100","author":"Brandao","year":"1997","journal-title":"Eur. J. Oper. Res."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"799","DOI":"10.1057\/palgrave.jors.2600595","article-title":"The multi-trip vehicle routing problem","volume":"49","author":"Mercer","year":"1998","journal-title":"J. Oper. Res. Soc."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1007\/BF02564791","article-title":"The many-to-many location-routing problem","volume":"6","author":"Nagy","year":"1998","journal-title":"Top"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1287\/trsc.1030.0046","article-title":"Efficient insertion heuristics for vehicle routing and scheduling problems","volume":"38","author":"Campbell","year":"2004","journal-title":"Transp. Sci."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"591","DOI":"10.1007\/s10852-007-9069-2","article-title":"A GA based heuristic for the vehicle routing problem with multiple trips","volume":"6","author":"Salhi","year":"2007","journal-title":"J. Math. Model. Algorithms"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1016\/j.cor.2005.02.044","article-title":"Adaptive memory programming for the vehicle routing problem with multiple trips","volume":"34","author":"Olivera","year":"2007","journal-title":"Comput. Oper. Res."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1016\/j.cor.2014.06.006","article-title":"An iterated local search for the multi-commodity multi-trip vehicle routing problem with time windows","volume":"51","author":"Cattaruzza","year":"2014","journal-title":"Comput. Oper. Res."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"454","DOI":"10.1016\/j.cor.2015.12.017","article-title":"The multiple trip vehicle routing problem with backhauls: Formulation and a two-level variable neighbourhood search","volume":"78","author":"Wassan","year":"2017","journal-title":"Comput. Oper. Res."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"417","DOI":"10.3934\/naco.2017026","article-title":"A robust multi-trip vehicle routing problem of perishable products with intermediate depots and time windows","volume":"7","author":"Tirkolaee","year":"2017","journal-title":"Numer. Algebr. Control Optim."},{"key":"ref_19","first-page":"92","article-title":"Optimization of multi-trip vehicle routing problem with time windows using genetic algorithm","volume":"3","author":"Anggodo","year":"2017","journal-title":"J. Environ. Eng. Sustain. Technol."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Tirkolaee, E.B., Hosseinabadi, A.A.R., Soltani, M., Sangaiah, A.K., and Wang, J. (2018). A hybrid genetic algorithm for multi-trip green capacitated arc routing problem in the scope of urban services. Sustainability, 10.","DOI":"10.3390\/su10051366"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1177\/0734242X18807001","article-title":"Developing an applied algorithm for multi-trip vehicle routing problem with time windows in urban waste collection: A case study","volume":"37","author":"Abbasian","year":"2019","journal-title":"Waste Manag. Res."},{"key":"ref_22","first-page":"100233","article-title":"Vehicle routing problem of contactless joint distribution service during COVID-19 pandemic","volume":"8","author":"Chen","year":"2020","journal-title":"Transp. Res. Interdiscip. Perspect."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"101866","DOI":"10.1016\/j.tre.2020.101866","article-title":"Multi-depot multi-trip vehicle routing problem with time windows and release dates","volume":"135","author":"Zhen","year":"2020","journal-title":"Transp. Res. Part E Logist. Transp. Rev."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"106399","DOI":"10.1016\/j.cie.2020.106399","article-title":"New compact integer programming formulations for the multi-trip vehicle routing problem with time windows","volume":"144","author":"Neira","year":"2020","journal-title":"Comput. Ind. Eng."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"342","DOI":"10.1287\/opre.40.2.342","article-title":"A new optimization algorithm for the vehicle routing problem with time windows","volume":"40","author":"Desrochers","year":"1992","journal-title":"Oper. Res."},{"key":"ref_26","unstructured":"Halse, K. (1992). Modeling and Solving Complex Vehicle Routing Problems. [Ph.D. Thesis, Technical University of Denmark]."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1287\/opre.45.3.395","article-title":"An optimization algorithm for the vehicle routing problem with time windows based on Lagrangian relaxation","volume":"45","author":"Kohl","year":"1997","journal-title":"Oper. Res."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1287\/trsc.33.1.101","article-title":"2-path cuts for the vehicle routing problem with time windows","volume":"33","author":"Kohl","year":"1999","journal-title":"Transp. Sci."},{"key":"ref_29","unstructured":"Larsen, J. (1999). Parallelization of the Vehicle Routing Problem with Time Windows, Citeseer."},{"key":"ref_30","unstructured":"Cook, W., and Rich, J.L. (1999). A Parallel Cutting-Plane Algorithm for the Vehicle Routing Problem with Time Windows, Rice University. Technical Report;."},{"key":"ref_31","unstructured":"Kallehauge, B., Larsen, J., and Madsen, O.B. (2000). Lagrangean Duality and Non-Differentiable Optimization Applied on Routing with Time Windows-Experimental Results, Relat\u00f3rio interno IMM-REP-2000-8; Department of Mathematical Modeling, Technical University of Denmark."},{"key":"ref_32","unstructured":"Chabrier, A., Danna, E., and Le Pape, C. (2002, January 27\u201329). Coop\u00e9ration entre g\u00e9n\u00e9ration de colonnes avec tourn\u00e9es sans cycle et recherche locale appliqu\u00e9e au routage de v\u00e9hicules. Proceedings of the Journ\u00e9es Nationales sur la R\u00e9solution Pratique de Probl\u00e8mes NP-Complets, Nice, France."},{"key":"ref_33","first-page":"216","article-title":"An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems","volume":"44","author":"Feillet","year":"2004","journal-title":"Netw. Int. J."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1023\/B:ANOR.0000032576.73681.29","article-title":"Solving VRPTWs with constraint programming based column generation","volume":"130","author":"Rousseau","year":"2004","journal-title":"Ann. Oper. Res."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"2972","DOI":"10.1016\/j.cor.2005.02.029","article-title":"Vehicle routing problem with elementary shortest path based column generation","volume":"33","author":"Chabrier","year":"2006","journal-title":"Comput. Oper. Res."},{"key":"ref_36","first-page":"1","article-title":"The shortest path problem with k-cycle elimination (k \u2265 3): Improving a branch and price algorithm for the VRPTW","volume":"10","author":"Irnich","year":"2003","journal-title":"INFORMS J. Comput."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Desaulniers, G., Desrosiers, J., and Solomon, M.M. (2005). Accelerating branch-and-price with local search: A case study on the vehicle routing problem with time windows. Column Generation, Kluwer Academic Publishers. Charpter 3.","DOI":"10.1007\/b135457"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"755","DOI":"10.1016\/j.ejor.2006.02.019","article-title":"An exact algorithm for a single-vehicle routing problem with time windows and multiple routes","volume":"178","author":"Azi","year":"2007","journal-title":"Eur. J. Oper. Res."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"536","DOI":"10.1016\/j.ejor.2011.04.037","article-title":"Solving the vehicle routing problem with time windows and multiple routes exactly using a pseudo-polynomial model","volume":"214","author":"Macedo","year":"2011","journal-title":"Eur. J. Oper. Res."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1007\/s11750-018-0481-8","article-title":"A branch-price-and-cut algorithm for the vehicle routing problem with time windows and multiple deliverymen","volume":"26","author":"Munari","year":"2018","journal-title":"Top"},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"222","DOI":"10.1016\/j.cie.2019.02.032","article-title":"A column generation algorithm for vehicle scheduling and routing problems","volume":"130","author":"Faiz","year":"2019","journal-title":"Comput. Ind. Eng."},{"key":"ref_42","unstructured":"Seixas, M.P., and Mendes, A.B. (2012, January 24\u201328). A branch-and-price approach for a multi-trip vehicle routing problem with time windows and driver work hours. Proceedings of the Congreso Latino-Iberoamericano de Investigaci\u00f3n Operativa. Simp\u00f3sio Brasileiro de Pesquisa Operacional, Rio de Janeiro, Brazil."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"824","DOI":"10.1016\/j.ejor.2019.06.032","article-title":"A branch-and-cut-and-price algorithm for the multi-trip separate pickup and delivery problem with time windows at customers and facilities","volume":"279","author":"Bettinelli","year":"2019","journal-title":"Eur. J. Oper. Res."},{"key":"ref_44","doi-asserted-by":"crossref","unstructured":"Marques, G., Sadykov, R., Dupas, R., and Deschamps, J.C. (2022). A branch-cut-and-price approach for the single-trip and multi-trip two-echelon vehicle routing problem with time windows. Transp. Sci.","DOI":"10.1287\/trsc.2022.1136"},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"102370","DOI":"10.1016\/j.tre.2021.102370","article-title":"The multi-trip vehicle routing problem with time windows and unloading queue at depot","volume":"152","author":"Huang","year":"2021","journal-title":"Transp. Res. Part E Logist. Transp. Rev."},{"key":"ref_46","unstructured":"(2022, August 20). Solomon\u2019s Benchmark Instances. Available online: https:\/\/www.sintef.no\/projectweb\/top\/vrptw\/100-customers\/."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/11\/412\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T01:11:02Z","timestamp":1760145062000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/11\/412"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,4]]},"references-count":46,"journal-issue":{"issue":"11","published-online":{"date-parts":[[2022,11]]}},"alternative-id":["a15110412"],"URL":"https:\/\/doi.org\/10.3390\/a15110412","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,11,4]]}}}