当前位置: 首页 > news >正文

论文导读|European Journal of Operational Research近期文章精选:旅行商问题专题

 

推文作者:王松阁

编者按

在“European Journal of Operational Research近期论文精选”中,我们有主题、有针对性地选择了European Journal of Operational Research中一些有趣的文章,不仅对文章的内容进行了概括与点评,而且也对文章的结构进行了梳理,旨在激发广大读者的阅读兴趣与探索热情。在本期“论文精选”中,我们以“旅行商问题”为主题,分别探究了先行约束广义旅行商问题、广义近似旅行商问题、非对称旅行商问题,涉及整数规划、分支切割、锥规划、迭代贪心等诸多知识。

推荐文章1

● 题目:Precedence constrained generalized traveling salesman problem: Polyhedral study, formulations, and branch-and-cut algorithm

先行约束广义旅行商问题:多面体研究、公式化和分支切割算法

● 期刊:European Journal of Operational Research

 原文链接:https://doi.org/10.1016/j.ejor.2023.01.039

● 作者:Daniil Khachai, Ruslan Sadykov, Olga Battaiaa, Michael Khachay

● 关键词

Travelling salesman(旅行商问题),Integer programming(整数规划),Branch-and-cut algorithm(分支切割算法),Facet-inducing inequalities(面诱导不等式),Polyhedral structure(多面体结构)

● 摘要

The Precedence Constrained Generalized Traveling Salesman Problem (PCGTSP) is an extension of two well-known combinatorial optimization problems - the Generalized Traveling Salesman Problem (GTSP) and the Precedence Constrained Asymmetric Traveling Salesman Problem (PCATSP), whose path version is known as the Sequential Ordering Problem (SOP). Similarly to the classic GTSP, the goal of the PCGTSP, for a given input digraph and partition of its node set into clusters, is to find a minimum cost cyclic route (tour) visiting each cluster in a single node. In addition, as in the PCATSP, feasible tours are restricted to visit the clusters with respect to the given partial order. Unlike the GTSP and SOP, to the best of our knowledge, the PCGTSP still remain to be weakly studied both in terms of polyhedral theory and algo-rithms. In this paper, for the first time for the PCGTSP, we propose several families of valid inequalities, establish dimension of the PCGTS polytope and prove sufficient conditions ensuring that the extended Balas' pi- and sigma-inequalities become facet-inducing. Relying on these theoretical results and evolving the state-of-the-art algorithmic approaches for the PCATSP and SOP, we introduce a family of MILP-models (formulations) and several variants of the branch-and-cut algorithm for the PCGTSP. We prove their high performance in a competitive numerical evaluation against the public benchmark library PCGTSPLIB, a known adaptation of the classic SOPLIB to the problem in question.

先行约束广义旅行商问题(PCGTSP)是两个著名的组合优化问题的扩展,分别是广义旅行商问题(GTSP)和先行约束不对称旅行商问题(PCATSP),其路径版本被称为顺序排列问题(SOP)。与经典GTSP类似,对于给定的输入有向图和将其节点集划分为簇的方式,PCGTSP的目标是找到一个最小成本的环路(路径),使得每个簇都在一个节点中被访问。此外,与PCATSP类似,可行的路径被限制为按照给定的偏序访问簇。与GTSP和SOP不同的是,就我们所知,PCGTSP在多面体理论和算法方面仍然缺乏深入研究。在本文中,我们首次针对PCGTSP提出了几类有效的不等式,建立了PCGTSP多面体的维度,并证明了确保扩展的Balas' π - 和 σ -不等式成为面诱导的充分条件。基于这些理论结果,并借鉴了PCATSP和SOP的最先进算法方法,我们提出了一系列线性整数规划(MILP)模型和PCGTSP的分支定界算法的多个变体。我们证明了它们在公共基准库PCGTSPLIB上进行的竞争性数值评估中表现出很高的性能,该基准库是将经典SOPLIB改编成与问题相应的版本。

● 文章结构

图片

● 点评

