1、郵路規(guī)劃和郵車調(diào)度的優(yōu)化一、問(wèn)題的提出本題是2007年全國(guó)研究生數(shù)學(xué)建模競(jìng)賽D題，題目如下：我國(guó)的郵政運(yùn)輸網(wǎng)絡(luò)采用郵區(qū)中心局體制，即以郵區(qū)中心局作為基本封發(fā)單元和網(wǎng)路組織的基本節(jié)點(diǎn)，承擔(dān)著進(jìn)、出、轉(zhuǎn)口郵件的處理、封發(fā)和運(yùn)輸任務(wù)，在此基礎(chǔ)上組織分層次的郵政網(wǎng)。郵路是郵政運(yùn)輸網(wǎng)絡(luò)的基本組成單元，它是指利用各種運(yùn)輸工具按固定班期、規(guī)定路線運(yùn)輸郵件，并與沿線有交接頻次的郵政局、所交換郵件總包所行駛的路線。郵路的結(jié)構(gòu)形式有三種：輻射形、環(huán)形和混合形。如圖1所示，郵路A為一條環(huán)形郵路，郵路B為一條輻射形郵路。圖1 郵路示意圖1、輻射形郵路：是指從起點(diǎn)局出發(fā)，走直線或曲折線的郵路，其特點(diǎn)是不論用一種或幾種運(yùn)

2、輸工具聯(lián)運(yùn)，從起點(diǎn)到終點(diǎn)后，仍按照原路線返回出發(fā)地點(diǎn)。因此須在同一條路線上往返兩個(gè)行程。這種郵路可以縮短運(yùn)遞時(shí)間，加快郵運(yùn)速度。但它的聯(lián)系點(diǎn)較少，需用的運(yùn)輸工具較多，所耗費(fèi)用較大。2、環(huán)形郵路：是指郵政運(yùn)輸工具走環(huán)形路線的郵路，即運(yùn)輸工具從起點(diǎn)出發(fā)單向行駛，繞行一周，經(jīng)過(guò)中途各站，回到出發(fā)地點(diǎn)。它的特點(diǎn)是不走重復(fù)路線，聯(lián)系點(diǎn)較多，運(yùn)輸工具的利用率高，運(yùn)費(fèi)也較省。但是郵件送到最后幾個(gè)交接點(diǎn)的時(shí)間較長(zhǎng)。3、混合形郵路：是指包含輻射形和環(huán)形兩種結(jié)構(gòu)形式的郵路。某地區(qū)的郵政局、所分布如圖2所示，分為地市中心局（簡(jiǎn)稱地市局）、縣級(jí)中心局（簡(jiǎn)稱縣局）和支局三級(jí)機(jī)構(gòu)，該地區(qū)的郵政運(yùn)輸網(wǎng)絡(luò)由區(qū)級(jí)郵政運(yùn)輸網(wǎng)和縣

3、級(jí)郵政運(yùn)輸網(wǎng)構(gòu)成。區(qū)級(jí)郵政運(yùn)輸網(wǎng)由從地市局出發(fā)并最終返回地市局的區(qū)級(jí)郵車所行駛的全部郵路構(gòu)成，縣級(jí)郵政運(yùn)輸網(wǎng)由從縣局出發(fā)并最終返回縣局的縣級(jí)郵車所行駛的全部郵路構(gòu)成。為使郵政企業(yè)實(shí)現(xiàn)低成本運(yùn)營(yíng)和較高的服務(wù)質(zhì)量，我們需要對(duì)該地區(qū)的郵政運(yùn)輸網(wǎng)絡(luò)進(jìn)行重構(gòu)，確定合適的郵路規(guī)劃方案并進(jìn)行郵車的合理調(diào)度。為了滿足郵政的時(shí)限要求，必須盡可能地保證各縣局、支局在營(yíng)業(yè)時(shí)間內(nèi)收寄的多數(shù)郵件能當(dāng)天運(yùn)送回地市局進(jìn)行分揀封發(fā)等處理，以及每天到達(dá)地市局的多數(shù)郵件能當(dāng)天運(yùn)送到目的地縣局、支局。該地區(qū)從地市局到縣局每天兩班車，從縣局到支局每天僅有一班車。該地區(qū)的郵政運(yùn)輸流程及時(shí)限規(guī)定如下：Step1：區(qū)級(jí)第一班次郵車從地市局

4、D出發(fā)將郵件運(yùn)送到各縣局Xi和沿途支局，并將各縣局Xi和沿途支局收寄的郵件運(yùn)送回地市局D；區(qū)級(jí)第一班次郵車出發(fā)時(shí)間必須在06:00之后，返回地市局D時(shí)間必須在11:00之前。Step2：縣局Xi將當(dāng)天區(qū)級(jí)第一班次郵車及前一天的區(qū)級(jí)第二班次郵車所送達(dá)的本縣郵件進(jìn)行集中處理，按寄達(dá)支局裝上相應(yīng)的縣級(jí)郵車；縣局Xi對(duì)郵件的集中處理時(shí)間為1小時(shí)（包括郵件的卸裝、分揀封發(fā)等處理時(shí)間）。Step3：各縣級(jí)郵車將郵件運(yùn)送到其負(fù)責(zé)的支局并將這些支局收寄的郵件運(yùn)送回縣局Xi；圖2 某地區(qū)郵政局、所分布圖（圖中代號(hào)1至73依次代表支局Z1, Z2, , Z73）Step4：區(qū)級(jí)第二班次郵車從地市局D出發(fā)將郵件運(yùn)送

