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

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

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

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

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

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

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