Algorithmes de tournées de véhicules pour l'optimisation des flux de produits et de patients dans un complexe hospitalier, Vehicle routing algorithms to optimize product flow and patients flow in a hospital complex

Yannick Kergosien

Description

Sous la direction de Jean Charles Billaut
Thèse soutenue le 05 juillet 2010: Tours
Cette thèse est une illustration de problèmes de Recherche Opérationnelle abordés dans le contexte hospitalier du CHRU de Tours. La problématique considérée relève des transports et plus exactement de tournées de véhicules. Cette thèse s'articule autour de l'étude de deux principaux problèmes : le transport de flux de produits et le transport de flux de patients. Le premier problème de tournées de véhicules concerne toute la gestion des différents types de flux logistiques (logistique hôtelière, pharmacie, lingerie,plateaux repas, etc.) à livrer ou à collecter dans les services de soins de chaque hôpital du CHRU de Tours. Le deuxième problème concerne les transports de patients aussi bien urgents (SAMU) que planifiés (Centrale des ambulanciers). Pour résoudre ces problèmes, plusieurs méthodes s'inspirant des techniques de la RO sont proposées : des méthodesexactes (programmation linéaire en nombres entiers), des heuristiques (algorithme glouton, recherche tabou avec et sans mémoire adaptative, algorithme génétique, algorithme mémétique) et des moteurs de simulation à événements discrets ont été développés. Des expérimentations numériques valident l'intérêt et la qualité des méthodes développées.
-Tournées de véhicules
This thesis illustrates the OR problems found in a general hospital context like the hospital complex of Tours. The problem is addressed in this thesis is a vehicle routing problem. This work focuses on the study of two main problems : the transportation of patient and the transportation of commodities. The first problem of vehicle routing deals with the logistics flows in an hospital complex (clean linen, meals carts, medicines, sterile equipments, etc.) which are to be delivered or picked up in the hospital units, locatedat different places in the city. The second problem deals with the emergency patient transport (Emergency Medical Assistance Service) as well as with the planned transports (ambulance central station). To solve these problems, several methods based on techniques of OR are proposed: exact methods (integer linear programming), heuristics (greedyalgorithm, tabu search with and without adaptive memory, genetic algorithm, memetic algorithm), and discrete event simulations.
Source: http://www.theses.fr/2010TOUR4010/document

Informations

• Publié par: Thesee
• Nombre de lectures: 61
• Langue: Français
• Poids de l'ouvrage: 5 Mo

Extrait

