IDPSP问题 matlab代码

IDPSP问题（即带时间窗口的车辆路径问题）是指在有限时间内，为满足一系列客户的需求，从一个仓库出发，依次经过客户位置并完成服务，最终回到仓库的问题。其中每个客户有一个时间窗口，即需要在规定时间内到达客户位置。

下面给出一个简单的基于matlab的代码，使用遗传算法来解决IDPSP问题：

function [best_solution, best_fitness] = idpsp_ga(customers, n_vehicles, vehicle_capacity, max_time, n_generations, pop_size, mutation_rate, crossover_rate)
% IDPSP problem solution using genetic algorithm

% customers: (n x 3) matrix, with columns (x, y, demand), where
% n is the number of customers, x and y are the coordinates of the customer,
% and demand is the amount of goods that the customer needs to be delivered.

% n_vehicles: the number of vehicles available for the deliveries
% vehicle_capacity: the maximum capacity of each vehicle
% max_time: the maximum time for each vehicle to complete its deliveries

% n_generations: the number of generations for the genetic algorithm
% pop_size: the size of the population for the genetic algorithm

% mutation_rate: the mutation rate for the genetic algorithm
% crossover_rate: the crossover rate for the genetic algorithm

n_customers = size(customers, 1);

% Calculate the distances between all pairs of customers
distances = zeros(n_customers, n_customers);
for i = 1:n_customers
    for j = 1:n_customers
        distances(i, j) = sqrt((customers(i, 1) - customers(j, 1))^2 + (customers(i, 2) - customers(j, 2))^2);
    end
end

% Initialize the population
pop = init_pop(n_customers, n_vehicles, vehicle_capacity);

% Evaluate the fitness of each individual in the population
fitness = eval_fitness(pop, distances, customers, n_vehicles, vehicle_capacity, max_time);

% Keep track of the best solution and its fitness
[best_fitness, best_idx] = min(fitness);
best_solution = pop(best_idx, :);

% Start the genetic algorithm
for i = 1:n_generations
    % Select parents for crossover
    parents = select_parents(pop, fitness);
    
    % Perform crossover
    offspring = crossover(parents, crossover_rate);
    
    % Perform mutation
    offspring = mutate(offspring, mutation_rate);
    
    % Evaluate the fitness of the offspring
    offspring_fitness = eval_fitness(offspring, distances, customers, n_vehicles, vehicle_capacity, max_time);
    
    % Merge the offspring with the current population
    pop = [pop; offspring];
    fitness = [fitness offspring_fitness];
    
    % Perform elitism (keep the best individuals from the previous generation)
    [fitness, idx] = sort(fitness);
    pop = pop(idx, :);
    pop = pop(1:pop_size, :);
    fitness = fitness(1:pop_size);
    
    % Update the best solution if necessary
    [min_fitness, min_idx] = min(fitness);
    if min_fitness < best_fitness
        best_fitness = min_fitness;
        best_solution = pop(min_idx, :);
    end
    
    % Print the best fitness so far
    fprintf('Generation %d: Best fitness = %f\n', i, best_fitness);
end

end

function pop = init_pop(n_customers, n_vehicles, vehicle_capacity)
% Initialize the population

pop = zeros(n_vehicles, n_customers);

for i = 1:n_vehicles
    % Randomly assign customers to each vehicle until the capacity is reached
    capacity_left = vehicle_capacity;
    while capacity_left > 0
        j = randi(n_customers);
        if capacity_left >= customers(j, 3) && sum(pop(:, j)) == 0
            pop(i, j) = 1;
            capacity_left = capacity_left - customers(j, 3);
        end
    end
end

end

function fitness = eval_fitness(pop, distances, customers, n_vehicles, vehicle_capacity, max_time)
% Evaluate the fitness of each individual in the population

n_customers = size(customers, 1);

% Calculate the total distance and time for each vehicle
total_distance = zeros(n_vehicles, 1);
total_time = zeros(n_vehicles, 1);
for i = 1:n_vehicles
    route = find(pop(i, :));
    for j = 1:length(route)-1
        total_distance(i) = total_distance(i) + distances(route(j), route(j+1));
        total_time(i) = total_time(i) + distances(route(j), route(j+1));
    end
end

% Calculate the waiting time for each customer
waiting_time = zeros(n_customers, 1);
for i = 1:n_customers
    if sum(pop(:, i)) > 0
        route = find(pop(:, i));
        arrival_time = total_time(route(1:end-1)) + distances(route(1:end-1), i);
        waiting_time(i) = max(customers(i, 4) - arrival_time, 0);
    end
end

% Calculate the fitness of each solution
fitness = max(total_distance) + sum(waiting_time) + max(total_time) - max_time;

end

function parents = select_parents(pop, fitness)
% Select parents for crossover using roulette wheel selection

n_parents = size(pop, 1);
parents = zeros(n_parents, size(pop, 2));

% Calculate the selection probabilities
prob = fitness / sum(fitness);

% Choose the parents using roulette wheel selection
for i = 1:n_parents
    r = rand();
    cum_prob = 0;
    for j = 1:length(prob)
        cum_prob = cum_prob + prob(j);
        if r <= cum_prob
            parents(i, :) = pop(j, :);
            break;
        end
    end
end

end

function offspring = crossover(parents, crossover_rate)
% Perform crossover using one-point crossover

n_parents = size(parents, 1);
n_genes = size(parents, 2);
offspring = zeros(n_parents, n_genes);

for i = 1:n_parents/2
    if rand() <= crossover_rate
        % Choose a crossover point
        crossover_point = randi(n_genes-1);
        
        % Perform one-point crossover
        offspring(2*i-1, :) = [parents(2*i-1, 1:crossover_point) parents(2*i, crossover_point+1:end)];
        offspring(2*i, :) = [parents(2*i, 1:crossover_point) parents(2*i-1, crossover_point+1:end)];
    else
        % No crossover, simply copy the parents to the offspring
        offspring(2*i-1, :) = parents(2*i-1, :);
        offspring(2*i, :) = parents(2*i, :);
    end
end

end

function offspring = mutate(parents, mutation_rate)
% Perform mutation by swapping two genes

n_parents = size(parents, 1);
n_genes = size(parents, 2);
offspring = parents;

for i = 1:n_parents
    if rand() <= mutation_rate
        % Choose two genes to swap
        gene1 = randi(n_genes);
        gene2 = randi(n_genes);
        
        % Perform the swap
        offspring(i, [gene1 gene2]) = offspring(i, [gene2 gene1]);
    end
end

end

这个代码使用了遗传算法来解决IDPSP问题，其中包括了初始化种群、评估适应度、选择父代、交叉和变异等步骤。需要注意的是，这里的时间窗口是以客户的需求时间为基准计算的。如果需要将时间窗口考虑为实际时间，需要对代码进行一些修改。