Constrained Time-Critical Routing For Multiple Mobile Agents

摘要

IntheInformationEra,integratingtechnologywiththereal-­‐worldenvironmentisatrendingparadigmthatattractsresearchersinmanyfields.Forexample,SmartCities’applicationsintegrateinformationtechnologywithexistinginfrastructurestooptimizemanyaspects,suchastime,energy,andcost.However,manydifficultiesshowup,includingatimeconstraintinsomeoftheapplicationswhenitisimplementedintherealworld.Oneoftheseapplicationsissmarttransportation.ThisthesisexploresVehicleRoutingProblem(VRP)andintroducesavariantofVRPthatrelatestotimeconstraintscalledVRPwithTimeWindow(VRPTW).Firstly,theproblemisformulatedintoalinearmathematicprogramwiththeobjectiveofminimizingthenumberofagentsusedinroutingandminimizingthetimespentinagents’routing.AheuristicapproachsolvesthisproblembyusingacombinedofA*SearchandRuinandRecreatealgorithmstofindtheshortestpathforagents.Additionally,theLocalSearchAlgorithmisusedtominimizethenumberofagentsusedinrouting.Twocasestudiestestthisheuristicapproach:acasestudyinchangingnumberofnodes,andacasestudyinchangingnodes’duration.Theresultsarerepresentedinnumberstoshowthereducednumberofagentsandtimecost,whilegraphplotsshowtheagents’routings.