高级检索

  • ISSN 1006-3080
  • CN 31-1691/TQ

树上的最小−最大k旅行商问题若干变种的精确算法

高哲成 余炜 刘朝晖

高哲成, 余炜, 刘朝晖. 树上的最小−最大k旅行商问题若干变种的精确算法[J]. 华东理工大学学报(自然科学版). doi: 10.14135/j.cnki.1006-3080.20200317001
引用本文: 高哲成, 余炜, 刘朝晖. 树上的最小−最大k旅行商问题若干变种的精确算法[J]. 华东理工大学学报(自然科学版). doi: 10.14135/j.cnki.1006-3080.20200317001
GAO Zhecheng, YU Wei, LIU Zhaohui. Exact Algorithms for Some Variants of the Min-Max k-Traveling Salesmen Problem on a Tree[J]. Journal of East China University of Science and Technology. doi: 10.14135/j.cnki.1006-3080.20200317001
Citation: GAO Zhecheng, YU Wei, LIU Zhaohui. Exact Algorithms for Some Variants of the Min-Max k-Traveling Salesmen Problem on a Tree[J]. Journal of East China University of Science and Technology. doi: 10.14135/j.cnki.1006-3080.20200317001

树上的最小−最大k旅行商问题若干变种的精确算法

doi: 10.14135/j.cnki.1006-3080.20200317001
基金项目: 国家自然科学基金(11671135),上海市自然科学基金(19ZR1411800),中央高校基本科研业务费(22220184028)
详细信息
    作者简介:

    高哲成(1994—),男,浙江绍兴人,硕士生,主要研究方向为组合优化。E-mail:Y30170156@mail.ecust.edu.cn

    通讯作者:

    余 炜,E-mail:yuwei@ecust.edu.cn

  • 中图分类号: O223

