Clarke-Wright-algoritmus

Magyar

Kiejtés

• IPA: [ ˈt͡slɒrkɛvriɡxtɒlɡoritmuʃ]

Főnév

Clarke-Wright-algoritmus

1. (matematika, algoritmusok)

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.

Fordítások

Tartalom

angol: Clarke and Wright savings algorithm (en)

További információk

• Clarke-Wright-algoritmus - Értelmező szótár (MEK)
• Clarke-Wright-algoritmus - Etimológiai szótár (UMIL)
• Clarke-Wright-algoritmus - Szótár.net (hu-hu)
• Clarke-Wright-algoritmus - DeepL (hu-de)
• Clarke-Wright-algoritmus - Яндекс (hu-ru)
• Clarke-Wright-algoritmus - Google (hu-en)
• Clarke-Wright-algoritmus - Helyesírási szótár (MTA)
• Clarke-Wright-algoritmus - Wikidata
• Clarke-Wright-algoritmus - Wikipédia (magyar)