外卖送餐最优路径python

外卖送餐最优路径问题是一个经典的旅行商问题（Traveling Salesman Problem，TSP），它的目标是找到一条最短路径，使得送餐员能够在最短的时间内访问所有的送餐点并回到起点。

在Python中，你可以使用一些优化算法来解决这个问题，例如遗传算法、模拟退火算法、蚁群算法等。下面是一个基于遗传算法的示例代码：

import random
import numpy as np

def calculate_distance(point1, point2):
    # 计算两点之间的距离
    x1, y1 = point1
    x2, y2 = point2
    return np.sqrt((x2 - x1)**2 + (y2 - y1)**2)

def calculate_total_distance(points, order):
    # 计算路径总长度
    total_distance = 0.0
    for i in range(len(order)):
        point1 = points[order[i]]
        point2 = points[order[(i + 1) % len(order)]]
        total_distance += calculate_distance(point1, point2)
    return total_distance

def create_route(points):
    # 随机生成初始路径
    route = list(range(len(points)))
    random.shuffle(route)
    return route

def mutate(route):
    # 变异操作：交换两个位置的顺序
    new_route = route.copy()
    index1, index2 = random.sample(range(len(route)), 2)
    new_route[index1], new_route[index2] = new_route[index2], new_route[index1]
    return new_route

def genetic_algorithm(points, population_size=100, generations=1000):
    # 遗传算法求解最优路径
    population = [create_route(points) for _ in range(population_size)]
    
    for _ in range(generations):
        # 计算适应度值
        fitness = [1 / calculate_total_distance(points, route) for route in population]
        
        # 选择操作：轮盘赌选择
        selected_indices = np.random.choice(range(population_size), size=population_size, p=fitness/np.sum(fitness))
        selected_population = [population[i] for i in selected_indices]
        
        # 变异操作
        mutated_population = [mutate(route) for route in selected_population]
        
        # 交叉操作：使用顺序交叉
        new_population = []
        for i in range(0, population_size, 2):
            parent1 = mutated_population[i]
            parent2 = mutated_population[(i + 1) % population_size]
            child1 = parent1.copy()
            child2 = parent2.copy()
            start_index, end_index = sorted(random.sample(range(len(points)), 2))
            for j in range(start_index, end_index + 1):
                child1[child1.index(parent2[j])] = parent1[j]
                child2[child2.index(parent1[j])] = parent2[j]
            new_population.extend([child1, child2])
        
        population = new_population
    
    best_route = min(population, key=lambda route: calculate_total_distance(points, route))
    return best_route

# 示例用法
points = [(0, 0), (1, 5), (2, 3), (5, 2), (6, 4)]
best_route = genetic_algorithm(points)
best_distance = calculate_total_distance(points, best_route)
print("最优路径：", best_route)
print("最短距离：", best_distance)

以上代码使用遗传算法来求解最优路径，其中`points`是送餐点的坐标列表。你可以根据实际情况修改`points`的值，并调整遗传算法的参数来获得更好的结果。