Exact Algorithms for Some Variants of the Min-Max k-Traveling Salesmen Problem on a Tree

  • 摘要: 树上的最小-最大$ k $旅行商问题是多旅行商问题在树形结构中的推广问题。研究了树上的最小-最大$ k $旅行商问题、树上的多仓库最小-最大$ k $旅行商问题以及树上的最小-最大$ k $路覆盖问题,提出了基于自下而上的动态规划的拟多项式时间精确算法。将树上的多仓库最小-最大$ k $旅行商问题的算法推广到树上的多仓库最小-最大$ k $路覆盖问题和树上的多仓库最小-最大$ k $中国邮递员问题,分别给出了首个拟多项式时间精确算法。

     

  • 图  1  TTiTij以及T(i)解释

    Figure  1.  Explanation of TTiTij and T(i)

    图  2  标准实例的转换

    Figure  2.  Transformation of an stomdard example

    图  3  一个根据深度非增顺序重新标号的例子

    Figure  3.  An example of renumbering in non-increasing order of depths

    表  1  图1(c)中的实例作为输入时算法2中的$ {H}_{1} $$ {H}_{2} $$ {H}_{4} $的结构

    Table  1.   Construction of $ {H}_{1} $, $ {H}_{2} $ and $ {H}_{4} $ by algorithm 2 for the instance in Fig. 1(c)

    $ j $$ i $Number$ {Q}_{j}' $$\; {\rm{in}} \;$$ {H}_{j} $
    1(1)$ \{\left(\mathrm{0,1},\mathrm{1,0},\left\{1\right\},1\right),(\mathrm{0,0},\mathrm{0,0},\varnothing ,0\left)\right\} $
    12(2)$ \left\{\right(\mathrm{0,0},\mathrm{0,0},\varnothing ,0),\left(\mathrm{0,1},\mathrm{1,0},\left\{1\right\},1\right)\} $
    1(1)$ \{\left(\mathrm{0,1},\mathrm{1,0},\left\{2\right\},2\right),(\mathrm{0,0},\mathrm{0,0},\varnothing ,0\left)\right\} $
    22(2)$ \left\{\right(\mathrm{0,0},\mathrm{0,0},\varnothing ,0),\left(\mathrm{0,1},\mathrm{1,0},\left\{2\right\},2\right)\} $
    1(1)$ \{\left(\mathrm{0,1},\mathrm{1,1},\left\{4\right\},4\right),(\mathrm{0,0},\mathrm{0,0},\varnothing ,0\left)\right\} $
    42(2)$ \left\{\right(\mathrm{0,0},\mathrm{0,0},\varnothing ,0),\left(\mathrm{0,1},\mathrm{1,1},\left\{4\right\},4\right)\} $
    下载: 导出CSV

    表  2  图1(c)中的实例作为输入,算法2过程中的$ {H}_{3} $的结构

    Table  2.   Construction of $ {H}_{3} $ by algorithm 2 for the instance in Fig. 1(c)

    $ {Q}_{1}':{Q}_{2}' $$ {H}_{3}^{1} $$ {H}_{3}^{2} $Number$ {Q}_{3}' $ in $ {H}_{3} $Deleted
    $ \left(1\right):\left(1\right) $$ (\mathrm{2,1},\mathrm{1,1},\left\{\mathrm{1,2}\right\},3) $$ (\mathrm{0,0},\mathrm{0,0},\varnothing ,0) $(1)$ \{\left(\mathrm{2,1},\mathrm{1,1},\left\{\mathrm{1,2}\right\},3\right),(\mathrm{0,0},\mathrm{0,0},\varnothing ,0\left)\right\} $No
    $ (\mathrm{0,1},\mathrm{1,1},\{3\},3) $(2)$ \{\left(\mathrm{2,1},\mathrm{1,1},\left\{\mathrm{1,2}\right\},3\right),(\mathrm{0,1},\mathrm{1,1},\left\{3\right\},3\left)\right\} $No
    $ \left(2\right):\left(2\right) $$ (\mathrm{0,0},\mathrm{0,0},\varnothing ,0) $$ (\mathrm{2,1},\mathrm{1,1},\left\{\mathrm{1,2}\right\},3) $(3)$ \{\left(\mathrm{0,0},\mathrm{0,0},\varnothing ,0\right),(\mathrm{2,1},\mathrm{1,1},\left\{\mathrm{1,2}\right\},3\left)\right\} $No
    $ (\mathrm{0,1},\mathrm{1,1},\{3\},3) $(4)$ \left\{\right(\mathrm{0,1},\mathrm{1,1},\left\{3\right\},3),(\mathrm{2,1},\mathrm{1,1},\left\{\mathrm{1,2}\right\},3\left)\right\} $No
    $ \left(1\right):\left(2\right) $$ (\mathrm{1,1},\mathrm{1,1},\left\{1\right\},3) $$ (\mathrm{1,1},\mathrm{1,1},\left\{2\right\},3) $(5)$ \{\left(\mathrm{1,1},\mathrm{1,1},\left\{1\right\},3\right),(\mathrm{1,1},\mathrm{1,1},\left\{2\right\},3\left)\right\} $No
    $ (\mathrm{0,1},\mathrm{0,0},\left\{1\right\},1) $$ (\mathrm{0,1},\mathrm{0,0},\left\{2\right\},2) $(6)$ \left\{\right(\mathrm{0,1},\mathrm{0,0},\left\{1\right\},1),(\mathrm{0,1},\mathrm{0,0},\left\{2\right\},2\left)\right\} $Yes
    (7)$ \{\left(\mathrm{1,1},\mathrm{1,1},\left\{1\right\},3\right),(\mathrm{0,1},\mathrm{0,0},\left\{2\right\},2\left)\right\} $No
    (8)$ \left\{\right(\mathrm{0,1},\mathrm{0,0},\left\{1\right\},1),(\mathrm{1,1},\mathrm{1,1},\left\{2\right\},3\left)\right\} $No
    $ \left(2\right):\left(1\right) $$ (\mathrm{1,1},\mathrm{1,1},\left\{2\right\},3) $$ (\mathrm{1,1},\mathrm{1,1},\left\{1\right\},3) $(9)$ \{\left(\mathrm{1,1},\mathrm{1,1},\left\{2\right\},3\right),(\mathrm{1,1},\mathrm{1,1},\left\{1\right\},3\left)\right\} $Yes
    $ (\mathrm{0,1},\mathrm{0,0},\left\{2\right\},2) $$ (\mathrm{0,1},\mathrm{0,0},\left\{1\right\},1) $(10)$ \left\{\right(\mathrm{0,1},\mathrm{0,0},\left\{2\right\},2),(\mathrm{0,1},\mathrm{0,0},\left\{1\right\},1\left)\right\} $Yes
    (11)$ \{\left(\mathrm{1,1},\mathrm{1,1},\left\{2\right\},3\right),(\mathrm{0,1},\mathrm{0,0},\left\{1\right\},1\left)\right\} $Yes
    (12)$ \left\{\right(\mathrm{0,1},\mathrm{0,0},\left\{2\right\},2),(\mathrm{1,1},\mathrm{1,1},\left\{1\right\},3\left)\right\} $Yes
    下载: 导出CSV

    表  3  图1(c)中的实例作为输入,算法2过程中的$ {H}_{5} $的结构

    Table  3.   Construction of $ {H}_{5} $ by algorithm 2 for the instance in Fig. 1(c)

    $ {Q}_{3}':{Q}_{4}' $$ {H}_{5}^{1} $$ {H}_{5}^{2} $Number$ {Q}_{5}' $$ \; {\rm{in}} \;$$ {H}_{5} $Deleted$ \underset{i=\mathrm{1,2}}{\mathrm{max}}{W}_{i5} $
    $ \left(1\right):\left(1\right) $$ (\mathrm{6,1},\mathrm{1,1},\left\{\mathrm{1,2},4\right\},5) $$ (\mathrm{0,0},\mathrm{0,0},\varnothing ,0) $(1)$ \{\left(\mathrm{6,1},\mathrm{1,1},\left\{\mathrm{1,2},4\right\},5\right),(\mathrm{0,0},\mathrm{0,0},\varnothing ,0\left)\right\} $Yes/
    $ (\mathrm{0,1},\mathrm{1,0},\{5\},5) $(2)$ \{\left(\mathrm{6,1},\mathrm{1,1},\left\{\mathrm{1,2},4\right\},5\right),(\mathrm{0,1},\mathrm{1,0},\left\{5\right\},5\left)\right\} $Yes/
    $ \left(2\right):\left(1\right) $$ (\mathrm{6,1},\mathrm{1,1},\left\{\mathrm{1,2},4\right\},5) $$ (\mathrm{0,1},\mathrm{0,1},\{3\},3) $(3)$ \{\left(\mathrm{6,1},\mathrm{1,1},\left\{\mathrm{1,2},4\right\},5\right),(\mathrm{0,1},\mathrm{0,1},\left\{3\right\},3\left)\right\} $No6
    $ (\mathrm{2,1},\mathrm{1,1},\{3\},5) $(4)$ \{\left(\mathrm{6,1},\mathrm{1,1},\left\{\mathrm{1,2},4\right\},5\right),(\mathrm{2,1},\mathrm{1,1},\left\{3\right\},5\left)\right\} $No6
    $ \left(3\right):\left(1\right) $$ \left(\mathrm{2,1},\mathrm{1,1},\left\{4\right\},5\right) $$ (\mathrm{4,1},\mathrm{1,1},\left\{\mathrm{1,2}\right\},5) $(5)$ \{\left(\mathrm{2,1},\mathrm{1,1},\left\{4\right\},5\right),(\mathrm{4,1},\mathrm{1,1},\left\{\mathrm{1,2}\right\},5\left)\right\} $No4
    $ \left(\mathrm{0,1},\mathrm{0,1},\left\{4\right\},4\right) $$ (\mathrm{2,1},\mathrm{0,1},\left\{\mathrm{1,2}\right\},3) $(6)$ \{\left(\mathrm{0,1},\mathrm{0,1},\left\{4\right\},4\right),(\mathrm{2,1},\mathrm{0,1},\left\{\mathrm{1,2}\right\},3\left)\right\} $Yes/
    (7)$ \{\left(\mathrm{2,1},\mathrm{1,1},\left\{4\right\},5\right),\left(\mathrm{2,1},\mathrm{0,1},\left\{\mathrm{1,2}\right\},3\right)\} $No2
    (8)$ \{\left(\mathrm{0,1},\mathrm{0,1},\left\{4\right\},4\right),\left(\mathrm{4,1},\mathrm{1,1},\left\{\mathrm{1,2}\right\},5\right)\} $No4
    $ \left(4\right):\left(1\right) $$ \left(\mathrm{4,1},\mathrm{1,1},\left\{\mathrm{3,4}\right\},5\right) $$ (\mathrm{4,1},\mathrm{1,1},\left\{\mathrm{1,2}\right\},5) $(9)$ \{\left(\mathrm{4,1},\mathrm{1,1},\left\{\mathrm{3,4}\right\},5\right),(\mathrm{4,1},\mathrm{1,1},\left\{\mathrm{1,2}\right\},5\left)\right\} $No4
    $ (\mathrm{2,1},\mathrm{0,1},\left\{\mathrm{1,2}\right\},3) $(10)$ \{\left(\mathrm{4,1},\mathrm{1,1},\left\{\mathrm{3,4}\right\},5\right),(\mathrm{2,1},\mathrm{0,1},\left\{\mathrm{1,2}\right\},3\left)\right\} $No4
    $ \left(5\right):\left(1\right) $$ \left(\mathrm{5,1},\mathrm{1,1},\left\{\mathrm{1,4}\right\},5\right) $$ (\mathrm{1,1},\mathrm{0,1},\left\{2\right\},3) $(11)$ \{\left(\mathrm{5,1},\mathrm{1,1},\left\{\mathrm{1,4}\right\},5\right),\left(\mathrm{1,1},\mathrm{0,1},\left\{2\right\},3\right)\} $No5
    $ (\mathrm{3,1},\mathrm{1,1},\left\{2\right\},5) $(12)$ \{\left(\mathrm{5,1},\mathrm{1,1},\left\{\mathrm{1,4}\right\},5\right),(\mathrm{3,1},\mathrm{1,1},\left\{2\right\},5\left)\right\} $No5
    $ \left(7\right):\left(1\right) $$ \left(\mathrm{5,1},\mathrm{1,1},\left\{\mathrm{1,4}\right\},5\right) $$ (\mathrm{0,1},\mathrm{0,0},\left\{2\right\},2) $(13)$ \{\left(\mathrm{5,1},\mathrm{1,1},\left\{\mathrm{1,4}\right\},5\right),(\mathrm{0,1},\mathrm{0,0},\left\{2\right\},2\left)\right\} $Yes/
    $ \left(8\right):\left(1\right) $//////
    $ \left(1\right):\left(2\right) $$ \left(\mathrm{2,1},\mathrm{0,1},\left\{\mathrm{1,2}\right\},3\right) $$ \left(\mathrm{0,1},\mathrm{0,1},\left\{4\right\},4\right) $(14)$ \{\left(\mathrm{2,1},\mathrm{0,1},\left\{\mathrm{1,2}\right\},3\right),\left(\mathrm{0,1},\mathrm{0,1},\left\{4\right\},4\right)\} $Yes/
    $ \left(\mathrm{4,1},\mathrm{1,1},\left\{\mathrm{1,2}\right\},5\right) $$ \left(\mathrm{2,1},\mathrm{1,1},\left\{4\right\},5\right) $(15)$ \{\left(\mathrm{4,1},\mathrm{1,1},\left\{\mathrm{1,2}\right\},5\right),\left(\mathrm{2,1},\mathrm{1,1},\left\{4\right\},5\right)\} $No4
    (16)$ \{\left(\mathrm{2,1},\mathrm{0,1},\left\{\mathrm{1,2}\right\},3\right),\left(\mathrm{2,1},\mathrm{1,1},\left\{4\right\},5\right)\} $No2
    (17)$ \{\left(\mathrm{4,1},\mathrm{1,1},\left\{\mathrm{1,2}\right\},5\right),\left(\mathrm{0,1},\mathrm{0,1},\left\{4\right\},4\right)\} $No4
    $ \left(2\right):\left(2\right) $$ \left(\mathrm{2,1},\mathrm{0,1},\left\{\mathrm{1,2}\right\},3\right) $$ \left(4,\mathrm{1,1},1,\left\{\mathrm{3,4}\right\},5\right) $(18)$ \{\left(\mathrm{2,1},\mathrm{0,1},\left\{\mathrm{1,2}\right\},3\right),\left(4,\mathrm{1,1},1,\left\{\mathrm{3,4}\right\},5\right)\} $No4
    $ \left(4,\mathrm{1,1},1,\left\{\mathrm{1,2}\right\},5\right) $(19)$ \{\left(4,\mathrm{1,1},1,\left\{\mathrm{1,2}\right\},5\right),\left(4,\mathrm{1,1},1,\left\{\mathrm{3,4}\right\},5\right)\} $No4
    $ \left(3\right):\left(2\right) $$ (\mathrm{0,0},\mathrm{0,0},\varnothing ,0) $$ (\mathrm{6,1},\mathrm{1,1},\left\{\mathrm{1,2},4\right\},5) $(20)$ \left\{\right(\mathrm{0,0},\mathrm{0,0},\varnothing ,0),(\mathrm{6,1},\mathrm{1,1},\left\{\mathrm{1,2},4\right\},5\left)\right\} $Yes/
    $ (\mathrm{0,1},\mathrm{1,0},\{5\},5) $(21)$ \left\{\right(\mathrm{0,1},\mathrm{1,0},\left\{5\right\},5),(\mathrm{6,1},\mathrm{1,1},\left\{\mathrm{1,2},4\right\},5\left)\right\} $Yes/
    $ \left(4\right):\left(2\right) $$ (\mathrm{0,1},\mathrm{0,1},\{3\},3) $$ (\mathrm{6,1},\mathrm{1,1},\left\{\mathrm{1,2},4\right\},5) $(22)$ \left\{\right(\mathrm{0,1},\mathrm{0,1},\left\{3\right\},3),(\mathrm{6,1},\mathrm{1,1},\left\{\mathrm{1,2},4\right\},5\left)\right\} $No6
    $ (\mathrm{2,1},\mathrm{1,1},\{3\},5) $(23)$ \left\{\right(\mathrm{2,1},\mathrm{1,1},\left\{3\right\},5),(\mathrm{6,1},\mathrm{1,1},\left\{\mathrm{1,2},4\right\},5\left)\right\} $No6
    $ \left(5\right):\left(2\right) $$ \left(\mathrm{1,1},\mathrm{0,1},\left\{1\right\},3\right) $$ (\mathrm{5,1},\mathrm{1,1},\left\{\mathrm{2,4}\right\},5) $(24)$ \{\left(\mathrm{1,1},\mathrm{0,1},\left\{1\right\},3\right),\left(\mathrm{5,1},\mathrm{1,1},\left\{\mathrm{2,4}\right\},5\right)\} $No5
    $ \left(\mathrm{3,1},\mathrm{1,1},\left\{1\right\},5\right) $(25)$ \{\left(\mathrm{3,1},\mathrm{1,1},\left\{1\right\},5\right),\left(\mathrm{5,1},\mathrm{1,1},\left\{\mathrm{2,4}\right\},5\right)\} $No5
    $ \left(7\right):\left(2\right) $//////
    $ \left(8\right):\left(2\right) $$ (\mathrm{0,1},\mathrm{0,0},\left\{1\right\},1) $$ (\mathrm{5,1},\mathrm{1,1},\left\{\mathrm{2,4}\right\},5) $(26)$ \{\left(\mathrm{0,1},\mathrm{0,0},\left\{1\right\},1\right),\left(\mathrm{5,1},\mathrm{1,1},\left\{\mathrm{2,4}\right\},5\right)\} $Yes/
    下载: 导出CSV
  • [1] GAREY M R, JOHNSON D S. Computers and Intractability: A Guide to The Theory of NP-Completeness[M]. New York: The MIT press, 1979.
    [2] AVERBAKH I, BERMAN O. (p−1)/(p+1)-Approximate algorithms for p-traveling salesmen problems on a tree with minmax objective[J]. Discrete Applied Mathematics, 1997, 75(3): 201-216. doi: 10.1016/S0166-218X(97)89161-5
    [3] AVERBAKH I, BERMAN O. A heuristic with worst-case analysis for minimax routing of two travelling salesmen on a tree[J]. Discrete Applied Mathematics, 1996, 68(1/2): 17-32. doi: 10.1016/0166-218X(95)00054-U
    [4] NAGAMOCHI H, OKADA K. A faster 2-approximation algorithm for the minmax p-traveling salesmen problem on a tree[J]. Discrete Applied Mathematics, 2004, 140(1/3): 103-114. doi: 10.1016/j.dam.2003.06.001
    [5] NAGAMOCHI H, OKADA K. Polynomial time 2-approximation algorithms for the minmax subtree cover problem[C]//International Symposium on Algorithms and Computation. Berlin Heidelberg: Springer, 2003: 138-147.
    [6] NAGAMOCHI H, OKADA K. Approximating the minmax rooted-tree cover in a tree[J]. Information Processing Letters, 2007, 104(5): 173-178. doi: 10.1016/j.ipl.2007.06.012
    [7] BECKER A, PAUL A. A framework for vehicle routing approximation schemes in trees[R][s.1]: [s.n.], 2019.
    [8] XU L, XU Z, XU D. Exact and approximation algorithms for the min-max k-traveling salesmen problem on a tree[J]. European Journal of Operational Research, 2013, 227(2): 284-292. doi: 10.1016/j.ejor.2012.12.023
    [9] KARUNO Y, NAGAMOCHI H, IBARAKI T. Vehicle scheduling on a tree to minimize maximum lateness[J]. Journal of Operations Research Society of Japan, 1996, 39(3): 345-355. doi: 10.15807/jorsj.39.345
  • 加载中
图(3) / 表(3)
计量
  • 文章访问数:  45
  • HTML全文浏览量:  26
  • PDF下载量:  0
  • 被引次数: 0
出版历程
  • 收稿日期:  2020-03-17
  • 网络出版日期:  2021-07-16

目录

    /

    返回文章
    返回