Utolsó mérföld szállítás több telephelyről Pythonban

Matematikai modellezés, megoldás és vizualizáció a PuLP és a VeRoViz segítségével

Az online vásárlás rohamos növekedésével a vállalatoknak egyre nagyobb igényekkel kell szembenézniük a gyors, alacsony költségű szállítás iránt. Utolsó mérföldes szállítás Az ellátási lánc utolsó szakaszára utal, amikor a csomagokat a raktárból a vevő portájáig szállítják. Ez egy összetett taktikai probléma, amely magában foglalja a csomagok tehergépkocsikhoz való hozzárendelésének és a teherautók ügyfelekhez való eljuttatásának közös meghatározását. Ez is egy nagyon drága probléma, a legfrissebb becslések az utolsó mérföldes szállítást a teljes szállítási költség 53%-ára helyezve. Ez aláhúzza a hatékony szállítási tervek létrehozásának szükségességét.

A probléma klasszikus formája egyetlen telephelyet (általában egy raktárt) foglal magában, ahonnan az összes teherautót berakodják és kiküldik. Egy bonyolultabb változatban több raktár található egymás közelében – például amikor a kiskereskedelmi láncok az üzlethelyiségekről szállítanak. Ebben az esetben előfordulhat, hogy egy adott ügyfelet több depó is kiszolgál, így a cégnek azt is meg kell határoznia, hogy mely telephelyekre milyen ügyfeleknek szállítanak ki. Előfordulhat, hogy egyetlen raktárban sem áll rendelkezésre az ügyfél megrendelésének összes tétele, ezért a rendelést több raktár között kell felosztani.

Az alábbiakban megvitatjuk, hogyan lehet modellezni és megoldani ezt a bonyolultabb többdepós problémaformát egészszámú programozás (IP). Ennek a problémának a következő aspektusai vannak:

1. Van egy sor teherautó, raktár, vásárló és termék.
2. Minden vásárló meghatározott mennyiséget rendelt minden termékből, és minden raktárban minden termékből bizonyos mennyiség áll rendelkezésre.
3. Minden teherautó pontosan egy raktárban található (azaz az útvonala mindig a bázisnál kezdődik és végződik). Ezen túlmenően a teherautóknak nem kell azonosaknak lenniük – minden teherautó eltérő kapacitású és kilométerenkénti költséggel rendelkezhet.

A cél az, hogy egyszerre meghatározzuk 1) az egyes telephelyekről az egyes ügyfelekhez szállítandó termékeket, 2) a csomagok tehergépkocsikhoz való hozzárendelését, és 3) az egyes teherautók vevőihez való eljuttatását, mindezt úgy, hogy a lehető legalacsonyabb összértéket érjük el. szállítási költség lehetséges.

Ezzel IP modellt fogunk megvalósítani és megoldani Pép És használni VeRoViz a teherautó-útvonalak megjelenítéséhez. Kezdésként importáljuk a szükséges könyvtárakat:

Egy példa forgatókönyv

Egy bútorgyártó cég két raktárral rendelkezik Fredericksburg, VA körzetében, és nyolc vevői rendelést kell kézbesíteni. Az adatok és a térkép lent látható. Jegyzet: A nodesArray változóval készült VeRoViz Sketch Tool, amely lehetővé teszi a helyadatok grafikus létrehozását és a Pythonba való exportálást.

A probléma modellezése

Bár számos módon megközelíthetjük ezt a problémát, egy egészszámú programozási modellt fogunk felépíteni és megoldani. Ez a probléma pontos matematikai specifikációját adja, és lehetővé teszi a közepes méretű problémapéldányok optimális megoldását készen lévő megoldók segítségével (bár a mi hatáskörünkön túlmenően, a nagyobb példányok gyakran nem oldhatók meg gyorsan készen lévő megoldókkal, és speciális megoldást igényelnek -megtervezett megoldási algoritmusok). Kezdjük a modell bemeneteivel:

Ezután meghatározzuk a döntési változóinkat:

Végül meghatározzuk az optimalizálási modellt:

