Vi föreslår och analyserar en allmän matematisk modell för dynamiska, stokastiska fordon routing problem som vi kallar den dynamiska resande reparatörer problem (DTRP). Modellen motiveras av tillämpningar där målet minimerar väntan på service i en stokastisk och dynamiskt föränderlig miljö. Detta är en avvikelse från traditionella fordon routing problem som försöker minimera total restid i en statisk, deterministisk miljö. Möjliga tillämpningsområden är reparation, inventering, räddningstjänst och schemaläggningsmodeller. DTRP definieras på följande sätt: Efterfrågan på tjänster anländer enligt en Poissonprocess i en Euclidean region A och vid ankomsten är självständigt och enhetligt tilldelade en plats i A. Varje efterfrågan kräver en oberoende och identiskt distribuerad tjänst av ett fordon som färdas med enhetshastighet. Problemet är att hitta en politik som minimerar den genomsnittliga tid en efterfrågan spenderar i systemet. Vi föreslår flera policyer för DTRP och analysera deras beteende. Med hjälp av metoder från köteori, geometrisk sannolikhet, kombinatorisk optimering och'simulering, finner vi en påtagligt optimal policy i lätt trafik och flera policyer som har systemtider inom en konstant faktor för den optimala politiken i tung trafik. Vi visar också att väntetiden växer mycket snabbare än i traditionella köer när trafikintensiteten ökar, men stabilitetstillståndet beror inte på systemets geometri.
En av de tidiga versionerna av ett DVR-problem är Dynamic Traveling Repairperson Problem REF där målet är att minimera den förväntade tiden för varje efterfrågan innan den serveras.
A Stochastic and Dynamic Vehicle Routing Problem in the Euclidean Plane
{'venue': 'Oper. Res.', 'journal': 'Oper. Res.', 'mag_field_of_study': ['Computer Science', 'Mathematics']}