Ugrás a tartalomhoz

vehicle routing problem

A Wikiszótárból, a nyitott szótárból
(VRP szócikkből átirányítva)

Angol


Főnév

vehicle routing problem (tsz. vehicle routing problems)

  1. (informatika) jármű útvonaltervezési probléma

A Vehicle Routing Problem (VRP), vagy járműútvonal-tervezési probléma egy kombinatorikus optimalizálási probléma, amelyben adott egy központi raktár (vagy több), egy sor ügyfél helyszín (címzett), és járművek, amelyek el kell, hogy lássák ezeket az ügyfeleket. A cél, hogy megtaláljuk a legoptimálisabb útvonalakat, amelyekkel a járművek teljesítik a kiszállításokat, a legkisebb költség, idő vagy távolság mellett.

A VRP az utazó ügynök problémájának (TSP) általánosítása, ahol több ügynök (jármű) jár be több célpontot, kapacitáskorlátokkal és egyéb megszorításokkal.


Alapprobléma

Input:

  • Egy központi raktár (depot)
  • n ügyfél különböző helyeken
  • k jármű (azonos vagy különböző kapacitással)
  • Minden ügyfélnek van egy igénye (pl. csomag súlya, darabszám)

Cél:

  • Olyan útvonalat rendelni minden járműhöz, hogy:
    • Minden ügyfél pontosan egyszer legyen kiszolgálva
    • Az összesített költség (pl. út hossza, üzemanyag, idő) minimális legyen
    • Ne sértsük meg a járművek kapacitását és egyéb szabályokat


Alkalmazási területek

  • Futár- és csomagküldő szolgálatok (pl. DHL, UPS)
  • Élelmiszerszállítás
  • Hulladékszállítás
  • Buszjárat-tervezés
  • Mobil szervizszolgáltatások


Példa

Egy pizzéria 1 raktárból 10 címre szállít ki, 3 autóval, mindegyik 3 pizza szállítására képes. Melyik útvonal legyen a legjobb, ha minden cím csak egyszer szerepelhet?


VRP típusai

1. CVRP – Capacitated VRP

  • Minden járműnek van egy fix kapacitása.

2. VRPTW – VRP with Time Windows

  • Ügyfelek csak bizonyos időablakokban fogadhatók.

3. MDVRP – Multi-Depot VRP

  • Több raktár van.

4. VRPPD – Pickup and Delivery VRP

  • Nem csak kiszállítás, hanem átvétel is van.

5. Open VRP

  • A járművek nem térnek vissza a raktárba.

6. Stochastic VRP

  • A bemenetek (igények, idők) bizonytalanok.


Matematikai modell (egyszerűsített CVRP)

Változók:

  • x_{ij}: 1, ha a jármű i → j él mentén halad, különben 0

Célfüggvény:

Minimize ∑∑ c_{ij} * x_{ij}

ahol c_{ij} a i → j távolságköltség

Megszorítások:

  1. Minden ügyfelet pontosan egyszer látogat meg valamely jármű
  2. A jármű nem lépheti túl kapacitását
  3. A jármű a raktárból indul és oda tér vissza
  4. Nincsenek szubtúrák (azaz nincs olyan részútvonal, ami nem kapcsolódik a raktárhoz)


Megoldási módszerek

1. Exakt algoritmusok (kis méret esetén)

  • Branch and Bound
  • Integer Programming
  • Dynamic Programming (pl. Held-Karp)

✅ Optimális ❌ Skálázódás gyenge


2. Heurisztikák (gyors, de nem mindig optimális)

  • Savings Algorithm (Clarke-Wright)
  • Sweep Algorithm
  • Nearest Neighbor + Insertion
  • Greedy Heuristics

✅ Gyors ❌ Lehet, hogy messze van az optimumtól


3. Metaheurisztikák (jó egyensúly)

  • Simulated Annealing
  • Genetikus algoritmusok
  • Tabu Search
  • Ant Colony Optimization (ACO)
  • Large Neighborhood Search (LNS)

✅ Jó minőségű eredmény ✅ Kezeli a bonyolult szabályokat ❌ Paraméterérzékenység


Egyszerű heurisztikus példa (Savings Algorithm)

  1. Kezdetben minden ügyfélhez külön út
  2. Kiszámoljuk az „összes megtakarítást” (pl. raktár → A → raktár + raktár → B → raktár - raktár → A → B → raktár)
  3. Rendezés megtakarítás szerint
  4. Összefűzzük az útvonalakat, ha nem sért kapacitást


Példa Pythonban (vázasított)

def nearest_neighbor_vrp(depot, clients, capacity):
    routes = []
    while clients:
        route = [depot]
        load = 0
        current = depot
        for client in sorted(clients, key=lambda x: distance(current, x)):
            if load + client.demand <= capacity:
                route.append(client)
                load += client.demand
                current = client
        route.append(depot)
        routes.append(route)
        for c in route[1:-1]:
            clients.remove(c)
    return routes

Kihívások

  • Skálázódás: több ezer ügyfél esetén már csak heurisztika jöhet szóba
  • Többféle megszorítás kombinálása (idő, kapacitás, prioritás)
  • Reálidős újratervezés (dinamikus VRP)


Összefoglalás

A Vehicle Routing Problem (VRP) a logisztika és szállítástervezés kulcsproblémája. Kritikus a költséghatékonyságban, különösen nagyvállalatok esetén. Bár az exakt megoldás sokszor nem életszerű, heurisztikákkal és metaheurisztikákkal közel optimális megoldások érhetők el.

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=vehicle_routing_problem&oldid=3494974”