运筹学经典问题(八):CVRP和VRP-TW
文章目录
- 问题描述
- 问题建模
- 决策变量
- 数学建模
- 基于容量的消除子环的约束 (load-based SECs)
- CVRP完整的数学模型
- 加上时间窗限制的CVRP
问题描述
给定一个图,图上的点代表客户,边代表客户之间的路线,边的权重代表客户之间的距离,点上的数字代表每个用户的需求量。
数学符号表示如下:
本文讨论的问题背景:
- 用户需求已知,且被一辆车满足(不要拆开);
- 有 m m m辆车,且有相同的最大载量 L L L;
- 路网络是对称的(往返距离一样,不考虑上下坡之类的问题);
- 要么取货要么送货;
- 1个仓库,而且车的路线 T T T要是闭环的(最后要回到仓库);
- 只考虑1个规划周期;
- 目标是最小化车辆的行驶距离;
- 点0代表仓库。
问题建模
决策变量
数学建模
疑问:这种建模方式怎么知道每辆车的路线?
会有图上的哪些边被选中,形成 m m m个环,就知道啦!
目标函数:最小化行驶距离
m a x ∑ i , j ∈ V , i ≠ j x i j ∗ c i j max \sum_{i,j \in V, i \neq j}x_{ij}*c_{ij} max∑i,j∈V,i=jxij∗cij
约束1:车辆从每个客户出发一次
∑ j ∈ V , i ≠ j x i j = 1 , ∀ i ∈ V − { 0 } \sum_{j \in V, i \neq j}x_{ij} = 1, \forall i \in V-\{0\} ∑j∈V,i=jxij=1,∀i∈V−{0}
约束2:车辆进入每个客户一次
∑ j ∈ V , i ≠ j x j i = 1 , ∀ i ∈ V − { 0 } \sum_{j \in V, i \neq j}x_{ji} = 1, \forall i \in V-\{0\} ∑j∈V,i=jxji=1,∀i∈V−{0}
约束3:最多用 m m m辆车
∑ j ∈ V − { 0 } x 0 j ≤ m \sum_{j \in V-\{0\}}x_{0j} \leq m ∑j∈V−{0}x0j≤m
如果只是上面的模型,可能会出现下图这种解,右下角这个环没有包含仓库!因此,我们需要一个约束去消除这种不包含仓库的子环。此外,上面的约束也没有约束车辆的容量限制!这也是VRP建模的一个略难的约束。
基于容量的消除子环的约束 (load-based SECs)
学术上称为Sub-tour-elimination constraints (SECs),该约束需要保证:
1. 每个环路不超过车辆最大容量;
2. 每个环路都包含仓库。
新引入一个变量:
u i u_i ui: 假设我们的问题是车辆去客户那里取货, u i u_i ui表示车辆到达客户点 i i i时的载量, ∀ i ∈ V \forall i \in V ∀i∈V;
因此有如下约束:
如果我们选择了 ( i , j ) (i, j) (i,j)这条连边,那么车辆到达客户 i i i时的容量,加上用户 i i i寄货的重量,要为车辆到达客户 j j j时的容量。逻辑上是相等的,但是我理解是为了刻画这个等式的成立是基于 ( i , j ) (i, j) (i,j)这条连边被选择,所以描述成了下面的 ≤ \leq ≤的形式。
u i + b i ≤ u j + ( 1 − x i j ) L , ∀ i , j ∈ V − 0 , i ≠ j u_i + b_i \leq u_j + (1-x_{ij})L, \forall i,j \in V -{0},i \neq j ui+bi≤uj+(1−xij)L,∀i,j∈V−0,i=j
但是这个约束并没有刻画车辆的容量限制?
应该还要加一个:
u i ≤ L , ∀ i ∈ V u_i \leq L, \forall i \in V ui≤L,∀i∈V
CVRP完整的数学模型
加上时间窗限制的CVRP
假设某些客户只想在特定时间段被服务,那么在上述问题的基础上,我们需要引入如下新的常量定义:
同时,我们需要引入一个新的决策变量:
a i a_i ai:到达客户 i i i时的时间, ∀ i ∈ V \forall i \in V ∀i∈V
新增的约束包括:
1. 定义到达第一个客户的时间:
t 0 j x i j ≤ a j , ∀ j ∈ V t_{0j}x_{ij} \leq a_j, \forall j \in V t0jxij≤aj,∀j∈V
2. 约束两个连续访问的用户的时间:访问用户 i i i的时间+用户 i i i被服务的时间+从 i i i到 j j j的形式时间 = 访问用户 j j j的时间
a i + s i + t i j ≤ a j + ( 1 − x i j ) T , ∀ i , j ∈ V − 0 , i ≠ j a_i + s_i + t_{ij} \leq a_j + (1-x_{ij})T, \forall i,j \in V-0, i \neq j ai+si+tij≤aj+(1−xij)T,∀i,j∈V−0,i=j
3. 约束每个用户被访问的时间在指定时间窗内:
w i s ≤ a i , ∀ i ∈ V − 0 w_i^s \leq a_i, \forall i \in V-0 wis≤ai,∀i∈V−0
a i + s i ≤ w i e , ∀ j ∈ V − 0 a_i + s_i \leq w_i^e, \forall j \in V-0 ai+si≤wie,∀j∈V−0
相关文章:

