A parameterized approximation algorithm for the mixed and windy capacitated arc routing problem: Theory and experiments
A parameterized approximation algorithm for the mixed and windy capacitated arc routing problem: Theory and experiments
复制标题
混合多风电容弧路由问题的参数化近似算法：理论与实验
DOI：
10.1002/net.21742
复制
发表时间：
2017
期刊：
影响因子：
2.1
通讯作者：
und M. Sorge
中科院分区：
文献类型：
--
作者：
R. van Bevern;C. Komusiewicz;und M. Sorge
我们证明了，任何多项式时间近似算法的然后顶点度量不对称旅行商问题产生一个多项式时间近似算法的混合和风的容量限制弧路由问题，其中是在子图中的弱连通组件的正需求弧诱导的数量-在许多应用中是一个小的数字。结合已知的结果，我们得到了一般情况下的常因子近似和近似。实验表明，我们的算法，加上几个启发式增强，优于许多以前的多项式时间算法。最后，由于在多项式时间内实现的解决方案的质量似乎主要取决于C和sinceC= 1，在几乎所有的基准实例，我们提出了Ob基准集，模拟城市分为几个组成部分的河流。© 2017 Wiley Periodicals，Inc.网络，第70卷（3），262-278 2017
We prove that any polynomial‐time ‐approximation algorithm for then‐vertex metric asymmetric Traveling Salesperson Problem yields a polynomial‐time ‐approximation algorithm for the mixed and windy Capacitated Arc Routing Problem, where is the number of weakly connected components in the subgraph induced by the positive‐demand arcs—a small number in many applications. In conjunction with known results, we obtain constant‐factor approximations for and ‐approximations in general. Experiments show that our algorithm, together with several heuristic enhancements, outperforms many previous polynomial‐time heuristics. Finally, since the solution quality achievable in polynomial time appears to mainly depend onCand sinceC= 1 in almost all benchmark instances, we propose the Ob benchmark set, simulating cities that are divided into several components by a river. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 70(3), 262–278 2017
登录
查看更多内容
影响因子：
2.1
作者：
K. Jansen
通讯作者：
K. Jansen
混合邮差问题的3/2近似算法
DOI：
10.1137/s0895480197331454
发表时间：
1999
期刊：
SIAM J. Discret. Math.
影响因子：
--
作者：
B. Raghavachari;J. Veerasamy
通讯作者：
J. Veerasamy
混合农村邮递员问题的启发式方法
DOI：
10.1016/s0305-0548(99)00031-3
发表时间：
2000
期刊：
Comput. Oper. Res.
影响因子：
--
作者：
Á. Corberán;R. Martí;Antonio Romero
通讯作者：
Antonio Romero
通过添加弧从少量组件到欧拉图
DOI：
10.1007/978-3-642-25870-1_28
发表时间：
2011
期刊：
Oper. Res. Lett.
影响因子：
--
作者：
Manuel Sorge;René van Bevern;R. Niedermeier;Mathias Weller
通讯作者：
Mathias Weller
农村邮递员通过所需边的分量数量进行参数化
DOI：
10.1016/j.jcss.2016.06.001
发表时间：
2017
期刊：
J. Comput. Syst. Sci.
影响因子：
--
作者：
G. Gutin;Magnus Wahlström;Anders Yeo
通讯作者：
Anders Yeo