Abstract-Vi anser en flera depå, flera fordon routing problem med bränsle begränsningar. Vi får en uppsättning mål, en uppsättning depåer och en uppsättning homogena fordon, ett för varje depå. Depåerna får också fungera som tankstationer. Fordonen får tanka vid varje depå, och vårt mål är att bestämma en rutt för varje fordon med en minsta total kostnad så att varje mål besöks minst en gång av något fordon, och fordonen aldrig kör ut bränsle när det går sin rutt. Vi hänvisar till detta problem som Multiple Depot, Fuel-Constomed, Multiple Vehicle Routing Problem (FCMVRP). Detta papper presenterar fyra nya blandade heltal linjära programmering formuleringar för att beräkna en optimal lösning för problemet. Omfattande beräkningsresultat för en stor uppsättning fall presenteras också. Index Villkor-bränsle begränsningar; gröna fordon routing; elfordon; blandad linjär programmering; obemannade fordon routing I detta dokument utökar vi den klassiska flera depå, flera fordon routing problem (MDMVRP) att inkludera bränsle begränsningar för fordon. Vi får en uppsättning mål, en uppsättning depåer och en uppsättning fordon, där varje fordon till en början är stationerat vid en särskild depå. Depåerna fyller också rollen som tankstationer, och det är rimligt att anta att när ett fordon besöker en depå, tankar det till sin fulla kapacitet. Målet med FCMVRP är att fastställa en rutt för varje fordon som startar och slutar vid dess motsvarande depå så att (i) varje mål besöks minst en gång av något fordon, (ii) inget fordon tar slut på bränsle när det går sin väg, och (iii) den totala kostnaden för rutterna för fordonen minimeras. Några av ansökningarna för FCMVRP är färdplanering för obemannade luftfarkoster (UAV) [1]-[3], routing för elfordon baserat på platserna för laddningsstationer [4], [5], och routing för gröna fordon [6]. Några av dessa tillämpningsområden är utarbetade på följande avsnitt. Små UAV används rutinmässigt i militära tillämpningar som gränspatrullering, spaning och övervakningsexpeditioner samt civila tillämpningar som fjärranalys, trafikövervakning och väder- och orkanövervakning [7]–[9]. Även om det finns flera fördelar på grund av små plattformar för UAV, finns det resursbegränsningar på grund av deras storlek och begränsad nyttolast. Det kanske inte är möjligt för en liten UAV att slutföra ett övervakningsuppdrag innan tankning vid en av depåerna på grund av bränslebegränsningarna. Betrakta till exempel ett typiskt övervakningsuppdrag med flera fordon som övervakar en uppsättning mål. För att slutföra detta uppdrag, fordonen kan behöva starta på sin † Graduate Student,
FCURP-MRS är en generalisering av flera fordon, flera depå, bränslebegränsade fordon routing problem som visas vara NP-hård REF, och därmed är också NP-hård.
Formulations and algorithms for the multiple depot, fuel-constrained, multiple vehicle routing problem
{'venue': '2016 American Control Conference (ACC)', 'journal': '2016 American Control Conference (ACC)', 'mag_field_of_study': ['Computer Science', 'Mathematics']}