5、到各縣局Xi和沿途支局，并將各縣局Xi收寄的郵件（包括當(dāng)日各縣級(jí)郵車運(yùn)回縣局Xi的郵件）和沿途支局收寄的郵件運(yùn)送回地市局D；請(qǐng)注意區(qū)級(jí)第二班次郵車在縣局Xi卸裝完郵件后的出發(fā)時(shí)間必須在縣局Xi的全部縣級(jí)郵車返回縣局并集中處理1小時(shí)以后，最終返回地市局D的時(shí)間必須在18:00之前。假設(shè)區(qū)級(jí)兩個(gè)班次郵車的行駛路線相同，要求區(qū)級(jí)郵政運(yùn)輸網(wǎng)必須至少覆蓋該地市附近的16個(gè)支局Z58, Z59, , Z73和5個(gè)縣局X1，X5。各縣級(jí)郵政運(yùn)輸網(wǎng)必須覆蓋本縣內(nèi)區(qū)級(jí)郵車不到達(dá)的支局。該地區(qū)郵局間公路網(wǎng)分布見(jiàn)表1，并且縣級(jí)郵車平均時(shí)速為30km/h，區(qū)級(jí)郵車的平均時(shí)速為65km/h，郵車在各支局卸裝郵件耗時(shí)5分

6、鐘，在各縣局卸裝郵件耗時(shí)10分鐘。問(wèn)題1：以縣局X1及其所轄的16個(gè)支局Z1, Z2, , Z16為研究對(duì)象，假設(shè)區(qū)級(jí)第一班次郵車08:00到達(dá)縣局X1，區(qū)級(jí)第二班次郵車16:00從縣局X1再出發(fā)返回地市局D，若每輛縣級(jí)郵車最多容納65袋郵件，試問(wèn)最少需要多少輛郵車才能滿足該縣的郵件運(yùn)輸需求？同時(shí)，為提高郵政運(yùn)輸效益，應(yīng)如何規(guī)劃郵路和如何安排郵車的運(yùn)行？（郵件量見(jiàn)表2，空車率=(郵車最大承運(yùn)的郵件量(袋)-郵車運(yùn)載的郵件量(袋)/郵車最大承運(yùn)的郵件量(袋)，單車由于空車率而減少的收入為（空車率*2元/km）問(wèn)題2：采用盡可能少、盡可能短的郵路可以減少郵政部門車輛和人員等的投入，從而顯著降低全區(qū)

7、郵政運(yùn)輸網(wǎng)的總運(yùn)行成本?？紤]投入車況較好的郵車，通常每條郵路只需要一輛郵車即能滿足運(yùn)載能力要求，試問(wèn)應(yīng)如何構(gòu)建該地區(qū)的郵政運(yùn)輸網(wǎng)絡(luò)（縣的劃分不能變更），請(qǐng)你給出郵路規(guī)劃和郵車調(diào)度方案。請(qǐng)注意郵車的調(diào)度必須滿足上文中有關(guān)該地區(qū)的郵政運(yùn)輸流程及時(shí)限規(guī)定。（每條郵路的運(yùn)行成本為3元/km）問(wèn)題3：考慮到部分縣與縣交界地帶的支局，其郵件由鄰縣縣局負(fù)責(zé)運(yùn)送可能會(huì)降低全區(qū)的運(yùn)行成本，帶來(lái)可觀的經(jīng)濟(jì)效益。若允許在一定程度上打破行政區(qū)域的限制，你能否給出更好的郵路規(guī)劃和郵車調(diào)度方案？（在此同樣不必考慮郵車的運(yùn)載能力的限制，每條郵路的運(yùn)行成本為3元/km）問(wèn)題4：縣局選址的合理與否對(duì)構(gòu)建經(jīng)濟(jì)、快速的郵政運(yùn)輸網(wǎng)絡(luò)

8、起到?jīng)Q定性的作用。假設(shè)圖2中縣局X1，X5均允許遷址到本縣內(nèi)任一支局處，同時(shí)原來(lái)的縣局弱化為普通支局。設(shè)想你是該地區(qū)網(wǎng)運(yùn)部門負(fù)責(zé)人，請(qǐng)你重新為各個(gè)縣局選址，陳述你的遷址理由并以書面材料形式提交省局網(wǎng)運(yùn)處。表1：(詳細(xì)信息請(qǐng)參照Excel文檔:郵局間直達(dá)公路里程.xls) 郵局i郵局j直達(dá)公路里程（km）DZ4250DZ5954DZ6043DZ6122DZ6240DZ6351DZ6551Z72Z7313表2： 支 郵 局 件 量Z1Z2Z3Z4Z5Z6Z7Z8Z9Z10Z11Z12Z13Z14Z15Z16寄達(dá)局為Z i的郵件量（袋）101569136114131711211211314支局Z i

