时间窗-时间依赖中国邮路问题的图转换算法

摘要：

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

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

作者: 陈加萍 孟宪超 孙景昊 谭国真

作者单位: 大连理工大学计算机科学与技术学院,大连,116023

会议类型: 国内会议

会议名称: 第七届全国Web信息系统及其应用学术会议、第五届全国语义Web与本体论学术研讨会、第四届全国电子政务技术及应用学术研讨会

会议地点: 呼和浩特

会议语种:中文

页码: 87-92

在线出版日期: 2010-08-01（万方平台首次上网日期，不代表论文的发表时间）