【进阶六】Python实现SDVRPTW（需求拆分）常见求解算法——禁忌搜索+模拟退火算法（TS+SA）

🕗 发布于 2024-04-28 16:27 算法 python SDVRPTW 路径优化 TS

基于python语言，采用经典禁忌搜索（TS）+模拟退火（SA）对 带硬时间窗的需求拆分车辆路径规划问题（SDVRPTW） 进行求解。

往期优质资源

经过一年多的创作，目前已经成熟的代码列举如下，如有需求可私信联系，表明需要的 **问题与算法**，原创不宜，有偿获取。

VRP问题	GA	ACO	ALNS	DE	DPSO	QDPSO	TS	SA
CVRP	√	√	√	√	√	√	√	√
VRPTW	√	√	√	√	√	√	√	√
MDVRP	√	√	√	√	√	√	√	√
MDHVRP	√	√	√	√	√	√	√	√
MDHVRPTW	√	√	√	√	√	√	√	√
SDVRP	√	√	√	√	√	√	√	√
SDVRPTW	√	√	√	√	√	√	√	√

1. 适用场景

求解SDVRPTW
车辆类型单一
车辆容量小于部分需求节点需求
单一车辆基地
带硬时间窗

2. 代码调整

2.1 需求拆分

与SDVRP问题相比，SDVRPTW问题不仅允许客户需求大于车辆载重，而且考虑了客户节点的时间窗约束。为了使得每个客户的需求得到满足，必须派遣一辆或多辆车辆在规定时间窗内对客户进行服务。对于需求节点的拆分，这里依然采取先验拆分策略，本文采用文献[1]提出的先验分割策略，表述如下：

（1）20/10/5/1拆分规则

m₂₀ =max{ $m\in Z^+ \cup \{0\} | 0.20Qm <= D_i$ }
m₁₀ =max{ $m\in Z^+ \cup \{0\} | 0.10Qm <= D_i-0.20Qm_{20}~$ }
m₅ =max{ $m\in Z^+ \cup \{0\} | 0.05Qm <= D_i-0.20Qm_{20}-0.10Qm_{10}$ }
m₁ =max{ $m\in Z^+ \cup \{0\} | 0.01Qm <= D_i-0.20Qm_{20}-0.10Qm_{10}-0.05Qm_{5}$ }

（2）25/10/5/1拆分规则

m₂₅ =max{ $m\in Z^+ \cup \{0\} | 0.25Qm <= D_i$ }
m₁₀ =max{ $m\in Z^+ \cup \{0\} | 0.10Qm <= D_i-0.25Qm_{25}~$ }
m₅ =max{ $m\in Z^+ \cup \{0\} | 0.05Qm <= D_i-0.25Qm_{25}-0.10Qm_{10}$ }
m₁ =max{ $m\in Z^+ \cup \{0\} | 0.01Qm <= D_i-0.25Qm_{25}-0.10Qm_{10}-0.05Qm_{5}$ }

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

2.2 需求拆分后的服务时长取值问题

节点的服务时长会影响车辆的行进时间，进而会影响与节点时间窗的匹配问题。一般来说，节点的服务时长与需求量成正比关系，在进行节点需求拆分后，新节点的需求量降低，其服务时长理应也降低。但从标准数据集来看，各需求节点的服务时长均采用同一数值。因此本文在代码实现过程中也采用固定值，不考虑新节点服务时长的变化。当然，如有需要，也可以设置单位货物的服务时长，根据拆分后节点的具体需求量设置相应的服务时长。

3. 求解结果

3.1 TS

（1）收敛曲线
在这里插入图片描述
（2）车辆路径

（3）输出内容
在这里插入图片描述

3.2 SA

（1）收敛曲线
在这里插入图片描述

（2）车辆路径
在这里插入图片描述

（3）输出内容
在这里插入图片描述

4. 代码片段

（1）数据结构

import math
import random
import numpy as np
import copy
import xlsxwriter
import matplotlib.pyplot as plt
import csv
import time
# 数据结构：解
class Sol():
    def __init__(self):
        self.obj=None # 目标函数值
        self.node_no_seq=[] # 解的编码
        self.route_list=[] # 解的解码
        self.timetable_list=[] # 车辆访问各点的时间
        self.route_distance_list = None
        self.action_id = None  # 对应的算子id
# 数据结构：需求节点
class Node():
    def __init__(self):
        self.id=0 # 节点id
        self.x_coord=0 # 节点平面横坐标
        self.y_coord=0  # 节点平面纵坐标
        self.demand=0 # 节点需求
        self.start_time=0 # 节点开始服务时间
        self.end_time=1440 # 节点结束服务时间
        self.service_time=0 # 单次服务时长
        self.vehicle_speed = 0 # 行驶速度
