当前位置: 首页 > news >正文

【进阶五】Python实现SDVRP(需求拆分)常见求解算法——蚁群算法(ACO)

基于python语言,采用经典遗传算法(ACO)对 需求拆分车辆路径规划问题(SDVRP) 进行求解。

目录

  • 往期优质资源
  • 1. 适用场景
  • 2. 代码调整
  • 3. 求解结果
  • 4. 代码片段
  • 参考

往期优质资源


经过一年多的创作,目前已经成熟的代码列举如下,如有需求可私信联系,表明需要的 问题与算法,原创不宜,有偿获取。
VRP问题GAACOALNSDEDPSOQDPSOTSSA
CVRP
VRPTW
MDVRP
MDHVRP
MDHVRPTW
SDVRP

1. 适用场景

  • 求解CVRP
  • 车辆类型单一
  • 车辆容量小于部分需求节点需求
  • 单一车辆基地

2. 代码调整


与CVRP问题相比,SDVRP问题允许客户需求大于车辆容量。为了使得每个客户的需求得到满足,必须派遣一辆或多辆车辆对客户进行服务,也就是需要对客户的需求进行拆分。关于如何进行拆分一般有两种方式:

  • 先验拆分策略:提前制定策略对客户的需求(尤其是大于车辆容量的客户需求)进行分解,将SDVRP问题转化为CVRP问题
  • 过程拆分策略:在车辆服务过程中对客户需求进行动态拆分

本文采用文献[1]提出的先验分割策略,表述如下:

(1)20/10/5/1拆分规则

  • m20 =max{ m ∈ Z + ∪ { 0 } ∣ 0.20 Q m < = D i m\in Z^+ \cup \{0\} | 0.20Qm <= D_i mZ+{0}∣0.20Qm<=Di }
  • m10 =max{ m ∈ Z + ∪ { 0 } ∣ 0.10 Q m < = D i − 0.20 Q m 20 m\in Z^+ \cup \{0\} | 0.10Qm <= D_i-0.20Qm_{20}~ mZ+{0}∣0.10Qm<=Di0.20Qm20  }
  • m5 =max{ m ∈ Z + ∪ { 0 } ∣ 0.05 Q m < = D i − 0.20 Q m 20 − 0.10 Q m 10 m\in Z^+ \cup \{0\} | 0.05Qm <= D_i-0.20Qm_{20}-0.10Qm_{10} mZ+{0}∣0.05Qm<=Di0.20Qm200.10Qm10 }
  • m1 =max{ m ∈ Z + ∪ { 0 } ∣ 0.01 Q m < = D i − 0.20 Q m 20 − 0.10 Q m 10 − 0.05 Q m 5 m\in Z^+ \cup \{0\} | 0.01Qm <= D_i-0.20Qm_{20}-0.10Qm_{10}-0.05Qm_{5} mZ+{0}∣0.01Qm<=Di0.20Qm200.10Qm100.05Qm5 }

(2)25/10/5/1拆分规则

  • m25 =max{ m ∈ Z + ∪ { 0 } ∣ 0.25 Q m < = D i m\in Z^+ \cup \{0\} | 0.25Qm <= D_i mZ+{0}∣0.25Qm<=Di }
  • m10 =max{ m ∈ Z + ∪ { 0 } ∣ 0.10 Q m < = D i − 0.25 Q m 25 m\in Z^+ \cup \{0\} | 0.10Qm <= D_i-0.25Qm_{25}~ mZ+{0}∣0.10Qm<=Di0.25Qm25  }
  • m5 =max{ m ∈ Z + ∪ { 0 } ∣ 0.05 Q m < = D i − 0.25 Q m 25 − 0.10 Q m 10 m\in Z^+ \cup \{0\} | 0.05Qm <= D_i-0.25Qm_{25}-0.10Qm_{10} mZ+{0}∣0.05Qm<=Di0.25Qm250.10Qm10 }
  • m1 =max{ m ∈ Z + ∪ { 0 } ∣ 0.01 Q m < = D i − 0.25 Q m 25 − 0.10 Q m 10 − 0.05 Q m 5 m\in Z^+ \cup \{0\} | 0.01Qm <= D_i-0.25Qm_{25}-0.10Qm_{10}-0.05Qm_{5} mZ+{0}∣0.01Qm<=Di0.25Qm250.10Qm100.05Qm5 }

