Clarke-Wright-algoritmus

1. Sablon:Label

Clarke-Wright-algoritmus

Definíció

A Clarke-Wright Savings algoritmus egy heurisztikus módszer a jármű útvonaltervezési probléma (Vehicle Routing Problem, VRP) megoldására. Az algoritmus célja, hogy minimalizálja a járművek által megtett távolságot, miközben betartja a járművek kapacitáskorlátait.

Algoritmus Működése

1. Kezdeti állapot:

  - Kezdetben minden ügyfélhez külön járművet rendelünk, amelyek mind a raktárból indulnak és oda térnek vissza.  
  - Példa: Ha három ügyfél van, az útvonalak: $(0\to 1\to 0),(0\to 2\to 0),(0\to 3\to 0)$, ahol $0$ a raktár.
  

1. Savings (megtakarítás) érték kiszámítása:

  - Minden két ügyfél között kiszámítjuk a megtakarítás értéket:
  $S_{ij}=d_{0i}+d_{0j}-d_{ij}$
  ahol:
  * $d_{0i}$: A raktár és az $i$-edik ügyfél közötti távolság.
  * $d_{0j}$: A raktár és a $j$-edik ügyfél közötti távolság.
  * $d_{ij}$: Az $i$-edik és $j$-edik ügyfél közötti távolság.
  

1. Savings értékek rendezése:

  - A megtakarításokat csökkenő sorrendbe rendezzük.

1. Útvonalak összefűzése:

  - A megtakarítások sorrendjében megpróbáljuk összefűzni az ügyfeleket egyetlen útvonalra, ha a következő feltételek teljesülnek:
    * Az összesített igény nem lépi túl a jármű kapacitását.
    * Az ügyfelek nem kerülnek többször az útvonalra.

1. Végeredmény:

  - Az algoritmus végén kapott útvonalak minimalizálják a teljes távolságot.

Python Implementáció

Az alábbi kód a Clarke-Wright Savings algoritmus implementációját mutatja be.

import math

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 clarke_wright(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):
            s = depot_distances[i] + depot_distances[j] - distances[i][j]
            savings.append(((i, j), s))
    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 = clarke_wright(customers, depot, capacity, demands)
print("Optimális útvonalak:", routes)

Példa Kimenet

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

Magyarázat:

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

Alkalmazások

1. Logisztikai rendszerek:

  Csomagszállítás optimalizálása.

1. Raktári kiszállítás:

  Az ellátási lánc hatékonyságának javítása.

1. Közlekedéstervezés:

  Tömegközlekedési útvonalak optimalizálása.

Előnyök és Hátrányok

Előnyök

• Egyszerű és gyors algoritmus.
• Jól működik kis és közepes méretű problémák esetén.

Hátrányok

• Nem garantálja az optimális megoldást.
• Nagyobb problémák esetén az eredmények közelítők, és metaheurisztikus módszerekre lehet szükség.

Összegzés

A Clarke-Wright Savings algoritmus egy hatékony heurisztikus módszer, amely gyorsan képes megoldani a jármű útvonaltervezési problémát. Egyszerű implementációja és hatékony működése miatt gyakran alkalmazzák kisebb logisztikai problémákban. Nagyobb méretű vagy komplex korlátozásokkal rendelkező problémák esetén azonban érdemes metaheurisztikus módszereket (pl. genetikus algoritmus) alkalmazni.

• Sablon:En: Sablon:T+