9、收寄的郵件量（袋）9145109101391596713151016二、基本假設(shè)1各條路線的路況相差不大，耗費(fèi)與路程成正比。2郵車保持勻速行駛。三、問(wèn)題1的分析和建模準(zhǔn)備1分析本問(wèn)題以一個(gè)縣（包含縣局X1和16個(gè)支局）為研究對(duì)象，解決以下兩個(gè)問(wèn)題：(1) 在滿足該縣郵件運(yùn)輸需求的前提條件下，求出最少郵車數(shù)量；(2) 合理規(guī)劃各郵車的運(yùn)行路線，在確保完成郵件運(yùn)輸任務(wù)的條件下，使經(jīng)濟(jì)效益最高。以上兩個(gè)問(wèn)題可以分成兩步來(lái)解決，第一步確定最少用多少輛郵車能夠按時(shí)完成郵件運(yùn)輸任務(wù)，第二步對(duì)16個(gè)支局進(jìn)行優(yōu)化分組，使得費(fèi)用最省。首先考慮最少郵車數(shù)量，由題目所給表2中的數(shù)據(jù)，寄達(dá)16個(gè)支局的郵件總數(shù)為176

10、袋，從各支局收寄的郵件總數(shù)為170袋，每一輛郵車最多容納65袋郵件，至少需要輛郵車，由于郵車數(shù)量n為整數(shù)，因此，即最少需要3輛郵車。如果3輛郵車在規(guī)定的時(shí)間內(nèi)能夠完成郵件運(yùn)輸任務(wù)，則3輛車就是郵車數(shù)量的最優(yōu)解。假設(shè)3輛郵車可以按時(shí)完成任務(wù)，則第二步要解決的問(wèn)題是，將16個(gè)支局分成3組，分別由3輛郵車包干負(fù)責(zé)郵件送達(dá)和收寄，每組（每輛郵車）的起點(diǎn)和終點(diǎn)都是縣局，每個(gè)支局都必須有郵車到達(dá)，且只需一次，科學(xué)地規(guī)劃郵車在本組內(nèi)的行駛路線，使得總費(fèi)用最小，題目所給由于空車率而減小的收入為空車率*2元/km，如果空車率變化不大，則損失與總行駛公里數(shù)成正比，而郵車的行駛費(fèi)用（含耗油量、磨損折舊、維修）通常與

11、行駛公里數(shù)成正比，所以，只要3輛郵車的總行駛里程最小，則行駛成本（費(fèi)用）費(fèi)用也是最小，假如16個(gè)支局已經(jīng)分成了3組，各組安排一輛郵車，它在本組內(nèi)的最優(yōu)行駛路線相當(dāng)于找出一條能夠到達(dá)組內(nèi)每個(gè)支局一次且只需一次，最后回到縣局，行駛里程最短的路線，這個(gè)問(wèn)題相當(dāng)于旅行售貨商(TSP)模型，但是有附加約束條件（時(shí)間約束和載重約束）。安排3輛郵車的最優(yōu)行駛路線可以作為一個(gè)整體優(yōu)化模型，其目標(biāo)可以有以下兩點(diǎn)考慮：(1) 3輛郵車的合計(jì)行駛里程最少；(2) 空車率損失最小?？哲嚶逝c寄達(dá)各支局的郵件量以及從各支局收寄的郵件量有關(guān)，在郵車達(dá)到一個(gè)支局以后，卸下寄達(dá)該支局的郵件，裝上需要寄走的郵件，空車率發(fā)生一些變

12、化，因?yàn)猷]車的負(fù)載每天有變化，所以空車率每天都不相同。縣局以及各支局之間的距離是相對(duì)固定不變的，我們應(yīng)當(dāng)盡可能使每一輛郵車的行駛路線相對(duì)固定，避免每天重新做規(guī)劃，使路線變來(lái)變?nèi)ィf(wàn)一某一天某個(gè)支局的郵件較多，偶爾超載幾袋郵件不至于發(fā)生大問(wèn)題。由此看來(lái)，兩個(gè)目標(biāo)函數(shù)相比較，第一目標(biāo)是關(guān)鍵，把3輛郵車的總行駛里程最少作為首要目標(biāo)，而第二目標(biāo)，即空車率最小可以作為次要目標(biāo)。設(shè)各輛郵車的行駛里程為，則目標(biāo)函數(shù)可以寫成： (1)約束條件有以下兩條：(1) 時(shí)間約束按照題意，區(qū)級(jí)（地市局）郵車8:00達(dá)到縣局，集中處理1小時(shí)（含郵件的卸裝），縣級(jí)郵車在9:00出發(fā)前往本縣支局，因?yàn)閰^(qū)級(jí)郵車16:00從縣局

