Cheapest Insertion Point Algorithm for Vehicle Routing with Time Windows

The function cheapestIP finds the cheapest insertion point for a new customer in a vehicle routing problem with time windows. It takes the current vehicle route (rv), all vehicle routes (rfvc), maximum travel time (L), service time (a), time window (b), service start time (s), and distance matrix (dist) as inputs. It returns the vehicle index (civ), insertion point index (cip), and the increased distance (C) after inserting the new customer.

function [civ, cip, C] = cheapestIP(rv, rfvc, L, a, b, s, dist) 
NV = size(rfvc, 1); 
outcome = []; // save the insert point
for i = 1:NV
    route = rfvc{i}; 
    len = length(route);
    LB = part_length(route, dist); // length of route before insert
    
    for j = 1:len + 1
        // first point, after the depot
        if j == 1
            temp_r = [rv route];
            
            LA = part_length(temp_r, dist); // length of route after insert     
            delta = LA - LB; // increased distance
            [bs, back] = begin_s(temp_r, a, s, dist); // calculate the start time
            violate_TW = (bs' <= b(temp_r));
            vTW = find(violate_TW == 0, 1, 'first'); // find the violated customer
            if isempty(vTW) && (back <= L) // if no violation
                outcome = [outcome; i j delta];
            end
        elseif j == len + 1 // last point, before the depot
            temp_r = [route rv];
            LA = part_length(temp_r, dist);
            delta = LA - LB;
            [bs, back] = begin_s(temp_r, a, s, dist);
            violate_TW = (bs' <= b(temp_r));          
            vTW = find(violate_TW == 0, 1, 'first');
            if isempty(vTW) && (back <= L)
                outcome = [outcome; i j delta];
            end
        else
            // add the point between the customers
            temp_r = [route(1:j - 1) rv route(j:end)];
            LA = part_length(temp_r, dist);       
            delta = LA - LB;
            [bs, back] = begin_s(temp_r, a, s, dist);
            violate_TW = (bs' <= b(temp_r)); 
            vTW = find(violate_TW == 0, 1, 'first');  
            if isempty(vTW) && (back <= L)
                outcome = [outcome; i j delta];
            end
        end
    end
end
// find the best insert point
// sort the insert with the increased distance
if ~isempty(outcome)
    addC = outcome(:, 3);
    [saC, sindex] = sort(addC);
    temp = outcome(sindex, :);
    civ = temp(1, 1);
    cip = temp(1, 2);
    C = temp(1, 3);
else
    civ = NV + 1;
    cip = 1;
    C = part_length(rv, dist);
end

The code iterates through each vehicle's route and inserts the new customer at each possible position. It then calculates the increased route length (delta) and checks if the insertion satisfies the constraints (time window and vehicle capacity). If the insertion is feasible, the vehicle index (i), insertion point index (j), and increased distance (delta) are stored in the outcome matrix. The algorithm then sorts the outcome matrix based on the increased distance and selects the insertion with the minimum increase. If no feasible insertion points are found, a new vehicle is created to accommodate the new customer.

This function provides a solution for finding the optimal location to insert a new customer into a vehicle route while considering constraints. The algorithm is efficient and can be used in various applications where optimal routing is required.