.png){kind=icon}
返回
On the Restricted Steiner Multi Cycle Problem
.png){kind=icon}
PRE
AI
DOI：10.1016/j.cor.2024.106752.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
We introduce a new problem, called Steiner Multi Cycle Problem, in which we are given a complete weighted graph = ( , ), which respects the triangle inequality, a collection of terminal sets { 1 , ... , }, where for each in [ ] we have a subset of and these terminal sets are pairwise disjoint. The goal is to find a set of disjoint cycles of minimum cost such that for each in [ ], all vertices of belong to a same cycle. Our main interest is in a restricted case where | | = 2, for each in [ ], which models a collaborative problem with pickup and delivery. We show that even the restricted problem is NP-Hard, and present three heuristics to solve it: a dynamic programming algorithm called Refinement Search Heuristic, which explores geometric and laminar set properties; a heuristic based on the Gonzales Clustering algorithm; and a GRASP Heuristic with Path Relinking. We performed computational experiments with 525 instances to compare these methods, which achieved results close to the optimum, highlighting the performance of the Refinement Search Heuristic both in quality and time.
Keyword:
Heuristics
Routing
Steiner cycle
Pickup-and-delivery
期刊
C
IF:
4.3
论文数:
6.5K
被引数:
1.8W
机构
引用论文
.png){kind=icon}
Fabrication and characterization of silver core and porous silica shell nanocomposite particles
PREAI
分享收藏
分享收藏
查看更多内容