点击次数：

论文类型：期刊论文

发表时间：2010-08-20

发表刊物：计算机与数字工程

收录刊物：ISTIC

卷号：38

期号：8

页面范围：87-92

ISSN号：1672-9722

关键字：时间窗;时间依赖;中国邮路问题;图转换算法;广义乡村邮路问题;0/1整数规划模型

摘要：研究时间依赖网络上带时间窗的中国邮路问题(TDCPPTW),该问题是对中国邮路问题的扩展,它考虑了时间因素,在实时软件测试等当前许多具有时间依赖性质的热门问题中更具优势.首先提出了一个新的图转换算法;然后,从理论上证明了该转换算法能够在伪多项式时间内将TDCPPTW转换为相应的广义乡村邮路问题(GRPP);最后,建立了一个0/1线性整数规划模型用于求解转换后的问题,并对随机生成的12个实例进行了求解实验.