Clarke-Wright-algoritmus

• IPA:

Clarke-Wright-algoritmus

1. (matematika, algoritmusok)

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.

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: ${\displaystyle (0\to 1\to 0),(0\to 2\to 0),(0\to 3\to 0)}$, ahol ${\displaystyle 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:
  ${\displaystyle S_{ij}=d_{0i}+d_{0j}-d_{ij}}$
  ahol:
  * ${\displaystyle d_{0i}}$: A raktár és az ${\displaystyle i}$-edik ügyfél közötti távolság.
  * ${\displaystyle d_{0j}}$: A raktár és a ${\displaystyle j}$-edik ügyfél közötti távolság.
  * ${\displaystyle d_{ij}}$: Az ${\displaystyle i}$-edik és ${\displaystyle 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.

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

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

Optimális útvonalak: , ]

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.

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.

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

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

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.

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