CAJ | 학술논문

基于时间自动机理论,提出了时间窗、时间依赖服务代价以及时间依赖旅行时间这3类时变网络中国邮路问题的统一建模的语义模型和求解方法.首先,将中国邮路问题可行解条件和时变参数与时间自动机联系起来,建立了3类问题的统一时间自动机系统(timed automata system,简称TAS)模型;然后,将时变网络中国邮路问题归结为TAS模型上的一系列可达性判定问题,并利用形式化验证算法给出了有效的求解方法.由于TAS模型中存在O(|A|+|AR|+1)个时间自动机,限制了问题求解规模.为此,通过扩展时间自动机语义,提出了TAS模型中的时间自动机合并策略,进而将TAS模型转换为一个广义时间自动机(GTA)模型.基于GTA模型,利用UPPAAL工具对9组、共54个随机算例进行实验.法验结果表明,该方法在求解精度上明显优于运筹学领域的方法.
기우시간자동궤이론,제출료시간창、시간의뢰복무대개이급시간의뢰여행시간저3류시변망락중국유로문제적통일건모적어의모형화구해방법.수선,장중국유로문제가행해조건화시변삼수여시간자동궤련계기래,건립료3류문제적통일시간자동궤계통(timed automata system,간칭TAS)모형;연후,장시변망락중국유로문제귀결위TAS모형상적일계렬가체성판정문제,병이용형식화험증산법급출료유효적구해방법.유우TAS모형중존재O(|A|+|AR|+1)개시간자동궤,한제료문제구해규모.위차,통과확전시간자동궤어의,제출료TAS모형중적시간자동궤합병책략,진이장TAS모형전환위일개엄의시간자동궤(GTA)모형.기우GTA모형,이용UPPAAL공구대9조、공54개수궤산례진행실험.법험결과표명,해방법재구해정도상명현우우운주학영역적방법.