在实现过程中,对于需求超过车辆容量的客户必须进行需求拆分,而对于未超过车辆容量的客户可以拆分也可以不拆分,这里设置了参数比例进行限制。

3. 求解结果


(1)收敛曲线

在这里插入图片描述

(2)车辆路径

在这里插入图片描述

4. 代码片段


(1)数据结构

# 数据结构:解
class Sol():def __init__(self):self.node_no_seq = None # 节点id有序排列self.obj = None # 目标函数self.fitness = None  # 适应度self.route_list = None # 车辆路径集合self.route_distance_list = None  # 车辆路径长度集合
# 数据结构:网络节点
class Node():def __init__(self):self.id = 0 # 节点idself.x_coord = 0 # 节点平面横坐标self.y_coord = 0 # 节点平面纵坐标self.demand = 0 # 节点需求
# 数据结构:全局参数
class Model():def __init__(self):self.best_sol = None # 全局最优解self.demand_id_list = [] # 需求节点集合self.demand_dict = {}self.sol_list = [] # 解的集合self.depot = None # 车场节点self.number_of_demands = 0 # 需求节点数量self.vehicle_cap = 0 # 车辆最大容量self.distance_matrix = {} # 节点距离矩阵self.demand_id_list_ = [] # 经先验需求分割后的节点集合self.demand_dict_ = {} # 需求分割后的节点需求集合self.distance_matrix_ = {}  # 原始节点id间的距离矩阵self.mapping = {}  # 需求分割前后的节点对应关系self.split_rate = 0.5 # 控制需求分割的比例(需求超出车辆容量的除外)self.popsize = 100 # 种群规模self.alpha = 2 # 信息启发式因子self.beta = 3 # 期望启发式因子self.Q = 100 # 信息素总量self.rho = 0.5 # 信息素挥发因子self.tau = {} # 弧信息素集合self.tau0 = 100 # 路径初始信息素

(2)距离矩阵

# 初始化参数
def cal_distance_matrix(model):for i in model.demand_id_list:for j in model.demand_id_list:d=math.sqrt((model.demand_dict[i].x_coord-model.demand_dict[j].x_coord)**2+(model.demand_dict[i].y_coord-model.demand_dict[j].y_coord)**2)model.distance_matrix[i,j]=ddist = math.sqrt((model.demand_dict[i].x_coord - model.depot.x_coord) ** 2 + (model.demand_dict[i].y_coord - model.depot.y_coord) ** 2)model.distance_matrix[i, model.depot.id] = distmodel.distance_matrix[model.depot.id, i] = dist

(3)蚁群移动

