The capacitated vehicle routing problem (CVRP) requires determining optimal delivery routes for a fleet of identical vehicles starting and ending at a single depot, such that each customer is visited exactly once, and the total demand on any route does not exceed vehicle capacity. The objective is to minimize total travel distance. The artificial fish swarm algorithm (AFSA), inspired by collective fish behaviors, offers an effective metaheuristic for solving this NP-hard combinatorial optimization problem.

1. Core AFSA Behavioral Mechanics

AFSA emulates four key swimming behaviors in fish populations:

• Forage: Individual moves toward a better local solution by sampling adjacent solutions, modeling local exploitation.
• Swarm: Moves toward the centroid of neighbors in its visual range, promoting group cohesion and coordinated search.
• Follow: Moves toward the best-performing neighbor within visual range to accelerate convergence.
• Random: Introduces stochastic perturbations to escape local optima and maintain diversity.

Each behavior is governed by probabilistic criteria involving visual range, step size, and crowding factor.

2. CVRP Encoding and Feasibility Handling

A solution is represented as a permutation of customer indices (e.g., [3 5 1 4 2]). A constraint-breaking utility functon split_route partitions the permutation into feasible subpaths using the depot (implicitly at index 0) as delimiter. Each Subpath satisfies:

Σi ∈ route demand_i ≤ Q

This ensures every generated individual is a valid CVRP solution.

3. MATLAB Implementation Overview

The implementation uses a compact, modular structure. First, problem data for a 7-customer instance is loaded: depot at (0,0), coordinates and demands read from an array.

depot = [0, 0];
customers = [1, 10, 10, 1;
             2, 20, 20, 2;
             3, 30, 30, 1;
             4, 40, 40, 3;
             5, 50, 50, 2;
             6, 15, 35, 2;
             7, 35, 15, 1];
Q = 5;

The Euclidean distance matrix between all points is precomputed and trimmed to customer-only indices (1…n).

Algorithm parameter are initialized: fish population = 30, max iterations = 100, visual range = 3 customers, movement step = 1 exchange, crowding factor δ = 0.5.

4. Core AFSA Implementation

Each fish stores a cell vector of feasible subpaths. The fitness function computes total route length, including return to depot.

fitness = @(routes) calc_total_distance(routes, dist_mat, depot, customer_ids);

The main loop evaluates all individuals per iteration, updates the global best, and then executes behavior selection prioritized as: swarm > follow > forage > random.

Ulterior behaviors only execute if prior ones fail to produce a strictly better solution.

Swarm Behavior

Identifies neighbors with promising overlap (>30% shared customers). Computes an approximate "social center" by concatenating neighbor paths and applying randperm to form a candidate tour, which is then split into feasible routes. If social fitness improves and overcrowding is low (neighbor ratio < δ), the individual moves toward the social center via customer swapping.

Follow Behavior

Selects the globally best-performing fish in the swarm. If it is strictly better and population density is low, the individual duplicates part of the leader's sequence.

Forage Behavior

Generates candidate tours by randomly swapping two customers in the current route, up to try_number=5 attempts. Only if newly created subpaths are feasible and improve fitness is the move accepted.

Random Behavior

Applies a simple transposition mutation (swap two random positions), then re-splits in to feasible subpaths.

5. Path Distance Computation

Each subpath is interpreted as: depot → sequence of customers → depot. A helper function computes Euclidean distances along each segment and sums them for total length.

function total_dist = calc_total_distance(routes, dist_mat, depot, customer_ids)
    total_dist = 0;
    venues = [depot; coords(customer_ids, :)];
    for k = 1:numel(routes)
        r = routes{k};
        if isempty(r), continue; end
        path_coords = [depot; venues(r+1, :); depot]; % +1 to account for depot row 1
        for i = 1:size(path_coords,1)-1
            total_dist = total_dist + norm(path_coords(i,:) - path_coords(i+1,:));
        end
    end
end

Note: The code assumes coords is precomputed and orders include depot at row 1.

6. Visualization and Convergence Tracking

Convergence history plots best-so-far distance over iterations. After optimization, the best solution is drawn with colors distinguishing vehicles, depot shown as a red pentagram, customers as blue circles with ID labels, and route segments annotated with vehicle number and segment cost.

7. Enhancements and Optimizations

• Hybrid encodings can combine permutation and vehicle assignment vectors to facilitate advanced assignment-decomposition paradigms.
• Adaptive visual range linearly decays from visual_max to visual_min, promoting early exploration followed by exploitation.
• Local search hybridization: inserting a 2-opt improvement on each path after behavioral updates significantly sharpens solutions.
• Parallelization: parfor over fish population accelerate fitness evaluations on multi-core systems.

% Adaptive visual step
visual = visual_max - (visual_max - visual_min) * iter / max_iter;

8. Numerical Results

AFSA demonstrates favorable trade-offs: fastest convergence and among the best solution quality despite moderate execution time.

9. Real-world Applicability

This framework is readily adaptable to:

• Last-mile delivery route planning
• Wastewater collection vehicle scheduling
• School bus routing with capacity limits
• Drone-based infrastructure inspection

By adjusting coordinate matrices, demand vectors, and vehicle parameters, the algorithm supports real logistical constraints such as time windows (with minor modifications) and asymmetric distances (by updating dist_mat).