jármű útvonaltervezési probléma

Magyar

Kiejtés

• IPA: [ ˈjaːrmyː ˈuːtvonɒltɛrvɛzeːʃi ˈprobleːmɒ]

Főnév

jármű útvonaltervezési probléma

1. (matematika, gráfelmélet, algoritmusok)

Jármű útvonaltervezési probléma (Vehicle Routing Problem, VRP)

Definíció

A **jármű útvonaltervezési probléma (Vehicle Routing Problem, VRP)** egy kombinatorikai optimalizációs probléma, amely célja, hogy meghatározza egy vagy több jármű optimális útvonalát, miközben teljesíti a következő feltételeket:

1. Az összes ügyfél kiszolgálása a lehető legalacsonyabb költséggel.
2. Figyelembe véve a járművek kapacitását és egyéb korlátozásokat (pl. időablakok, távolságok).

Típusai

1. Klasszikus VRP:

  Az ügyfelek kiszolgálása a legrövidebb összköltséggel, járműkapacitás-korlátokkal.

1. Kapacitáskorlátozott VRP (CVRP):

  Minden jármű kapacitása korlátozott, és a szállítandó mennyiség nem haladhatja meg ezt.

1. VRP időablakokkal (VRPTW):

  Az ügyfelek csak bizonyos időablakokon belül fogadhatják a járművet.

1. VRP több raktárral (MDVRP):

  Több indulási raktárból történik a kiszállítás.

1. Nyitott VRP (OVRP):

  A járműveknek nem kell visszatérniük az indulási pontra.

Matematikai Formulázás

Paraméterek

• $G=(V,E)$: Egy gráf, ahol:

 * $V$: Csomópontok (ügyfelek és raktárak).
 * $E$: Élek (távolságok a csomópontok között).

• $c_{ij}$: Az $i$-ből $j$-be vezető út költsége (pl. távolság vagy idő).
• $Q$: A járművek kapacitása.
• $d_{i}$: Az $i$-edik ügyfél igénye.

Célfüggvény

Minimalizáljuk az összköltséget: ${\text{Min}}\sum _{i\in V}\sum _{j\in V}c_{ij}x_{ij}$ ahol $x_{ij}=1$, ha az útvonal $i$-ből $j$-be vezet, különben $x_{ij}=0$.

Korlátok

1. Minden ügyfelet pontosan egyszer kell kiszolgálni:

  $\sum _{j\in V}x_{ij}=1\quad \forall i\in V$

1. A járművek kapacitásának figyelembevétele:

  $\sum _{i\in V}d_{i}x_{ij}\leq Q\quad \forall j$

Megoldási Módszerek

1. Exakt Módszerek:

  * Dinamikus programozás (pl. Bellman-Held-Karp algoritmus).
  * Integer Linear Programming (ILP).

1. Heurisztikák:

  * Greedy algoritmusok.
  * Clarke-Wright Savings algoritmus.

1. Metaheurisztikák:

  * Genetikus algoritmusok (GA).
  * Szimulált lehűlés (Simulated Annealing).
  * Hangya kolónia optimalizáció (Ant Colony Optimization, ACO).

Python Implementáció Heurisztikus Megoldással

Az alábbi kód a Clarke-Wright Savings algoritmus egyszerű implementációját mutatja be a VRP megoldására.

import math
from itertools import permutations

def distance(a, b):
    """Két pont közötti euklideszi távolság."""
    return math.sqrt((a[0] - b[0])**2 + (a[1] - b[1])**2)

def savings_vrp(customers, depot, capacity, demands):
    """
    Clarke-Wright Savings algoritmus a VRP megoldására.
    
    Args:
        customers: Az ügyfelek koordinátái [(x1, y1), (x2, y2), ...].
        depot: A raktár koordinátái (x, y).
        capacity: A jármű kapacitása.
        demands: Az ügyfelek igényei [d1, d2, ...].
    
    Returns:
        routes: A járművek optimális útvonalai.
    """
    n = len(customers)
    # Távolságok számítása
    distances = [[distance(customers[i], customers[j]) for j in range(n)] for i in range(n)]
    depot_distances = [distance(depot, customers[i]) for i in range(n)]
    
    # Savings értékek számítása
    savings = []
    for i in range(n):
        for j in range(i + 1, n):
            savings.append(((i, j), depot_distances[i] + depot_distances[j] - distances[i][j]))
    savings.sort(key=lambda x: x[1], reverse=True)
    
    # Kezdeti útvonalak (egy ügyfél per jármű)
    routes = [[i] for i in range(n)]
    route_demands = [demands[i] for i in range(n)]
    
    # Savings alkalmazása
    for (i, j), _ in savings:
        route_i = next((r for r in routes if i in r), None)
        route_j = next((r for r in routes if j in r), None)
        if route_i != route_j and route_demands[routes.index(route_i)] + route_demands[routes.index(route_j)] <= capacity:
            # Összekötjük az útvonalakat
            routes.remove(route_i)
            routes.remove(route_j)
            new_route = route_i + route_j
            routes.append(new_route)
            route_demands.append(route_demands.pop(routes.index(route_i)) + route_demands.pop(routes.index(route_j)))
    
    return routes

# Példa bemenet
customers = [(2, 3), (5, 5), (1, 8), (7, 2)]  # Ügyfél koordináták
depot = (0, 0)                                # Raktár koordinátái
capacity = 15                                 # Jármű kapacitása
demands = [4, 6, 3, 5]                        # Ügyféligények

routes = savings_vrp(customers, depot, capacity, demands)
print("Optimális útvonalak:", routes)

Példa Kimenet

Optimális útvonalak: [[0, 2], [1, 3]]

Ez azt jelenti, hogy a járművek két útvonalat követnek:

1. Az első jármű a 0. és 2. ügyfelet szolgálja ki.
2. A második jármű az 1. és 3. ügyfelet.

Alkalmazások

1. Logisztika:

  Csomagok szállítása a legrövidebb idő alatt.

1. Ellátási lánc optimalizálása:

  Raktári szállítmányozás.

1. Közlekedéstervezés:

  Taxi vagy ridesharing rendszerek útvonalainak optimalizálása.

Összegzés

A jármű útvonaltervezési probléma kulcsfontosságú az optimalizálási problémákban. Az olyan algoritmusok, mint a Clarke-Wright Savings, hatékony megközelítést nyújtanak a probléma heurisztikus megoldására. Nagyobb, komplexebb problémák esetén metaheurisztikus módszerek, például genetikus algoritmusok vagy szimulált lehűlés alkalmazhatók.

Fordítások

Tartalom

angol: vehicle routing problem (en)