arc routing problem

Angol

Főnév

arc routing problem (tsz. arc routing problems)

1. (informatika) Az Arc Routing Problem (ARP) – magyarul: él-alapú útvonaltervezési probléma – egy kombinatorikus optimalizálási probléma, amelyben egy gráf éleit (nem a csúcsait!) kell meglátogatni, karbantartani vagy kiszolgálni, miközben a megtett út teljes költségét minimalizáljuk. A probléma gyakori példái közé tartoznak az úttakarítás, szemétszállítás, hókotrás, postázás vagy utak festése.

---

🧠 1. Alapötlet

Ellentétben a legismertebb Travelling Salesman Problem (TSP)-mel, ahol csúcsokat kell meglátogatni, az ARP-ben élek (útszakaszok, útvonalak) azok, amelyeket be kell járni vagy karban kell tartani.

---

🔧 2. Problémaformulálás

Legyen adott:

• Egy irányított vagy irányítatlan gráf ${\textstyle G=(V,E)}$, ahol:
  • ${\textstyle V}$: csúcsok (kereszteződések)
  • ${\textstyle E}$: élek (utak)
• Az élekhez rendelt költségfüggvény ${\textstyle c(e)}$: pl. távolság, idő, üzemanyag
• Egy kiindulási pont (pl. raktár, telephely)
• Egy részhalmaz ${\textstyle R\subseteq E}$: a kötelezően bejárandó élek

Cél:

Olyan minimális költségű útvonal(ak) meghatározása, amelyek minden kötelező élt bejárnak legalább egyszer, és visszatérnek a kiindulási pontra (ha szükséges).

---

🧮 3. Típusai

1. Chinese Postman Problem (CPP)

• Minden él bejárása kötelező
• Irányított, irányítatlan, vegyes gráfokon is definiálható
• Polinomiális időben megoldható

2. Rural Postman Problem (RPP)

• Csak az élek egy részét kell bejárni
• NP-nehéz probléma, nincs ismert hatékony megoldás

3. Capacitated Arc Routing Problem (CARP)

• A bejárandó élek terhelést hordoznak (pl. hulladékmennyiség)
• Járművek kapacitása korlátozott
• Járműflottát kell optimalizálni

4. Mixed Windy Rural Postman Problem (MWRPP)

• Gráf vegyes (irányított + irányítatlan élek)
• Az élek irányfüggő költségűek (pl. emelkedő-lejtő)

---

🚛 4. Valós alkalmazások

• Szemétszállítás
• Hókotrás
• Úttisztítás és -festés
• Utcai világítás karbantartása
• Postai kézbesítés vidéki hálózatokon
• Drónos ellenőrzés energiahálózatokon

---

🧪 5. Megoldási módszerek

Egyszerűbb esetekre:

• Fleury-algoritmus, Hierholzer-algoritmus (Euler-út)
• Lineáris programozás (kisebb példákhoz)

Bonyolult esetekhez:

• Heurisztikák (pl. path-scanning, augment-and-merge)
• Metaheurisztikák:
  • Genetikus algoritmusok
  • Tabu search
  • Simulated annealing
• Branch-and-bound, column generation (nagyvárosi rendszerekhez)

---

📈 6. Összehasonlítás más problémákkal

Probléma	Mit kell meglátogatni?	Megoldás nehézsége
TSP	Csúcsok (városok)	NP-nehéz
VRP	Csúcsok, kapacitással	NP-nehéz
CPP	Minden él	polinomiális
RPP	Egyes élek	NP-nehéz
CARP	Élek + kapacitás	NP-nehéz

---

🧾 7. Összefoglalás

Az Arc Routing Problem:

• Olyan útvonaltervezési probléma, ahol éleket kell bejárni, nem csúcsokat
• Számos városi és logisztikai alkalmazásban kulcsszerepű
• Egyszerűbb formái megoldhatók, bonyolultabb változatai NP-nehéz optimalizálási problémák

További információk

• arc routing problem - Szótár.net (en-hu)
• arc routing problem - Sztaki (en-hu)
• arc routing problem - Merriam–Webster
• arc routing problem - Cambridge
• arc routing problem - WordNet
• arc routing problem - Яндекс (en-ru)
• arc routing problem - Google (en-hu)
• arc routing problem - Wikidata
• arc routing problem - Wikipédia (angol)