# 蚂蚁移动
def movePosition(model):sol_list=[]local_sol=Sol()local_sol.obj=float('inf')for _ in range(model.popsize):#随机初始化蚂蚁为止node_no_seq=[random.randint(0,len(model.demand_id_list_)-1)]all_node_no_seq=copy.deepcopy(model.demand_id_list_)all_node_no_seq.remove(node_no_seq[-1])#确定下一个访问节点while len(all_node_no_seq)>0:next_node_no=searchNextNode(model,node_no_seq[-1],all_node_no_seq)node_no_seq.append(next_node_no)all_node_no_seq.remove(next_node_no)sol=Sol()sol.node_no_seq=node_no_seqsol.obj,sol.route_list,sol.route_distance=calObj(node_no_seq,model)sol_list.append(sol)if sol.obj < local_sol.obj:local_sol = copy.deepcopy(sol)model.sol_list=copy.deepcopy(sol_list)if local_sol.obj<model.best_sol.obj:model.best_sol=copy.deepcopy(local_sol)
# 搜索下一移动节点
def searchNextNode(model,current_node_no,SE_List):prob=np.zeros(len(SE_List))for i,node_no in enumerate(SE_List):eta=1/model.distance_matrix_[current_node_no,node_no] if model.distance_matrix_[current_node_no,node_no] else 0.0001tau=model.tau[current_node_no,node_no]prob[i]=((eta**model.alpha)*(tau**model.beta))#采用轮盘法选择下一个访问节点cumsumprob=(prob/sum(prob)).cumsum()cumsumprob -= np.random.rand()return SE_List[list(cumsumprob >= 0).index(True)]
# 更新路径信息素
def upateTau(model):rho=model.rhofor k in model.tau.keys():model.tau[k]=(1-rho)*model.tau[k]#根据解的node_no_seq属性更新路径信息素(TSP问题的解)for sol in model.sol_list:node_no_seq=sol.node_no_seqfor i in range(len(node_no_seq)-1):from_node_no=node_no_seq[i]to_node_no=node_no_seq[i+1]model.tau[from_node_no,to_node_no]+= model.Q/sol.objfor k in model.tau.keys():model.tau[k]= max(model.tau[k],0.000001)

参考

【1】 A novel approach to solve the split delivery vehicle routing problem

相关文章:

【进阶五】Python实现SDVRP(需求拆分)常见求解算法——蚁群算法(ACO)

基于python语言&#xff0c;采用经典遗传算法&#xff08;ACO&#xff09;对 需求拆分车辆路径规划问题&#xff08;SDVRP&#xff09; 进行求解。 目录 往期优质资源1. 适用场景2. 代码调整3. 求解结果4. 代码片段参考 往期优质资源 经过一年多的创作&#xff0c;目前已经成熟…...

php.exe运行时,提示缺少VCRUNTIME140.dll

php.exe运行时&#xff0c;提示缺少VCRUNTIME140.dll 下载地址 https://www.microsoft.com/zh-cn/download/details.aspx?id48145根据需要选择下载3.运行安装后&#xff0c;再次运行php.exe。...

Android垃圾回收机制

1.垃圾回收机制 垃圾回收&#xff0c;也叫GC(Garbage Collection)&#xff0c;指的是释放垃圾占用的空间&#xff0c;防止内存泄露。有效的使用可以使用的内存&#xff0c;对内存堆中已经死亡的或者长时间没有使用的对象进行清除和回收。 JVM的内存区域主要分为程序计数器、虚…...

深度学习专家学习计划

深度学习专家学习计划 一、学习背景与目标 作为一名有6年工作经验的Java开发人员,您已具备基本的编程能力和数据处理经验。现计划转岗至深度学习领域,成为深度学习专家。本计划将结合您的工作背景和现有知识,为您制定详细且精确的学习计划,帮助您逐步达到专家水平。 二、…...

关于Ubuntu虚拟机突然上不了网的问题

今天刚重新把Ubuntu虚拟机下回来准备大干一场&#xff0c;结果去吃饭回来虚拟机就上不去网了&#xff0c;具体体现为右上角没有网络的图标&#xff0c;下图是有网络的情况&#xff0c;废话不多说&#xff0c;直接给出解决方案&#xff1a;博客在此 我就是运行了这三行代码就成功…...

[mysql必备面试题]-InnoDB和MyISAM引擎的区别

InnoDB 是 MySQL 默认的事务型存储引擎&#xff0c;只有在需要它不支持的特性时&#xff0c;才考虑使用其它存储引擎。 实现了四个标准的隔离级别&#xff0c;默认级别是可重复读(REPEATABLE READ)。在可重复读隔离级别下&#xff0c;通过多版本并发控制(MVCC) 间隙锁(Next-K…...

android 播放rtsp流的三种方式,2024阿里Android高级面试题总结

