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

创始人

2024-05-30 22:57:54

0次

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

1问题描述

1.1场景

单向：纯取货/纯送货；
单配送中心：只有一个配送中心/车场；
单车型：只考虑一种车型，
需求不可拆分：客户需求只能有一辆车满足；
车辆封闭：完成配送任务的车辆需回到配送中心；
车辆充足：不限制车辆数量，即配送车辆需求均能满足；
非满载：任意客户点的需求量小于车辆最大载重；

1.2要求

优化目标：最小化车辆启动成本和车辆行驶成本之和；
约束条件：车辆行驶距离约束，重量约束；
已知信息：配送中心位置、客户点位置、客户点需求、车辆最大载重、车辆最大行驶距离、车辆启动成本、车辆单位距离行驶成本；

2数学模型

2.1符号定义

2.2数学模型

2.3参数设置

车辆启动成本 C0 =30，车辆单位距离行驶成本C1 =1
详见problem.py

3遗传算法设计

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变异

4程序设计

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

import datetime
import heapq
import timeimport numpy as np
from matplotlib import pyplot as pltimport 路径优化.CVRP.problem as problem
from 路径优化.CVRP.population import Populationclass Algorithm:def __init__(self, problem: problem.CVRP):self.problem = problemnp.random.seed(47)self.currentGen = 0self.MAXGEN = 10000self.trace = {"obj": [], "solution": []}passdef mutation(self, pop):for i in range(10, 100):r1, r2 = np.random.randint(low=0, high=len(pop.chromMatrix[0]), size=2)chrom = pop.chromMatrix[i]chrom[r1], chrom[r2] = chrom[r2], chrom[r1]passdef crossover(self):passdef selection(self, pop: Population):off = Population(self.problem)fitV = pop.fitVif not isinstance(fitV, np.ndarray):fitV = np.asarray(fitV)elites_idx = heapq.nlargest(10, range(pop.NIND), pop.fitV.__getitem__)for i in range(0, 10):off.chromMatrix[i] = pop.chromMatrix[elites_idx[i]]# print(off)ps = fitV / np.sum(fitV)pc = np.cumsum(ps)for i in range(10, 100):r = np.random.random()select = 0for j in range(pop.NIND):if r < pc[j]:select = jbreakoff.chromMatrix[i] = pop.chromMatrix[select]return offdef run(self):population = Population(self.problem)population.initPop()self.problem.evaluate(population)while not self.terminated(population):offspring = self.selection(population)self.mutation(offspring)self.problem.evaluate(offspring)  # 计算目标函数值population = offspringreturn self.finish(population)def terminated(self, population):self.log(population)if self.currentGen + 1 >= self.MAXGEN:return Trueself.currentGen += 1return Falsedef log(self, pop: Population):idx = np.argmax(pop.fitV)self.trace["obj"].append(pop.objV[idx])self.trace["solution"].append(pop.phenMatrix[idx])print("obj=", pop.objV[idx])def finish(self, pop: Population):print("final solution:")idx = np.argmax(pop.fitV)routes = pop.phenMatrix[idx]print(routes)print("veh used:", len(routes))self.draw(routes)self.save(pop)def save(self, pop: Population):with open('final result.txt', 'a') as f:idx = np.argmax(pop.fitV)routes = pop.phenMatrix[idx]f.write("veh used:%d\n" % len(routes))f.write("%s\n" % routes)f.write("%s\n" % pop.objV[idx])def draw(self, routes):customers = self.problem.customersfor route in routes:x = []y = []for i in route:x.append(customers[i].x)y.append(customers[i].y)plt.plot(x, y, 'o-', alpha=0.8, linewidth=0.8)plt.xlabel('x')plt.ylabel('y')currentTime = datetime.datetime.strftime(datetime.datetime.now(), '%Y%m%d%H%M%S')plt.savefig("cg" + currentTime, bbox_inches="tight")plt.show()

5求解结果

本文求解结果，图左 obj= 566.6042140064762 final solution: [[0, 23, 30, 12, 7,
1, 13, 11, 0], [0, 6, 3, 2, 28, 4, 9, 18, 0], [0, 24, 29, 10, 25, 14,
0]] veh used: 3

6中博客求解结果：图右，运算结果最优解为728.1，路径为[0, 6, 19, 11, 3, 2, 28, 4, 9, 22, 8,
27, 18, 0], [0, 24, 29, 15, 10, 25, 5, 20, 16, 14, 0], [0, 23, 17, 21,
31, 26, 30, 12, 1, 13, 7, 0]