全國數學建模大賽試題-乘用車物流運輸計劃問題

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