13、出發(fā)返回，縣級(jí)郵車完成運(yùn)輸任務(wù)返回縣局以后，縣局還需要集中處理1小時(shí)，所以縣級(jí)郵車必須在15:00之前回到縣局，可以利用的時(shí)間最多為6小時(shí)，即行車時(shí)間加上裝卸時(shí)間合起來(lái)不超過(guò)6小時(shí)，如果某一輛郵車的行駛里程為L(zhǎng)，負(fù)責(zé)m個(gè)支局，則行車時(shí)間為小時(shí)（2L分鐘），卸裝郵件用時(shí)5m分鐘，于是該郵車的時(shí)間約束可以表示為： (2)(2) 運(yùn)載量約束題目規(guī)定，每一輛郵車最多裝65袋郵件。假設(shè)按照行車計(jì)劃，某一輛郵車去m個(gè)支局，寄達(dá)這些支局的郵件量為Pj，支局收寄的郵件量為Qj，則該郵車從縣局出發(fā)時(shí)的郵件總量為，達(dá)到某個(gè)支局以后，卸下Pj袋，裝上Qj袋，經(jīng)過(guò)若干次卸和裝，到達(dá)第n個(gè)支局以后，郵車上的郵件量變?yōu)椋?/p>

14、在達(dá)到最后一個(gè)支局后，所有寄達(dá)各支局的郵件全部卸完，從各支局收寄的郵件全部裝上郵車，總裝載量變?yōu)?，在郵車行駛?cè)^(guò)程中，限制運(yùn)載量始終不超過(guò)65袋，于是運(yùn)載量約束可以表示為： (3)由以上分析可知，問(wèn)題1需要解決的問(wèn)題是：先把16個(gè)支局分成3個(gè)組，一輛郵車承包一個(gè)組，負(fù)責(zé)組內(nèi)各支局郵件的送達(dá)和收寄，然后規(guī)劃各組最優(yōu)行駛路線使目標(biāo)函數(shù)最優(yōu)，分組以及組內(nèi)行車路線都會(huì)影響最后結(jié)果，這是一個(gè)求整體最優(yōu)化的規(guī)劃問(wèn)題，它有明確的目標(biāo)函數(shù)和約束條件，但不能把分組和組內(nèi)行駛路線隔離起來(lái)，即不能孤立地分開(kāi)處理成兩個(gè)問(wèn)題。這相當(dāng)于有附加約束條件的多人旅行商問(wèn)題。為了對(duì)16個(gè)支局進(jìn)行科學(xué)分組并建立解決問(wèn)題1的數(shù)學(xué)模型

15、，需要做一些建模前的準(zhǔn)備工作，例如求出16個(gè)支局和縣城共17個(gè)節(jié)點(diǎn)中任意兩個(gè)點(diǎn)之間的最短路、找出該公路網(wǎng)的最小生成樹(shù)、根據(jù)兩兩節(jié)點(diǎn)之間的距離對(duì)16個(gè)支局進(jìn)行聚類分析。2任意兩點(diǎn)之間的最短路徑在圖論中求解最短路的較成熟的方法是Dijkstra和Floyd算法，其中Dijkstra算法適用于指定某個(gè)節(jié)點(diǎn)為起點(diǎn)，從該點(diǎn)出發(fā)到其它任意點(diǎn)的最短路，換另外起點(diǎn)時(shí)需要重新編程，而Floyd算法能夠一次性求出任意兩點(diǎn)之間的最短路，它是一種通過(guò)循環(huán)進(jìn)行逐步比較、動(dòng)態(tài)尋優(yōu)的方法，可以在Matlab中用矩陣運(yùn)算來(lái)解決，輸入節(jié)點(diǎn)的距離矩陣，輸出計(jì)算結(jié)果（最短路矩陣和表示最短路經(jīng)過(guò)哪些節(jié)點(diǎn)的路徑矩陣）先編寫Flody算

