reverse_opt.py

import numpy as np

def optimize_routes(depot, customers, coords, demands, capacity=1000):
    """Vehicle routing with nearest-neighbor + 2-opt improvement."""
    dist = lambda a, b: np.linalg.norm(coords[a] - coords[b])

    def nearest_neighbor(remaining):
        route = [depot]; load = 0
        left = list(remaining)
        while left:
            curr = route[-1]
            feasible = [c for c in left if load + demands.get(c, 0) <= capacity]
            if not feasible: route.append(depot); load = 0; continue
            nearest = min(feasible, key=lambda c: dist(curr, c))
            route.append(nearest); load += demands.get(nearest, 0); left.remove(nearest)
        if route[-1] != depot: route.append(depot)
        return route

    def total_distance(route):
        return sum(dist(route[i], route[i+1]) for i in range(len(route)-1))

    def two_opt(route):
        improved = True
        while improved:
            improved = False
            for i in range(1, len(route)-2):
                for j in range(i+1, len(route)-1):
                    new = route[:i] + route[i:j+1][::-1] + route[j+1:]
                    if total_distance(new) < total_distance(route):
                        route = new; improved = True
        return route

    route = nearest_neighbor(customers)
    route = two_opt(route)
    return {"route": route, "total_distance": round(total_distance(route), 1),
            "stops": len(customers), "vehicles_needed": route.count(depot) - 1}

if __name__ == "__main__":
    np.random.seed(42); n = 15
    coords = {0: np.array([50.0, 50.0])}
    demands = {}
    for i in range(1, n+1):
        coords[i] = np.random.rand(2) * 100
        demands[i] = np.random.randint(50, 200)
    result = optimize_routes(0, list(range(1, n+1)), coords, demands, capacity=500)
    print(f"Route distance: {result['total_distance']} | Vehicles: {result['vehicles_needed']}")