### Python 实现配送中心选址算法 #### 配送中心选址问题概述 配送中心选址问题是设施布局中的一个重要分支，旨在找到最佳位置来建立一个或多个配送中心，使得总成本最小化。这通常涉及到运输费用、建设成本和其他运营开销。 #### 使用遗传算法求解配送中心选址问题 遗传算法是一种启发式的全局搜索方法，适用于处理复杂的组合优化问题。对于配送中心选址而言，可以通过编码潜在的位置作为染色体个体，并利用交叉变异操作探索可能的解决方案空间[^2]。 下面是一个简单的Python实现例子： ```python import numpy as np from random import randint, uniform, sample class GeneticAlgorithmForFacilityLocation: def __init__(self, demand_points, candidate_centers, num_of_centers=3, population_size=50, crossover_rate=0.9, mutation_rate=0.1, generations=100): """ 初始化参数 :param demand_points: list of tuples (x,y), 表示各个需求点的位置坐标 :param candidate_centers: list of tuples (x,y)，表示候选配送中心的位置坐标 :param num_of_centers: int, 所需选择的配送中心数量，默认为3个 :param population_size: 种群大小，默认为50 :param crossover_rate: 交配概率，默认为0.9 :param mutation_rate: 变异概率，默认为0.1 :param generations: 进化的代数，默认为100 """ self.demand_points = demand_points self.candidate_centers = candidate_centers self.num_of_centers = min(num_of_centers, len(candidate_centers)) self.population_size = population_size self.crossover_rate = crossover_rate self.mutation_rate = mutation_rate self.generations = generations @staticmethod def fitness(individual, demands, candidates): """计算适应度函数""" selected_indices = set([i for i in individual if i >= 0]) total_cost = sum(min(abs(x - cx) + abs(y - cy) for idx, (cx, cy) in enumerate(candidates) if idx in selected_indices) for x, y in demands) return -total_cost # 负号用于最大化目标值 def generate_initial_population(self): """生成初始种群""" pop = [] while len(pop) < self.population_size: indv = [-1]*len(self.candidate_centers) indices = sample(range(len(self.candidate_centers)), k=self.num_of_centers) for index in indices: indv[index] = index pop.append(np.array(indv)) return np.vstack(pop) def main(): # 定义一些测试数据 DEMAND_POINTS = [(uniform(-10, 10), uniform(-10, 10)) for _ in range(10)] CANDIDATE_CENTERS = [(uniform(-10, 10), uniform(-10, 10)) for _ in range(20)] ga_solver = GeneticAlgorithmForFacilityLocation(DEMAND_POINTS, CANDIDATE_CENTERS, num_of_centers=3) best_solution = None max_fitness_value = float('-inf') current_generation = ga_solver.generate_initial_population() for gen in range(ga_solver.generations): next_gen = [] for parent_a, parent_b in zip(current_generation[:ga_solver.population_size//2], reversed(current_generation)): child_one, child_two = parent_a.copy(), parent_b.copy() if np.random.rand() <= ga_solver.crossover_rate: cross_point = randint(0, len(parent_a)-1) temp = child_one[cross_point:].copy() child_one[cross_point:] = child_two[cross_point:] child_two[cross_point:] = temp if np.random.rand() <= ga_solver.mutation_rate: mutate_index = randint(0, len(child_one)-1)**randint(0, 1)*mutate_index if mutate_index not in child_one else -1 child_one[mutate_index] = new_val next_gen.extend((child_one, child_two)) current_generation = sorted(next_gen, key=lambda x: ga_solver.fitness(x, DEMAND_POINTS, CANDIDATE_CENTERS), reverse=True)[:ga_solver.population_size] top_individual = current_generation[0] fit_score = ga_solver.fitness(top_individual, DEMAND_POINTS, CANDIDATE_CENTERS) if fit_score > max_fitness_value: max_fitness_value = fit_score best_solution = top_individual print(f'Generation {gen}: Best Fitness Value={max_fitness_value}') if __name__ == '__main__': main() ``` 这段代码展示了如何使用遗传算法在一组预定义的需求点和候选地点之间寻找最优的三个配送中心位置。注意这里的距离被简化为了曼哈顿距离（即绝对差之和），实际应用中可以根据具体情况进行调整。