# 数据结构：车场节点
class Depot():
    def __init__(self):
        self.id=0 # 节点id
        self.x_coord=0 # 节点平面横坐标
        self.y_coord=0  # 节点平面纵坐标
        self.start_time=0 # 节点开始服务时间
        self.end_time=1440 # 节点结束服务时间
        self.v_speed = 0 # 行驶速度
        self.v_cap = 80 # 车辆容量
# 数据结构：全局参数
class Model():
    def __init__(self):
        self.best_sol=None # 全局最优解
        self.sol_list=[] # 解的集合
        self.demand_dict = {}  # 需求节点集合
        self.depot = None  # 车场节点集合
        self.demand_id_list = [] # 需求节点id集合
        self.distance_matrix = {}  # 距离矩阵
        self.time_matrix = {}  # 时间矩阵
        self.number_of_demands = 0 # 需求点数量
        self.demand_id_list_ = []  # 经先验需求分割后的节点集合
        self.demand_dict_ = {}  # 需求分割后的节点需求集合
        self.distance_matrix_ = {}  # 原始节点id间的距离矩阵
        self.time_matrix_ = {}  # 原始节点id间的时间矩阵
        self.mapping = {}  # 需求分割前后的节点对应关系
        self.split_rate = 0.5 # 控制需求分割的比例（需求超出车辆容量的除外）
        self.popsize = 100 # 种群规模
        self.split_rate = 0.5 # 控制需求分割的比例（需求超出车辆容量的除外）
        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 d
        dist = 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] = dist
        model.distance_matrix[model.depot.id, i] = dist

（3）邻域

# 构造初始解
def genInitialSol(node_no_seq):
    node_no_seq=copy.deepcopy(node_no_seq)
    random.shuffle(node_no_seq)
    return node_no_seq
# 定义邻域算子
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]=temporary
        return node_no_seq
    elif 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_seq
    elif 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

原文地址：https://blog.csdn.net/python_n/article/details/138242072

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：嵌入式全栈开发学习笔记---Linux基本命令2
下一篇：MySQL数据库总结

ASO优化应用程序截图元数据的终极指南（含3C规则）
让我们举一些实际的例子：如果你的应用程序是一个照片编辑器，你可能想设计一个带有相机的图标，而如果你的应用程序是一个计步器，你可能想展示一个走路的人。视觉元数据是应用程序上的一种窗口，因为它可以帮助用户
阅读更多2024-11-07
Go语言基础语法
因此，这里的索引是指字节在字符串中的位置，而不是字符在字符串中的位置（对于多字节字符，后者可能更有用，但 Go 的 range 在字符串上不提供这种索引）。在 Go 语言中，chan 关键字用于创建通
阅读更多2024-11-07
长亭那个检测能力超强的 WAF，出免费版啦
告诉你们一个震撼人心的消息，那个检测能力超强的 WAF——长亭雷池，他推出免费社区版啦，体验地址见文末。八年前我刚从学校毕业，在腾讯做安全研究，看到宇森在 BlackHat 上演讲的议题《永别了
阅读更多2024-11-07
Spring JDBC模板
定义一个实体类，用于映射数据库表中的数据。return id;定义一个DAO类，使用JdbcTemplate进行数据库操作。// 插入用户)";// 查询所有用户// 根据ID查询用户//
阅读更多2024-11-07
数据分析：宏基因组DESeq2差异分析筛选差异物种
数据分析：宏基因组DESeq2差异分析筛选差异物种
阅读更多2024-11-07
【教程】第二章：设计任务管理系统 —— 胸有成竹，步步为营
NocoBase 使用一种叫做“Collection”的定义来描述数据结构，这样可以统一不同来源的数据，为数据管理和分析提供坚实基础。它支持创建多种类型的数据表，包括普通表、继承表、树表、日历表、文件
阅读更多2024-11-07
动漫风格大模型和lora推荐
使用comfyui内置下载器下载。
阅读更多2024-11-07
跨境电商营销：Pinterest的5个便捷营销工具
了解Pinterest营销工具的特点和使用方法，结合可靠的网络工具，为账号运营和营销推广工作提供更优保障！
阅读更多2024-11-07
[蓝桥杯算法从小白到大牛]动态规划第二讲:三步问题
目录1->题目链接2->题目解析3->讲解算法原理核心流程:3.1->状态表示3.2->状态转移方程(最重要的一步)3.3->初始化3.4->
阅读更多2024-11-07
IPTV直播源自动检测和更新工具
Guovin/TV 是直播源自动检测和更新工具，支持多种运行方式。
阅读更多2024-11-07