jármű útvonaltervezési probléma

• IPA:

jármű útvonaltervezési probléma

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

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).

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.

• ${\displaystyle G=(V,E)}$: Egy gráf, ahol:

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

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

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

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

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

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

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

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).

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 - b)**2 + (a - b)**2)

def savings_vrp(customers, depot, capacity, demands):
    """
    Clarke-Wright Savings algoritmus a VRP megoldására.
    
    Args:
        customers: Az ügyfelek koordinátái .
        depot: A raktár koordinátái (x, y).
        capacity: A jármű kapacitása.
        demands: Az ügyfelek igényei .
    
    Returns:
        routes: A járművek optimális útvonalai.
    """
    n = len(customers)
    # Távolságok számítása
    distances = , customers) for j in range(n)] for i in range(n)]
    depot_distances = ) 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 + depot_distances - distances))
    savings.sort(key=lambda x: x, reverse=True)
    
    # Kezdeti útvonalak (egy ügyfél per jármű)
    routes =  for i in range(n)]
    route_demands =  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 + route_demands <= 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 =   # Ügyfél koordináták
depot = (0, 0)                                # Raktár koordinátái
capacity = 15                                 # Jármű kapacitása
demands =                         # Ügyféligények

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

Optimális útvonalak: , ]

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.

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.

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.