Google Maps alapú új típusú megközelítés korlátos elosztási rendszer optimalizálására

Absztrakt

A fuvarszervezési probléma (VRP) egy komplex kombinatorikus optimalizálási feladat, ami a következőképpen írható le: adott a járművek egy halmaza, előre meghatározott, közös kapacitással, egy központi depó, és adottak vásárlói igények; a feladat egy minimális összköltségű útvonalhálózat keresése, mely az összes vásárlói igényt kielégíti. A többes utazóügynök probléma (mTSP) a jól ismert utazóügynök probléma (TSP) egy általánosítása, ahol egy vagy több utazóügynök lehet a feladat megoldásában. Ismeretes, hogy a mTSP alapú algoritmusok VRP-k megoldására is használhatóak, további kikötések definiálásával. Több egzakt algoritmus is létezik az irodalomban, melyek néhány megszorítás relaxációját tartalmazzák mTSP-nek. Ezen algoritmusok elméletileg igazolt optimumot szolgáltatnak. Az mTSP probléma kombinatorikus komplexitása miatt szükséges valamilyen heurisztika alkalmazása a megoldásban, különösen valós méretű feladatok esetén. Jelen munka célja annak tárgyalása, hogy hogyan alkalmazhatóak a genetikus algoritmusok ilyen típusú problémák megoldására. Áttekinti a korábbi megközelítéseket azok hátrányaival együtt, és ajánl egy újszerű reprezentáción alapuló megoldást, és több példán keresztül szemlélteti annak hatékonyságát. A cikk kitér a megvalósított szoftver megoldásokra is, bemutat egy új Google Maps API-n alapuló távolságmátrix-generáló programot, és egy kényelmes eszközt az eredmények megjelenítésére. Továbbá ajánl egy teljes keretrendszert és módszert valós elosztási feladatok megoldására. Az újszerű algoritmus, az új eszközök és a kapott útvonalhálózatok gazdaságilag hatékonynak bizonyulnak logisztikai problémák esetén, amelyet a cikk egy valós életből vett példán szemléletet.