基于遗传算法的CVRP建模求解（Python）

基于遗传算法的CVRP建模求解（Python）

• 一、CVRP问题描述
• • 1.1场景
  • 1.2要求
  • 二、CVRP数学模型
  • • 2.1符号定义
    • 2.2数学模型
    • 2.3参数设置
    • 三、遗传算法设计
    • • 3.1 染色体编码、解码
      • 3.2交叉变异
      • 四、基于遗传算法的CVRP建模求解（Python）
      • 五、CVRP标准算例测试集
      • 参考

        带容量约束的车辆路径优化问题，CVRP，对一系列装卸货点进行适当的路径规划，在满足约束条件（客户需求、车辆载重和容积、车型、车辆行驶里程、配送中心数量等限制）和目标最优化（路程最短、成本最低、使用车辆数最少、配送时间最快等）下，将客户的配送需求从配送中心送达客户点，或从客户点送回配送中心。

        一、CVRP问题描述

        1.1场景

        单向：纯取货/纯送货；

        单配送中心：只有一个配送中心/车场；

        单车型：只考虑一种车型，

        需求不可拆分：客户需求只能有一辆车满足；

        车辆封闭：完成配送任务的车辆需回到配送中心；

        车辆充足：不限制车辆数量，即配送车辆需求均能满足；

        非满载：任意客户点的需求量小于车辆最大载重；

        1.2要求

        优化目标：最小化车辆启动成本和车辆行驶成本之和；

        约束条件：车辆行驶距离约束，重量约束；

        已知信息：配送中心位置、客户点位置、客户点需求、车辆最大载重、车辆最大行驶距离、车辆启动成本、车辆单位距离行驶成本；

        二、CVRP数学模型

        2.1符号定义

        2.2数学模型

        2.3参数设置

        车辆启动成本 C0 =30，车辆单位距离行驶成本C1 =1

        详见problem.py

        三、遗传算法设计

        3.1 染色体编码、解码

        同TSP问题生成方式，以客户点（编号为1，2，3…）为自然数编码（不包含配送中心0）

        解码：考虑车辆载重和行驶距离约束的8客户点染色体[8，4，1，5，2，3，6，7]解码为

        【0，8，4，1，0】

        【0，5，2，0】

        【0，3，6，7，0】

        3.2交叉变异

        采用两点交叉、和2-opt变异，和TSP问题相同，见基于自适应遗传算法的TSP问题建模求解（Java）

        四、基于遗传算法的CVRP建模求解（Python）

        下载连接：https://download.csdn.net/download/qq_43276566/87554423

        分为四个模块，populatioin.py、algorithm.py，problem.py 和程序运行接口run-cvrp.py。

        完整代码如下：

        import datetimeimport heapqimport itertoolsimport timeimport numpy as npimport mathfrom typing import Dict, Listfrom scipy import spatialfrom matplotlib import pyplot as pltnp.set_printoptions(    precision=2,  # 显示到小数点后几位，默认是4    threshold=None,  # 超过默认1000行数据，折叠显示    edgeitems=None,  # 折叠显示前/后    linewidth=4000,  # 换行字符长度)def timer(func):    def inner(*args, **kwargs):        start = time.time()        gbest = func(*args, **kwargs)        end = time.time()        print(f'程序运行时间：{round(end - start, 2)}s')        return gbest    return innerclass Population:    pop_size: int    def __init__(self, problem):        self.pop_size = 100  # 种群规模        self.problem = problem        self.chrom_matrix = np.empty(shape=(self.pop_size, 31), dtype=np.int64)  # 种群染色体编码矩阵        self.phenMatrix = []  # 每条染色体的表现型        self.objV = []  # 目标函数值        self.fitV = []  # 适应度函数    def init_chrom(self):        """        :return:初始化染色体        """        chrom = np.arange(1, self.problem.num_customer)        np.random.shuffle(chrom)        return chrom    def initialize_pop(self):        """初始化种群"""        # self.chrom_matrix = []        # for i in range(self.pop_size):        #     chrom = self.init_chrom()        #     self.chrom_matrix.append(chrom)        self.chrom_matrix = [self.init_chrom() for _ in range(self.pop_size)]    def decodePop(self):        for i in range(self.pop_size):            routes = self.decode_chrom(self.chrom_matrix[i])            self.phenMatrix.append(routes)    def decode_chrom(self, chrom: list):        problem = self.problem        capacity = 0        distance = 0        route = [0]        totalDist = 0        routes = []        i = 0        while i