Tiered-facility vehicle routing problem with global cross-docking
Date
2018-03
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
ENGLISH ABSTRACT: The service delivery of public healthcare is severely threatened due to insu cient resources.
A current South African public healthcare organisation responsible for processing pathological
specimens makes use of a public transportation network containing laboratories of multiple tiers
corresponding to different processing capabilities in its business model. The effective transportation
of specimens between facilities in this network may potentially lead to significant financial
cost savings.
The quest to establish a mathematical model for the transportation of specimens in this transportation
network has led to the formulation of a novel variant of the celebrated vehicle routing problem (VRP) in the operations research literature, called the tiered-facility vehicle routing problem with global cross-docking (TVRPGC). This tri-objective combinatorial optimisation
problem calls for the efficient route scheduling of a vehicle
eet tasked with the transportation of pathological specimens. The objectives of the model are to minimise the total distance covered by the fleet (so as to save on transportation variable costs), to minimise the number of vehicles required for specimen collection (so as to save on transportation fixed costs), and to minimise
the travel time of the vehicle which spends the longest time on the road (so as to ensure specimen
integrity and balance driver workload). The model constraints take into account maximum driver autonomy (a constraint on the time a vehicle may spend on the road), specimen collection demand, permissible workloads at the various facilities in the network of processing laboratories, and requirements in terms of which laboratories are capable of processing the various specimens.
Crucially, the model also allows for the novel feature of local hand-over of specimens at facilities between vehicles.
The aforementioned model is validated, and exact and approximate solution techniques are developed for the model and implemented on a computer. These techniques draw inspiration from a thorough study of the prototype VRP in the literature | the capacitated VRP.
Investigations are launched into (i) the computational complexity of the exact solution procedure,
(ii) the quality of solutions returned by the approximate solution technique with respect to a real-life instance of the TVRPGC within a South African pathology healthcare service provider context, and (iii) the desirability of a facility clustering-based approach toward decomposing
instances of the TVRPGC into smaller problem subinstances.
AFRIKAANSE OPSOMMING: Dienslewering in publieke gesondheidsorg word noemenswaardig deur onvoldoende hulpbronne gekniehalter. 'n Huidige Suid-Afrikaanse gesondheidsorg-organisasie wat verantwoordelik is vir die analasie en verwerking van patologiese monsters maak van 'n publieke vervoernetwerk met laboratoria van verskeie verwerkingskapasiteite in sy besigheidsmodel gebruik. Die doeltreffende vervoer van monsters tussen fasiliteite in hierdie netwerk mag potensieel tot beduidende finansiële kostebesparings lei. Pogings tot die daarstelling van 'n wiskundige model vir die verskeping van monsters in hierdie vervoernetwerk het gelei na die formulering van 'n nuwe variasie op die gevierde voertuigroe- teringsprobleem (VRP) in die operasionele navorsingsliteratuur wat as die veelvlakkige-fasiliteit voertuigroeteringsprobleem met globale kruiskonsolidasie (VVRPGK) bekend staan. Hierdie driedoelige kombinatoriese optimeringsprobleem vra na die doeltreffende roete-skedulering van 'n vloot voertuie geoormerk vir die verskeping van patologiese monsters. Die doele van die model is om die totale afstand wat deur die vloot voertuie afgelê word, te minimeer (besparing van verskepingsveranderlike-koste), om die getal voertuie in die vloot wat vir monsterverskeping benodig word, te minimeer (besparing van verskepingsvastekoste), en om die tydsduur van die voertuig wat die langste tyd op die pad deurbring, te minimeer (handhawing van monsterintegriteit en die balansering van voertuigbestuurderwerkslading). Die modelbeperkings neem in ag die maksimum bestuurderoutonomie ('n beperking op die tydsduur wat 'n bestuurder op die pad mag deurbring), aanvraag na monsterverskeping, toelaatbare werksladings by die onderskeie fasiliteite in die netwerk van verwerkingslaboratoria, en vereistes in terme van watter laboratoria daartoe in staat is om die onderskeie monsters te verwerk. Die kruks van die model is egter die nuwe kenmerk waarvolgens lokale kruiskonsolidasie van monsters tussen voertuie by enige fasiliteit toegelaat word. Die bogenoemde model gevalideer daar word ook eksakte en benaderde oplossingstegnieke vir die model ontwikkel en rekenaarmatig geïmplementeer. Hierdie tegnieke vind inspirasie uit 'n deeglike studie van die prototipe VRP in die literatuur | die gekapasiteerde VRP. Daar word ondersoek ingestel na (i) die berekeningskompleksiteit van die eksakte oplossingsmetodologie, (ii) die kwaliteit van oplossings gelewer deur die benaderde oplossingstegniek in die konteks van 'n realistiese VVRPGK geval in die Suid Afrikaanse patologiese gesondheidsdiens, en (iii) die wenslikheid van 'n fasiliteitsgroeperingsbenadering tot dekomposisie van VVRPGK gevalle na kleiner probleemdeelgevalle.
AFRIKAANSE OPSOMMING: Dienslewering in publieke gesondheidsorg word noemenswaardig deur onvoldoende hulpbronne gekniehalter. 'n Huidige Suid-Afrikaanse gesondheidsorg-organisasie wat verantwoordelik is vir die analasie en verwerking van patologiese monsters maak van 'n publieke vervoernetwerk met laboratoria van verskeie verwerkingskapasiteite in sy besigheidsmodel gebruik. Die doeltreffende vervoer van monsters tussen fasiliteite in hierdie netwerk mag potensieel tot beduidende finansiële kostebesparings lei. Pogings tot die daarstelling van 'n wiskundige model vir die verskeping van monsters in hierdie vervoernetwerk het gelei na die formulering van 'n nuwe variasie op die gevierde voertuigroe- teringsprobleem (VRP) in die operasionele navorsingsliteratuur wat as die veelvlakkige-fasiliteit voertuigroeteringsprobleem met globale kruiskonsolidasie (VVRPGK) bekend staan. Hierdie driedoelige kombinatoriese optimeringsprobleem vra na die doeltreffende roete-skedulering van 'n vloot voertuie geoormerk vir die verskeping van patologiese monsters. Die doele van die model is om die totale afstand wat deur die vloot voertuie afgelê word, te minimeer (besparing van verskepingsveranderlike-koste), om die getal voertuie in die vloot wat vir monsterverskeping benodig word, te minimeer (besparing van verskepingsvastekoste), en om die tydsduur van die voertuig wat die langste tyd op die pad deurbring, te minimeer (handhawing van monsterintegriteit en die balansering van voertuigbestuurderwerkslading). Die modelbeperkings neem in ag die maksimum bestuurderoutonomie ('n beperking op die tydsduur wat 'n bestuurder op die pad mag deurbring), aanvraag na monsterverskeping, toelaatbare werksladings by die onderskeie fasiliteite in die netwerk van verwerkingslaboratoria, en vereistes in terme van watter laboratoria daartoe in staat is om die onderskeie monsters te verwerk. Die kruks van die model is egter die nuwe kenmerk waarvolgens lokale kruiskonsolidasie van monsters tussen voertuie by enige fasiliteit toegelaat word. Die bogenoemde model gevalideer daar word ook eksakte en benaderde oplossingstegnieke vir die model ontwikkel en rekenaarmatig geïmplementeer. Hierdie tegnieke vind inspirasie uit 'n deeglike studie van die prototipe VRP in die literatuur | die gekapasiteerde VRP. Daar word ondersoek ingestel na (i) die berekeningskompleksiteit van die eksakte oplossingsmetodologie, (ii) die kwaliteit van oplossings gelewer deur die benaderde oplossingstegniek in die konteks van 'n realistiese VVRPGK geval in die Suid Afrikaanse patologiese gesondheidsdiens, en (iii) die wenslikheid van 'n fasiliteitsgroeperingsbenadering tot dekomposisie van VVRPGK gevalle na kleiner probleemdeelgevalle.
Description
Thesis (PhD)--Stellenbosch University, 2018.
Keywords
Metaheuristics, UCTD, Vehicle routing problem, Linear programming, Pathology -- Specimens -- Transportation, Docking