计算机与数字工程
計算機與數字工程
계산궤여수자공정
COMPUTER & DIGITAL ENGINEERING
2010年
8期
87-92
,共6页
陈加萍%孟宪超%孙景昊%谭国真
陳加萍%孟憲超%孫景昊%譚國真
진가평%맹헌초%손경호%담국진
时间窗%时间依赖%中国邮路问题%图转换算法%广义乡村邮路问题%0/1整数规划模型
時間窗%時間依賴%中國郵路問題%圖轉換算法%廣義鄉村郵路問題%0/1整數規劃模型
시간창%시간의뢰%중국유로문제%도전환산법%엄의향촌유로문제%0/1정수규화모형
研究时间依赖网络上带时间窗的中国邮路问题(TDCPPTW),该问题是对中国邮路问题的扩展,它考虑了时间因素,在实时软件测试等当前许多具有时间依赖性质的热门问题中更具优势.首先提出了一个新的图转换算法;然后,从理论上证明了该转换算法能够在伪多项式时间内将TDCPPTW转换为相应的广义乡村邮路问题(GRPP);最后,建立了一个0/1线性整数规划模型用于求解转换后的问题,并对随机生成的12个实例进行了求解实验.
研究時間依賴網絡上帶時間窗的中國郵路問題(TDCPPTW),該問題是對中國郵路問題的擴展,它攷慮瞭時間因素,在實時軟件測試等噹前許多具有時間依賴性質的熱門問題中更具優勢.首先提齣瞭一箇新的圖轉換算法;然後,從理論上證明瞭該轉換算法能夠在偽多項式時間內將TDCPPTW轉換為相應的廣義鄉村郵路問題(GRPP);最後,建立瞭一箇0/1線性整數規劃模型用于求解轉換後的問題,併對隨機生成的12箇實例進行瞭求解實驗.
연구시간의뢰망락상대시간창적중국유로문제(TDCPPTW),해문제시대중국유로문제적확전,타고필료시간인소,재실시연건측시등당전허다구유시간의뢰성질적열문문제중경구우세.수선제출료일개신적도전환산법;연후,종이론상증명료해전환산법능구재위다항식시간내장TDCPPTW전환위상응적엄의향촌유로문제(GRPP);최후,건립료일개0/1선성정수규화모형용우구해전환후적문제,병대수궤생성적12개실례진행료구해실험.