本文对先行约束广义旅行商问题 (PCGTSP)进行了系统研究,涵盖了多面体研究和算法分析两个方面。文章扩展了已有的PCATSP结果,提出了多种新颖的有效不等式,并对PCGTS多面体的维度进行了分析。也首次为PCGTSP问题提出了一种分支切割算法,为解决该问题提供了新的算法思路。

推荐文章2

● 题目:The generalized close enough traveling salesman problem

广义近似旅行商问题

● 期刊:European Journal of Operational Research

 原文链接:https://doi.org/10.1016/j.ejor.2023.04.010

● 作者:Andrea Di Placido, Claudia Archetti, Carmine Cerrone, Bruce Goldend

● 关键词

Metaheuristics(元启发式算法),Close enough traveling salesman problem(广义近似旅行商问题),Genetic algorithms(遗传算法),Conic programming(锥规划)

● 摘要

This paper studies a generalization of the close enough traveling salesman problem referred to as the generalized close enough traveling salesman problem (GCETSP). The canonical problem contains a set of customers, each associated with an area (neighborhood) that is generally circular. In the GCETSP, each customer is associated with a set of disks with different radii. Having multiple disks around the customer allows us to model several real-world applications, in which a higher benefit is gained by more closely approaching each target. A prize is assigned to each disk and is collected if the disk is traversed. The goal is to determine the route that visits each customer and the depot and maximizes the difference between the total collected prize and the route length. The total collected prize is given by the sum of the customer prices' associated with the innermost disk traversed by the route. We propose a heuristic algorithm and an evolutionary approach, specifically, a genetic algorithm (GA), to solve this problem. We evaluate the GA's performance on instances generated from benchmark CETSP and TSP instances. We then compare GA solutions with CETSP solutions and solutions obtained through an alternative approach based on pre-selecting intersection points with customers' disks. The results show that the GA can identify high-quality solutions with a short computing time.

本文研究了近似旅行商问题的一种推广,称为广义近似旅行商问题(GCETSP)。经典问题包含一组客户,每个客户与一个圆形的区域相关联。在GCETSP中,每个客户与一组具有不同半径的圆盘相关联。围绕一位客户有多个不同圆盘来模拟现实世界的几种不同应用,更接近目标的圆盘会获得更高效益。每个圆盘具有对应的奖励值,穿越该圆盘时即可获得相应奖励。目标是确定访问每个客户和中转站的路线,最大化总收集奖励和路线长度的差值,总收集奖励为路线穿越的最内圆盘所对应的客户价格之和。我们提出了一种启发式算法和一种遗传算法(GA)来解决这个问题,并利用CETSP和TSP的基准算例所生成的实例来评估遗传算法的性能。然后将GA的解与CETSP解以及通过基于预先选择与客户圆盘的交点的替代方法所得到的解进行比较,结果显示GA能够在短时间内识别出高质量的解。

● 文章结构

图片

● 点评

本文采用遗传算法(GA)和构造算法来解决GCETSP问题。GA针对GCETSP的特殊特点进行了优化,构造算法则基于解决TSP、SOCP和最短路径问题的顺序来构建可行路径。这两种方法为解决GCETSP提供了有效的工具。通过与另一种启发式方法nearOpt进行对比实验,GA表现出更好的性能。本研究在无人机使用中的抄表、RFID系统等现实应用的建模优化中具有一定启示。

推荐文章3

● 题目:An asymmetric traveling salesman problem based matheuristic algorithm for flowshop group scheduling problem

一种基于非对称旅行商问题的数学启发式算法,用于流水车间群调度问题

● 期刊:European Journal of Operational Research

 原文链接:https://doi.org/10.1016/j.ejor.2023.03.038

● 作者:Xuan He, Quan-Ke Pan, Liang Gao, Janis S. Neufeld

● 关键词

Scheduling(调度),Asymmetric traveling salesman(非对称旅行商),Branch-and-cut(分枝切割法),Iterated greedy(迭代贪心),Matheuristic(数学启发式)

● 摘要

