【进阶五】Python实现SDVRP(需求拆分)常见求解算法——禁忌搜索+模拟退火算法(TS+SA)

基于python语言,采用经典禁忌搜索(TS)+模拟退火(SA)对 需求拆分车辆路径规划问题(SDVRP) 进行求解。

目录

  • 往期优质资源
  • 1. 适用场景
  • 2. 代码调整
  • 3. 求解结果
    • 3.1 TS
    • 3.2 SA
  • 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. 求解结果


3.1 TS


(1)收敛曲线
在这里插入图片描述

(2)车辆路径
在这里插入图片描述

3.2 SA


(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  # 车辆路径长度集合self.action_id = None # 对应的算子id
# 数据结构:网络节点
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.tabu_list=None # 禁忌表self.TL=30 # 禁忌长度

(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 createActions(n):action_list=[]nswap=n//2#第一种算子(Swap):前半段与后半段对应位置一对一交换for i in range(nswap):action_list.append([1,i,i+nswap])#第二中算子(DSwap):前半段与后半段对应位置二对二交换for i in range(0,nswap-1,2):action_list.append([2,i,i+nswap])#第三种算子(Reverse):指定长度的序列反序for i in range(0,n,4):action_list.append([3,i,i+3])return action_list
# 执行邻域搜索
def doAction(node_no_seq,action):node_no_seq=copy.deepcopy(node_no_seq)if action[0]==1:index_1=action[1]index_2=action[2]temporary=node_no_seq[index_1]node_no_seq[index_1]=node_no_seq[index_2]node_no_seq[index_2]=temporaryreturn node_no_seqelif action[0]==2:index_1 = action[1]index_2 = action[2]temporary=[node_no_seq[index_1],node_no_seq[index_1+1]]node_no_seq[index_1]=node_no_seq[index_2]node_no_seq[index_1+1]=node_no_seq[index_2+1]node_no_seq[index_2]=temporary[0]node_no_seq[index_2+1]=temporary[1]return node_no_seqelif action[0]==3:index_1=action[1]index_2=action[2]node_no_seq[index_1:index_2+1]=list(reversed(node_no_seq[index_1:index_2+1]))return node_no_seq

参考

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

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

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

相关文章

MySQL索引(图文并茂)

目录 一、索引的概念 二、索引的作用 三、创建索引的原则依据 四、索引的分类和创建 1、索引的分类 2、索引的创建 2.1 普通索引 2.1.1 直接创建索引 2.1.2 修改表方式创建 2.1.3 创建表的时候指定索引 2.2 唯一索引 2.2.1 直接创建唯一索引 2.2.2 修改表方式创建 …

C 多维数组

C 语言支持多维数组。多维数组声明的一般形式如下&#xff1a; type name[size1][size2]...[sizeN];例如&#xff0c;下面的声明创建了一个三维 5 . 10 . 4 整型数组&#xff1a; int threedim[5][10][4];二维数组 多维数组最简单的形式是二维数组。一个二维数组&#xff0c…

每秒批量插入10000条数据到MySQL中,资源消耗(带宽、IOPS)有多少?

文章目录 &#x1f50a;博主介绍&#x1f964;本文内容起因代码资源情况改造 &#x1f4e2;文章总结&#x1f4e5;博主目标 &#x1f50a;博主介绍 &#x1f31f;我是廖志伟&#xff0c;一名Java开发工程师、Java领域优质创作者、CSDN博客专家、51CTO专家博主、阿里云专家博主、…

Redis入门到实战-第十二弹

Redis实战热身Bitfields篇 完整命令参考官网 官网地址 声明: 由于操作系统, 版本更新等原因, 文章所列内容不一定100%复现, 还要以官方信息为准 https://redis.io/Redis概述 Redis是一个开源的&#xff08;采用BSD许可证&#xff09;&#xff0c;用作数据库、缓存、消息代理…

Elasticsearch:使用在本地计算机上运行的 LLM 以及 Ollama 和 Langchain 构建 RAG 应用程序

无需 GPU 的隐私保护 LLM。在本博客中&#xff0c;我将演示使用不同的工具 Ollama 构建的 RAG 应用程序。 与本文相关的所有源代码均已发布在 github上。 请克隆存储库以跟随文章操作。我们可以通过如下的方式来克隆&#xff1a; git clone https://github.com/liu-xiao-guo/o…

Unity 学习笔记 5.控制飞机飞行

目录 1.摄像机跟随的方法 2.鼠标按键响应 3.键盘按键响应 4.导入素材 5.让飞机向前飞 6.摄像机跟随飞机移动 7.鼠标控制飞机倾斜 8.键盘控制飞机飞行 下载源码 UnityPackage 1.摄像机跟随的方法 2.鼠标按键响应 3.键盘按键响应 4.导入素材 下载素材 步骤&#xff1a; 将…

itextPdf生成pdf简单示例

文章环境 jdk1.8&#xff0c;springboot2.6.13 POM依赖 <dependency><groupId>com.itextpdf</groupId><artifactId>itextpdf</artifactId><version>5.5.13</version></dependency><dependency><groupId>com.ite…

3/21 work

自由发挥登录窗口的应用场景&#xff0c;实现一个登录窗口界面。&#xff08;不要使用课堂上的图片和代码&#xff0c;自己发挥&#xff0c;有利于后面项目的完成&#xff09; 要求&#xff1a; 1. 需要使用Ui界面文件进行界面设计 2. ui界面上的组件相关设置&#xff0c;通…

网络——套接字编程UDP

目录 端口号 源端口号和目的端口号 认识TCP协议和UDP协议 网络字节序 socket编程接口 socket常见接口 sockaddr结构 UDP socket bind recvfrom sendto 编写客户端 绑定INADDR_ANY 实现聊天功能 端口号 在这之前我们已经说过源IP地址和目的IP地址&#xff0c;还有…

【vue核心技术实战精讲】1.6 - 1.8 VUE 指令 (中)

文章目录 前言 本节内容1、v-on使用v-on好处效果 2、事件修饰符2.1、按键码 (<font color red>已废弃&#xff0c;不用研究)示例效果 3、v-for 列表渲染示例效果 前言 上节,我们学习了 Vue指令之v-text 、 v-html、v-if 、v-show、v-bind 点击进入上一节 本节内容 Vue…

敏捷开发——第二次作业JS/服务器的部署

部署 Web 服务器 1. 安装 Apache HTTP 服务器并部署静态网页应用 ⭐⭐ 默认情况下&#xff0c;Apache 在 /var/www/html 目录下寻找要提供服务的文件。可以将静态网页文件放置在这个目录下 2.安装 Nginx 并部署静态页面应用 3. 实践部分 1. 2. 3. 在 /var/www/html 目录下…

matlab 条件数的倒数

目录 一、概述1、算法概述2、主要函数3、参考文献二、条件设置错误的矩阵的敏感度三、求解单位矩阵的条件四、参考链接本文由CSDN点云侠原创,原文链接。如果你不是在点云侠的博客中看到该文章,那么此处便是不要脸的爬虫。 一、概述 1、算法概述

快速上手 Elasticsearch:Docker Compose 部署详解

最近面试竞争日益激烈&#xff0c;Elasticsearch作为一款广泛应用的中间件&#xff0c;几乎成为面试中必考的知识点。最近&#xff0c;AIGC也备受关注&#xff0c;而好多的AI项目中也采用了Elasticsearch作为向量数据库&#xff0c;因此我们迫切希望学习Elasticsearch。对于学习…

鸿蒙NXET实战:高德地图定位SDK【获取Key+获取定位数据】(二)

如何申请key 1、创建新应用 进入[控制台]&#xff0c;创建一个新应用。如果您之前已经创建过应用&#xff0c;可直接跳过这个步骤。 2、添加新Key 在创建的应用上点击"添加新Key"按钮&#xff0c;在弹出的对话框中&#xff0c;依次&#xff1a;输入应用名名称&…

如何修复WordPress网站媒体库上传文件失败的问题

公司最近推出了一系列新产品&#xff0c;为了更新网站的视频和图片&#xff0c;我们需要将它们上传至网站媒体库。然而&#xff0c;在上传视频时&#xff0c;我们却遇到了一些问题。系统提示说&#xff0c;我们尝试上传的视频文件大小超出了站点的最大上传限制。尽管我们的视频…

apisix创建https

总结了下apisix 使用https 的问题和方法 1、apisix 默认https 端口是9443 2、apisix 需要上传证书后才可以使用https 否二curl测试会报错 SSL routines:CONNECT_CR_SRVR_HELLO 3、apisix 上传证书方法 我是使用的自签名证书&#xff0c;注意自签名证书的Common Name 要写你…

Open CASCADE学习|显示文本

目录 1、修改代码 Viewer.h&#xff1a; Viewer.cpp&#xff1a; 2、显示文本 OpenCasCade 你好啊 霜吹花落 1、修改代码 在文章《Open CASCADE学习|显示模型》基础上&#xff0c;增加部分代码&#xff0c;实现对文本显示的支持&#xff0c;具体如下&#xff1a; Viewer…

思腾合力携AI服务器亮相第二十一届中国电博会

博会已发展成为海峡两岸IT产业界规模最大、参展企业最多、产业配套最全的知名展会之一&#xff0c;今年以“数字赋能、创新制造”为主题&#xff0c;线下参展企业达400家。展会期间&#xff0c;举办了论坛与产业洽谈会等系列活动&#xff0c;进一步推动了两岸电子信息产业融合发…

进程和线程,线程实现的几种基本方法

什么是进程&#xff1f; 我们这里学习进程是为了后面的线程做铺垫的。 一个程序运行起来&#xff0c;在操作系统中&#xff0c;就会出现对应的进程。简单的来说&#xff0c;一个进程就是跑起来的应用程序。 在电脑上我们可以通过任务管理器可以看到&#xff0c;跑起来的应用程…

redis在springboot项目中的应用

一&#xff0c;将查询结果放到redis中作为缓存&#xff0c;减轻mysql的压力。 只有在数据量大的时候&#xff0c;查询速度慢的时候才有意义。 本次测试的数据量为百万级别。 测试代码: 功能为根据昵称进行模糊匹配。 GetMapping("/get-by-nick")public String get…