Clinical laboratories play a key role in delivering health care services, as the results of clinical tests affect 70% of medical decisions. Therefore, to provide high-quality services, smaller laboratories often send some of their samples to a well-equipped central laboratory. This study aims to minimize total transportation costs in collecting blood samples from geographically dispersed locations. Given the perishable nature of blood samples, the collection process must be completed within 2 h. Since these laboratories do not own a vehicle fleet, a third-party logistics (TPL) service provider is used in the collection process. We define this problem as a heterogenous fleet open vehicle routing problem with dynamic hub location (HFOVRP-HL). The main contribution of our work is developing a novel open vehicle routing problem (OVRP) model in which sequences of open routes and their intersections, creating dynamic and virtual hub nodes, are allowed. A mixed-integer programming (MIP) formulation is presented and solved using the CPLEX solver in GAMS, and the optimal solution is obtained. Computational results demonstrate that HFOVRP-HL outperforms classical HFOVRP, generalized HFOVRP with decoupling points (HFOVRP-DP), and HFOVRP with fixed hubs. Sensitivity analysis on key parameters confirms the model’s validity and superiority, offering substantial reductions in transportation costs. This research provides valuable insights for optimizing blood sample logistics in clinical laboratory networks.
GrasasA.RamalhinhoH.PessoaL. S.ResendeM. G. C.CaballéI.BarbaN.On the Improvement of Blood Sample Collection at Clinical Laboratories. BMC Health Services Research, Vol. 14, 2014. https://doi.org/10.1186/1472-6963-14-12.
2.
YücelE.SalmanF.S.GelE. S.ÖrmeciE. L.GelA.Optimizing Specimen Collection for Processing in Clinical Testing Laboratories. European Journal of Operational Research, Vol. 227, 2013, pp. 503–514.
3.
Becan-McBrideK.Avoiding Specimen Transportation Errors. MLO: Medical Laboratory Observer, Vol. 34, 2002, pp. 38–39.
4.
MillerJ. M.The Impact of Specimen Management in Microbiology. MLO: Medical Laboratory Observer, Vol. 30, No. 5, 1998, pp. 28–30.
5.
LiX.LeungS. C. H.TianP.A Multistart Adaptive Memory-Based Tabu Search Algorithm for the Heterogeneous Fixed Fleet Open Vehicle Routing Problem. Expert Systems with Applications, Vol. 39, 2012, pp. 365–374.
Book, R. Book Review: Computers and Intractability: A Guide to the Theory of NP-Completeness. Bulletin of the American Mathematical Society, Vol. 3, 1980, pp. 898–904. https://doi.org/10.1090/s0273-0979-1980-14848-x.
8.
SchrageL.Formulation and Structure of More Complex/Realistic Routing and Scheduling Problems. Networks, Vol. 11, 1981, pp. 229–232.
9.
YousefikhoshbakhtM.DidehvarF.RahmatiF.Solving the Heterogeneous Fixed Fleet Open Vehicle Routing Problem by a Combined Metaheuristic Algorithm. International Journal of Production Research, Vol. 52, 2014, pp. 2565–2575.
10.
BrandãoJ.A Memory-Based Iterated Local Search Algorithm for the Multi-Depot Open Vehicle Routing Problem. European Journal of Operational Research, Vol. 284, No. 2, 2020, pp. 559–571. https://doi.org/10.1016/j.ejor.2020.01.008.
11.
ŞevkliA. Z.GülerB.A Multi-Phase Oscillated Variable Neighbourhood Search Algorithm for a Real-World Open Vehicle Routing Problem. Applied Soft Computing Journal, Vol. 58, 2017, pp. 128–144.
12.
BritoJ.MartínezF. J.MorenoJ. A.VerdegayJ. L.An ACO Hybrid Metaheuristic for Close-Open Vehicle Routing Problems with Time Windows and Fuzzy Constraints. Applied Soft Computing Journal, Vol. 32, 2015, pp. 154–163.
13.
DiaoX.FanH.RenX.LiuC.Multi-Depot Open Vehicle Routing Problem with Fuzzy Time Windows. Journal of Intelligent and Fuzzy Systems, Vol. 40, 2021, pp. 427–438.
14.
YulizaE.PuspitaF. M.SupadiS. S.The Robust Counterpart Open Capacitated Vehicle Routing Problem with Time Windows on Waste Transport Problems. Bulletin of Electrical Engineering and Informatics, Vol. 9, 2020, pp. 2074–2081.
15.
PuspitaF. M.SimanjuntakA. S. B.MelatiR.OctarinaS.Demand Robust Counterpart Open Capacitated Vehicle Routing Problem Time Windows and Deadline Model of Garbage Transportation with LINGO 13.0. International Journal of Electrical and Computer Engineering, Vol.10, 2020, pp. 6380–6388.
16.
YulizaE.PuspitaF. M.SupadiS. S.Heuristic Approach for Robust Counterpart Open Capacitated Vehicle Routing Problem with Time Windows. Science and Technology Indonesia, Vol. 6, 2021, pp. 53–57.
17.
AtefiR.SalariM.CoelhoL. C.RenaudJ.The Open Vehicle Routing Problem with Decoupling Points. European Journal of Operational Research, Vol. 265, 2018, pp. 316–327.
18.
Ruiz y RuizE.García-CalvilloI.Nucamendi-GuillénS.Open Vehicle Routing Problem with Split Deliveries: Mathematical Formulations and a Cutting-Plane Method. Operational Research, Vol. 22, 2022, pp. 1017–1037.
19.
Soto-MendozaV.García-CalvilloI.Ruiz-y-RuizE.Pérez-TerrazasJ.A Hybrid Grasshopper Optimization Algorithm Applied to the Open Vehicle Routing Problem. Algorithms, Vol. 13, No. 4, 2020, p. 96. https://doi.org/10.3390/A13040096.
20.
CaoE.LaiM.The Open Vehicle Routing Problem with Fuzzy Demands. Expert Systems with Applications, Vol. 37, 2010, pp. 2405–2411.
21.
CaoE.LaiM.YangH.Open Vehicle Routing Problem with Demand Uncertainty and Its Robust Strategies. Expert Systems with Applications, Vol. 41, 2014, pp. 3569–3575.
22.
SunL.WangB.A Goal-Robust-Optimization Approach for Solving Open Vehicle Routing Problems with Demand Uncertainty. Wireless Personal Communications, Vol. 103, 2018, pp. 1059–1075.
23.
RahmaniA.A New Closed–Open Vehicle Routing Approach in Stochastic Environments. International Journal of Computer Mathematics: Computer Systems Theory, Vol. 6, 2021, pp. 113–129.
24.
PichpibulT.KawtummachaiR.A Heuristic Approach Based on Clarke-Wright Algorithm for Open Vehicle Routing Problem. The Scientific World Journal, Vol. 2013, 2013, p. 874349. https://doi.org/10.1155/2013/874349.
25.
HamtaN.RabieeS.Open Vehicle Routing Problem with Robust Optimization Approach. International Journal of Industrial Engineering & Production Research, Vol. 32, 2021, pp. 1–20.
26.
SariklisD.PowellS.A Heuristic Method for the Open Vehicle Routing Problem. Journal of the Operational Research Society, Vol. 51, 2000, pp. 564–573.
27.
MarinakisY.MarinakiM.A Bumble Bees Mating Optimization Algorithm for the Open Vehicle Routing Problem. Swarm and Evolutionary Computation, Vol. 15, 2014, pp. 80–94.
28.
RenC. Y.Study on Hybrid Genetic Algorithm for Multi-Type Vehicle Open Vehicle Routing Problem. Advanced Materials Research, Vol. 204–210, 2011, pp. 1287–1290.
29.
HuangF.LiuC.An Improved Tabu Search for Open Vehicle Routing Problem. Proc., 2010 International Conference on Management and Service Science, MASS 2010, Wuhan, China, IEEE, New York, 2010. https://doi.org/10.1109/ICMSS.2010.5576368.
30.
FleszarK.OsmanI. H.HindiK. S.A Variable Neighbourhood Search Algorithm for the Open Vehicle Routing Problem. European Journal of Operational Research, Vol. 195, 2009, pp. 803–809.
31.
OzcetinE.OzturkG.A Variable Neighborhood Search for Open Vehicle Routing Problem. Concurrency and Computation: Practice and Experience, Vol. 35, 2023, p. e7598.
32.
RuizE.Soto-MendozaV.BarbosaA. E. R.ReyesR.Solving the Open Vehicle Routing Problem with Capacity and Distance Constraints with a Biased Random Key Genetic Algorithm. Computers & Industrial Engineering, Vol. 133, 2019, pp. 207–219.
33.
BrandãoJ.A Tabu Search Algorithm for the Open Vehicle Routing Problem. European Journal of Operational Research, Vol. 157, 2004, pp. 552–564.
34.
LiF.GoldenB.WasilE.The Open Vehicle Routing Problem: Algorithms, Large-Scale Test Problems, and Computational Results. Computers & Operations Research, Vol. 34, 2007, pp. 2918–2930.
35.
RepoussisP. P.TarantilisC. D.BräysyO.IoannouG.A Hybrid Evolution Strategy for the Open Vehicle Routing Problem. Computers & Operations Research, Vol. 37, 2010, pp. 443–455.
36.
SinghG.DhirV.Open Vehicle Routing Problem by Ant Colony Optimization. International Journal of Advanced Computer Science and Applications, Vol. 5, No. 3, 2014, pp. 63–68. www.ijacsa.thesai.org.
37.
YuS.DingC.ZhuK.A Hybrid GA-TS Algorithm for Open Vehicle Routing Optimization of Coal Mines Material. Expert Systems with Applications, Vol. 38, 2011, pp. 10568–10573.
38.
MirhassaniS. A.AbolghasemiN.A Particle Swarm Optimization Algorithm for Open Vehicle Routing Problem. Expert Systems with Applications, Vol. 38, 2011, pp. 11547–11551.
39.
FuZ.EgleseR.LiL.A New Tabu Search Heuristic for the Open Vehicle Routing Problem. Journal of the Operational Research Society, Vol. 56, 2005, pp. 267–274.
40.
TarantilisC. D.IoannouG.KiranoudisC. T.PrastacosG. P.Solving the Open Vehicle Routeing Problem via a Single Parameter Metaheuristic Algorithm. Journal of the Operational Research Society, Vol. 56, 2005, pp. 588–596.
41.
DuttaJ.BarmaP. S.KarS.DeT.A Modified Kruskal’s Algorithm to Improve Genetic Search for Open Vehicle Routing Problem. International Journal of Business Analytics, Vol. 6, 2019, pp. 55–76.
42.
LetchfordA. N.LysgaardJ.EgleseR. W.A Branch-and-Cut Algorithm for the Capacitated Open Vehicle Routing Problem. Journal of the Operational Research Society, Vol. 58, 2007, pp. 1642–1651.
43.
DerigsU.ReuterK.A Simple and Efficient Tabu Search Heuristic for Solving the Open Vehicle Routing Problem. Journal of the Operational Research Society, Vol. 60, 2009, pp. 1658–1669.
44.
HosseinabadiA. A. R.VahidiJ.BalasV. E.MirkamaliS. S.OVRP_GELS: Solving Open Vehicle Routing Problem Using the Gravitational Emulation Local Search Algorithm. Neural Computing and Applications, Vol. 29, 2018, pp. 955–968.
45.
LiX. Y.TianP.LeungS. C. H.An Ant Colony Optimization Metaheuristic Hybridized with Tabu Search for Open Vehicle Routing Problems. Journal of the Operational Research Society, Vol. 60, 2009, pp. 1012–1025.
46.
TarantilisC. D.IoannouG.KiranoudisC. T.PrastacosG. P.A Threshold Accepting Approach to the Open Vehicle Routing Problem. RAIRO - Operations Research, Vol. 38, 2004, pp. 345–360.
47.
MarinakisY.MarinakiM.A Honey Bees Mating Optimization Algorithm for the Open Vehicle Routing Problem. Proc., Genetic and Evolutionary Computation Conference, GECCO’11, New York, ACM Press, New York, pp. 101–108.
48.
ZhengF.DuL.LiX.ZhangJ.TianB.JalladR.Multi-Objective Medical Supplies Distribution Open Vehicle Routing Problem with Fairness and Timeliness Under Major Public Health Emergencies. Management System Engineering, Vol. 2, 2023, p. 5. https://doi.org/10.1007/s44176-023-00015-6.
49.
TonbulE.TakanM. A.BüyükköseG. T.ErginelN.Modeling Open Vehicle Routing Problem with Real Life Costs and Solving via Hybrid Civilized Genetic Algorithm. Sigma Journal of Engineering and Natural Sciences—Sigma Mühendislik ve Fen Bilimleri Dergisi, Vol. 42, No. 3, 2024, pp. 714–730.
50.
Sánchez-OroJ.López-SánchezA. D.ColmenarJ. M.A General Variable Neighborhood Search for Solving the Multi-Objective Open Vehicle Routing Problem. Journal of Heuristics, Vol. 26, 2020, pp. 423–452.
51.
DuttaJ.BarmaP. S.MukherjeeA.KarS.DeT.A Hybrid Multi-Objective Evolutionary Algorithm for Open Vehicle Routing Problem Through Cluster Primary-Route Secondary Approach. International Journal of Management Science and Engineering Management, Vol. 17, 2022, pp. 132–146.
52.
DasdemirE.TestikM. C.ÖztürkD. T.ŞakarC. T.GüleryüzG.TestikÖ. M.A Multi-Objective Open Vehicle Routing Problem with Overbooking: Exact and Heuristic Solution Approaches for an Employee Transportation Problem. Omega, Vol. 108, 2022, p. 102587.
53.
LiuR.JiangZ.GengN.A Hybrid Genetic Algorithm for the Multi-Depot Open Vehicle Routing Problem. OR Spectrum, Vol. 36, 2014, pp. 401–421.
54.
LahyaniR.GouguenheimA. L.CoelhoL. C.A Hybrid Adaptive Large Neighbourhood Search for Multi-Depot Open Vehicle Routing Problems. International Journal of Production Research, Vol. 57, 2019, pp. 6963–6976.
55.
SotoM.SevauxN.RossiA.ReinholzA.Multiple Neighborhood Search, Tabu Search and Ejection Chains for the Multi-Depot Open Vehicle Routing Problem. Computers & Industrial Engineering, Vol. 107, 2017, pp. 211–222.
56.
PengZ.PirozmandP.XiongY.Improved Harris Hawks Optimizer Algorithm to Solve the Multi-Depot Open Vehicle Routing Problem. Evolutionary Intelligence, 2024, Vol. 17, pp. 2495–2513. https://doi.org/10.1007/s12065-023-00898-0.
57.
ShaoW.XiaoT.SuZ.DingJ.LüZ.A Hybridization of Granular Adaptive Tabu Search with Path Relinking for the Multi-Depot Open Vehicle Routing Problem. Egyptian Informatics Journal, Vol. 24, No. 4, 2023, p. 100420. https://doi.org/10.1016/j.eij.2023.100420.
58.
Lalla-RuizE.MesM.Mathematical Formulations and Improvements for the Multi-Depot Open Vehicle Routing Problem. Optimization Letters, Vol. 15, 2021, pp. 271–286.
59.
SoaresV. C.RoboredoM.On the Exact Solution of the Multi-Depot Open Vehicle Routing Problem. Optimization Letters, Vol. 18, 2024, pp. 1053–1069.
60.
RepoussisP. P.TarantilisC. D.IoannouG.The Open Vehicle Routing Problem with Time Windows. Journal of the Operational Research Society, Vol. 58, 2007, pp. 355–367.
61.
BrandãoJ.Iterated Local Search Algorithm with Ejection Chains for the Open Vehicle Routing Problem with Time Windows. Computers & Industrial Engineering, Vol. 120, 2018, pp. 146–159.
62.
XiaY.FuZ.Improved Tabu Search Algorithm for the Open Vehicle Routing Problem with Soft Time Windows and Satisfaction Rate. Cluster Computing, Vol. 22, 2019, pp. 8725–8733.
63.
YuN.QianB.HuR.ChenY.WangL.Solving Open Vehicle Problem with Time Window by Hybrid Column Generation Algorithm. Journal of Systems Engineering and Electronics, Vol. 33, 2022, pp. 997–1009.
64.
ZhengJ. G.YangQ.ChenS. L.Research on the Distribution of Emergency Supplies During the COVID-19 Epidemic. Complexity, Vol. 2023, 2023, p. 9023040. https://doi.org/10.1155/2023/9023040.
65.
WangC.MaH.ZhuD.HouY.A Hybrid Genetic Algorithm for Multi-compartment Open Vehicle Routing Problem with Time Window in Fresh Products Distribution. Engineering Letters, Vol. 32, No. 6, 2024, pp. 1213–1220.
66.
NorouziN.Tavakkoli-MoghaddamR.GhazanfariM.AlinaghianM.SalamatbakhshA.A New Multi-objective Competitive Open Vehicle Routing Problem Solved by Particle Swarm Optimization. Networks and Spatial Economics, Vol. 12, 2012, pp. 609–633.
67.
AmirA.The Open Vehicle Routing Problem with Time Windows Considering Driver’s Working Hour. International Journal for Research in Applied Science and Engineering Technology, Vol. 6, 2018, pp. 2908–2913.
68.
ZhangY.LiH.WangZ.WangH.A Multi-Objective Learning Whale Optimization Algorithm for Open Vehicle Routing Problem with Two-Dimensional Loading Constraints. Mathematics, Vol. 12, No. 5, 2024, p. 731. https://doi.org/10.3390/math12050731.
69.
NiuY.YangZ.ChenP.XiaoJ.Optimizing the Green Open Vehicle Routing Problem with Time Windows by Minimizing Comprehensive Routing Cost. Journal of Cleaner Production, Vol. 171, 2018, pp. 962–971.
70.
NiuY.YangZ.WenR.XiaoJ.ZhangS.Solving the Green Open Vehicle Routing Problem Using a Membrane-Inspired Hybrid Algorithm. Sustainability, Vol. 14, 2022, p. 8661. https://doi.org/10.3390/su14148661.
71.
ShenL.TaoF.WangS.Multi-Depot Open Vehicle Routing Problem with Time Windows Based on Carbon Trading. International Journal of Environmental Research and Public Health, Vol. 15, No. 9, 2018, p. 2025. https://doi.org/10.3390/ijerph15092025.
72.
BezerraS. N.de SouzaS. R.SouzaM. J. F.A General VNS for the Multi-Depot Open Vehicle Routing Problem with Time Windows. Optimization Letters, Vol. 17, 2023, pp. 2033–2063.
73.
YousefikhoshbakhtM.DolatnejadA.A Column Generation for the Heterogeneous Fixed Fleet Open Vehicle Routing Problem. International Journal of Production Management and Engineering, Vol. 5, 2017, p. 55.
74.
YousefikhoshbakhtM.DolatnejadA.DidehvarF.RahmatiF.A Modified Column Generation to Solve the Heterogeneous Fixed Fleet Open Vehicle Routing Problem. Journal of Engineering, Vol. 2016, 2016, p. 5692792. https://doi.org/10.1155/2016/5692792.
75.
SinghtaunC.PiyapornthanaH.A Mathematical Model and Solution Approach for a Heterogeneous Fleet Open Vehicle Routing Problem. International Journal of Geomate, Vol. 22, 2022, pp. 17–23.
76.
AhmedZ. H.YousefikhoshbakhtM.An Improved Tabu Search Algorithm for Solving Heterogeneous Fixed Fleet Open Vehicle Routing Problem with Time Windows. Alexandria Engineering Journal, Vol. 64, 2023, pp. 349–363. https://doi.org/10.1016/j.aej.2022.09.008.
77.
AhmedZ. H.YousefikhoshbakhtM.A Hybrid Algorithm for the Heterogeneous Fixed Fleet Open Vehicle Routing Problem with Time Windows. Symmetry, Vol. 15, 2023, p. 486. https://doi.org/10.3390/sym15020486.
78.
YousefikhoshbakhtM.DidehvarF.RahmatiF.AhmedZ. H.Fixed Fleet Open Vehicle Routing Problem: Mathematical Model and a Modified Ant Colony Optimization. Bulletin of the Polish Academy of Sciences Technical Sciences, Vol. 72, No. 1, 2021, pp. 123–135.
79.
AksenD.ÖzyurtZ.ArasN.Open Vehicle Routing Problem with Driver Nodes and Time Deadlines. Journal of the Operational Research Society, Vol. 58, 2007, pp. 1223–1234.
80.
López-SánchezA. D.Hernández-DíazA. G.VigoD.CaballeroR.MolinaJ.A Multi-Start Algorithm for a Balanced Real-World Open Vehicle Routing Problem. European Journal of Operational Research, Vol. 238, 2014, pp. 104–113.
81.
YuV. F.JewpanyaP.RediA. A. N. P.Open Vehicle Routing Problem with Cross-Docking. Computers & Industrial Engineering, Vol. 94, 2016, pp. 6–17.
82.
NaderipourM.AlinaghianM.Measurement, Evaluation and Minimization of CO2, NOx, and CO Emissions in the Open Time Dependent Vehicle Routing Problem. Measurement, Vol. 90, 2016, pp. 443–452.
83.
XiaY.FuZ.An Adaptive Tabu Search Algorithm for the Open Vehicle Routing Problem with Split Deliveries by Order. Wireless Personal Communications, Vol. 103, 2018, pp. 595–609.
84.
AzadehA.Farrokhi-AslH.The Close–Open Mixed Multi Depot Vehicle Routing Problem Considering Internal and External Fleet of Vehicles. Transportation Letters, Vol. 11, 2019, pp. 78–92.
85.
NirwanS.AbdullahM. H. L.RahimS. S.Postal Item Delivery Route Optimization Based on Close-Open Mix Vehicle Routing Problem. Journal of Positive Psychology and Wellbeing, Vol. 5, No. 3, 2021, pp. 219–226.
86.
WuX.HuD.MaB.JiangR.The Two Echelon Open Vehicle Routing Problem: Optimization of Crowdshipping Based Parcel Delivery. KSCE Journal of Civil Engineering, Vol. 26, 2022, pp. 4073–4085.
87.
ZhenL.TanZ.WangS.YiW.LyuJ.Shared Mobility Oriented Open Vehicle Routing with Order Radius Decision. Transportation Research Part A: Policy and Practice, Vol. 144, 2021, pp. 19–33.
88.
McDonaldJ. J.Vehicle Scheduling — A Case Study. Journal of the Operational Research Society, Vol. 23, 1972, pp. 433–444.
89.
DumasM. B.RabinowitzM.Policies for Reducing Blood Wastage in Hospital Blood Banks. Management Science, Vol. 23, 1977, pp. 1124–1132. https://doi.org/10.1287/mnsc.23.10.1124.
90.
YiJ.Vehicle Routing with Time Windows and Time-Dependent Rewards: A Problem from the American Red Cross. Manufacturing & Service Operations Management, Vol. 5, 2003, pp. 74–77.
91.
RevereL.Re-engineering Proves Effective for Reducing Courier Costs. Business Process Management Journal, Vol. 10, 2004, pp. 400–414. https://doi.org/10.1108/14637150410548074.
92.
DoernerK. F.GronaltM.HartlR. F.KiechleG.ReimannM.Exact and Heuristic Algorithms for the Vehicle Routing Problem with Multiple Interdependent Time Windows. Computers & Operations Research, Vol. 35, 2008, pp. 3034–3048. https://doi.org/10.1016/j.cor.2007.02.012.
93.
JørgensenP.JacobsenP.PoulsenJ. H.Identifying the Potential of Changes to Blood Sample Logistics Using Simulation. Scandinavian Journal of Clinical and Laboratory Investigation, Vol. 73, 2013, pp. 279–285.
94.
ElaloufA.TsadikovichD.HovavS.Optimization of Blood Sample Collection with Timing and Quality Constraints. International Transactions in Operational Research, Vol. 25, 2018, pp. 191–214.
95.
LiuY.WuF.LiuZ.WangK.WangF.QuX.Can Language Models be Used for Real-World Urban-Delivery Route Optimization?The Innovation, Vol. 4, No. 6, 2023, p. 100520. https://doi.org/10.1016/j.xinn.2023.100520.
96.
QuX.LinH.LiuY.Envisioning the Future of Transportation: Inspiration of ChatGPT and Large Models. Communications in Transportation Research, Vol. 3, 2023, p. 100103. https://doi.org/10.1016/j.commtr.2023.100103.
Supplementary Material
Please find the following supplemental material available below.
For Open Access articles published under a Creative Commons License, all supplemental material carries the same license as the article it is associated with.
For non-Open Access articles published, all supplemental material carries a non-exclusive license, and permission requests for re-use of supplemental material or any part of supplemental material shall be sent directly to the copyright owner as specified in the copyright notice associated with the article.