Ebben a modellben a minimálisra csökkenteni kívánt célfüggvény (1) egyszerűen az összes felmerülő utazási költség összege. A (2) megszorítások biztosítják, hogy minden helyen, ha egy adott teherautó megérkezik a helyszínre, akkor a teherautó is elindul. A (3) pontban szereplő megkötések biztosítják, hogy egyetlen teherautó se induljon el olyan raktárból, amely nem a bázisa. A (4) pontban szereplő korlátozások biztosítják, hogy minden vásárló megkapja az összes megrendelt terméket. Az (5)-ben szereplő megszorítások biztosítják, hogy egyetlen útvonalon se forduljanak elő aláramkörök. Mivel az áramkört alkotó helyek egy csoportjának ugyanannyi éle lesz, mint a csomópontoknak, megakadályozzuk, hogy ez minden egyes teherautó esetében előforduljon az ügyfelek minden lehetséges, nem üres részében. A (6) pontban szereplő megkötések biztosítják, hogy minden egyes raktár és termék esetében a teherautókra rakott és az adott raktárból az ügyfeleknek szállított termék összmennyisége ne haladja meg a raktárban elérhető mennyiséget. A (7) pontban foglalt megkötések biztosítják, hogy egyetlen termék sem kerüljön berakodásra a teherautóba, és ne kerüljön kiszállításra az ügyfélnek, hacsak a teherautó nem látogatja meg az ügyfelet. A (8) pontban foglalt megkötések biztosítják, hogy az egyes teherautók esetében a fedélzetre rakott termékek összmennyisége ne haladja meg a kapacitását. Végül a (9–10) megszorításai meghatározzák a döntési változók tartományait (binárisan a x változók; nem negatív egész szám a u változók).

Az egyszerűség és az újrafelhasználhatóság érdekében létrehozunk egy Python-függvényt, amely ennek a modellnek a példányait állítja elő bizonyos bemeneti adatokhoz. Pép:

A példa forgatókönyv probléma megoldása

Most, hogy elkészítettük a modellt, felhasználhatjuk, hogy optimális megoldást találjunk a forgatókönyvünkhöz. Az alábbiakban a mellékelt CBC megoldót használjuk Pép. Ez 15-45 másodpercig tarthat, amíg megtalálja az optimális megoldást. Ha hozzáfér a hatalmasabbhoz CPLEX megoldó, használhatja helyette a megjegyzésekkel ellátott sorokat, hogy sokkal gyorsabban kapjon megoldást.

Ennek futtatása a következő kimeneti üzenetet adja:

A teherautó-útvonalak kibontása és megtekintése

Most ki kell kinyernünk a teherautó útvonalait a megoldott modell döntési változóiból. Minden egyes teherautó esetében tudni akarjuk a megállóhelyeit, és azt, hogy az egyes megállókban milyen termékeket kell szállítani. Ahhoz, hogy ezt az információt megkapjuk, át kell szűrnünk a nem nulla döntési változókat.

Ez összeállítja a következő teherautó-útvonalakat:

Ne feledje, hogy a C1 ügyfelet két teherautó (T2 és T4) keresi fel – tehát osztott rendelés. Tekintettel az egyidejű vásárlói igényekre és a rendelkezésre álló erőforrásokra, ez optimális döntésnek bizonyul. Erre akkor is szükség lehet, ha például egy megrendelés olyan tételeket tartalmaz, amelyek egyetlen raktárban sem találhatók meg.

A teherautó-útvonalak vizualizálása

Utolsó lépésként használjuk VeRoViz szép vizualizáció létrehozásához a kamionok útvonalaihoz:

Következtetés

Bár ennek a problémának számos változata lehetséges, ez a példa bemutatja, hogyan modellezhetünk és oldhatunk meg egy ilyen problémát egész számok programozásával. Azt is bemutatja, hogyan használható a Python erős komponensek összeragasztására, mint pl Pép és a VeRoViz hasznos döntéstámogató rendszerek gyors létrehozásához. Boldog szállítást!

A forráskód egy notebookban megtekinthető itt vagy letöltve itt.

Last Mile Delivery from Több telephelyről a Pythonban újraközölve a következő forrásból: https://towardsdatascience.com/last-mile-delivery-from-multiple-depots-in-python-26c4325407b4?source=rss—-7f60cf5620c9—4 felé datatascience.com/feed

<!–

->