禁忌搜索算法求解CVRP问题Python代码复现

以下是禁忌搜索算法求解CVRP问题的Python代码实现。其中，CVRP问题是指车辆路径问题，即一组配送员需要在有限的时间内将货物从仓库送到多个客户处，并且每个客户有不同的需求量和时间窗口。算法的目标是在满足所有客户需求的前提下，最小化车辆的行驶路程。

import numpy as np
import random

class CVRP:
    def __init__(self, n_customers, max_demand, max_distance, capacity, coordinates):
        self.n_customers = n_customers
        self.max_demand = max_demand
        self.max_distance = max_distance
        self.capacity = capacity
        self.coordinates = coordinates

    def distance(self, i, j):
        return np.linalg.norm(self.coordinates[i] - self.coordinates[j])

    def demand(self):
        return np.random.randint(1, self.max_demand+1, self.n_customers)

    def solve(self, n_vehicles, max_iter, tabu_size):
        # Initialize variables
        best_solution = None
        best_cost = np.inf
        current_solution = []
        current_cost = np.inf
        tabu_list = []

        # Generate initial solution
        for i in range(n_vehicles):
            route = [0]
            capacity = self.capacity
            demand = self.demand()
            for j in range(1, self.n_customers+1):
                if capacity < demand[j-1]:
                    route.append(0)
                    route.append(j)
                    capacity = self.capacity - demand[j-1]
                else:
                    route.append(j)
                    capacity -= demand[j-1]
            route.append(0)
            current_solution.append(route)

        # Main loop
        for i in range(max_iter):
            # Find the best move
            best_move = None
            best_delta = np.inf
            for k in range(n_vehicles):
                for i in range(1, len(current_solution[k])-1):
                    for j in range(i+1, len(current_solution[k])-1):
                        delta = self.distance(current_solution[k][i-1], current_solution[k][j]) + \
                                self.distance(current_solution[k][i], current_solution[k][j+1]) - \
                                self.distance(current_solution[k][i-1], current_solution[k][i]) - \
                                self.distance(current_solution[k][j], current_solution[k][j+1])
                        if delta < best_delta and (k, i, j) not in tabu_list:
                            best_move = (k, i, j)
                            best_delta = delta

            # Apply the best move
            if best_move is not None:
                k, i, j = best_move
                current_solution[k][i:j+1] = current_solution[k][i:j+1][::-1]
                current_cost += best_delta
                tabu_list.append(best_move)
                if len(tabu_list) > tabu_size:
                    tabu_list.pop(0)

            # Update the best solution
            if current_cost < best_cost:
                best_solution = current_solution.copy()
                best_cost = current_cost

            # Print progress
            print(f"Iteration {i}: Best cost = {best_cost}")

        return best_solution, best_cost

代码中的`CVRP`类包含了以下方法：

- `__init__`: 初始化方法，接受以下参数：
- `n_customers`: 客户数量。
- `max_demand`: 每个客户的最大需求量。
- `max_distance`: 车辆的最大行驶距离。
- `capacity`: 车辆的最大容量。
- `coordinates`: 每个客户的坐标。
- `distance`: 计算两个客户之间的距离。
- `demand`: 随机生成每个客户的需求量。
- `solve`: 求解CVRP问题的方法，接受以下参数：
- `n_vehicles`: 车辆数量。
- `max_iter`: 最大迭代次数。
- `tabu_size`: 禁忌表的大小。

在`solve`方法中，我们首先生成了一个初始解，其中每个车辆依次访问每个客户，直到车辆的容量不足以满足下一个客户的需求为止。然后，我们开始迭代，每次迭代都尝试对当前解进行改进，直到达到最大迭代次数为止。在每次迭代中，我们尝试找到一个最佳移动，即将一个客户从一辆车移到另一辆车，或者将一个客户从一辆车移到同一辆车的不同位置。我们计算每个移动的成本，并选择成本最小的移动。如果找到了一个移动，则应用该移动，并将其添加到禁忌表中，以避免在接下来的几个迭代中再次尝试相同的移动。最后，我们更新最佳解和最佳成本，并打印出当前的进展情况。