运筹学经典问题(八):CVRP和VRP-TW
文章目录 问题描述问题建模决策变量数学建模基于容量的消除子环的约束 (load-based SECs) CVRP完整的数学模型加上时间窗限制的CVRP 问题描述 给定一个图,图上的点代表客户,边代表客户之间的路线,边的权重代表客户之间…...
AI与技术美术(TechArt)
AI技术与TA 人工智能(AI)技术在技术美术(TechArt)领域的应用,为创业者开辟了一片新的天地。技术美术作为一个跨学科领域,融合了传统美术和现代技术,特别是AI技术,以创造新型的艺术表…...

二叉树层序遍历 及相关题目
1,力扣102 给你二叉树的根节点 root ,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。 示例 1: 输入:root [3,9,20,null,null,15,7] 输出:[[3],[9,20],[15,7]]示例…...

【前端面试3+1】11 http和https有何不同及https的加密过程、数组有哪些方法及作用、tcp三次握手四次挥手、【分发饼干】
一、http和https有何不同?https的加密过程 1、不同: HTTP和HTTPS的主要区别在于安全性。HTTP是超文本传输协议,是一种用于传输数据的协议,但是传输的数据是明文的,容易被窃听和篡改。而HTTPS是在HTTP基础上加入了SSL/T…...

替代 Redis 和 Memcached:25 倍吞吐量! | 开源日报 No.213
dragonflydb/dragonfly Stars: 22.4k License: NOASSERTION Dragonfly 是一个内存数据存储,适用于现代应用工作负载,可替代 Redis 和 Memcached。与传统的内存数据存储相比,Dragonfly 提供了 25 倍的吞吐量、更高的缓存命中率和更低尾部延…...
Qt与OpenCV实现图像模板匹配
在 Qt 中使用 OpenCV 实现模板匹配可以通过集成 OpenCV 库和使用其相关函数来完成。以下是一般的步骤: 安装 OpenCV:首先,确保你已经安装了 OpenCV 库,并将其配置到你的开发环境中。 创建 Qt 项目:使用 Qt creator 或…...

OpenHarmony实战:CMake方式组织编译的库移植
以double-conversion库为例,其移植过程如下文所示。 源码获取 从仓库获取double-conversion源码,其目录结构如下表: 表1 源码目录结构 名称描述double-conversion/cmake/CMake组织编译使用到的模板double-conversion/double-conversion/源…...

Linux云计算之Linux基础3——Linux基本认识操作
1、终端 终端(terminal):人和系统交互的必要设备,人机交互最后一个界面(包含独立的输入输出设备) 物理终端(console):直接接入本机器的键盘设备和显示器虚拟终端(tty):通过软件方式虚拟实现的终端。它可以…...

canvas画图,画矩形、圆形、直线可拖拽移动,可拖拽更改尺寸大小
提示:canvas画图,画矩形,圆形,直线,曲线可拖拽移动 文章目录 前言一、画矩形,圆形,直线,曲线可拖拽移动总结 前言 一、画矩形,圆形,直线,曲线可拖…...
Github 2024-04-04 Go开源项目日报 Top10
根据Github Trendings的统计,今日(2024-04-04统计)共有10个项目上榜。根据开发语言中项目的数量,汇总情况如下: 开发语言项目数量Go项目10Python项目1Prometheus监控系统和时间序列数据库 创建周期:4149 天开发语言:Go协议类型:Apache License 2.0Star数量:52463 个Fork…...
并发与限流实战:如何利用 RabbitMQ 在 SpringBoot 应用中实现并发控制与流量限制
在高并发场景下,如大促销、秒杀等,我们可以采用 RabbitMQ 配合 SpringBoot 来实现并发控制与流量限制。你可以将 RabbitMQ 作为一个缓冲区,暂存大量并发请求,然后消费者可以根据自身处理能力去处理这些请求。下面就以一个高并发订…...
VUE实现下一页的功能
实现步骤:1、确定分页参数:确定当前页码和每页显示的数量;2、获取数据:使用vue的axios或其他http库向后端发送请求,传递当前页码和每页显示的数量作为参数;3、更新数据:在vue组件中,…...