使用SurfaceViewMediaPlayer <SurfaceView android:id“id/surface_view” android:layout_width“250dp” android:layout_height“250dp” app:layout_constraintRight_toRightOf“parent” app:layout_constraintTop_toTopOf“parent” /> private String uri …...

unity显示当前时间

1建立文本组件和一个空对象 2创建一个脚本并复制下面代码 using System.Collections; using System.Collections.Generic; using TMPro; using UnityEngine;public class showtime: MonoBehaviour {public TextMeshProUGUI time;private void Update(){string currentTime Sy…...

SDK报错(1)undefined reference to `f_mount‘

利用SDK读取sd卡时&#xff0c;添加了xilffs库&#xff0c;而且包含了ff.h头文件&#xff0c;还是对fat库的函数报错 网上有的说在ARM v7 gcc linker中添加xilffs的方法可以解决&#xff0c;但我试了没有用 最后在赛灵思论坛找到了一个解决方法&#xff0c;原文连接如下 在SDK…...

YOLOv8_pose-Openvino和ONNXRuntime推理【CPU】

纯检测系列&#xff1a; YOLOv5-Openvino和ONNXRuntime推理【CPU】 YOLOv6-Openvino和ONNXRuntime推理【CPU】 YOLOv8-Openvino和ONNXRuntime推理【CPU】 YOLOv7-Openvino和ONNXRuntime推理【CPU】 YOLOv9-Openvino和ONNXRuntime推理【CPU】 跟踪系列&#xff1a; YOLOv5/6/7-O…...

百科 | 光伏电站如何开展运维工作?

从目前太阳能光伏电站的运行管理工作实际经验看&#xff0c;要保证光伏发电系统安全、经济、高效运行&#xff0c;必须建立规范和有效的管理机制&#xff0c;特别是要加强电站的运行维护管理。 一、建立完善的技术文件管理体系 对每个电站都要建立全面完整的技术文件资料档案…...

监听抖音直播间的评论并实现存储

监听抖音直播间评论&#xff0c;主要是动态监听dom元素的变化&#xff0c;如果评论是图片类型的&#xff0c;获取alt的值 主要采用的是MutationObserver&#xff1a;https://developer.mozilla.org/zh-CN/docs/Web/API/MutationObserver index.js如下所示:function getPL() {…...

一体机电脑辐射超标整改

电脑一体机是目前台式机和笔记本电脑之间的一个新型的市场产物&#xff0c;它将主机部分、显示器部分整合到一起的新形态电脑&#xff0c;该产品的创新在于内部元件的高度集成。随着无线技术的发展&#xff0c;电脑一体机的键盘、鼠标与显示器可实现无线链接&#xff0c;机器只…...

重学SpringBoot3-路径匹配机制

更多SpringBoot3内容请关注我的专栏&#xff1a;《SpringBoot3》 期待您的点赞&#x1f44d;收藏⭐评论✍ 重学SpringBoot3-路径匹配机制 AntPathMatcherPathPatternParser 和 PathPattern演示AntPathMatcher 示例PathPattern 示例性能和精确度的提升 选择使用哪一种 在 Spring…...

【贪心算法】摆动序列

如果连续数字之间的差严格地在正数和负数之间交替&#xff0c;则数字序列称为 摆动序列 。第一个差&#xff08;如果存在的话&#xff09;可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。 例如&#xff0c; [1, 7, 4, 9, 2, 5] 是一个 摆动序列 &…...

Unload-labs

function checkFile() {var file document.getElementsByName(upload_file)[0].value;if (file null || file "") {alert("请选择要上传的文件!");return false;}//定义允许上传的文件类型var allow_ext ".jpg|.png|.gif";//提取上传文件的类…...

SRS-220VDC-4Z-10A静态中间继电器 额定电压DC220V 四副转换触点 JOSEF约瑟

系列型号&#xff1a; SRS-24VDC-4Z-8A静态中间继电器&#xff1b;SRS-24VDC-4Z-10A静态中间继电器&#xff1b; SRS-24VDC-4Z-16A静态中间继电器&#xff1b;SRS-24VAC-4Z-8A静态中间继电器&#xff1b; SRS-24VAC-4Z-10A静态中间继电器&#xff1b;SRS-24VAC-4Z-16A静态中…...

解决electron打包vue-element-admin项目页面无法跳转的问题

解决electron打包vue-element-admin项目页面无法跳转的问题 说明之前通过这个教程已经打包成功&#xff0c;但是发现进行账号密码登录后页面无法跳转的问题。现在已经解决&#xff0c;所以记录一下。 1、检查路由模式是否为hash模式&#xff0c;如果不是改成hash模式。 new Ro…...

Uniapp Vue2 image src动态绑定static目录下的图片

报错的static地址写法&#xff1a; this.url ../static/img.png this.url /static/img.png 正确的static地址写法&#xff1a; this.url /static/img.png 动态绑定 <image :src"url"></image>...

【UE5】动画混合空间的基本用法

项目资源文末百度网盘自取 什么是动画混合空间 混合空间分为两种: 通过一个数值控制通过两个数值控制 下面通过演示让大家更直观地了解 在Character文件夹中单击右键,选择动画(Animation),选择旧有的混合空间1D 然后选择骨骼&#xff08;动画是基于骨骼显示的,所以需要选择…...

linux之kylin系统nginx的安装

一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

VB.net复制Ntag213卡写入UID

本示例使用的发卡器&#xff1a;https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...

【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器

一.自适应梯度算法Adagrad概述 Adagrad&#xff08;Adaptive Gradient Algorithm&#xff09;是一种自适应学习率的优化算法&#xff0c;由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率&#xff0c;适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...

Unity3D中Gfx.WaitForPresent优化方案

前言 在Unity中&#xff0c;Gfx.WaitForPresent占用CPU过高通常表示主线程在等待GPU完成渲染&#xff08;即CPU被阻塞&#xff09;&#xff0c;这表明存在GPU瓶颈或垂直同步/帧率设置问题。以下是系统的优化方案&#xff1a; 对惹&#xff0c;这里有一个游戏开发交流小组&…...

AtCoder 第409​场初级竞赛 A~E题解

A Conflict 【题目链接】 原题链接&#xff1a;A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串&#xff0c;只有在同时为 o 时输出 Yes 并结束程序&#xff0c;否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

uniapp微信小程序视频实时流+pc端预览方案

方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度​WebSocket图片帧​定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐​RTMP推流​TRTC/即构SDK推流❌ 付费方案 &#xff08;部分有免费额度&#x…...

WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)

一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解&#xff0c;适合用作学习或写简历项目背景说明。 &#x1f9e0; 一、概念简介&#xff1a;Solidity 合约开发 Solidity 是一种专门为 以太坊&#xff08;Ethereum&#xff09;平台编写智能合约的高级编…...

LeetCode - 199. 二叉树的右视图

题目 199. 二叉树的右视图 - 力扣&#xff08;LeetCode&#xff09; 思路 右视图是指从树的右侧看&#xff0c;对于每一层&#xff0c;只能看到该层最右边的节点。实现思路是&#xff1a; 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...

群晖NAS如何在虚拟机创建飞牛NAS

套件中心下载安装Virtual Machine Manager 创建虚拟机 配置虚拟机 飞牛官网下载 https://iso.liveupdate.fnnas.com/x86_64/trim/fnos-0.9.2-863.iso 群晖NAS如何在虚拟机创建飞牛NAS - 个人信息分享...

OD 算法题 B卷【正整数到Excel编号之间的转换】

文章目录 正整数到Excel编号之间的转换 正整数到Excel编号之间的转换 excel的列编号是这样的&#xff1a;a b c … z aa ab ac… az ba bb bc…yz za zb zc …zz aaa aab aac…; 分别代表以下的编号1 2 3 … 26 27 28 29… 52 53 54 55… 676 677 678 679 … 702 703 704 705;…...