時間依賴的無向中國郵路問題分支切割算法.pdf

1、路由問題具有重要的理論意義和眾多的實際應用，半個多世紀得到了國內外學者深入的研究。傳統(tǒng)的路由問題通常被認為用于服務弧或點的代價是常量，屬于靜態(tài)的網絡優(yōu)化問題。然而現實情形中旅行時間或代價常隨時間發(fā)生變化并非定值，所以單純的將代價視為常量只是對現實的一個近似。由此進一步加入時間因素成為實際應用中更為迫切的要求，即在時間依賴網絡中研究上述問題。本文對時間依賴的無向中國郵路問題分支切割算法進行了研究。主要內容如下：
　　 ⑴給出了時間

2、依賴的中國郵路問題統(tǒng)一定義及其分類，并分析了此類問題所呈現的一些重要特性及與傳統(tǒng)的中國郵路問題的區(qū)別。如傳統(tǒng)的兩階段求解方法將不再成立，建模時其時間依賴函數所呈現的情形等。
　　 ⑵結合上述特性給出此問題在無向圖情形下，即時間依賴無向中國郵路問題的兩類整數規(guī)劃模型。模型中均實現了一步求解的方法并考慮了各邊被遍歷的次序。在模型正確性證明之后，探討如何給出其它各變形的數學模型。
　　 ⑶給出了在無向圖上獲得問題上下界的策略，