The flowshop group scheduling problem (FGSP) has become a hot research problem owing to its practical applications in modern industry in recent years. The FGSP can be regarded as a combination of two cou-pled sub-problems. One is the group scheduling sub-problem with sequence-dependent setup times. The other is the job scheduling sub-problem within each group. A mixed integer linear programming model is built for the FGSP with the makespan criterion. Based on the problem-specific knowledge, i.e., the sequence-dependent group setup times are greater than the processing time of jobs, and the number of machines is small, the group scheduling sub-problem is approximated into an asymmetric traveling sales-man problem (ATSP). Then, a matheuristic algorithm (MA) is proposed by integrating a branch-and-cut algorithm and an iterated greedy (IG) algorithm, where the branch-and-cut algorithm is used to generate the optimal Hamiltonian circuit for sub-group sequences of a group sequence obtained by the IG. On 405 test instances, the proposed MA performs significantly better than several state-of-the-art algorithms in the literature.

近年来,由于在现代工业中的实际应用,流水车间群调度问题(FGSP)已成为一个热门的研究问题。FGSP可以看作是两个耦合子问题的组合。一个是带有序列相关设置时间的群调度子问题,另一个是每个群内的作业调度子问题。针对以最大完工时间为目标的FGSP,建立了一个混合整数线性规划模型。基于问题特定的知识,即序列相关的群设置时间大于作业的处理时间,并且机器数量较少,将群调度子问题近似为不对称旅行商问题(ATSP)。然后,提出了一种数学启发式算法(MA),它将分支定界算法和迭代贪心(IG)算法结合在一起,其中分支定界算法用于为由IG得到的群序列的子群序列生成最优哈密顿回路。在405个测试实例上,所提出的MA表现明显优于文献中几种最先进的算法。

● 文章结构

图片

● 点评

本研究主要针对流水车间分组调度问题(FCSP)的最大完工时间准则展开研究,提出了一种新颖的数学启发式算法(MA)。研究创新点包括在问题层面上将分组调度子问题近似为非对称旅行商问题(ATSP),并在算法层面上采用分支定界和迭代贪心算法的结合。还针对问题特点设计了特殊的局部搜索和断续规则机制,以增强迭代贪心算法的搜索性能。该算法在解决能够近似为非对称旅行商问题的流水车间调度问题上表现出色,对于一些经典的流水车间调度问题,如无等待流水车间调度问题和阻塞流水车间调度问题,该算法同样适用。

相关文章:

论文导读|European Journal of Operational Research近期文章精选:旅行商问题专题

推文作者:王松阁 编者按 在“European Journal of Operational Research近期论文精选”中,我们有主题、有针对性地选择了European Journal of Operational Research中一些有趣的文章,不仅对文章的内容进行了概括与点评,而且也对文…...

playwright迭代元素

DOM结构 <ul><li>apple</li><li>banana</li><li>orange</li> </ul>迭代元素操作 通过 page.get_by_role("listitem") 会匹配到 apple, banana, orange&#xff0c; 如果要对这一组数据中的每个元素进行操作&#…...

65 | 增长模型案例

增长模型代表了一种综合性的方法论,旨在通过深入了解用户行为、市场趋势和数据洞察,来指导企业制定有效的增长战略。这种方法突破了传统的经验主义,将决策过程建立在数据驱动和实验的基础之上。增长模型不仅仅是一种理论,更是一种实际操作的框架,帮助企业在各个层面实现业…...

Django视图-HttpRequest请求对象和HttpResponse响应对象

文章目录 HttpRequestHttpResponse实践request对象的属性和方法响应 def index(request): 这个request其实就是内部已经封装好的Http请求HttpRequest&#xff0c;它是一个请求对象Django中的视图主要用来接受Web请求&#xff0c;并做出响应。 视图的本质就是一个Python中的函数…...

原来Lambda表达式是这样写的

原来Lambda表达式是这样写的 lambda 是一个匿名函数&#xff0c;我们可以把 lambda 表达式理解为是一段可以传递的代码。 lambda 简明地将代码或方法作为参数传递进去执行。 函数式编程&#xff1a;核心是把函数作为值。 函数式接口 &#xff1a;只有一个抽象方法的接口称之…...

