运筹学经典问题(八):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表达式提…...
基于php医院预约挂号系统
摘 要 随着信息时代的来临,过去的管理方式缺点逐渐暴露,对过去的医院预约挂号管理方式的缺点进行分析,采取计算机方式构建医院预约挂号系统。本文通过阅读相关文献,研究国内外相关技术,开发并设计一款医院预约挂号系统…...
Java NIO详解
一、概念 NIO, 即new io,也叫非阻塞io 二、NIO三个核心组件: Buffer数据缓冲区Channel通道Selector选择器 1、Buffer缓冲区 缓冲区本质上是一个可以存放数据的内存块(类似数组),可以在这里进行数据写入和读取。此…...
InstantID作者的风格保持新项目InstantStyle发布,一个强化版的IPapadter来了!
之前已经和大家介绍过InstantID相关相关的文章,感兴趣的小伙伴可以点击下面链接进行阅读~ 无缝衔接Stable Diffusion,一张照片几秒钟就能生成个性化图片-InstantID_instant-id 模型-CSDN博客 今天向大家介绍Ins…...
【Java程序员面试专栏 综合面试指南】5年资深程序员面试指南
基础知识对于5年内工作经验的同学考察相对比较多。包括编程语言、计算机网络、操作系统、设计模式、分布式知识、MySQL、Redis这种。其中随着年限的增长,基础知识考察的会越来越少,例如操作系统基本上只在学生阶段考察,计算机网络对于5年经验来说也考察的相对较少。5年以上对…...
echart 仪表盘实现指针的渐变色及添加图片
需求: 在仪表盘中设置指针为渐变色,并在仪表盘中间添加图片。 实现重点: 1、仪表盘指针渐变色的实现 渐变色通过设置pointer的itemStyle属性内的color实现,重点是echart版本,这个原本使用4.8.0的版本不起作用ÿ…...
C#面试题目含参考答案(一)
前言 面试是应聘一个工作岗位的环节,来考察一个人的工作能力与综合素质。在应聘C#程序员或与C#相关岗位时,我们都会被问到一些与.NET、C#、数据库、业务知识或编程思想等问题。本文列举一些问题及提供参考答案,题目(一)。 题目 1、什么是面向对象的三大特性 参考答案:…...
【Canvas技法】图解绘制圆弧的重要函数 arc(x,y,r,startAngle,endAngle,clockWise)
【一图释疑】 【绘制上图用代码】 <!DOCTYPE html> <html lang"utf-8"> <meta http-equiv"Content-Type" content"text/html; charsetutf-8"/> <head><title>Html5/Canvas中绘制圆弧的重要函数 arc(x,y,r,startA…...
vulhub中Apache Solr 远程命令执行漏洞复现(CVE-2019-0193)
Apache Solr 是一个开源的搜索服务器。Solr 使用 Java 语言开发,主要基于 HTTP 和 Apache Lucene 实现。此次漏洞出现在Apache Solr的DataImportHandler,该模块是一个可选但常用的模块,用于从数据库和其他源中提取数据。它具有一个功能&#…...
水泥5G智能制造工厂数字孪生可视化平台,推进水泥行业数字化转型
水泥5G智能制造工厂数字孪生可视化平台,推进水泥行业数字化转型。水泥5G智能制造工厂数字孪生可视化平台,是水泥行业数字化转型的关键推手。数字孪生平台运用先进的信息技术和数字化手段,实现水泥生产过程的数字化模拟、可视化监控和智能化管…...
vue 一个简单实例化Vue.js 是一个流行的前端框架,如何创建一个基本的计数器应用
当然可以!Vue.js 是一个流行的前端框架,用于构建用户界面。下面是一个简单的 Vue.js 例子,演示了如何创建一个基本的计数器应用。 首先,确保你已经在项目中引入了 Vue.js。你可以通过 CDN 引入 Vue.js,或者在项目中安…...
低价做营销企业网站/seo网络推广是干嘛的
随着时间的推移,我们在实践中也不断的演进我们的服务部署方案,希望WEB防护,不只是单独的云WAF来保护服务,而有其它的相关服务,对WAF进行增强加固的合理配合。我们使用Openresty系统构建了WAF,而在实际的应用…...
网站开发模式分为/长春seo网站排名
06-9-27在网吧里,任何时间都会有人在吃饭,有人在睡觉,有人在玩。不论是清晨,中午,还是深夜,都有一些人挺不住了,他们用疲惫无神的双眼仔细注视着屏幕,仿佛创作中的马克思。他们是铁人…...
狭义的网络营销是什么/seo关键词排名优化
什么是类图? 的UML 类图是用于构建和可视化的面向对象的系统的图形表示法。统一建模语言(UML)中的类图是一种静态结构图,通过显示系统来描述系统的结构: 类,他们的属性(或属性)&am…...
网站开发的核心技术/新网站如何推广
小X 正困在一个密室里,他希望尽快逃出密室。 密室中有N 个房间,初始时,小X 在1 号房间,而出口在N 号房间。 密室的每一个房间中可能有着一些钥匙和一些传送门,一个传送门会单向地创造一条从房间X 到房间Y 的通道。另外…...
网站psd切图做响应式效果/惠州seo外包平台
原文地址为: 征服ExtJs那棵树(ExtJs官方开发手册汉语详解--TreePanel)结构图 概述 TreePanel是在Ext JS中最功能丰富的组件之一,是一个非常棒的工具,用于显示在应用程序中的结构化数据。TreePanel是从GridPane继承的类,因此,所有GridPanel的特…...
如何用wordpress做企站/汕头seo推广优化
原文链接:(http://blog.csdn.net/u013474104/article/details/43527937) 有一次我把/etc/profile下的配置文件给更改错了,谁知道,操作系统启动出现了问题。不论执行什么命令都会报:-bash:命令 :command not found 解决方案: 使…...