GraalVM运行模式和企业级应用
文章目录 GraalVM运行模式JIT模式AOT模式 GraalVM的问题和解决方案GraalVM企业级应用传统架构的问题Serverless架构函数计算Serverless应用场景Serverless应用 GraalVM内存参数 GraalVM运行模式 JIT模式 JIT( Just-In-Time )模式 ,即时编译模…...

数据挖掘入门项目二手交易车价格预测之特征工程
文章目录 目标常见的特征工程具体步骤1. 导入数据2. 删除异常值3. 特征构造3.1 为树模型构造特征3.2 为LR NN 之类的模型构造特征 4. 特征筛选过滤式包裹式嵌入式 5. 总结 本文数据集来自阿里天池:https://tianchi.aliyun.com/competition/entrance/231784/informat…...

MFC通用静态库制作与使用
开发环境VS2013 1、新建工程,选择Win32 Project,命名,选择路径等 2、选择Static library ,勾选MFC 3、点击完成。在工程中添加相应的头文件、源文件等通用功能函数或者类。 4、在其他工程引入使用。在使用的工程项目设置中Linker…...

点亮创意:ChatGPT如何搭桥DALL-E图像编辑新纪元
每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗?订阅我们的简报,深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同,从行业内部的深度分析和实用指南中受益。不要错过这个机会,成为AI领…...

《QT实用小工具·十二》邮件批量发送工具
1、概述 源码放在文章末尾 该项目实现了邮件的批量发送,如下图所示: 项目部分代码如下所示: #ifndef SMTPCLIENT_H #define SMTPCLIENT_H#include <QtGui> #include <QtNetwork> #if (QT_VERSION > QT_VERSION_CHECK(5,0,…...

4.2总结
了解了部分Api的使用并学习了接口的API API API包含了较多种类(System,Runtime等) System其实就是一个工具类,提供了一些与系统相关的方法 下面有一些常间的System方法 方法名说明public static void exit (int status)终止当前运行的ja…...

ArcGIS 10.8中文版详细安装教程(附安装包)
ArcGIS 10.8中文版详细安装教程(附安装包) 关键词:ArcGIS 10.8中文版安装 1.概述 ArcGIS Desktop 10.8中文版是由ESRI公司开发的一款专业的地理信息系统,一套完整的桌面GIS软件套件,它包含ArcMap、ArcCatalog、ArcG…...
什么是EL表达式?怎么使用?
文章目录 一、什么是EL表达式1、命令格式:${作用域对象别名.共享数据} 二、EL表达式与作用域对象别名1、JSP文件可以使用的作用域对象2、EL表达式提供作用域对象别名3、EL表达式将引用对象属性写入到响应体4、EL表达式简化版 三、EL表达式与运算表达式四、EL表达式提…...

XML Group端口详解
在XML数据映射过程中,经常需要对数据进行分组聚合操作。例如,当处理包含多个物料明细的XML文件时,可能需要将相同物料号的明细归为一组,或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码,增加了开…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)
HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...

K8S认证|CKS题库+答案| 11. AppArmor
目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作: 1)、切换集群 2)、切换节点 3)、切换到 apparmor 的目录 4)、执行 apparmor 策略模块 5)、修改 pod 文件 6)、…...

工业安全零事故的智能守护者:一体化AI智能安防平台
前言: 通过AI视觉技术,为船厂提供全面的安全监控解决方案,涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面,能够实现对应负责人反馈机制,并最终实现数据的统计报表。提升船厂…...

【第二十一章 SDIO接口(SDIO)】
第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...
Golang dig框架与GraphQL的完美结合
将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用,可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器,能够帮助开发者更好地管理复杂的依赖关系,而 GraphQL 则是一种用于 API 的查询语言,能够提…...

AI书签管理工具开发全记录(十九):嵌入资源处理
1.前言 📝 在上一篇文章中,我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源,方便后续将资源打包到一个可执行文件中。 2.embed介绍 🎯 Go 1.16 引入了革命性的 embed 包,彻底改变了静态资源管理的…...
Linux离线(zip方式)安装docker
目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1:修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本:CentOS 7 64位 内核版本:3.10.0 相关命令: uname -rcat /etc/os-rele…...

算法:模拟
1.替换所有的问号 1576. 替换所有的问号 - 力扣(LeetCode) 遍历字符串:通过外层循环逐一检查每个字符。遇到 ? 时处理: 内层循环遍历小写字母(a 到 z)。对每个字母检查是否满足: 与…...

免费PDF转图片工具
免费PDF转图片工具 一款简单易用的PDF转图片工具,可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件,也不需要在线上传文件,保护您的隐私。 工具截图 主要特点 🚀 快速转换:本地转换,无需等待上…...