全國數(shù)學(xué)建模大賽試題-乘用車物流運(yùn)輸計劃問題

#式(55)~(60)為乘用車供需約束，表示經(jīng)過該點(diǎn)的轎運(yùn)車所運(yùn)載的乘用車數(shù)量大于該點(diǎn)乘用車的需求量。需要說明的是，式(48)原則上應(yīng)為等式約束，由于前兩階段優(yōu)化模型為不考慮線路情況下得到的轎用車使用量和裝載情況，本文假設(shè)第三階段模型不考慮繞行情況，因而前兩階段的最優(yōu)可行解實(shí)際上是第三階段可行解的下限解，故本模型引入松弛變量H，將等式約束(48)轉(zhuǎn)化為如下不等式約束：1囪1囪X+3藝x13+_，乙X+33x13300+_，乙X+乙乙X+2 1DDijDDi2 1DCijDCi2 1DBijDBii=1j=2i=1i=1j=2i=1i=1j=2i=11.300xX+33x13+—.乙X+33x13300+—，乙X+33x<c+口2 1DAijDAi2 1DEijDEi2 1DAEjDAEi sumi=1j=2i=1i=1j=2i=1i=1j=2i=1(62)式中：H為大于0的整數(shù)變量。引入松弛變量簡化分析后，本文提出以下兩種求解方法：方法一：方法一的首要目標(biāo)在于最小化轎運(yùn)車總數(shù)量，即在松弛變量H盡可能小的條件下，最小化總行駛里程。方法二：由于方法一中在松弛變量H很小(例如四=1)的情況下，可行的解空間非常有限，尋找最優(yōu)里程更為困難，較難得到最優(yōu)解，下面提出一種局部整數(shù)-分散連續(xù)的逐步優(yōu)化方法?？紤]到相比于離散變量，連續(xù)變量的優(yōu)化問題更易于求解［7］，本文的方法二考慮將離散變量連續(xù)化。首先，將線路1各型轎運(yùn)車上下層每列各種方案出現(xiàn)的次數(shù)設(shè)為整型變量，其余線路均為連續(xù)變量，求得線路1各型轎運(yùn)車上下層每列的方案，線路1的裝載方案在之后的連續(xù)化過程中保持恒定；接著設(shè)定線路i裝載方案次數(shù)為整型變量，線路1……同裝載為恒定不變的整數(shù)，線路i+1……6裝載方案為連續(xù)變量；重復(fù)該過程，直到所有線路對應(yīng)各種方案的出現(xiàn)次數(shù)全部固定。顯然該方法各線路最終求得的裝載方案均為整數(shù)，在松弛變量固定的情況下，該方法對應(yīng)的裝載方案所需的里程數(shù)是可以接受的可行解。具體步驟如下：STEP1:m=1；STEP2：固定xDpi，七四的值保持不變，p=1,2,...,m-1，保持前m-1種路線各型轎運(yùn)車上下層每列各種方案笛現(xiàn)的次數(shù)不變；j/N,j/N，第m條路線各型轎運(yùn)車上下層每列各種方案出現(xiàn)的次數(shù)設(shè)為整型變量；'"\DjeR?X族eR,q=m+1,...6，后6-m條路線各型轎運(yùn)車上下層每列各種方案出現(xiàn)的次數(shù)設(shè)為連續(xù)變量;STEP3:將上述變量代入第三階段優(yōu)化模型進(jìn)行求解；STEP4：IFm<6，則m=m+1，轉(zhuǎn)至STEP2；ELSE結(jié)束程序，輸出結(jié)果。計算結(jié)果利用LINGO軟件實(shí)現(xiàn)上述啟發(fā)式-淘汰搜索三階段優(yōu)化模型。第一、二階段得到的最優(yōu)解為搜索空間內(nèi)的全局最優(yōu)解，對于第三階段優(yōu)化模型，由于求解規(guī)模過于龐大，加上松弛變量后，仍然很難獲得全局最優(yōu)解，因此本模型通過第三階段優(yōu)化得到的結(jié)果是搜索空間內(nèi)的局部最優(yōu)解。啟發(fā)式優(yōu)化過程中轎運(yùn)車使用量最小值，通過第一階段求解得到轎運(yùn)車使用量的最優(yōu)可行解為113輛，通過第二階段優(yōu)化求得2-2、1-1和1-2型轎運(yùn)車數(shù)量分別為10，90和18輛。具體各種類型的使用量如表所示。五，另一種啟發(fā)式方法這種啟發(fā)式方法的思想是通過對轎運(yùn)車、乘用車分類的辦法將問題簡化為前三問的規(guī)模，即將轎運(yùn)車、乘用車合并成3-5類，各類車輛長度之間沒有交集。每類轎運(yùn)車以該類中最短的轎運(yùn)車長度作為該類轎運(yùn)車長度，每類乘用車以該類中最長的乘用車長度作為該類乘用車長度。這時就可以按照前三問的方法和程序進(jìn)行計算機(jī)求解，花時間僅以秒計。但得到類似前三問的解答時并不全部執(zhí)行，僅執(zhí)行包含最長的乘用車、最短的轎運(yùn)車而且浪費(fèi)很小的方案，并將它們從任務(wù)總體中去除，這樣剩下的轎運(yùn)車、乘用車又形成新的問題，但由于此時各類中最長的乘用車、最短的轎運(yùn)車的運(yùn)輸任務(wù)已經(jīng)完成，故有關(guān)類的轎運(yùn)車長度、有關(guān)類的乘用車長度可能分別變大、變小。而且這樣的迭代過程中轎運(yùn)車、乘用車的總數(shù)是嚴(yán)格單調(diào)下降的，多次迭代后應(yīng)該可以找到較優(yōu)解。在給定轎運(yùn)車長度、乘用車長度后，明顯發(fā)現(xiàn)有些乘用車很容易安排，例如長度小于等于轎運(yùn)車長度的1/5或1/4或1/6減去安全間隔的，因為它們在極不利的情況下都可以自我搭配而使浪費(fèi)極小，甚至為零。當(dāng)然也會有