CVRP with Heuristics

Welcome to the Meta-Heuristic CVRP Engine. This application is a comprehensive solver designed to tackle the Capacitated Vehicle Routing Problem (CVRP).

How it works: The solver operates on a Meta-Heuristic framework. It generates initial solutions using a Stochastic GRASP (Greedy Randomized Adaptive Search Procedure) based on the classic Clarke & Wright Savings algorithm, guided by your chosen "Depth" parameter. It then relentlessly optimizes these routes via Variable Neighborhood Descent (VND) applying four powerful Local Search operators: Inter-route Swap, Inter-route 2-Opt (Cross-Exchange), Intra-route Swap, and Intra-route 2-Opt. By running through your chosen number of Iterations, the engine produces hundreds of scenarios behind the scenes and surfaces the global best route configuration.

Key Features:

Dual Visualization: Toggle seamlessly between an abstract 2D Euclidean Graph (via Chart.js) and a real-world Geographic Map (via OpenStreetMap) using Haversine distance calculations.
Interactive Map Builder: Click on the map to dynamically place your Depot and Cities. Assign exact demands, and dynamically delete nodes if you make a mistake.
Import/Export Data: Easily save your synthetic or geographic problem sets as `.txt` files, and load them back later for further optimization.
Customizable Engine: Tweak vehicle capacity, search depth, iterations, and toggle individual Local Search operators to see how they impact the final routing distance.

Stochastic GRASP & VND Local Search Algorithm

FUNCTION MetaHeuristic_CVRP(Nodes, DistanceMatrix, Demands, Capacity, Depth, MaxIterations):
    GlobalBestDistance = INFINITY
    GlobalBestRoutes = NULL

    FOR iter = 1 TO MaxIterations DO:
        // --- PHASE 1: SAVINGS CALCULATION ---
        SavingsList = []
        FOR EACH city i = 1 TO N:
            FOR EACH city j = i+1 TO N:
                S_ij = Distance(i, Depot) + Distance(Depot, j) - Distance(i, j)
                SavingsList.append({i, j, saving: S_ij})
        
        Sort SavingsList in DESCENDING order of saving

        // --- PHASE 2: INITIALIZATION ---
        CurrentRoutes = []
        FOR EACH city i = 1 TO N:
            Route = [Depot, i, Depot]
            Route.Load = Demands[i]
            CurrentRoutes.append(Route)

        // --- PHASE 3: STOCHASTIC ROUTE MERGING (GRASP CORE) ---
        WHILE True:
            ValidCandidates = []
            FOR EACH pair (i, j) in SavingsList:
                Route_i = findRoute(i)
                Route_j = findRoute(j)
                
                IF Route_i != Route_j AND (i and j are adjacent to Depot):
                    IF Route_i.Load + Route_j.Load <= Capacity:
                        ValidCandidates.append({Route_i, Route_j, i, j})
                        IF length(ValidCandidates) == Depth: BREAK FOR
            
            IF length(ValidCandidates) == 0: BREAK WHILE
                
            RandomIndex = randomInt(0, length(ValidCandidates) - 1)
            SelectedMerge = ValidCandidates[RandomIndex]
            
            MergedRoute = Merge(SelectedMerge.Route_i, SelectedMerge.Route_j)
            CurrentRoutes.remove(SelectedMerge.Route_i)
            CurrentRoutes.remove(SelectedMerge.Route_j)
            CurrentRoutes.append(MergedRoute)
            Remove SelectedMerge's pair from SavingsList
        END WHILE

        // --- PHASE 4: VARIABLE NEIGHBORHOOD DESCENT (LOCAL SEARCH) ---
        IF InterSwapEnabled: CurrentRoutes = ApplyInterRouteSwap(CurrentRoutes, Capacity)
        IF Inter2OptEnabled: CurrentRoutes = ApplyInterRouteCrossExchange(CurrentRoutes, Capacity)
        IF IntraSwapEnabled: CurrentRoutes = ApplyIntraRouteSwap(CurrentRoutes)
        IF Intra2OptEnabled: CurrentRoutes = ApplyIntraRoute2Opt(CurrentRoutes)

        // --- PHASE 5: EVALUATION ---
        CurrentTotalDist = CalculateTotalDistance(CurrentRoutes)
        IF CurrentTotalDist < GlobalBestDistance:
            GlobalBestDistance = CurrentTotalDist
            GlobalBestRoutes = DeepCopy(CurrentRoutes)
    END FOR
    RETURN GlobalBestRoutes, GlobalBestDistance
END FUNCTION

📈 Synthetic Data (2D Euclidean) Import/Export abstract coordinate data.

🌍 Map Data (Geographic Haversine) Click map to place nodes, or Load/Export real coordinates.

📦 Total Demand: 552 Units

🏙️ Cities: 20 + 1 Depot

📍 Max Demand: 47 Units

📏 Distance Mode: Euclidean (2D)

Capacity:

Depth:

Iterations:

🔄 Inter-route Swap ✂️ Inter-route 2-Opt* 🔁 Intra-route Swap 🔀 Intra-route 2-Opt

Kullanılan Araç Sayısı -

En İyi Toplam Mesafe -

Error: Check parameters! (Capacity >= Max Demand, Depth >=1, Iterations >=1)

CVRP with Heuristics

Stochastic GRASP & VND Local Search Algorithm

Detailed Routes Output