点击次数：

论文类型：期刊论文

发表时间：2015-07-04

发表刊物：OPTIMIZATION METHODS & SOFTWARE

收录刊物：SCIE、EI

卷号：30

期号：4

页面范围：804-824

ISSN号：1055-6788

关键字：time varying; time window; time dependent; postman problem; timed automata

摘要：In this work, we present timed automata as a natural tool for posing and solving time varying postman problems. We show that these problems can be reduced to the problem of finding the shortest runs in our Timed Automata System (TAS) model. The problem can then be solved by incorporating the reachability analysis (RA) algorithm into a binary search framework. However, the scale of the TAS model is too large to adapt the RA algorithm embedded in the UppAal. Thus, we propose a composition strategy to transform the current TAS model into a Generalized Timed Automaton (GTA) model, such that the number of timed automata in our model decreases from Omicron(vertical bar A vertical bar = vertical bar A(R vertical bar) + 1) to Omicron(1)Computational results show that the GTA model can solve small-sized instances optimally and that it can obtain a better optimality gap than those obtained by the cutting plane algorithm.