基于一种新的边权编码方案的中国邮递员问题的DNA计算模型

权编码方法是DNA计算中一个重要且有挑战性的问题.设计了一种新的用于表示赋权图中边权的DNA编码方案,给出了用该方案求解中国邮递员问题的DNA算法,并利用Markov链分析了DNA算法中生成各种路径的随机过程.对于任一赋权图G=(V,E),首先通过边到点映射把它转换为广义边图G'=(V',E').图G的每条边ei被分别映射为图G'的一个顶点(v'i).若G中ei与ej邻接,则连接G1中v'i和v'j.若G中vi为奇顶点,则在与vi关联的边对应的G'的顶点上添加自环.用于编码顶点v'i的DNA串si的长度等于边ei的权值.用于编码边v'i v'j的DNA串sij为si的后半部分与sj的前半部分并置后的逆补.所提出的DNA编码方案具有易于编码、易于推广且错误率低的特点.该工作可提高DNA计算中表示和处理数值的能力,扩展DNA计算求解最优化问题的范围.  

时变网络中国邮路问题的时间自动机模型

基于时间自动机理论,提出了时间窗、时间依赖服务代价以及时间依赖旅行时间这3类时变网络中国邮路问题的统一建模的语义模型和求解方法.首先,将中国邮路问题可行解条件和时变参数与时间自动机联系起来,建立了3类问题的统一时间自动机系统(timed automata system,简称TAS)模型;然后,将时变网络中国邮路问题归结为TAS模型上的一系列可达性判定问题,并利用形式化验证算法给出了有效的求解方法.由于TAS模型中存在O(|A|+|AR|+1)个时间自动机,限制了问题求解规模.为此,通过扩展时间自动机语义,提出了TAS模型中的时间自动机合并策略,进而将TAS模型转换为一个广义时间自动机(GTA)模型.基于GTA模型,利用UPPAAL工具对9组、共54个随机算例进行实验.实验结果表明,该方法在求解精度上明显优于运筹学领域的方法.  

二层SA/GA算法解决时间依赖中国邮路问题

中国邮路问题是图论中的经典问题，得到了深入研究和广泛应用。近年来，由于计算机网络与通信、智能交通系统等复杂应用领域的需求，研究时间依赖网络中的问题具有更为重要的现实应用意义。首先给出了时间依赖中国邮路问题的定义，然后证明了传统中国邮路问题的定理在时间依赖中国邮路问题中不成立，最后设计了二层SA/GA算法(模拟退火/遗传算法)来解决该问题，对随机产生的实例进行了测试，并根据问题下界对算法结果进行了分析。  

A comparison of two different formulations for arc routing problems on mixed graphs

Arc routing problems on mixed graphs have been modelled in the literature either using just one variable per edge or associating to each edge two variables, each one representing its traversal in the corresponding direction. In this paper, and using the mixed general routing problem as an example, we compare theoretical and computationally both formulations as well as the lower bounds obtained from them using Linear Programming based methods. Extensive computational experiments, including some big and newly generated random instances, are presented.  

A constraint programming approach to the Chinese postman problem with time windows

The Chinese postman problem with time windows (CPPTW) is modelled as a constraint programme and results are reported for a set of test problems with up to 69 edges. Two different formulations are proposed. The first formulation approaches the problem directly and the second transforms the problem to an equivalent vehicle routing problem with time windows. The results demonstrate that optimal solutions can be obtained quickly when the time windows are tight. However, the results also show that as the time windows are made wider and the number of feasible solutions increases, these constraint programming formulations take significantly longer to find a provably optimal solution. The results also demonstrate how the size and density of the graph affects the computing time needed to find an optimal solution.  

A tabu search algorithm for the min–max k-Chinese postman problem

In this paper we present a tabu search algorithm for the min–max k-Chinese postman problem (MM k-CPP). Given an undirected edge-weighted graph and a distinguished depot node, the MM k-CPP consists of finding k>1 tours (starting and ending at the depot node) such that each edge is traversed by at least one tour and the length of the longest tour is minimized. A special emphasis is put on investigating the trade-off between running time effort and solution quality when applying different improvement procedures in the course of the neighborhood construction. Furthermore, different neighborhoods are analyzed. Extensive computational results show that the tabu search algorithm outperforms all known heuristics and improvement procedures.

Scope and purpose

Given a road network, the Chinese postman problem (CPP) is to find the shortest postman tour covering all the roads in the network. Applications of the CPP include road maintenance, garbage collection, mail delivery, etc. Since usually large road networks have to be serviced the work load must be distributed among k2 vehicles. In contrast to the usual objective to minimize the total distance traveled by the k vehicles (k-CPP), for the min–max k-Chinese postman problem (MM k-CPP) the aim is to minimize the length of the longest of the k tours. This kind of objective is preferable when customers have to be served as early as possible. Furthermore, tours will be enforced to be more balanced resulting in a fair scheduling of tours. Although the CPP and the k-CPP are polynomially solvable, the MM k-CPP is -hard. Hence, we must rely on heuristics producing approximate solutions. The purpose of this paper is to present a tabu search algorithm for the MM k-CPP which outperforms all known heuristics. In many cases we obtained solutions which could be proved to be near-optimal or even optimal.  

Straight line approximation and 1D representation of off-line handwritten text

Algorithms to process off-line Arabic handwriting before recognition are presented. First, an algorithm that converts smoothed and thinned images into straight line approximations is described. Second, an algorithm is developed to obtain a 1D representation of off-line Arabic handwriting. This is achieved by first finding the start-end pair of vertices of writing. Then a stroke is traversed from the start to the end vertex by solving the Chinese postman's problem for its graph. Special rules are applied to enforce temporal information on the stroke to obtain the most likely traversal that is consistent with Arabic handwriting. Finally, an algorithm is suggested to reduce straight line approximations to other approximations in which loops are represented by vertices with features. In testing, 2256 unconstrained handwritten strokes, written by six writes, were used. In 96.5% of the samples, the algorithm restored the actual temporal information.  

时间依赖网络中国邮路问题

中国邮路问题是图论中的经典问题,得到了深入的研究和广泛应用。近年来,由于计算机网络与通信、智能交通系统等复杂应用领域的需求,时间依赖网络问题的研究具有更为重要的现实应用意义。本文首次提出了时间依赖网络中的中国邮路问题,建立了该问题的整数线性规划模型,并对该模型的上界进行了分析,最后给出了网络应用实例。  

Test minimization for human-computer interaction

This paper introduces a model-based approach for minimization of test sets to validate the interaction of human-computer systems. The novelty of the approach is twofold: (i) Test cases generated and selected holistically cover both the behavioral model and the complementary, fault model of the system under test (SUT). (ii) Methods known from state-based conformance testing and graph theory are extended to construct efficient, heuristic search-based algorithms for minimizing the test sets that are constructed in step (i), considering also structural features. Experience shows that the approach can help to considerably save test costs, up to 60% Fevzi Belli received the M.S., Ph.D., and Habilitation degrees in electrical engineering and computer science from the Berlin Technical University. He is presently a Professor of Software Engineering in the Faculty of Computer Science, Electrical Engineering and Mathematics, University of Paderborn, Paderborn, Germany. Prior to this, he headed several projects at a software house in Munich, was a Professor of Computing Science at the Hochschule Bremerhaven and a faculty member of the University of Maryland, European Division. He chaired several international conferences, e.g., ISSRE 1998 and is author and co-author of more than 100 papers published in scientific journals and conference proceedings. His research interests are in testing/fault tolerance/reliability of software and programming techniques. Christof J. Budnik received the MS degree in electrical engineering and computer science in 2001 from the University of Paderborn. In 2002, he joined the Department of Computer Science, Electrical Engineering and Mathematics at the same University where he is currently a faculty member. His research interests are in the areas of software quality, testing of interactive systems and safety-critical user interfaces.  

Approximate solutions for the maximum benefit chinese postman problem

The Maximum Benefit Chinese Postman Problem (MBCPP) is an interesting and practical generalization of the classical Chinese Postman Problem, which has many real-world applications. Each arc on the MBCPP network is associated with a service cost for the traversal with service, a deadhead cost for the traversal with no service, and a set of benefits. Each time an arc is traversed, a benefit is generated. The objective of the MBCPP is to find a postman tour traversing a selected set of arcs with the total net benefit maximized. Such a generalization reflects real-world situations more closely. The MBCPP has been shown to be more complicated than the Rural Postman Problem, which is an NP-hard problem. Therefore, it is difficult to find polynomial-time bounded algorithms to solve the problem exactly. In this paper, we first review an existing exact solution procedure, and introduce several heuristic algorithms including the Branch-Scan algorithm, the Connection algorithm with various connection strategies, and the Directed Tree algorithm, to solve the MBCPP approximately. We also apply one-opt, two-opt, component exchange, and component-drop procedures to improve the solutions. The proposed algorithms are tested and compared. Extensive computational results are provided and analysed.