Chinese Postman Problem is an unsettled graphic problem. It was approached seldom by evolutionary computation. Now we use genetic algorithm to solve Chinese Postman Problem in undirected graph and get good results. It...Chinese Postman Problem is an unsettled graphic problem. It was approached seldom by evolutionary computation. Now we use genetic algorithm to solve Chinese Postman Problem in undirected graph and get good results. It could be extended to solve Chinese postman problem in directed graph. We make these efforts for exploring in optimizing the mixed Chinese postman problem.展开更多
In this paper,we address the k-Chinese postman problem under interdiction budget constraints(the k-CPIBC problem,for short),which is a further generalization of the k-Chinese postman problem and has many practical app...In this paper,we address the k-Chinese postman problem under interdiction budget constraints(the k-CPIBC problem,for short),which is a further generalization of the k-Chinese postman problem and has many practical applications in real life.Specifically,given a weighted graph G=(V,E;w,c;v_(1))equipped with a weight function w:E→R^(+)that satisfies the triangle inequality,an interdiction cost function c:E→Z^(+),a fixed depot v_(1)∈V,an integer k∈^Z^(+)and a budget B∈N,we are asked to find a subset S_(K)■E such that c(S_(K))=∑_(e∈S_(k)c_(e))≤B and that the subgraph G\S_(k)is connected,the objective is to minimize the value min_(C_(E)\S_(k))max{w(C_(i))|C_(i)∈C_(E)\S_(K)}among such all aforementioned subsets S_(k),where C_(E)S_(k)is a set of k-tours(of G\S_(k))starting and ending at the depot v_(1),jointly traversing each edge in G\S_(k)at least once,and w(C_(i))=∑e∈C_(i)w(e)for each tour C_(i)∈C_(E)\S_(k).We obtain the following main results:(1)Given an-approximation algorithm to solve the minimization knapsack problem,we design an(α+β)-approximation algorithm to solve the k-CPIBC problem,whereβ=7/2-1/k-[1/k].(2)We present aβ-approximation algorithm to solve the special version of the k-CPIBC problem,where c(e)1 for each edge e in G and is defined in(1).展开更多
If we restrict the postman to traversing each edge at most twice in the windypostman problem (WPP), we will get a new problem: 2WPP. An approximation algorithmhas been posed by M. Guan for the WPP. In the present pape...If we restrict the postman to traversing each edge at most twice in the windypostman problem (WPP), we will get a new problem: 2WPP. An approximation algorithmhas been posed by M. Guan for the WPP. In the present paper, we improve the estimatederror given by M. Guan and show that we can estimate the error for the 2WPP by findinga minimum cost circulation. We also pose a new sufficient condition for the equivalencebetween WPP and 2WPP, which can be checked in polynomial time steps.展开更多
接口或API测试是日常软件测试过程中常见内容之一,接口测试工具可选性很多,文章主要针对常用的三个接口测试工具:SoapUI、JMeter、Postman,分析它们之间的不同之处以及在实际工作中的应用。具体而言,使用不同的工具来解决日常软件测试...接口或API测试是日常软件测试过程中常见内容之一,接口测试工具可选性很多,文章主要针对常用的三个接口测试工具:SoapUI、JMeter、Postman,分析它们之间的不同之处以及在实际工作中的应用。具体而言,使用不同的工具来解决日常软件测试中的不同接口类型的接口测试问题、性能测试问题、工作效率问题。在运营商运营支撑系统(Operation Support Systems,OSS)领域实际项目测试过程中,有的放矢地选择测试工具,不仅能有效提高了软件质量,同时有助于提高测试人员的效率。展开更多
时间依赖网络相比传统网络模型有更广泛的应用领域,比如公交网络和通信网络都可以抽象成为时间依赖的网络模型。当模型中弧的访问代价为时间依赖的变量时,中国邮路问题的求解将变得非常困难。首先分析了传统的中国邮路问题求解算法,如...时间依赖网络相比传统网络模型有更广泛的应用领域,比如公交网络和通信网络都可以抽象成为时间依赖的网络模型。当模型中弧的访问代价为时间依赖的变量时,中国邮路问题的求解将变得非常困难。首先分析了传统的中国邮路问题求解算法,如奇偶图上作业法和Edmonds&Johnson算法,以及不能有效求解时间依赖中国邮路问题的根本原因;其次给出了一般时变无向中国邮路问题的特性,并在此基础上设计了该问题的分支限界最优化算法;然后针对FIFO(First In First Out)这一类特殊时变网络,设计了新的剪枝条件,从而得到了更有效求解FIFO网络的时变无向中国邮路问题的分支限界最优化算法;最后对算法进行了实验,算法实验结果正确。展开更多
基金Supported by the National Natural Science Foundation of China(60133010,70071042)
文摘Chinese Postman Problem is an unsettled graphic problem. It was approached seldom by evolutionary computation. Now we use genetic algorithm to solve Chinese Postman Problem in undirected graph and get good results. It could be extended to solve Chinese postman problem in directed graph. We make these efforts for exploring in optimizing the mixed Chinese postman problem.
基金supported by the National Natural Science Foundation of China(Nos.11861075,12101593)Project for Innovation Team(Cultivation)of Yunnan Province(No.202005AE-160006)+2 种基金Peng-Xiang Pan is also supported by Project of Yunnan Provincial Department of Education Science Research Fund(No.2020Y0040)Jun-Ran Lichen is also supported by Fundamental Research Funds for the Central Universities(No.buctrc202219)Jian-Ping Li is also supported by Project of Yunling Scholars Training of Yunnan Province(No.K264202011820).
文摘In this paper,we address the k-Chinese postman problem under interdiction budget constraints(the k-CPIBC problem,for short),which is a further generalization of the k-Chinese postman problem and has many practical applications in real life.Specifically,given a weighted graph G=(V,E;w,c;v_(1))equipped with a weight function w:E→R^(+)that satisfies the triangle inequality,an interdiction cost function c:E→Z^(+),a fixed depot v_(1)∈V,an integer k∈^Z^(+)and a budget B∈N,we are asked to find a subset S_(K)■E such that c(S_(K))=∑_(e∈S_(k)c_(e))≤B and that the subgraph G\S_(k)is connected,the objective is to minimize the value min_(C_(E)\S_(k))max{w(C_(i))|C_(i)∈C_(E)\S_(K)}among such all aforementioned subsets S_(k),where C_(E)S_(k)is a set of k-tours(of G\S_(k))starting and ending at the depot v_(1),jointly traversing each edge in G\S_(k)at least once,and w(C_(i))=∑e∈C_(i)w(e)for each tour C_(i)∈C_(E)\S_(k).We obtain the following main results:(1)Given an-approximation algorithm to solve the minimization knapsack problem,we design an(α+β)-approximation algorithm to solve the k-CPIBC problem,whereβ=7/2-1/k-[1/k].(2)We present aβ-approximation algorithm to solve the special version of the k-CPIBC problem,where c(e)1 for each edge e in G and is defined in(1).
文摘If we restrict the postman to traversing each edge at most twice in the windypostman problem (WPP), we will get a new problem: 2WPP. An approximation algorithmhas been posed by M. Guan for the WPP. In the present paper, we improve the estimatederror given by M. Guan and show that we can estimate the error for the 2WPP by findinga minimum cost circulation. We also pose a new sufficient condition for the equivalencebetween WPP and 2WPP, which can be checked in polynomial time steps.
文摘接口或API测试是日常软件测试过程中常见内容之一,接口测试工具可选性很多,文章主要针对常用的三个接口测试工具:SoapUI、JMeter、Postman,分析它们之间的不同之处以及在实际工作中的应用。具体而言,使用不同的工具来解决日常软件测试中的不同接口类型的接口测试问题、性能测试问题、工作效率问题。在运营商运营支撑系统(Operation Support Systems,OSS)领域实际项目测试过程中,有的放矢地选择测试工具,不仅能有效提高了软件质量,同时有助于提高测试人员的效率。
文摘时间依赖网络相比传统网络模型有更广泛的应用领域,比如公交网络和通信网络都可以抽象成为时间依赖的网络模型。当模型中弧的访问代价为时间依赖的变量时,中国邮路问题的求解将变得非常困难。首先分析了传统的中国邮路问题求解算法,如奇偶图上作业法和Edmonds&Johnson算法,以及不能有效求解时间依赖中国邮路问题的根本原因;其次给出了一般时变无向中国邮路问题的特性,并在此基础上设计了该问题的分支限界最优化算法;然后针对FIFO(First In First Out)这一类特殊时变网络,设计了新的剪枝条件,从而得到了更有效求解FIFO网络的时变无向中国邮路问题的分支限界最优化算法;最后对算法进行了实验,算法实验结果正确。
