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

  • András Király
  • János Abonyi
Kulcsszavak: mTSP, VRP, genetikus algoritmus, multi-kromoszóma, optimalizáció

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.

Megjelent
2010-02-15
Hogyan kell idézni
Király, A., & Abonyi, J. (2010). Google Maps alapú új típusú megközelítés korlátos elosztási rendszer optimalizálására. Acta Agraria Kaposváriensis, 14(3), 1-14. Elérés forrás http://journal.ke.hu/index.php/aak/article/view/1952

Ugyanannak a szerző(k)nek a legtöbbet olvasott cikkei

1 2 > >>