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

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

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

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

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

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