【进阶五】Python实现SDVRP(需求拆分)常见求解算法——离散粒子群算法(DPSO)

基于python语言,采用经典离散粒子群算法(DPSO)对 需求拆分车辆路径规划问题(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.pl=[] # 个体历史最优解self.pg=None # 种群历史最优解self.v=[] # 速度集合self.Vmax=5 # 最大移动速度self.w=0.8 # 惯性权重self.c1=2 # 信息启发式因子self.c2=2 # 信息启发式因子

(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]=max(d,0.0001) if i != j else 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 updatePosition(model):w=model.wc1=model.c1c2=model.c2pg = model.pgfor id,sol in enumerate(model.sol_list):x=sol.node_no_seqv=model.v[id]pl=model.pl[id].node_no_seqr1=random.random()r2=random.random()new_v=[]for i in range(model.number_of_demands):v_=w*v[i]+c1*r1*(pl[i]-x[i])+c2*r2*(pg[i]-x[i])if v_>0:new_v.append(min(v_,model.Vmax))else:new_v.append(max(v_,-model.Vmax))new_x=[min(int(x[i]+new_v[i]),model.number_of_demands-1) for i in range(model.number_of_demands) ]new_x=adjustRoutes(new_x,model)model.v[id]=new_vnew_x_obj,new_x_route_list,new_x_route_distance=calObj(new_x,model)if new_x_obj<model.pl[id].obj:model.pl[id].node_no_seq=copy.deepcopy(new_x)model.pl[id].obj=new_x_objmodel.pl[id].route_list=new_x_route_listmodel.pl[id].route_distance = new_x_route_distanceif new_x_obj<model.best_sol.obj:model.best_sol.obj=copy.deepcopy(new_x_obj)model.best_sol.node_no_seq=copy.deepcopy(new_x)model.best_sol.route_list=copy.deepcopy(new_x_route_list)model.best_sol.route_distance = copy.deepcopy(new_x_route_distance)model.pg=copy.deepcopy(new_x)model.sol_list[id].node_no_seq = copy.deepcopy(new_x)model.sol_list[id].obj = copy.deepcopy(new_x_obj)model.sol_list[id].route_list = copy.deepcopy(new_x_route_list)model.sol_list[id].routes_distance = copy.deepcopy(new_x_route_distance)
# 调整不可行解
def adjustRoutes(node_no_seq,model):all_node_id_list=copy.deepcopy(model.demand_id_list_)repeat_node=[]for id,node_no in enumerate(node_no_seq):if node_no in all_node_id_list:all_node_id_list.remove(node_no)else:repeat_node.append(id)for i in range(len(repeat_node)):node_no_seq[repeat_node[i]]=all_node_id_list[i]return node_no_seq

参考

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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/284527.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

linux文本三剑客 --- grep、sed、awk

1、grep grep&#xff1a;使用正则表达式搜索文本&#xff0c;将匹配的行打印出来&#xff08;匹配到的标红&#xff09; 命令格式&#xff1a;grep [option] pattern file <1> 命令参数 -A<显示行数>&#xff1a;除了显示符合范本样式的那一列之外&#xff0c;并…

C语言中的联合体和枚举

联合体 联合体的创建 联合体的关键字是union union S {char a;int i; };除了关键字和结构体不一样之外&#xff0c;联合体的创建语法形式和结构体的很相似&#xff0c;如果不熟悉结构体的创建&#xff0c;可以看一下我上一篇的博客关于结构体知识的详解。 联合体的特点 联合…

Personal Website

Personal Website Static Site Generators hexo hugo jekyll Documentation Site Generator gitbook vuepress vitepress docsify docute docusaurus Deployment 1. GitHub Pages 2. GitLab Pages 3. vercel 4. netlify Domain 域名注册 freessl 域名解析域名…

【GUI】自动化办公

目录 一、GUI介绍 二、环境安装 三、鼠标移动操作 四、鼠标点击操作 五、拖动鼠标 六、鼠标滚动操作 七、屏幕快照&图像识别基础 7.1 屏幕快照&#xff08;截图&#xff09; 7.2 图像识别 八、键盘控制 一、GUI介绍 GUI自动化就是写程序直接控制键盘和鼠标。这些…

电脑如何关闭自启动应用?cmd一招解决问题

很多小伙伴说电脑刚开机就卡的和定格动画似的&#xff0c;cmd一招解决问题&#xff1a; CtrlR打开cmd,输入&#xff1a;msconfig 进入到这个界面&#xff1a; 点击启动&#xff1a; 打开任务管理器&#xff0c;禁用不要的自启动应用就ok了

【prometheus-operator】k8s监控集群外redis

1、部署exporter GitHub - oliver006/redis_exporter: Prometheus Exporter for Redis Metrics. Supports Redis 2.x, 3.x, 4.x, 5.x, 6.x, and 7.x redis_exporter-v1.57.0.linux-386.tar.gz # 解压 tar -zxvf redis_exporter-v1.57.0.linux-386.tar.gz # 启动 nohup ./redi…

SpringCloud-记

目录 什么是SpringCloud 什么是微服务 SpringCloud的优缺点 SpringBoot和SpringCloud的区别 RPC 的实现原理 RPC是什么 eureka的自我保护机制 Ribbon feigin优点 Ribbon和Feign的区别 什么是SpringCloud Spring Cloud是一系列框架的有序集合。它利用Spring Boot的开发…

力扣面试150 阶乘后的零 数论 找规律 质因数

Problem: 172. 阶乘后的零 思路 &#x1f468;‍&#x1f3eb; 大佬神解 一个数末尾有多少个 0 &#xff0c;取决于这个数 有多少个因子 10而 10 可以分解出质因子 2 和 5而在阶乘种&#xff0c;2 的倍数会比 5 的倍数多&#xff0c;换而言之&#xff0c;每一个 5 都会找到一…

AI时代Python金融大数据分析实战:ChatGPT让金融大数据分析插上翅膀

❤️作者主页&#xff1a;小虚竹 ❤️作者简介&#xff1a;大家好,我是小虚竹。2022年度博客之星评选TOP 10&#x1f3c6;&#xff0c;Java领域优质创作者&#x1f3c6;&#xff0c;CSDN博客专家&#x1f3c6;&#xff0c;华为云享专家&#x1f3c6;&#xff0c;掘金年度人气作…

电脑照片分辨率怎么调?这款dpi修改工具好用

许多考试平台在上传证件照片的时候&#xff0c;大多都会对图片分辨率有具体要求&#xff0c;但是如果遇上手上的图片分辨率达不到要求&#xff0c;那么怎么改图片分辨率呢&#xff1f;可以利用专业的dpi修改工具来处理&#xff0c;比如今天分享的就是一个在线修改图片分辨率的方…

唯众物联网安装调试员实训平台物联网一体化教学实训室项目交付山东技师学院

近日&#xff0c;山东技师学院物联网安装调试员实训平台及物联网一体化教学实训室采购项目已顺利完成交付并投入使用&#xff0c;标志着学院在物联网技术教学与实践应用方面迈出了坚实的一步。 山东技师学院作为国内知名的技师培养摇篮&#xff0c;一直以来致力于为社会培养高…

select , poll, epoll思维导图

目录 1. 总的框架结构 2. select 3. poll 4. epoll 1. 总的框架结构 2. select

自动驾驶轨迹规划之时空语义走廊(一)

欢迎大家关注我的B站&#xff1a; 偷吃薯片的Zheng同学的个人空间-偷吃薯片的Zheng同学个人主页-哔哩哔哩视频 (bilibili.com) 目录 1.摘要 2.系统架构 3.MPDM 4.时空语义走廊 ​4.1 种子生成 4.2 具有语义边界的cube inflation ​4.3 立方体松弛 本文解析了丁文超老师…

解决Animate.css动画效果无法在浏览器运行问题

背景 在开发官方网站的时候&#xff0c;临时更换了电脑&#xff0c;发现原本正常的动画效果突然不动了。 经过 chrome、Microsoft Edge都无法运行。 Animate.css | A cross-browser library of CSS animations. 问题排查 通过审查元素后发现类名是注入并且生效的。 验证 然…

视频素材库在哪里找无水印?推荐几个优质高清视频素材网

在探索创作无限可能的旅程中&#xff0c;每位视频创作者都渴望找到那些能够让作品生动起来、讲述更加动人故事的素材。为此&#xff0c;我继续为你介绍一系列的无水印高清素材网站&#xff0c;它们不仅能为你的视频添加视觉与听觉的魅力&#xff0c;还能帮助你以更高效的方式实…

阿里云2核4G服务器支持多少人在线?2C4G多少钱一年?

2核4G服务器支持多少人在线&#xff1f;阿里云服务器网账号下的2核4G服务器支持20人同时在线访问&#xff0c;然而应用不同、类型不同、程序效率不同实际并发数也不同&#xff0c;2核4G服务器的在线访问人数取决于多个变量因素。 阿里云2核4G服务器多少钱一年&#xff1f;2核4…

分布式ID生成方案总结

分布式场景下&#xff0c;需要保证每一个服务拿到的id是唯一的。本文讨论、分析、总结了一些常见的分布式ID生成方案 结论&#xff1a;技术上没有银弹&#xff0c;每种分布式id都有自己的使用场景。uuid适用于业务比较简单&#xff0c;对性能没有太高追求等。 目前主流是 基于数…

Linux V4L2 应用编程

V4L2&#xff1a;Video4Linux2&#xff0c;是 Linux 内核中的一个框架&#xff0c;提供了一套用于视频设备驱动程序开发的 API。它是一个开放的、通用的、模块化的视频设备驱动程序框架&#xff0c;允许 Linux 操作系统和应用程序与各种视频设备&#xff08;如摄像头、视频采集…

【NLP笔记】RNN总结

文章目录 经典RNN单向RNN双向RNNDeep RNNRNN特性总结 变体RNNLSTMGRU 参考及转载内容&#xff1a; 循环神经网络&#xff08;RNN&#xff09;深度学习05-RNN循环神经网络完全理解RNN&#xff08;循环神经网络&#xff09; 传统的CNN&#xff08;Covolutional Neural Network&am…

【异或】Leetcode 136. 只出现一次的数字

【异或】Leetcode 136. 只出现一次的数字 解法1 只需要全部异或一下&#xff0c;剩下的就是剩下的元素 ---------------&#x1f388;&#x1f388;题目链接 136. 只出现一次的数字&#x1f388;&#x1f388;------------------- 解法1 只需要全部异或一下&#xff0c;剩下的…