Last Mile-leverans från flera depåer i Python

Matematisk modellering, lösning och visualisering med hjälp av PuLP och VeRoViz

Med den snabba tillväxten av onlinehandel står företag inför ständigt ökande krav på snabb leverans till låg kostnad. Sista milleverans syftar på slutskedet av försörjningskedjan, där paket levereras från en depå till kundens dörr. Detta är ett komplext taktiskt problem som innebär att man gemensamt bestämma hur man ska tilldela paket till lastbilar och hur man dirigerar lastbilarna till kunder. Det är också ett mycket dyrt problem, med senaste uppskattningar placera sista milen leverans till 53% av den totala fraktkostnaden. Detta understryker behovet av att skapa effektiva leveransplaner.

Den klassiska formen av detta problem innebär en enda depå (vanligtvis ett lager) från vilket alla lastbilar lastas och skickas ut på sina leveranser. En mer komplex version innebär flera depåer i närheten av varandra - till exempel när butikskedjor levererar från butikslägen. I det här fallet kan en given kund betjänas av mer än en depå, så företaget måste också bestämma vilka depåer som ska skicka till vilka kunder. Ibland kommer ingen enskild depå att ha alla artiklar i en kunds beställning tillgängliga, vilket kräver att beställningen delas upp på flera depåer.

Nedan kommer vi att diskutera hur man modellerar och löser denna mer komplexa problemform med flera depåer med hjälp av heltalsprogrammering (IP). Detta problem har följande aspekter:

1. Det finns en uppsättning lastbilar, depåer, kunder och produkter.
2. Varje kund har beställt en specifik mängd av varje produkt, och varje depå har en viss mängd av varje produkt tillgänglig.
3. Varje lastbil är baserad på exakt en depå (vilket innebär att dess rutt alltid börjar och slutar vid basen). Dessutom behöver lastbilar inte vara identiska – varje lastbil kan ha olika volymkapacitet och kostnad per mil.

Målet är att samtidigt bestämma 1) produkterna som ska skickas från varje depå till varje kund, 2) hur man tilldelar paket till lastbilar och 3) hur man dirigerar varje lastbil till sina kunder, allt på ett sätt som uppnår lägsta totalsumma leveranskostnad möjlig.

Vi kommer att implementera och lösa en IP-modell med Massa Och använda VerRoViz för att visualisera lastbilsrutter. Till att börja med importerar vi de nödvändiga biblioteken:

Ett exempelscenario

Ett möbelföretag har två depåer i Fredericksburg, VA-området med åtta kundorder som ska levereras. Data och karta visas nedan. Notera: Smakämnen nodesArray variabel bereddes med VeRoViz Sketch Tool, som möjliggör grafiskt skapande av platsdata och export till Python.

Modellera problemet

Även om det finns ett antal sätt man kan närma sig detta problem, kommer vi att bygga och lösa en heltalsprogrammeringsmodell. Detta ger en exakt matematisk specifikation av problemet och gör att probleminstanser av måttlig storlek kan lösas optimalt med hjälp av vanliga lösare (även om större instanser ofta inte kan lösas snabbt med vanliga lösare och kräver speciellt -designade lösningsalgoritmer). Vi börjar med modellingångarna:

Därefter definierar vi våra beslutsvariabler:

Slutligen definierar vi optimeringsmodellen:

I denna modell är den objektiva funktion (1) som vi vill minimera helt enkelt summan av alla uppkomna resekostnader. Restriktioner i (2) säkerställer att för varje plats, om en viss lastbil anländer till platsen, så avgår även lastbilen. Restriktioner i (3) säkerställer att ingen lastbil avgår från en depå som inte är dess bas. Begränsningar i (4) säkerställer att varje kund får alla produkter de beställt. Restriktioner i (5) säkerställer att inga underkretsar uppstår i någon rutt. Eftersom en grupp platser som bildar en krets kommer att ha samma antal kanter som noder, förhindrar vi att detta inträffar i alla möjliga icke-tomma undergrupper av kunder för varje lastbil. Begränsningar i (6) säkerställer att för varje depå och produkt, de totala enheterna av produkten som lastas på lastbilar och skickas till kunder från den depån inte överstiger tillgängligheten vid depån. Restriktioner i (7) säkerställer att inga enheter av någon produkt lastas på en lastbil och skickas till en kund om inte lastbilen besöker kunden. Begränsningar i (8) säkerställer att för varje lastbil, den totala volymen av produkter som lastas ombord inte överstiger dess kapacitet. Slutligen anger begränsningar i (9–10) domänerna för beslutsvariablerna (binär för x variabler; icke-negativt heltal för u variabler).

För enkelhet och återanvändbarhet kommer vi att skapa en Python-funktion för att konstruera instanser av denna modell för specifika indata med hjälp av Massa:

Lösning av exempelscenarieproblemet

Nu när vi har formulerat modellen kan vi använda den för att hitta en optimal lösning för vårt scenario. Nedan använder vi CBC-lösaren som medföljer Massa. Det kan ta 15–45 sekunder att hitta en optimal lösning. Om du har tillgång till de mer kraftfulla CPLEX solver, kan du använda de kommenterade raderna istället för att få en lösning mycket snabbare.

Att köra detta ger oss följande utdatameddelande:

Extrahera och visa lastbilens resplaner

Nu behöver vi extrahera lastbilens resplaner från beslutsvariablerna i den lösta modellen. För varje lastbil vill vi veta dess hållplatser och vilka produkter som ska levereras vid varje hållplats. För att få denna information måste vi sålla igenom beslutsvariablerna som inte är noll.

Detta skapar följande lastbilsresplaner:

Observera att kund C1 besöks av två lastbilar (T2 och T4) - alltså en delad order. Med tanke på de samtidiga kundkrav och resurser som finns tillgängliga visar sig detta vara ett optimalt beslut. Detta kan också vara nödvändigt när, till exempel, en order innehåller en uppsättning artiklar som inte finns på någon enskild depå.

Visualisera lastbilsrutter

Som vårt sista steg använder vi VerRoViz för att skapa en snygg visualisering för lastbilsrutter:

Slutsats

Även om många varianter av detta problem är möjliga, illustrerar detta exempel hur vi kan modellera och lösa ett sådant problem med hjälp av heltalsprogrammering. Den visar också hur Python kan användas för att limma ihop kraftfulla komponenter som t.ex Massa och VerRoViz att snabbt skapa användbara beslutsstödssystem. Glad leverans!

Källkoden kan ses i en anteckningsbok här. eller laddas ner här..

Last Mile Delivery från flera depåer i Python Återpublicerad från källa https://towardsdatascience.com/last-mile-delivery-from-multiple-depots-in-python-26c4325407b4?source=rss—-7f60cf5620c9—4 via https:// mot datascience.com/feed

<!–

->