带提货和送货的车辆路径问题

import numpy as np
import random

# 定义距离矩阵
distance_matrix = np.array([
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
])

# 定义客户位置和需求
customers = [
    {'id': 1, 'demand': 10},
    {'id': 2, 'demand': 20},
    {'id': 3, 'demand': 15},
    {'id': 4, 'demand': 5}
]

# 定义车辆容量
vehicle_capacity = 30

# 遗传算法参数
population_size = 100
generations = 100
mutation_rate = 0.01

# 初始化种群
def initialize_population(population_size, num_customers):
    population = []
    for _ in range(population_size):
        route = list(range(1, num_customers + 1))
        random.shuffle(route)
        population.append(route)
    return population

# 计算路径长度
def calculate_route_length(route, distance_matrix):
    length = 0
    for i in range(len(route)):
        length += distance_matrix[route[i-1]-1][route[i]-1]
    return length

# 选择操作
def selection(population, fitness):
    selected = random.choices(population, weights=fitness, k=len(population))
    return selected

# 交叉操作
def crossover(parent1, parent2):
    child = [-1] * len(parent1)
    start, end = sorted(random.sample(range(len(parent1)), 2))
    child[start:end] = parent1[start:end]
    for i in range(len(parent2)):
        if parent2[i] not in child:
            for j in range(len(child)):
                if child[j] == -1:
                    child[j] = parent2[i]
                    break
    return child

# 变异操作
def mutation(route):
    for i in range(len(route)):
        if random.random() < mutation_rate:
            j = random.randint(0, len(route)-1)
            route[i], route[j] = route[j], route[i]
    return route

# 主函数
def main():
    num_customers = len(customers)
    population = initialize_population(population_size, num_customers)
    
    for generation in range(generations):
        fitness = [1 / calculate_route_length(route, distance_matrix) for route in population]
        selected = selection(population, fitness)
        
        new_population = []
        while len(new_population) < population_size:
            parent1, parent2 = random.sample(selected, 2)
            child = crossover(parent1, parent2)
            child = mutation(child)
            new_population.append(child)
        
        population = new_population[:population_size]
    
    best_route = min(population, key=lambda x: calculate_route_length(x, distance_matrix))
    print("Best Route:", best_route)
    print("Route Length:", calculate_route_length(best_route, distance_matrix))

if __name__ == "__main__":
    main()