smartsofthelp 5.0 最专业的数据库优化工具,数据库配置优化,数据库高并发优化,SQL 语句优化...

下载地址:百度网盘 请输入提取码 SQL操作返回历史记录&#xff1a; 2023-08-21 20:42:08:220 输入&#xff1a;select version as 版本号 2023-08-21 20:42:08:223 输出&#xff1a;当前数据库实例版本号&#xff1a;Microsoft SQL Server 2012 - 11.0.2100.60 (X64) …...

智影 R100:首款三维Mesh建模的SLAM激光扫描仪

近年来&#xff0c;激光SLAM系统凭借其更加快速且准确获取更丰富信息的优势&#xff0c;迅速风靡测绘领域&#xff0c;让原本耗时耗力的外业测量变得更加高效。手持激光扫描仪作为基于激光SLAM技术衍生的众多产品之一&#xff0c;相较于架站式激光扫描仪更加轻巧便利&#xff0…...

Next.js - Loading UI and Streaming

特殊文件 loading.js 可帮助您使用 React Suspense 创建有意义的加载用户界面。使用此约定&#xff0c;您可以在加载路由段内容时显示来自服务器的即时加载状态。渲染完成后&#xff0c;新的内容会自动切换进来。 即时加载状态 即时加载状态是在导航时立即显示的后备用户界面…...

快速解决Ubuntu 中 wine 程序 中文显示为方块/显示错误/无法显示中文(2023)

解决办法就是在创建prefix的命令行里加上LANG“zh_CN.UTF8” 或 LC_ALL“zh_CN.UTF8”&#xff0c;并安装cjkfonts&#xff0c;即可。 1、生成prefix、安装cjk字体 以下是基本流程&#xff1a; 现在假定wine和winetricks已经装好&#xff0c; // 先创建一个prefix&#xff0…...

漏洞指北-VulFocus靶场专栏-中级02

漏洞指北-VulFocus靶场专栏-中级02 中级005 &#x1f338;thinkphp lang 命令执行&#xff08;thinkphp:6.0.12&#xff09;&#x1f338;step1&#xff1a;burp suite 抓包 修改请求头step2 修改成功&#xff0c;访问shell.php 中级006 &#x1f338;Metabase geojson任意文件…...

【开源三方库】bignumber.js:一个大数数学库

OpenHarmony&#xff08;OpenAtom OpenHarmony简称“OpenHarmony”&#xff09;三方库&#xff0c;是经过验证可在OpenHarmony系统上可重复使用的软件组件&#xff0c;可帮助开发者快速开发OpenHarmony应用。如果是发布到开源社区&#xff0c;称为开源三方库&#xff0c;开发者…...

【C++】iota函数 + sort函数实现基于一个数组的多数组对应下标绑定排序

目录 一、iota函数 1. 函数解析 ​① 迭代器类型(补充) ② 头文件 ③ 参数 2. 函数用途与实例 二、sort函数 1、 函数解读 2、实现倒序排列 2.1 greater 与 less 模板参数 2.2 lambda表达式 三、下标绑定排序&#xff08;zip&#xff09; --- 833.字符串中的查找与替换 一、…...

C# window forms 进度条实现

在 C# Windows Forms 应用程序中&#xff0c;如果在后台执行长时间运行的任务&#xff0c;并希望同时更新进度条&#xff0c;可以使用多线程来实现。这将确保进度条的更新不会阻塞主线程&#xff0c;从而保持界面的响应性。以下是一个示例&#xff0c;演示了如何在后台执行任务…...

ListNode相关

目录 2. 链表相关题目 2.1 合并两个有序链表&#xff08;简单&#xff09;&#xff1a;递归 2.2 删除排序链表中的重复元素&#xff08;简单&#xff09;&#xff1a;一次遍历 2.3 两链表相加&#xff08;中等&#xff09;&#xff1a;递归 2.4 删除链表倒数第N个节点&…...

docker的资源控制及docker数据管理

