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

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

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

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

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

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

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