aUNIVERSIT?renFRAN?OISfRABELAISTDEUnivTOURSUniv?COLEConf?rences,DOCTORALEersit?SSTJURLABORAelaisTOIRESainD'INFerrand,ORMANanTIQUEours,:ICDEA2101DominiqueEQUIPETORDONNANCEMENTUTETersit?CONDUITEFEILLETTH?SE?colepr?senGANDt?eascalparMa?tre:?coleYLENT?annicran?oiskProfesseur,KERTGOSIENDESMAZESsoutencuequalit?leusagers,:es,5:JuilletProfesseur2010Unipran?oisourours,obtenirPlesgradeMinesdeCMP:helDoBlaisecteurClermondeGU?RETl'univConfersist?MinesFIRran?oisMa?tre-ersit?RabelaiselaisPRINSDiscipline/ersit?Sphnologie?cyiINVITEaProfesseur,llait?CEREGE-LR-MOS:deInformatiquedesAlgorithmesecdeUtourn?esydeICDvY?hiculesBILLApJean-Charlesourdesl'optimisationersit?s,desvuxFdeRabproTduitsLIetDominiquederopatienetsseur,dansdesundecomplexet-Etienne,hospitalierGOURTH?SEMicdirig?eProfesseur,persit?arP:deBILLAt-FUTLIMOSJean-CharlesChristelleProfesseur,deUniv?ersit?ceF,ran?oisdesRabdeelaistes,TCCyNours,ChristopheLIdeRAPPORUnivTEURSF:RabFEILLETTDominiqueLIPChristianroUnivfdeeecsdeseur,ro?colees,desMEMBREMines:deJeanSainUnivt-Etienne,deCMPRoPRINShelle,ChristianOSUProfesseur,DirectionUnivlaersit?etderelationsTvecleshnologieCHRdedeToursrooratoRemerciemenoirtsAndr?Aran-vjeanttvtout,dejeettien?ga-sBarat,?traremercierPmesetencadranueltstsdets.th?se,deChristopheduranLenLamt?hilippetLJeantCharlesdepuisBillaut,etpqu'?ourlesm'aqveux,oirkaeuitousd?,pass?encouragu?,traorienjet?etetTconseill?vduranPiton,tJaulin,cesheltroisGautier,ann?es.remerciemenGr?celes?emleursj'aiconseils,ans,leursccommensonneltaires,(d?partemenleursProust.connaissantcl'?quipesoratoireetl'uleurTbtonneT'Kindthecumeur,momenj'aihangesputh?se.menerctoran?vbienbcettelesth?se,enprogresserparticipetmes?largirpr?s.mesBardu.connaissancestdansm'onleann?es.mmondteGuillou,de,laLouisrecPhilipphercBailloux,heGadesaudes,enPg?n?ralemCharles,aiseux.surtoutvdans?leersonnesdomainel'endetlaailRecyhercdehsaeenseignanOperc?rationnelle.pJederemercieh'Tainformatique)udirecteurssiremerciemencthaleureusemenerstbreslesOrdonnancemenmemdubres'Informadeemonersit?juryRab:PDominiqueremercieFSoukhal,eilletVincenetPChristianaPrinsj'aiquibm'onettesfaitinl'honnoureurremercied'accepterddedurappreorterlesquelscettetth?se.moJejeremerciets?galemenjtdMiconhel?Gourgandauxd'ahercvouoirnpPr?oursspid?maceamisjurysoutenetcesChristelleran?oisGu?retournamilled'enaisalemenvYoiresfaitAlainpartie.yMesDanielremerciemenJeantsGigot,vCousin,onetAnne-MarieaussiP?eJeanMicDesmazesMorisset,sansascalquiThicetterryth?seNathalien'auraitJean-LouispasedeuMeslieutsainsionqueaussiDominiquetoutesOsuppappartenanour?nousvironnaenvdeoirv"ouvqueertc?toles?pplusortestroisdu?CHRvU".lesEnn,tsjehremercieheursleleConseiler-G?n?raladministratifd'Indrel'?coleetolytecLoireoursptourainsilesonnancemenChristiantCesquitsmon'?galemenav?t?tousaccord?mempdeoureletbConduiteonLabd?roulemendttideucettedeth?se.niv"CommenFt?ois?tudierelaisdesours.probl?mesarmihjeoparticuli?remenspAmeuritaliersEmmanconcretsN?ron,sitpeteatricrsMartineauovnlesquelsnepass?netr?svonoustlesj'aiex-dpliquen?cttr?s?",t?ressanainspimajeJetiensaussisinc?remenlesto?tsremeLabrciiearectoutesj'ailes?galemenpdeersononsnesmenduEnnCHRremercieU?tudiandqeeT'aiourscaquir?sm'onquittaccord??uncertainstempvsdepr?cieuxrecphes,ourloinm'aiderde?Ed?nirparticulier,etremercie?tudieretercesPprobl?mes.terminer,Jeremercietiens?cialemenparticuli?rementoutetfamille?mesrequimerciertSandrineuPterrintroiset3Jean-F4REMERMENTSCIEi?R?sum?bulancesL'organisation(Cendesg?n?tique,syst?mesutenhospitalierstralen?cessiteexactesdesTprisespdeconcerned?cisionplus?probl?meplusieursdesni-glouton,veloppeaux,pqu'ilsdesoienmentdestrat?giquesicomunemebulanciersleMaisdimensionnemenortstcesd'?quiptesenouecplus?opOp?rationnelsPcomme5lalaplanicationdansdecr?ationtourn?es.eLesrestecdeuxi?mehniquesdeet(SAMU)lesbuoutilssionnemendedelaSAMURecbulanciers,hercphetempsOp??ration-U.nellem?thoplaeuvdenpttiers),fournirtabuneadapta-aidemoteurdansdiscretsces:priseshospitalierdeded?cision.deCettetsth?selesesttsuneutualiillustrationpdemesurel'applicationetdesletecd'unehniquesmadeaRunOtaille.dansabletranspcontstexteurgenhospitalierpdudesCHRD'uneUdeded'eectifsTenours.dD'untreelafa?onag?n?rale,plapartprobl?matiqueaussiabtationord?edesppatienorteauxsuurourl'opplutimisations'inspirandeshniquestourn?esOdeos?esvm?tho?d?leshgrammationi-brescules.heuristiquesCettehercth?seas'sansaes,rtim?m?tique).culesimautour?nemend?t?eMotsl'?tudehercde;deuxOptimisationp?erincipaux?hiculesprobl?mesb:ortsletitraLogistiquentrespdortrendeh?pitaux,uxmdesationprotransduitsorts,etlaledutranspossibleortladeetpatiendimensionne-ts.tCes?quipprobdel?mnestionnprennenitdansuneh?pitalimpgrandeortanceLeparticuli?reprobl?meauord?seinlesduortsCHRpatienUaussdebienTtsoursquedulani?sfaittralequ'ilamestlanciers).comppart,os?questionddimen-etplusieursouh?pitauxexactem?parpill?stsurr?partitiontoute'amlaenvillele.etLeCenpremierdesprobl?memconcernesetouteose.ld'autreasegestionosedesundi?rend'aec-tsentr?elyptranspesdedetsuxr?aliserlogistiquesam(logistiquedh?teli?re,CHRpharmacie,Plingerie,r?soudreplateauxprobl?mes,repas,sieursedestc.t)tec?delivrerRouson?propcollecter:danseslesdesservices(modedesoinsrodlin?aireenomcen-haquedesh?pital(algorithmedurecCHheRouUvdeetTm?moireours.tivCettealgorithmeprobl?matiquealgorithmes'inscritUndansdelulatione?vcadretsd'unea?tuded?vsur?.lacl?sr?organisationRecdehela?rationnellelogistiqueComplexedu;CHR;U.ournCettesr?organi-vsation;pr?vrooitl?melatranspre-planicationdedesatourn?esende;vhospitali?re.?hiculesen6R?SUM?:
:
theytabupcenroblemspofquestionorganization,vplanning,Researcdesignpandtheespbulaneciallyproblemoptimizationbareevpresproblemeossible,nThetcalinstation).aofgeneraleenhospitalrealconytext.basedThesetegerproblemsmemoryoftenoleadOptimizationtodierendecision-makingtranspproblemsofthaaeattranspcanwb(ameosolvitedbbersonsyandopseconderationalproblem,researcofhotecsevhniques.hniquesThissedthesisramming),isandthmemeticesimORordsproblemscomillus-routingtration;foundhospitals,inolingawhengeneralthehospitalwconteamtexthManproblemtheshospitalpatiencomplex(EmergencyofService)Tasours.transpThecenproblemsrststudiedisinfthisthethesisndealofwithevetehicleemergencyroutingamproblemsstation.andismoreassignmenpreciselyregardswithtranspthetstbulances.woothesefollomethowinORgvpproproblemsds:ptransp(greedyortationhofadaptivcommogeneticditiesandandntranspao.rtationOpof;patienlexts.VThesetranspproblemspatienaLogistics.retquitetheimpoortanoftortforptheandhospitalcreationcomplexaofarehouseTersonsoursinsidesincelargetheospital.lattersecondisdcomplosedwithofemergencysevteralortationhMedi-oAssistancesaspitalellunitswithscatteredplannedallortsaroundbulancethetraltoThewn.questiThenrstavoehidesign,cregardsldistributionetheroutingumproblemerdealsamwithctheplogisticsbowwstheinservicethethehospitalbulancecom-tralplexThe(cleanquestionlinaen,timemealtcarts,itmedicines,thesterileofequipmenortationts,patienetc.),bdelivameryTorspiclkupeinproblems,theeralhospitaldsunits,onloteccatedhaatedeeniereoAbstractexactnmethot(inplaceslinearinrogtheheuristicscitalgorithm,ysearc.withThiswithoutstudyeis,partalgorithm,ofalgorithm),adiscreteproejecttofulreorganizationtiofntheKeywlogistics:oerationalws.hThisHospitalreorganizationpincludes;a;vehiclesehicle;routingortationproblemofbtsetHospitalw7een8ABSTRACT.T.able.des.mati?res.In.tro.duction.g?n?rale.19.La.RPeLac.herc1.2.9he32Op34?Leration.nelle39etetle.milieu.hospitalier........ou.......SA...........CHR....19.Quelques.illustrations.de.la.R.Olaa.p.pliqu?e.au.milieu.hosp.italier..Les...............des..20.Ob.jettraleet.plan.de.la.th?se......1.4.ours.....isation.........................de.on.9...........30........22.1.Pr?sen.tation.du31con?textecollecteret.des.probl?matiques.25.1.1.Concastexte.hospitalier.?.T.ours......Cen.bulanciers.............La.Am...........34..................26probl?matiques1.2deLa.Logistique........R?orga.la...........1.4.2.................1.5...................I.43.t.probl?me.4..27.1.2.1.Les.arc.hi.v.es..........1.2.7.salubrit?.................................1.2.8.services.livrer.?............27.1.2.2.La.blanc.hisserie31.Le.Bretonneau.............................1.3.trale.am.et.MU..................29.1.2.3.L'UCP1.3.1ACen.des.bulanciers.......................1.3.2.SAMU.................................37.Deux.au29U1.2.4TLa.pharmacie..................1.4.1.n.de.logistique.....................39.CA.SAMU............30.1.2.5.La.st?rilisation............40.Conclusion.....................................42.Flux.mati?res.2.osi30i1.2.6duLadeLogistiquelogistiqueH?teli?re5..existanT.ABLE.DES.MA.TI?RES.2.1.Pr?sen.tation.g?n?rale............tes.......................PLNE.m?ta-heuristiques...e.......70...des...des....45.2.1.1.Rapp.el.de.lavprobl?matique..ou.........................Mo.appliqu?.....91.......e..45.2.1.2.Ob.jectif.d.e75l'?tude......Mutation.......herc.........d'un.....3.4.2.......78.........exp.......7846.2.2.Litt?rature.autourR?sultatsde.ce.p.roR?sultatsb.l?me..3.6.........4.des.87.oth?ses.....Impacts.....................Initialisation.opulation49.2.2.1.In.tro.duction.aux3.3.3probl?mes.d.e.transp.orts......Croisemen.............75.individus........50.2.2.2.Probl?mes3.4detabtransp.o.rts.connexes..........3.4.1.solution...........?rateur..............52Liste2.2.3.Probl?mes.de.transp.o.rts.dans.le.milieu3.5hospitaliertaux...............G?n?ration....54.2.3.Conclusion....79.our.............80.our...............................des.dimensionnemen.es.ap-.Con.h.mo........56873lesOptimisation.des.t.ou.rn?es.et.dimensionnemenAlgorithmet.des.?quip.es.:.Mo.d?le.ex-93ploratoire.59.3.1.D?nition.et.notation3.3.2dud'unprobl?mep.......................74.S?lection.individus..................59.3.2.PLNE....3.3.4.t.individus.........................3.3.5.des...........................76.Rec.he.ou........61.3.2.1.Les.v.ariables................7