目录 一.docker的资源控制 1.CPU 资源控制 1.1 资源控制工具 1.2 cgroups有四大功能 1.3 设置CPU使用率上限 1.4 进行CPU压力测试 1.5 设置50%的比例分配CPU使用时间上限 1.6 设置CPU资源占用比&#xff08;设置多个容器时才有效&#xff09; 1.6.1 两个容器测试cpu 2&…...

通过请求头传数据向后端发请求

axios &#xff08;get post请求、头部参数添加&#xff09;傻瓜式入门axios_axiospost请求参数_web_blog的博客-CSDN博客...

产品流程图是什么?怎么做?

产品流程图是什么&#xff1f; 产品流程图是一种图形化的表达方式&#xff0c;用于描述产品开发、制造、销售、使用等各个阶段中涉及的流程、步骤和关系。它通过图形符号、箭头、文本等元素&#xff0c;展示了产品的各个环节之间的关联和顺序&#xff0c;通常被用于可视化产…...

面试之快速学习STL-map

关联式容器 包括 map、multimap、set 以及 multiset 这 4 种容器。和序列式容器区别&#xff1a; a . 关联式容器在存储元素时还会为每个元素在配备一个键&#xff0c;整体以键值对的方式存储到容器中。 b . 相比前者&#xff0c;关联式容器可以通过键值直接找到对应的元素&am…...

ES的索引结构与算法解析

提到ES&#xff0c;大多数爱好者想到的都是搜索引擎&#xff0c;但是明确一点&#xff0c;ES不等同于搜索引擎。不管是谷歌、百度、必应、搜狗为代表的自然语言处理(NLP)、爬虫、网页处理、大数据处理的全文搜索引擎&#xff0c;还是有明确搜索目的的搜索行为&#xff0c;如各大…...

32.Netty源码之服务端如何处理客户端新建连接

highlight: arduino-light 服务端如何处理客户端新建连接 Netty 服务端完全启动后&#xff0c;就可以对外工作了。接下来 Netty 服务端是如何处理客户端新建连接的呢&#xff1f; 主要分为四步&#xff1a; md Boss NioEventLoop 线程轮询客户端新连接 OP_ACCEPT 事件&#xff…...

MFC内存泄露

1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...

FastAPI 教程:从入门到实践

FastAPI 是一个现代、快速&#xff08;高性能&#xff09;的 Web 框架&#xff0c;用于构建 API&#xff0c;支持 Python 3.6。它基于标准 Python 类型提示&#xff0c;易于学习且功能强大。以下是一个完整的 FastAPI 入门教程&#xff0c;涵盖从环境搭建到创建并运行一个简单的…...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...

蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练

前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1)&#xff1a;从基础到实战的深度解析-CSDN博客&#xff0c;但实际面试中&#xff0c;企业更关注候选人对复杂场景的应对能力&#xff08;如多设备并发扫描、低功耗与高发现率的平衡&#xff09;和前沿技术的…...

什么是EULA和DPA

文章目录 EULA&#xff08;End User License Agreement&#xff09;DPA&#xff08;Data Protection Agreement&#xff09;一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA&#xff08;End User License Agreement&#xff09; 定义&#xff1a; EULA即…...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)

文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...

MySQL用户和授权

开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务&#xff1a; test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...

Java线上CPU飙高问题排查全指南

一、引言 在Java应用的线上运行环境中&#xff0c;CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时&#xff0c;通常会导致应用响应缓慢&#xff0c;甚至服务不可用&#xff0c;严重影响用户体验和业务运行。因此&#xff0c;掌握一套科学有效的CPU飙高问题排查方法&…...

Mysql8 忘记密码重置,以及问题解决

1.使用免密登录 找到配置MySQL文件&#xff0c;我的文件路径是/etc/mysql/my.cnf&#xff0c;有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...

STM32---外部32.768K晶振(LSE)无法起振问题

晶振是否起振主要就检查两个1、晶振与MCU是否兼容&#xff1b;2、晶振的负载电容是否匹配 目录 一、判断晶振与MCU是否兼容 二、判断负载电容是否匹配 1. 晶振负载电容&#xff08;CL&#xff09;与匹配电容&#xff08;CL1、CL2&#xff09;的关系 2. 如何选择 CL1 和 CL…...