16、法的子程序（函數(shù)）如下：function D,R=floyd(a)n=size(a,1);D=a;for i=1:n for j=1:n R(i,j)=j; endendfor k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j)=u(K)+X(K,J)-(N-2)*(1-X(K,J)+(N-3)*X(J,K); ); );sum( city( J)| J #GT# 1: x( 1, J) = 1; for(city(K)|K#gt#1:U(K)=1;U(K)=N-1-(N-2)*X(1,K););end圖3 縣局X1以及16個(gè)支局的網(wǎng)絡(luò)最小生成樹(shù)運(yùn)行以上程序，

17、求得一種最小生成樹(shù)如圖3所示，樹(shù)的總長(zhǎng)度為221km，包含16條邊：X1-Z4，X1-Z12，X1-Z13，Z13-Z1，Z4-Z3，Z3-Z2，Z4-Z5，Z5-Z6，Z6-Z7，Z4-Z10，Z10-Z9，Z9-Z8，Z10-Z15，Z15-Z16，Z15-Z11，Z15-Z14。需要注意的是：最小生成樹(shù)不一定是唯一的。求網(wǎng)絡(luò)最小生成樹(shù)的成熟算法有Prim（普里姆）算法和Kruskal（克魯斯卡爾）算法。下面給出分別Prim算法和Kruskal算法的matlab程序。(1) Prim算法的matlab程序a=0, 27, 44, 17, 11, 27, 42, inf, inf, inf,

18、 20, 25, 21, 21, 18, 27, inf;27, 0, 31, 27, 49, inf,inf,inf,inf,inf,inf,inf,52,21,41,inf,inf;44,31,0,19,inf,27,32,inf,inf,inf,47,inf,inf,inf,50,inf,inf;17,27,19,0,14,inf,inf,inf,inf,inf,30,inf,inf,inf,31,inf,inf;11,49,inf,14,0,13,20,inf,inf,28,15,inf,inf,inf,15,25,30;27,inf,27,inf,13,0,9,21,inf,26,2

19、6,inf,inf,inf,28,29,inf;42,inf,32,inf,20,9,0,13,inf,32,inf,inf,inf,inf,inf,33,inf;inf,inf,inf,inf,inf,21,13,0,19,inf,inf,inf,inf,inf,inf,inf,inf;inf,inf,inf,inf,inf,inf,inf,19,0,11,20,inf,inf,inf,inf,33,21;inf,inf,inf,inf,28,26,32,inf,11,0,10,20,inf,inf,29,14,13;20,inf,47,30,15,26,inf,inf,20,10,0,18

20、,inf,inf,14,9,20;25,inf,inf,inf,inf,inf,inf,inf,inf,20,18,0,23,inf,inf,14,inf;21,52,inf,inf,inf,inf,inf,inf,inf,inf,inf,23,0,27,22,inf,inf;21,21,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,27,0,inf,inf,inf;18,41,50,31,15,28,inf,inf,inf,29,14,inf,22,inf,0,11,inf;27,inf,inf,inf,25,29,33,inf,33,14,9,14,inf

21、,inf,11,0,9;inf,inf,inf,inf,30,inf,inf,inf,21,13,20,inf,inf,inf,inf,9,0;T=;e=0;v=1;n=size(a,1);c=2:n;for j=2:n b(1,j-1)=1; b(2,j-1)=j; b(3,j-1)=a(1,j);endwhile size(T,2)n-1 m,i=min(b(3,:); T(:,size(T,2)+1)=b(:,i); e=e+b(3,i); v=b(2,i);v, t=find(c=b(2,i); c(t)= ;b(:,i)= ; for j=1:length(c) d=a(v,b(2,

22、j); if d0 & a(i,j)800 k=k+1; b(1,k)=i;b(2,k)=j; b(3,k)=a(i,j); end endendB,i=sortrows(b,3);B=B;m=size(b,2);t=1:n;k=0;T= ;c=0;for i=1:m if t(B(1,i)=t(B(2,i) k=k+1; T(k,1:2)=B(1:2,i); c=c+B(3,i); tmin=min(t(B(1,i),t(B(2,i); tmax=max(t(B(1,i),t(B(2,i); for j=1:n if t(j)=tmax t(j)=tmin; end end end if k

23、=n-1 break; endendT,c以上程序運(yùn)行結(jié)果與LINGO的結(jié)果基本相同（見(jiàn)圖3）。4聚類分析聚類分析通過(guò)分析數(shù)據(jù)，根據(jù)它們之間的相似關(guān)系，合理地劃分?jǐn)?shù)據(jù)集合，使同一類別內(nèi)的個(gè)體差別盡量小，而不同類別上的個(gè)體差別盡量大。聚類分析是一種探索性的分析，在分類過(guò)程中，人們不必事先給出一個(gè)分類標(biāo)準(zhǔn)，也不必確定分成幾類，聚類分析能夠從樣本數(shù)據(jù)出發(fā)，按照它們?cè)谛再|(zhì)上的的相近程度在沒(méi)有先驗(yàn)知識(shí)的情況下自動(dòng)進(jìn)行分類。聚類分析的方法中有一種稱為層次聚類分析方法，它使具有共同特點(diǎn)的樣本聚齊在一起，根據(jù)觀測(cè)值或變量之間的親疏程度，將最相似的對(duì)象結(jié)合在一起，以逐次聚合（分解）的方式將觀測(cè)值分類。又分成兩種

24、：(1) 自頂向下，開(kāi)始時(shí)所有對(duì)象為一類，然后逐步分裂，直至每個(gè)對(duì)象單獨(dú)為一類。(2) 自底向上，開(kāi)始時(shí)每個(gè)對(duì)象為一類，逐次合并相近的對(duì)象，直至所有樣本都聚為一類。圖4 根據(jù)距離對(duì)16個(gè)支局聚類分析的結(jié)果分類的重要依據(jù)是對(duì)象之間的距離，這里所說(shuō)的距離是廣義上的距離概念，不是單純的幾何意義上的距離。前面我們求出了任意兩個(gè)節(jié)點(diǎn)之間的最短路，不妨就把節(jié)點(diǎn)之間的幾何距離作為分類的主要依據(jù)，對(duì)它們進(jìn)行自底向上的聚類分析。開(kāi)始時(shí)類的總數(shù)等于對(duì)象數(shù)目，然后將相互之間距離最近的兩個(gè)（或幾個(gè)）對(duì)象歸為一類，逐步減少類別的總數(shù)，直至達(dá)到預(yù)設(shè)的類別數(shù)或較理想的狀態(tài)。判別聚類效果是否優(yōu)的標(biāo)準(zhǔn)是同一類內(nèi)的差別（平均距離

25、）盡可能小，而不同類之間差別（指標(biāo)）盡可能大?？梢杂媒y(tǒng)計(jì)分析軟件SPSS來(lái)進(jìn)行聚類分析，將最短路矩陣輸入SPSS，統(tǒng)計(jì)分析軟件，執(zhí)行AnalyzeClassifyHierarchical Cluster（層次聚類分析），在Cluster Method（聚類方法）選項(xiàng)中選擇Within-group linkage（組內(nèi)連接法，即同一類中所有項(xiàng)之間的平均距離最?。?，點(diǎn)擊“OK”，得到結(jié)果如圖4所示。從結(jié)果分析，支局10,15,9,16,14,11,8,12是第一組（排隊(duì)越靠前，關(guān)系越緊密），5,6,4,3,7是第二組，1,13,2是第三組。因?yàn)檫@種分組只考慮了支局之間的距離，沒(méi)有考慮郵車裝載量約束

26、，如第一組含8個(gè)支局，郵件的總量為97袋，超過(guò)最大裝載量65，所以聚類結(jié)果只能供參考而不能作為郵車規(guī)劃的依據(jù)。為了在分類的同時(shí)考慮郵件裝載量約束，可以建立規(guī)劃模型對(duì)16個(gè)支局進(jìn)行分類（分組）。用表示16個(gè)支局，表示3個(gè)組，Pi表示寄達(dá)支局Zi的郵件量，Qi表示從支局Zi收寄的郵件量，用0-1型決策變量Xik表示支局i，是否分在第k組，表示支局i分在第k組，表示否。每?jī)蓚€(gè)支局之間均存在最短路（有些支局之間沒(méi)有直接通路，但存在經(jīng)過(guò)其它支局的間接路徑），用Cij表示支局i與支局j之間的最短路。約束條件如下：(1) 每個(gè)支局必須分一次，且只能分到一組。(2) 每個(gè)組最多8個(gè)支局，最少3個(gè)支局（該條件并

27、非必須）。(3) 各組寄達(dá)和收寄的郵件總量都不超過(guò)65袋。第k組內(nèi)兩兩支局之間最短路經(jīng)的總和為，組內(nèi)支局?jǐn)?shù)量為，組內(nèi)平均距離為，優(yōu)化分組的目標(biāo)是使總平均距離達(dá)到最小。綜上所述，建立優(yōu)化分組的規(guī)劃模型如下： (4)以上規(guī)劃模型可以用LINGO求解，編寫程序如下：MODEL:SETS: ZHIJU/1.16/: P,Q; GROUP/1.3/:L,M,YJ,YD; FL( ZHIJU, GROUP): X; LINKS(ZHIJU,ZHIJU)|&2#GT#&1:C;ENDSETSDATA: P=10,15,6,9,13,6,11,4,13,17,11,2,11,21,13,14;Q=9,14,5

28、,10,9,10,13,9,15,9,6,7,13,15,10,16;C=31 27 38 51 58 71 67 57 47 52 48 21 41 52 61 19 33 27 32 45 64 53 47 61 57 52 48 56 63 14 27 34 47 49 39 29 42 38 38 29 38 44 13 20 33 35 25 15 33 32 32 15 24 30 9 21 37 26 26 43 45 45 28 29 38 13 32 32 35 47 52 52 35 33 42 19 30 39 50 65 65 48 44 40 11 20 31 54

29、61 34 25 21 10 20 43 51 24 14 13 18 36 41 14 9 18 23 46 25 14 23 27 22 33 42 39 48 57 11 20 9;ENDDATAFOR( FL : BIN( X); FOR(ZHIJU(I): SUM(GROUP(K): X(I,K) = 1);FOR(GROUP(K):M(K)=SUM(ZHIJU(I):X(I,K);FOR(GROUP:M=3);FOR(GROUP(K):YJ(K)=SUM(ZHIJU(I):X(I,K)*P(I);FOR(GROUP(K):YD(K)=SUM(ZHIJU(I):X(I,K)*Q(I)

30、;FOR(GROUP:YJ=65); FOR(GROUP:YD=65);FOR(GROUP(K):L(K)=SUM(LINKS(I,J):C(I,J)*X(I,K)*X(J,K);MIN=SUM(GROUP:L/M);END運(yùn)行以上程序，得到結(jié)果如下：第1組：2,3,4,5,6,7，總里程387km，總郵件60,61。第2組：1,11,12,13,14，總里程344km，總郵件55,50。第3組：8,9,10,15,16，總里程150km，總郵件61,59。以上分組可以作為規(guī)劃郵車路線的參考。四、問(wèn)題1的模型1組內(nèi)路徑優(yōu)化模型雖然郵路并不限定是環(huán)形郵路，可以是輻射形或混合形，對(duì)于少數(shù)比較孤立的

31、支局，也許只能去了以后再原路返回（根據(jù)具體情況具體分析），但是，因?yàn)榫嚯x矩陣中兩點(diǎn)之間的距離取最短路，若兩點(diǎn)之間沒(méi)有直接的通路，該兩點(diǎn)之間的距離不表示成無(wú)窮大，而是取最短路，故本題的郵政網(wǎng)絡(luò)可以看成是一個(gè)完全圖（即任意一對(duì)頂點(diǎn)都有一條邊相連），于是，形式上的環(huán)形路線實(shí)際上有可能帶有輻射形，個(gè)別點(diǎn)有可能不止經(jīng)過(guò)一次。假如已經(jīng)把支局分了3組，每一輛郵車負(fù)責(zé)一個(gè)組，則余下的問(wèn)題是規(guī)劃郵車行駛路線，從縣局出發(fā)，逐次行進(jìn)到達(dá)一個(gè)一個(gè)支局，每個(gè)支局都到一次且僅需一次，最后回到縣局，整個(gè)旅程是一個(gè)回路（圈），合理安排行駛路線，使總里程最短，這類似于網(wǎng)絡(luò)優(yōu)化中的旅行商（TSP）問(wèn)題，但是附加了額外的約束條件。

32、可以參考一些解決TSP問(wèn)題的方法求解。我們另辟途徑，把該問(wèn)題轉(zhuǎn)換成以縣局為起點(diǎn)和終點(diǎn)，對(duì)組內(nèi)支局優(yōu)化排序，合理安排裝卸點(diǎn)的順序，使行駛總里程最短的規(guī)劃問(wèn)題。郵車行走路線分成m+1個(gè)步驟，第一步從縣局出發(fā)到某個(gè)支局，該支局即排在第一位，第二步從該支局出發(fā)到另一個(gè)支局（這個(gè)支局排在第二位），依次類推，直至第m步到達(dá)組內(nèi)最后一個(gè)支局，然后第m+1步從最后一個(gè)支局返回縣局。行駛路線不同（即支局的排序不同），全程的總路程也不同，總路程最小的排序就是郵車行進(jìn)的最佳路線，即我們要尋找的最優(yōu)解。引入0-1型決策變量Xnj，下標(biāo)n表示郵車行走的步數(shù)，下標(biāo)j表示到達(dá)哪一個(gè)支局，表示郵車第n個(gè)目標(biāo)（裝卸點(diǎn)）是支局j

33、，表示否。用Cij表示支局i與支局j之間的最短路。約束條件有以下4條：(1) 每一步到達(dá)一個(gè)支局，即。(2) 每一個(gè)支局必須到一次且只需一次，即。必須分一次，且只能分到一組。(3) 在郵車行進(jìn)的任何路段上，裝載的郵件不超過(guò)65袋。(4) 行車時(shí)間不超過(guò)6小時(shí)（360分鐘），若行駛總里程為L(zhǎng)，在m個(gè)支局進(jìn)行裝卸，則行車時(shí)間為小時(shí)（2L分鐘），卸裝郵件用時(shí)5m分鐘，于是該郵車的時(shí)間約束為：。設(shè)寄達(dá)組內(nèi)各支局的郵件量為Pj，各支局收寄的郵件量為Qj，則郵車從縣局出發(fā)時(shí)的郵件總量為，達(dá)到第一個(gè)支局以后，卸下袋，裝上袋，從該支局出發(fā)時(shí)的裝載量為。由于m個(gè)X1j中實(shí)際只有一個(gè)等于1（其余m-1個(gè)都等于0）

34、，所以計(jì)算式中雖然有求和表達(dá)式，但是實(shí)際上裝卸的只是郵車所到達(dá)支局計(jì)劃內(nèi)應(yīng)該卸和裝的郵件，依此類推，從第n個(gè)支局出發(fā)時(shí)的裝載量的遞推關(guān)系為。從最后一個(gè)支局出發(fā)返回縣局的路上，郵車的裝載量變?yōu)?，綜上所述，各段路程上郵車裝載量是變化的，計(jì)算公式為： (5)限制運(yùn)載量始終不超過(guò)65袋，即。在郵車從一個(gè)點(diǎn)到另一個(gè)點(diǎn)的途中，若裝載量為Wj（單位：袋），該段路程長(zhǎng)度為L(zhǎng)j（單位：km），則題目定義空車率為，由空車引起的損失費(fèi)為，與行駛里程成正比。目標(biāo)函數(shù)可以取兩種：(1) 總路程最??；(2) 空車損失最小。由于空車損失與行駛里程成正比，所以優(yōu)化的最基本目標(biāo)是優(yōu)化到達(dá)各支局的先后次序使行駛總里程最小。首先要

35、根據(jù)決策變量的0-1值，計(jì)算出郵車從一個(gè)支局到另一個(gè)支局所走過(guò)的路程，假設(shè)在第n步郵車達(dá)到支局i，在第n+1步達(dá)到支局j，即和同時(shí)等于1，則走過(guò)的里程為，式中Cij是支局之間的最短路距離矩陣。用表示縣局到各支局的最短路距離，則郵車從縣局出發(fā)到第一個(gè)點(diǎn)的行駛里程為，從第一個(gè)裝卸點(diǎn)到最后一個(gè)裝卸點(diǎn)（共有m-1段）行駛的總里程為，從最后一個(gè)點(diǎn)返回縣局的行駛里程為。綜上所述，以總里程最短作為目標(biāo)函數(shù)，當(dāng)總路程最短時(shí)，自然行車時(shí)間也是最短，求出目標(biāo)函數(shù)的最小值以后就可以判斷時(shí)間約束條件是否能夠得到滿足，故模型中暫時(shí)不用考慮時(shí)間約束。由此建立如下數(shù)學(xué)模型： (6)式中裝載量Wi由(5)式來(lái)計(jì)算。以上規(guī)劃可

36、以用LINGO來(lái)求解，對(duì)于第一組（支局2,3,4,5,6,7），編寫程序如下：MODEL:SETS: STATION/2,3,4,5,6,7/: JL,P,Q; ORDER/1.6/:W; LINE( ORDER, STATION): X; LINKS(STATION,STATION):C;ENDSETSDATA: JL=36,17,11,24,31,44; P=15,6,9,13,6,11; Q=14,5,10,9,10,13; C=0,19,33,27,32,4519,0,14,27,34,4733,14,0,13,20,3327,27,13,0,9,2132,34,20,9,0,1345

37、,47,33,21,13,0;ENDDATAFOR( LINE : BIN( X);M=SIZE(STATION); FOR(STATION(I): SUM(ORDER(N): X(N,I) = 1);FOR(ORDER(N):SUM(STATION(I):X(N,I)=1);W0=SUM(STATION:P);W(1)=W0-SUM(STATION(J):(P(J)-Q(J)*X(1,J);FOR(ORDER(N)|N#GE#2:W(N)=W(N-1)-SUM(STATION(J):(P(J)-Q(J)*X(N,J);FOR(ORDER(N):W(N)=65);L=SUM(STATION(I

38、):X(1,I)*JL(I)+X(6,I)*JL(I);L1=SUM(ORDER(N)|N#LT#M:SUM(LINKS(I,J):C(I,J)*X(N,I)*X(N+1,J);MIN=L+L1;END運(yùn)行以上程序，求得最優(yōu)解（最短總路徑）為126km，最優(yōu)行駛路線依次為縣局457623縣局，共經(jīng)過(guò)了7個(gè)路段，在各路段上裝載的郵件量依次為60,61,57,59,63,62,61袋。用同樣方法，對(duì)程序稍做改動(dòng)，可以求得第二組（支局1,11,12,13,14）的最優(yōu)解為141km，最優(yōu)行駛路線依次為縣局113121114縣局，共經(jīng)過(guò)了6個(gè)路段，在各路段上裝載的郵件量依次為55,54,56,61,5

39、6,50袋。第三組（支局8,9,10,15,16）的最優(yōu)解為98km，最優(yōu)行駛路線依次為縣局10981615縣局，共經(jīng)過(guò)了6個(gè)路段，在各路段上裝載的郵件量依次為61,53,55,60,62,59袋。以上三組中第二組的行駛里程最長(zhǎng)，為141km，需用時(shí)282分鐘，加上卸裝用時(shí)25分鐘，合計(jì)用時(shí)307分鐘不超過(guò)360分鐘，滿足約束條件。2關(guān)于空車率損失的討論在求出各段路程上的裝載量Wj以后，空車率為，由空車率而減少收入為。從縣局出發(fā)到組內(nèi)每一個(gè)支局卸裝以后再回到縣局，整個(gè)旅程分成m+1個(gè)段落，各段裝載量Wj以及長(zhǎng)度Lj不同，分段計(jì)算各段的空車率損失，目標(biāo)函數(shù)設(shè)為全程累計(jì)因空車率而減少的收入達(dá)到最小

40、，此時(shí)約束條件必須考慮時(shí)間約束，建立優(yōu)化模型如下： (7)就第一組6個(gè)支局（2,3,4,5,6,7），編寫LINGO程序如下：MODEL:SETS: STATION/2,3,4,5,6,7/: JL,P,Q; ORDER/1.6/:L,W,U; LINE( ORDER, STATION): X; LINKS(STATION,STATION):C;ENDSETSDATA: JL=36,17,11,24,31,44; P=15,6,9,13,6,11; Q=14,5,10,9,10,13; C=0,19,33,27,32,45 19,0,14,27,34,47 33,14,0,13,20,33 2

41、7,27,13,0,9,21 32,34,20,9,0,13 45,47,33,21,13,0;ENDDATAFOR( LINE : BIN( X);M=SIZE(STATION); FOR(STATION(I): SUM(ORDER(N): X(N,I) = 1);FOR(ORDER(N):SUM(STATION(I):X(N,I)=1);W0=SUM(STATION:P);U0=1-W0/65;W(1)=W0-SUM(STATION(J):(P(J)-Q(J)*X(1,J);FOR(ORDER(N)|N#GE#2:W(N)=W(N-1)-SUM(STATION(J):(P(J)-Q(J)*X(N,J);FOR(ORDER(N):W(N)=65);FOR(ORDER(N):U(N)=1-W(N)/65);L0=SUM(STATION(I):X(1,I)*JL(I);FOR(ORDER(N)|N#LT#M:L(N)=SUM(LINKS(I,J):C(I,J)*X(N,I)*X(N+1,J);L(M)=SUM(STATION(I):X(M,I)*JL(I);Z=SUM(ORDER(N):U(N)*L(N);S=L0+SUM(O