基于python下sko.GA的遗产算法解决CVRP(含容量约束的车辆最短路径)问题

本文主要是介绍基于python下sko.GA的遗产算法解决CVRP(含容量约束的车辆最短路径)问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

多vehicle的CVRP看作是one vehicle的CVRP,只是在vehicle自身负载的货物不够时,需要返回depot点
题目如下:
在这里插入图片描述
python代码

from sko.GA import GA_TSP
import matplotlib.pyplot as plt
import numpy as np# 坐标分布情况,(4,4)为补货地点吗
points_coordinate = np.array([[4,4],[2,8],[8,8],[0,7],[1,7],[5,6],[7,6],[3,5],[6,5],[5,3],[8,3],[1,2],[2,2],[3,1],[6,1],[0,0],[7,0]] )
# 除初始点(4,4)以外,每个地点货物需求量
requirements = [1,1,2,4,2,4,8,8,1,2,1,2,4,4,8,8]plt.scatter(*list(zip(*points_coordinate)))
plt.show()

在这里插入图片描述

# 可以将补货行为理解为多车辆单次VRP,总需求/最大载量,最小需要4次
num_vehicle = 4
max_capacity = 15
num_points = len(points_coordinate)
num_customers = num_points - 1
distance_matrix = np.linalg.norm(points_coordinate[:, None, :] - points_coordinate[None, :, :], axis=-1)# 计算总行驶距离:初始点(4,4)到第1路径点+第1路径的到第n路径点再回到初始点
# routine中包含初始点,用于计算车辆回到初始点的距离
def obj_func(routine):num_points, = routine.shapereturn distance_matrix[0, routine[0]] \+ sum([distance_matrix[routine[i % num_points], routine[(i + 1) % num_points]] for i in range(num_points)]) \+ distance_matrix[routine[-1], 0]# 增加约束,计算所有超出最大载量的累积数值,当作在计算个体fitness的时候的惩罚
def constraint_capacity(routine):capacity = 0c = 0for i in routine:if i != 0:c += requirements[i-1]else:capacity += max(0, c-max_capacity)c = 0capacity = max(c-max_capacity, capacity)return capacityga_tsp = GA_TSP(func=obj_func, n_dim=num_customers, size_pop=200, max_iter=200, prob_mut=1)# 生产Chrom个体,每个个体代表一个routine
# np.zeros(shape=(ga_tsp.size_pop, num_vehicle-1):为3次回到初始点(首次出发不算在内)
# ga_tsp.Chrom + 1:为剔除初始点的points_coordinate中的index
ga_tsp.Chrom = np.concatenate([np.zeros(shape=(ga_tsp.size_pop, num_vehicle-1), dtype=int), ga_tsp.Chrom + 1],axis=1)
#添加约束
ga_tsp.has_constraint = True
ga_tsp.constraint_ueq = [constraint_capacity]
best_points, best_distance = ga_tsp.run()
print(best_distance)

画图

fig, ax = plt.subplots(1, 2)
best_points_ = np.concatenate([[0], best_points, [0]])
best_points_coordinate = points_coordinate[best_points_, :]
ax[0].plot(best_points_coordinate[:, 0], best_points_coordinate[:, 1], 'o-r')
ax[1].plot(ga_tsp.generation_best_Y)
plt.show()

在这里插入图片描述

这篇关于基于python下sko.GA的遗产算法解决CVRP(含容量约束的车辆最短路径)问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1030755

相关文章

Python如何使用__slots__实现节省内存和性能优化

《Python如何使用__slots__实现节省内存和性能优化》你有想过,一个小小的__slots__能让你的Python类内存消耗直接减半吗,没错,今天咱们要聊的就是这个让人眼前一亮的技巧,感兴趣的... 目录背景:内存吃得满满的类__slots__:你的内存管理小助手举个大概的例子:看看效果如何?1.

Python+PyQt5实现多屏幕协同播放功能

《Python+PyQt5实现多屏幕协同播放功能》在现代会议展示、数字广告、展览展示等场景中,多屏幕协同播放已成为刚需,下面我们就来看看如何利用Python和PyQt5开发一套功能强大的跨屏播控系统吧... 目录一、项目概述:突破传统播放限制二、核心技术解析2.1 多屏管理机制2.2 播放引擎设计2.3 专

Python中随机休眠技术原理与应用详解

《Python中随机休眠技术原理与应用详解》在编程中,让程序暂停执行特定时间是常见需求,当需要引入不确定性时,随机休眠就成为关键技巧,下面我们就来看看Python中随机休眠技术的具体实现与应用吧... 目录引言一、实现原理与基础方法1.1 核心函数解析1.2 基础实现模板1.3 整数版实现二、典型应用场景2

Python实现无痛修改第三方库源码的方法详解

《Python实现无痛修改第三方库源码的方法详解》很多时候,我们下载的第三方库是不会有需求不满足的情况,但也有极少的情况,第三方库没有兼顾到需求,本文将介绍几个修改源码的操作,大家可以根据需求进行选择... 目录需求不符合模拟示例 1. 修改源文件2. 继承修改3. 猴子补丁4. 追踪局部变量需求不符合很

Spring事务中@Transactional注解不生效的原因分析与解决

《Spring事务中@Transactional注解不生效的原因分析与解决》在Spring框架中,@Transactional注解是管理数据库事务的核心方式,本文将深入分析事务自调用的底层原理,解释为... 目录1. 引言2. 事务自调用问题重现2.1 示例代码2.2 问题现象3. 为什么事务自调用会失效3

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

mysql出现ERROR 2003 (HY000): Can‘t connect to MySQL server on ‘localhost‘ (10061)的解决方法

《mysql出现ERROR2003(HY000):Can‘tconnecttoMySQLserveron‘localhost‘(10061)的解决方法》本文主要介绍了mysql出现... 目录前言:第一步:第二步:第三步:总结:前言:当你想通过命令窗口想打开mysql时候发现提http://www.cpp

python+opencv处理颜色之将目标颜色转换实例代码

《python+opencv处理颜色之将目标颜色转换实例代码》OpenCV是一个的跨平台计算机视觉库,可以运行在Linux、Windows和MacOS操作系统上,:本文主要介绍python+ope... 目录下面是代码+ 效果 + 解释转HSV: 关于颜色总是要转HSV的掩膜再标注总结 目标:将红色的部分滤

SpringBoot启动报错的11个高频问题排查与解决终极指南

《SpringBoot启动报错的11个高频问题排查与解决终极指南》这篇文章主要为大家详细介绍了SpringBoot启动报错的11个高频问题的排查与解决,文中的示例代码讲解详细,感兴趣的小伙伴可以了解一... 目录1. 依赖冲突:NoSuchMethodError 的终极解法2. Bean注入失败:No qu

Python 中的异步与同步深度解析(实践记录)

《Python中的异步与同步深度解析(实践记录)》在Python编程世界里,异步和同步的概念是理解程序执行流程和性能优化的关键,这篇文章将带你深入了解它们的差异,以及阻塞和非阻塞的特性,同时通过实际... 目录python中的异步与同步:深度解析与实践异步与同步的定义异步同步阻塞与非阻塞的概念阻塞非阻塞同步