An Exact Algorithm for the Vehicle Routing Problem with Time Windows and Perishable Products

References

• Ahmadi-Javid A, Mansourfar M, Lee C-G, Liu L (2023) Optimal distribution of perishable foods with storage temperature control and quality requirements: An integrated vehicle routing problem. Comput. Indust. Engrg. 182:109215.Crossref, Google Scholar
• Amorim P, Almada-Lobo B (2014) The impact of food perishability issues in the vehicle routing problem. Comput. Indust. Engrg. 67:223–233.Crossref, Google Scholar
• Artuso P, Rossetti A, Minetto S, Marinetti S, Moro L, Del Col D (2019) Dynamic modeling and thermal performance analysis of a refrigerated truck body during operation. Internat. J. Refrigeration 99:288–299.Crossref, Google Scholar
• Awad M, Ndiaye M, Osman A (2021) Vehicle routing in cold food supply chain logistics: A literature review. Internat. J. Logist. Management 32(2):592–617.Crossref, Google Scholar
• Baldacci R, Mingozzi A, Roberti R (2011) New route relaxation and pricing strategies for the vehicle routing problem. Oper. Res. 59(5):1269–1283.Link, Google Scholar
• Bektaş T, Laporte G (2011) The pollution-routing problem. Transportation Res. Part B Methodological 45(8):1232–1250.Crossref, Google Scholar
• Bektaş T, Erdoğan G, Røpke S (2011) Formulations and branch-and-cut algorithms for the generalized vehicle routing problem. Transportation Sci. 45(3):299–316.Link, Google Scholar
• Bräysy O, Gendreau M (2005) Vehicle routing problem with time windows, part I: Route construction and local search algorithms. Transportation Sci. 39(1):104–118.Link, Google Scholar
• Chen H-K, Hsueh C-F, Chang M-S (2009) Production scheduling and vehicle routing with time windows for perishable food products. Comput. Oper. Res. 36(7):2311–2319.Crossref, Google Scholar
• Cordeau JF, Ghiani G, Guerriero E (2014) Analysis and branch-and-cut algorithm for the time-dependent travelling salesman problem. Transportation Sci. 48(1):46–58.Link, Google Scholar
• Costa L, Contardo C, Desaulniers G (2019) Exact branch-price-and-cut algorithms for vehicle routing. Transportation Sci. 53(4):946–985.Link, Google Scholar
• Dabia S, Demir E, Van Woensel T (2017) An exact approach for a variant of the pollution-routing problem. Transportation Sci. 51(2):607–628.Link, Google Scholar
• Dabia S, Ropke S, Van Woensel T, De Kok T (2013) Branch and price for the time-dependent vehicle routing problem with time windows. Transportation Sci. 47(3):380–396.Link, Google Scholar
• Dantzig GB, Ramser JH (1959) The truck dispatching problem. Management Sci. 6(1):80–91.Link, Google Scholar
• Deng F, Qin H, Li J, Cheng C (2023) The pickup and delivery problem with time windows and incompatibility constraints in cold chain transportation. Transportation Sci. 57(2):444–462.Link, Google Scholar
• Franceschetti A, Honhon D, Van Woensel T, Bektaş T, Laporte G (2013) The time-dependent pollution-routing problem. Transportation Res. Part B Methodological 56:265–293.Crossref, Google Scholar
• Fukasawa R, He Q, Song Y (2016) A branch-cut-and-price algorithm for the energy minimization vehicle routing problem. Transportation Sci. 50(1):23–34.Link, Google Scholar
• Fukasawa R, Longo H, Lysgaard J, de Aragão MP, Reis M, Uchoa E, Werneck RF (2006) Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Math. Programming 106(3):491–511.Crossref, Google Scholar
• GitHub (2025) VRPTWQ Solomon instances. Accessed April 21, 2026, https://github.com/SelinHulagu/vrptwq-solomon-instances.Google Scholar
• Gogou E, Katsaros G, Derens E, Alvarez G, Taoukis PS (2015) Cold chain database development and application as a tool for the cold chain management and food quality evaluation. Internat. J. Refrigeration 52:109–121.Crossref, Google Scholar
• Gschwind T, Irnich S, Rothenbächer AK, Tilk C (2018) Bidirectional labeling in column-generation algorithms for pickup-and-delivery problems. Eur. J. Oper. Res. 266(2):521–530.Crossref, Google Scholar
• He Q, Irnich S, Song Y (2019) Branch-and-cut-and-price for the vehicle routing problem with time windows and convex node costs. Transportation Sci. 53(5):1409–1426.Link, Google Scholar
• Heijungs R (2024) Statistics 2: Inferential. Probability, Statistics and Life Cycle Assessment: Guidance for Dealing with Uncertainty and Sensitivity (Springer, Cham, Switzerland), 233–330.Crossref, Google Scholar
• Hsiao Y-H, Chen M-C, Chin C-L (2017) Distribution planning for perishable foods in cold chains with quality concerns: Formulation and solution procedure. Trends Food Sci. Tech. 61:80–93.Crossref, Google Scholar
• Hsu C-I, Hung S-F, Li H-C (2007) Vehicle routing problem with time-windows for perishable food delivery. J. Food Engrg. 80(2):465–475.Crossref, Google Scholar
• Jepsen M, Petersen B, Spoorendonk S, Pisinger D (2008) Subset-row inequalities applied to the vehicle-routing problem with time windows. Oper. Res. 56(2):497–511.Link, Google Scholar
• Kara I, Kara BY, Yetis MK (2007) Energy minimizing vehicle routing problem. Dress A, Xu Y, Zhu B, eds. Combinatorial Optimization and Applications. COCOA 2007, Lecture Notes in Computer Science, vol. 4616 (Springer, Berlin, Heidelberg), 62–71.Google Scholar
• Laguerre O, Hoang HM, Flick D (2013) Experimental investigation and modelling in the food cold chain: Thermal and quality evolution. Trends Food Sci. Tech. 29(2):87–97.Crossref, Google Scholar
• Lera-Romero G, Bront JJM, Soulignac FJ (2024) A branch-cut-and-price algorithm for the time-dependent electric vehicle routing problem with time windows. Eur. J. Oper. Res. 312(3):978–995.Crossref, Google Scholar
• Lin X, Negenborn RR, Lodewijks G (2015) Survey on operational perishables quality control and logistics. Corman F, Voß S, Negenborn R, eds. Computational Logistics. ICCL 2015, vol. 9335 (Springer, Cham, Switzerland), 398–421.Google Scholar
• Moureh J, Flick D (2004) Airflow pattern and temperature distribution in a typical refrigerated truck configuration loaded with pallets. Internat. J. Refrigeration 27(5):464–474.Crossref, Google Scholar
• Óskarsdóttir K, Oddsson GV (2019) Towards a decision support framework for technologies used in cold supply chain traceability. J. Food Engrg. 240:153–159.Crossref, Google Scholar
• Osvald A, Stirn LZ (2008) A vehicle routing algorithm for the distribution of fresh vegetables and similar perishable food. J. Food Engrg. 85(2):285–295.Crossref, Google Scholar
• Pecin D, Contardo C, Desaulniers G, Uchoa E (2017a) New enhancements for the exact solution of the vehicle routing problem with time windows. INFORMS J. Comput. 29(3):489–502.Link, Google Scholar
• Pecin D, Pessoa A, Poggi M, Uchoa E (2017b) Improved branch-cut-and-price for capacitated vehicle routing. Math. Programming Comput. 9:61–100.Crossref, Google Scholar
• Qi C, Hu L (2020) Optimization of vehicle routing problem for emergency cold chain logistics based on minimum loss. Physical Comm. 40:101085.Crossref, Google Scholar
• Righini G, Salani M (2006) Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints. Discrete Optim. 3(3):255–273.Crossref, Google Scholar
• Rong A, Akkerman R, Grunow M (2011) An optimization approach for managing fresh food quality throughout the supply chain. Internat. J. Production Econom. 131(1):421–429.Crossref, Google Scholar
• Şahin MK, Yaman H (2022) A branch and price algorithm for the heterogeneous fleet multi-depot multi-trip vehicle routing problem with time windows. Transportation Sci. 56(6):1636–1657.Link, Google Scholar
• Solomon MM (1987) Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper. Res. 35(2):254–265.Link, Google Scholar
• Song BD, Ko YD (2016) A vehicle routing problem of both refrigerated- and general-type vehicles for perishable food products delivery. J. Food Engrg. 169:61–71.Crossref, Google Scholar
• Song H, Kim J, Kim B-S, Koo J (2019) Development of a food temperature prediction model for real time food quality assessment. Internat. J. Refrigeration 98:468–479.Crossref, Google Scholar
• Stellingwerf HM, Kanellopoulos A, van der Vorst JGAJ, Bloemhof JM (2018) Reducing CO2 emissions in temperature-controlled road transportation using the LDVRP model. Transportation Res. Part D Transport Environment 58:80–93.Crossref, Google Scholar
• Stellingwerf HM, Groeneveld LH, Laporte G, Kanellopoulos A, Bloemhof JM, Behdani B (2021) The quality-driven vehicle routing problem: Model and application to a case of cooperative logistics. Internat. J. Production Econom. 231:107849.Crossref, Google Scholar
• Taher MB, Kousksou T, Zeraouli Y, Ahachad M, Mahdaoui M (2021) Thermal performance investigation of door opening and closing processes in a refrigerated truck equipped with different phase change materials. J. Energy Storage 42:103097.Crossref, Google Scholar
• Tassou S, De-Lille G, Ge Y (2009) Food transport refrigeration—Approaches to reduce energy consumption and environmental impacts of road transport. Appl. Thermal Engrg. 29(8–9):1467–1477.Crossref, Google Scholar
• Toth P, Vigo D (2002) The Vehicle Routing Problem (SIAM, Philadelphia).Crossref, Google Scholar
• Van Boekel MA (2008) Kinetic modeling of food quality: A critical review. Comprehensive Rev. Food Sci. Food Safety 7(1):144–158.Crossref, Google Scholar
• Xiao Y, Zhao Q, Kaku I, Xu Y (2012) Development of a fuel consumption optimization model for the capacitated vehicle routing problem. Comput. Oper. Res. 39(7):1419–1431.Crossref, Google Scholar
• Yu B, Yang ZZ, Yao BZ (2011) A hybrid algorithm for vehicle routing problem with time windows. Expert Systems Appl. 38(1):435–441.Crossref, Google Scholar
• Zachariadis EE, Tarantilis CD, Kiranoudis CT (2015) The load-dependent vehicle routing problem and its pick-up and delivery extension. Transportation Res. Part B Methodological 71:158–181.Crossref, Google Scholar
• Zhang J, Cao W, Park M (2019) Reliability analysis and optimization of cold chain distribution system for fresh agricultural products. Sustainability 11(13):3618.Crossref, Google Scholar