郵政運(yùn)輸網(wǎng)絡(luò)中的郵路規(guī)劃和郵車調(diào)度優(yōu)化研究

1、1郵政運(yùn)輸網(wǎng)絡(luò)中的郵路郵政運(yùn)輸網(wǎng)絡(luò)中的郵路規(guī)劃和郵車調(diào)度問題劃和郵車調(diào)度問題1問題重述問題重述古往今來，郵政在人們的生活中都扮演著不可或缺的角色。隨著時代的發(fā)展，郵件投送的時限和成本成了郵政運(yùn)輸問題的關(guān)鍵因素。根據(jù)題目給出的實際情況，本文提出了關(guān)于如何合理規(guī)劃郵路的問題，具體內(nèi)容如下：對一片有特定道路相連且有行政劃分的地區(qū)進(jìn)行郵路規(guī)劃，有以下的問題需要解決：(1)以縣局X1及其所轄的16個支局Z1Z2……Z16(下文簡稱為1，2，……)

2、為研究對象。假設(shè)區(qū)級第一班次郵車08:00到達(dá)縣局X1，區(qū)級第二班次郵車16:00從縣局X1再出發(fā)返回地市局D，若每輛縣級郵車最多容納65袋郵件，在不超載的情況下，利用最少的車輛和最短的郵路，達(dá)到減少空車損失的目的。(2)采用盡可能少、盡可能短的郵路可以減少郵政部門車輛和人員等的投入，從而顯著降低全區(qū)郵政運(yùn)輸網(wǎng)的總運(yùn)行成本的郵路規(guī)劃。(3)當(dāng)縣局可以跨縣投寄時的郵路規(guī)劃。(4)選擇最合適的縣局地點，并重新規(guī)劃郵路，使得運(yùn)行的成本最低。2

3、模型假設(shè)模型假設(shè)1所有的郵車在郵路上均按照平均時速勻速行駛。2縣局對市局送來郵件的集中處理時間(1小時)既包括區(qū)級郵車的裝卸時間10分鐘，也包括縣級郵車的裝卸時間10分鐘。且在這1個小時的起始階段進(jìn)行裝卸區(qū)級郵車的工作；而縣級郵車的裝卸工作最早在集中處理工作結(jié)束前10分鐘進(jìn)行，也可以在集中處理工作結(jié)束之后進(jìn)行。3縣局對將要送到市局的郵件的集中處理時間(1小時)既包括縣級郵車的裝卸時間10分鐘，也包括區(qū)級郵車的裝卸時間10分鐘。且在這1個

4、小時的起始階段進(jìn)行裝卸縣級郵車的工作；而區(qū)級郵車的裝卸工作最早在集中處理工作結(jié)束前10分鐘進(jìn)行，也可以在集中處理工作結(jié)束之后進(jìn)行。4兩班次的區(qū)級郵車行駛路線完全相同，若路線為環(huán)形則運(yùn)行方向必須一致。如：D→61→58→53→X5→52→59→60→D與D→60→59→52→X5→53→58→61→D兩種行車路線即為不同的兩條路線。5問題4中選定縣局后，縣級郵車不得打破行政區(qū)劃限制而跨縣投寄。34模型建立與求解模型建立與求解4.14.1問

5、題問題1的解決的解決4.1.14.1.1模型的建立模型的建立根據(jù)題意，問題一可以歸納為如下數(shù)學(xué)模型。121212min()min()..()kkkCPPPLgPPPstPPPP?????????????其中：表示郵路方案；表示空置損失費(fèi)；12()kPPP???12()kCPPP???表示方案的總路徑；P表示郵路方案集。12()kLgPPP???4.1.24.1.2方案的比較與確定方案的比較與確定根據(jù)題目要求，需要在限定的時間內(nèi)完成投送郵

6、件的工作。首先，很自然地想到求出能夠遍歷這些點的最短路徑，從理論上初步判斷需要的車輛數(shù)。4.1.2.1Floyd算法Floyd算法的基本思想就是直接在圖的帶權(quán)鄰接矩陣中用插入頂點的方法依次構(gòu)造出v個矩陣，使最后得到的矩陣成為圖的距離矩(1)(2)()vLLL???、、、()vL陣，同時也求出插入點矩陣以便得到兩點間的最短路徑。此算法的主要程序流程如下：Step1：輸入賦權(quán)鄰接矩陣，()WijStep2：賦初值：對所有，，，，。ij()(