郵路規(guī)劃 2007年全國研究生數學建模競賽

1、2007 2007 年全國研究生數學建模競賽 年全國研究生數學建模競賽承 諾 書我們仔細閱讀了中國大學生數學建模競賽的競賽規(guī)則.我們完全明白，在競賽開始后參賽隊員不能以任何方式（包括電話、電子郵件、網上咨詢等）與隊外的任何人（包括指導教師）研究、討論與賽題有關的問題。我們知道，抄襲別人的成果是違反競賽規(guī)則的, 如果引用別人的成果或其他公開的資料（包括網上查到的資料） ，必須按照規(guī)定的參考文獻的表述方式在正文引用處和參考文獻中明確列出

2、。我們鄭重承諾，嚴格遵守競賽規(guī)則，以保證競賽的公正、公平性。如有違反競賽規(guī)則的行為，我們將受到嚴肅處理。我們參賽選擇的題號是（從 A/B/C/D 中選擇一項填寫）： D 我們的參賽報名號為（如果賽區(qū)設置報名號的話）： 所屬學校（請?zhí)顚懲暾娜?西安電子科技大學 參賽隊員（打印并簽名）：1.

3、 2. 3. 指導教師或指導教師組負責人 (打印并簽名)： 日期： 2012 年 8 月 28 日賽區(qū)評閱編號（由賽區(qū)組委會評閱前進行編號）：1郵政運輸網絡中的郵路 郵政運輸網絡中的郵路規(guī)劃和郵車調度 劃和郵車調度摘要

4、 摘要本文研究的是合理簡化后的某地區(qū)郵政網絡中的郵路規(guī)劃和郵車調度問題，本文通過深入分析，針對提出的問題建立了相應的組合優(yōu)化模型，并利用圖論的相關知識結合多種優(yōu)化算法進行求解。在滿足該縣的郵件運輸需求條件下，為使縣級郵車的數目最少，本文建立規(guī)劃模型，使由區(qū)級郵車運送包裹的支局數目盡可能的多，以減少縣級郵車的數目，得出縣級郵車只需 2 輛即可；進一步在給定郵車數量的基礎上，以空載帶來的損失最小為目標建立多旅行商模型，采用 Floyd 算法

5、編制的改進型貪心算法進行求解，得到一個較優(yōu)的郵路規(guī)劃，該方案由于空車率而減少的收入為40.36 元。問題二可以歸結為一個多目標且具有復雜約束的多旅行商問題，本文建立規(guī)劃模型，結合改良圈算法和換頂算法，得出每輛區(qū)級郵車的最佳路線，再通過 TSP 算法確定各縣級郵車的行駛方案，并得出郵車調動時刻表。為解決跨縣運輸郵件的郵路規(guī)劃問題，本文首先使用 SPSS 軟件對所有支局進行聚類分析，判斷可能需要重新劃分的支局，再分別計算這些支局劃分前后的運

6、行成本，進行比較之后得出支局被重新劃分后的郵車行駛方案與郵車調動時刻表。新方案成本為 6051 元，比劃分前減少了 36 元。為構建經濟、快速的郵政運輸網絡，本文通過對原縣局及各個支局交通便利程度、地理位置、到支局的距離、區(qū)車加縣車的總里程數等多方面進行分析，選定了新縣局地址。并采用問題二的方法進行規(guī)劃并尋優(yōu)，找到 12 條郵路的較優(yōu)解，總成本減少至 5886 元。關鍵字 關鍵字：郵路規(guī)劃 Hamilton 圖 Floyd