{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,19]],"date-time":"2025-11-19T11:18:53Z","timestamp":1763551133959,"version":"build-2065373602"},"reference-count":54,"publisher":"MDPI AG","issue":"9","license":[{"start":{"date-parts":[[2020,8,27]],"date-time":"2020-08-27T00:00:00Z","timestamp":1598486400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Information"],"abstract":"<jats:p>In the dynamic vehicle routing problem with mixed backhauls (DVRPMB) both pick up orders and delivery orders, not related to each other, are served. The requests of the former arrive dynamically while the latter are known a priori. In this study, we focus on the case of limited fleet, which fulfills all delivery orders, but may not have enough capacity to serve all pick up orders within the available working horizon. The problem\u2019s dynamic nature and the attention to customer service raise interesting considerations, especially related to the problem\u2019s objectives. The problem is solved through periodic re-optimization, acknowledging the fact that this pseudo-dynamic approach may lead to some limitations. For the underlying (static) optimization problem we propose appropriate objective functions, which account for vehicle productivity and propose a branch-and-price (BP) approach to solve it to optimality. The results indicate how the performance of the various objectives is impacted by different re-optimization frequencies and policies in this practically relevant environment of dynamic demand served by a limited fleet. Specifically, extensive experimentation indicates that accounting for vehicle productivity within a typical periodic re-optimization solution framework may result to higher customer service under a range of operational settings, in comparison to conventional objectives.<\/jats:p>","DOI":"10.3390\/info11090414","type":"journal-article","created":{"date-parts":[[2020,8,27]],"date-time":"2020-08-27T08:05:18Z","timestamp":1598515518000},"page":"414","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["The Effect of Limited Resources in the Dynamic Vehicle Routing Problem with Mixed Backhauls"],"prefix":"10.3390","volume":"11","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0666-9787","authenticated-orcid":false,"given":"Georgios","family":"Ninikas","sequence":"first","affiliation":[{"name":"ORTEC bv, 2719 E Zoetermeer, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ioannis","family":"Minis","sequence":"additional","affiliation":[{"name":"Department of Financial and Management Engineering, University of the Aegean, 82100 Chios, Greece"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2020,8,27]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1002\/net.21567","article-title":"Reoptimization strategies for a dynamic vehicle routing problem with mixed backhauls","volume":"64","author":"Ninikas","year":"2014","journal-title":"Networks"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1007\/s41604-017-0005-y","article-title":"Load transfer operations for a dynamic vehicle routing problem with mixed backhauls","volume":"1","author":"Ninikas","year":"2018","journal-title":"J. Veh. Routing Algorithms"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1002\/net.10067","article-title":"The single-vehicle routing problem with unrestricted backhauls","volume":"41","author":"Bookbinder","year":"2003","journal-title":"Networks"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"568","DOI":"10.1016\/j.ejor.2006.05.009","article-title":"General solutions to the single vehicle routing problem with pick-ups and deliveries","volume":"180","author":"Gribkovskaia","year":"2007","journal-title":"Eur. J. Oper. Res."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1016\/j.ejor.2010.02.037","article-title":"A branch-and-price algorithm for the Vehicle Routing Problem with Deliveries, Selective Pickups and Time Windows","volume":"206","author":"Desaulniers","year":"2010","journal-title":"Eur. J. Oper. Res."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Toth, P., and Vigo, D. (2002). The VRP with pickup and delivery. The Vehicle Routing Problem, Society of Industrial and Applied Mathematics.","DOI":"10.1137\/1.9780898718515"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s11750-007-0009-0","article-title":"Static pick-up and delivery problems: A classification scheme and survey","volume":"15","author":"Berbeglia","year":"2007","journal-title":"Top"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1016\/j.ejor.2009.04.024","article-title":"Dynamic pick-up and delivery problems","volume":"202","author":"Berbeglia","year":"2010","journal-title":"Eur. J. Oper. Res."},{"key":"ref_9","first-page":"21","article-title":"A survey on pick-up and delivery problems. Part I: Transportation between customers and depot","volume":"58","author":"Parragh","year":"2008","journal-title":"J. Betr."},{"key":"ref_10","first-page":"81","article-title":"A survey on pick-up and delivery problems. Part II: Transportation between pick-up and delivery locations","volume":"58","author":"Parragh","year":"2008","journal-title":"J. Betr."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"326","DOI":"10.1145\/321043.321046","article-title":"Integer programming formulations and travelling salesman problems","volume":"7","author":"Miller","year":"1960","journal-title":"J. Assoc. Comput. Mach."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"1067","DOI":"10.1080\/07408170903113771","article-title":"A single vehicle routing problem with fixed distribution and optional collections","volume":"41","author":"Marianov","year":"2009","journal-title":"IIE Trans."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"1045","DOI":"10.1057\/palgrave.jors.2602087","article-title":"Solving a vehicle routing problem arising in soft-drink distribution","volume":"57","author":"Renaud","year":"2006","journal-title":"J. Oper. Res. Soc."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1108\/09600030710734866","article-title":"Routing of supply vessels to petroleum installations","volume":"37","author":"Aas","year":"2007","journal-title":"Int. J. Phys. Distrib. Logist. Manag."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"2908","DOI":"10.1016\/j.cor.2007.01.007","article-title":"The single vehicle routing problem with deliveries and selective pick-ups","volume":"35","author":"Gribkovskaia","year":"2008","journal-title":"Comput. Oper. Res."},{"key":"ref_16","unstructured":"Golden, B.L., and Assad, A.A. (1988). Dynamic vehicle routing problems. Vehicle Routing: Methods and Studies, Elsevier Science Publishers B.V."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"704","DOI":"10.1016\/j.ejor.2015.04.009","article-title":"An ant colony system for responsive dynamic vehicle routing","volume":"245","author":"Schyns","year":"2015","journal-title":"Eur. J. Oper. Res."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Karami, F., Vancroonenburg, W., and Vanden Berghe, G. (2020). A periodic optimization approach to dynamic pickup and delivery problems with time windows. J. Sched.","DOI":"10.1007\/s10951-020-00650-x"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1287\/trsc.1050.0133","article-title":"Dynamic column generation for dynamic vehicle routing with time windows","volume":"40","author":"Chen","year":"2006","journal-title":"Transp. Sci."},{"key":"ref_20","unstructured":"Kilby, P., Prosser, P., and Shaw, P. (1998). Dynamic VRPs: A Study of Scenarios, School of Computer Science, University of St. Andrews. Technical Report APES-06-1998."},{"key":"ref_21","first-page":"165","article-title":"Waiting and buffering strategies for the dynamic pickup and delivery problem with time windows","volume":"46","author":"Pureza","year":"2008","journal-title":"Inf. Inf. Syst. Oper. Res."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"635","DOI":"10.1016\/j.trb.2003.09.002","article-title":"Waiting strategies for the dynamic pickup and delivery problem with time windows","volume":"38","author":"Laporte","year":"2004","journal-title":"Transp. Res. Part B"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"171","DOI":"10.3141\/1617-24","article-title":"On-line vehicle routing with time windows, optimization-based heuristics approach for freight demands requested in real-time","volume":"1617","author":"Shieh","year":"1998","journal-title":"Transp. Res. Rec."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1287\/trsc.1030.0070","article-title":"The a-priori dynamic travelling salesman problem with time windows","volume":"38","author":"Larsen","year":"2004","journal-title":"Transp. Sci."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1287\/trsc.33.4.381","article-title":"Parallel tabu search for real-time vehicle routing and dispatching","volume":"33","author":"Gendreau","year":"1999","journal-title":"Transp. Sci."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1007\/s10878-005-4922-6","article-title":"Ant colony system for a dynamic vehicle routing problem","volume":"10","author":"Montemanni","year":"2005","journal-title":"J. Comb. Optim."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"426","DOI":"10.1287\/trsc.34.4.426.12325","article-title":"Diversion issues in real-time vehicle dispatching","volume":"34","author":"Ichoua","year":"2000","journal-title":"Transp. Sci."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"298","DOI":"10.1287\/trsc.1040.0095","article-title":"Waiting Strategies for Dynamic Vehicle Routing","volume":"29","author":"Branke","year":"2005","journal-title":"Transp. Sci."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0377-2217(02)00915-3","article-title":"Real-time vehicle routing: Solution concepts, algorithms and parallel computing strategies","volume":"151","author":"Ghiani","year":"2003","journal-title":"Eur. J. Oper. Res."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Zeimpekis, V., Tarantilis, C.D., Giaglis, G.M., and Minis, I. (2007). Dynamic Fleet Management: Concepts, Systems, Algorithms & Case Studies, Springer.","DOI":"10.1007\/978-0-387-71722-7"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1287\/trsc.1050.0114","article-title":"Exploiting knowledge about future demands for real-time vehicle dispatching","volume":"40","author":"Ichoua","year":"2006","journal-title":"Transp. Sci."},{"key":"ref_32","unstructured":"Goel, A. (2008). Fleet Telematics: Real-Time Management and Planning of Commercial Vehicle Operations, Springer."},{"key":"ref_33","first-page":"199","article-title":"Recent developments in dynamic vehicle routing systems","volume":"Volume 43","author":"Larsen","year":"2008","journal-title":"The Vehicle Routing Problem: Latest Advances and New Challenges"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.ejor.2012.08.015","article-title":"A review of dynamic vehicle routing problems","volume":"225","author":"Pillac","year":"2013","journal-title":"Eur. J. Oper. Res."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1002\/net.21628","article-title":"Dynamic Vehicle Routing Problems: Three Decades and Counting","volume":"67","author":"Psaraftis","year":"2016","journal-title":"Networks"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/j.trc.2009.04.018","article-title":"Can agents measure up? A comparative study of an agent-based and on-line optimization approach for a drayage problem with uncertainty","volume":"18","author":"Srour","year":"2010","journal-title":"Transp. Res. Part C Emerg. Technol."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"977","DOI":"10.1287\/opre.1040.0124","article-title":"Scenario-based planning for partially dynamic vehicle routing with stochastic customers","volume":"52","author":"Bent","year":"2004","journal-title":"Oper. Res."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"312","DOI":"10.1016\/j.ejor.2011.09.023","article-title":"Cyclic-order neighborhoods with application to the vehicle routing problem with stochastic demand","volume":"217","author":"Goodson","year":"2014","journal-title":"Eur. J. Oper. Res."},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Ninikas, G. (2014). Solving the Dynamic Vehicle Routing Problem with Mixed Backhauls Through re-Optimization. [Ph.D. Thesis, University of the Aegean].","DOI":"10.1002\/net.21567"},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"316","DOI":"10.1287\/opre.46.3.316","article-title":"Branch-and-price: Column generation for solving huge integer programs","volume":"46","author":"Barnhart","year":"1998","journal-title":"Oper. Res."},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Crainic, T., and Laporte, G. (1998). A unified framework for deterministic time constrained vehicle routing and crew scheduling problems. Fleet Management and Logistics, Kluwer Academic Publisher.","DOI":"10.1007\/978-1-4615-5755-5"},{"key":"ref_42","doi-asserted-by":"crossref","unstructured":"Desaulniers, G., Desrosiers, J., and Solomon, M.M. (2005). A primer in column generation. Column Generation, Springer.","DOI":"10.1007\/b135457"},{"key":"ref_43","doi-asserted-by":"crossref","unstructured":"Desaulniers, G., Desrosiers, J., and Solomon, M.M. (2005). Column Generation, No 5. GERAD 25th Anniversary, Springer.","DOI":"10.1007\/b135457"},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1002\/net.20033","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":"Networks"},{"key":"ref_45","unstructured":"Feillet, D., Gendreau, M., and Rousseau, L.M. (2005). New Refinements for the Solution of Vehicle Routing Problems with Branch and Price, Center for Reasearch on Transportation. Technical Report C7PQMR PO2005-08-X."},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"474","DOI":"10.1287\/opre.46.4.474","article-title":"DRIVE: Dynamic routing of independent vehicles","volume":"46","author":"Savelsbergh","year":"1998","journal-title":"Oper. Res."},{"key":"ref_47","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_48","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_49","unstructured":"Christofides, N., Mingozzi, A., Toth, P., and Sandi, C. (1979). The vehicle routing problem. Combinatorial Optimization, John Wiley."},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"568","DOI":"10.1287\/opre.12.4.568","article-title":"Scheduling of vehicles from a central depot to a number of delivery points","volume":"12","author":"Clarke","year":"1964","journal-title":"Oper. Res."},{"key":"ref_51","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1002\/jos.122","article-title":"A reactive tabu search meta-heuristic for the vehicle routing problem with back-hauls","volume":"5","author":"Osman","year":"2002","journal-title":"J. Sched."},{"key":"ref_52","doi-asserted-by":"crossref","first-page":"669","DOI":"10.1016\/j.trb.2003.09.001","article-title":"Double-horizon based heuristics for the dynamic pick-up and delivery problem with time windows","volume":"38","author":"Krishnamurti","year":"2004","journal-title":"Transp. Res. Part B"},{"key":"ref_53","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1002\/net.21861","article-title":"Anticipation versus reactive reoptimization for dynamic vehicle routing with stochastic requests","volume":"73","author":"Ulmer","year":"2018","journal-title":"Networks"},{"key":"ref_54","doi-asserted-by":"crossref","unstructured":"Lee, J., Kim, D., and Lee, J. (2019). Zone-based multi-access edge computing scheme for user device mobility management. Appl. Sci., 9.","DOI":"10.3390\/app9112308"}],"container-title":["Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2078-2489\/11\/9\/414\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T10:07:34Z","timestamp":1760177254000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2078-2489\/11\/9\/414"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,27]]},"references-count":54,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2020,9]]}},"alternative-id":["info11090414"],"URL":"https:\/\/doi.org\/10.3390\/info11090414","relation":{},"ISSN":["2078-2489"],"issn-type":[{"type":"electronic","value":"2078-2489"}],"subject":[],"published":{"date-parts":[[2020,8,27]]}}}