陳天宇　黃敏敏

【摘 要】隨著我國經(jīng)濟突飛猛進的發(fā)展，物流成為社會分工中重要的環(huán)節(jié)。物流系統(tǒng)的優(yōu)劣也影響了業(yè)務(wù)流程的運行效率及其成本。國內(nèi)某家物流公司的主要業(yè)務(wù)是從分布在全國的M個主機廠，將N種品牌商品小汽車調(diào)運到全國多個城市的4S店。文章應(yīng)用0-1規(guī)劃的思想解決了整車物流調(diào)度的優(yōu)化問題。

【關(guān)鍵詞】遺傳算法；0-1[2]規(guī)劃；Floyd算法

1.模型建立

我們假設(shè)貨車運達所有訂單后，停留在最終的目的地且不返回，因此不產(chǎn)生回途所需要的空載費用以及小汽車運載的業(yè)務(wù)費。

1.1相應(yīng)的一系列費用陳述如下

①貨車P從訂單點i到訂單點j的空載費用=貨車運輸途中因部分車位空閑而產(chǎn)生的空載運輸成本為0.2元/（公里·車位）*空載車位數(shù)量*訂單點i，j之間的距離，即為：0.2×T×d。

②小汽車訂單點i到訂單點j的業(yè)務(wù)費用=運輸商品小汽車的業(yè)務(wù)費為0.7元/（公里·輛）*從訂單點i卸下訂單后的小汽車數(shù)量（也即為貨車可運載小汽車總車位數(shù)量-空車位數(shù)量）*訂單點i，j之間的距離，即為：0.7×（Bp-Tij）×dij。

③貨車P從訂單點i到訂單點j的油耗費=油耗動力成本為0.5元/公里*訂單點i，j之間的距離，即為：0.5×d。

④貨車P從訂單點i到訂單點j的過路費=過路費成本為0.4元/公里*訂單點i，j之間的距離，即為：0.4×d。

⑤以上費用為貨車P從運單點i到j(luò)的總體費用，進行求和得到編號為P的貨車在兩訂單點之間的運營成本：W=

0.2×T+0.7×

（B

-T）+0.9×d。

⑥一輛貨車在訂單點i，j之間產(chǎn)生的總體費用，因問題一中92個訂單點的總體費用只需將其針對i、j求和即可，但考慮到貨車P不一定經(jīng)過每一個訂單點，因此我們在此引入一個0-1變量Xijp，定義。

X=1 編號為P的貨車從訂單點i行駛到j(luò)

0 編號為P的貨車不從訂單點i行駛到j(luò)

由此即可得到編號為P的貨車在兩訂單點之間的總運輸費，記為 W2：

W2=0.2

×T+0.7×

（B

-T）+0.9×d×X

⑦而從某個主機廠調(diào)度貨車來完成運輸訂單，保證在完成運輸任務(wù)的基礎(chǔ)上得到總體運輸成本為：W3=0.2

×T+0.7×

（B

-T）+0.9×d×X。

由題意有，需要我們把握在完成運輸任務(wù)的基礎(chǔ)上使得運費最少，再結(jié)合上述的費用稱述，因此我們得到目標(biāo)函數(shù)為：

min=W3=0.2

×T+0.7×

（B

-T）+0.9×d×X。

1.2約束條件，在此，我們主要考慮以下因素

①每一輛貨車所能裝載的小汽車數(shù)量有限（也即車位有限）：D×Y≤B。

②一個運力貨車運單的目的地城市的數(shù)量不超過3個：Y≤3。

③允許將不同訂單用同一貨車運輸，但是不允許將同一訂單拆分用不同貨車運輸：X×Y=1。

由上述可得，模型建立如下：

min=W3=0.2

×T+0.7×

（B

-T）+0.9×d×X。

s.t

D

×Y≤

B

Y≤3

X×

Y=1

Y=0，1

X=0，1

2.模型求解

文章解決的是一個典型的規(guī)劃問題，我們采用遺傳算法進行問題的求解。

遺傳算法[1]基本原理：長度為L的n個二進制串bi（i=1，2，…，n）組成遺傳算法的初解群，在每個串中，每個二進制位就是個體染色體的基因。

遺傳算法的步驟和意義：

（1）初始化：選擇一個群體集合bi，i=1，2，...n，這個初始的群體即問題假設(shè)解的集合。一般取n=30-160。

（2）選擇：根據(jù)適者生存原則選擇下一代的個體。在選擇時，以適應(yīng)度為選擇原則。適應(yīng)度準(zhǔn)則體現(xiàn)了適者生存，不適應(yīng)者淘汰的自然法則。給出目標(biāo)函數(shù)f，則f（bi）稱為個體bi的適應(yīng)度。為選中bi為下一代個體的次數(shù)。顯然：

1）適應(yīng)度較高的個體，繁殖下一代的數(shù)目較多。

2）適應(yīng)度較小的個體，繁殖下一代的數(shù)目較少；甚至被淘汰。

如此產(chǎn)生對環(huán)境適應(yīng)能力較強的后代。即選擇出和最優(yōu)解較接近的中間解。

（3）交叉：對于選中用于繁殖下一代的個體，隨機地選擇兩個個體的相同位置，按交叉概率P。在選中的位置實行交換。這個過程反映了隨機信息交換；目的在于產(chǎn)生新的基因組合，也即產(chǎn)生新的個體。交叉時，可實行單點交叉或多點交叉。例如有個體：S1=100101、S2=010111，選擇它們的左邊3位進行交叉操作，則有：S1=010101、S2=100111，一般而言，取值為0.25—0.75。

（4）變異：根據(jù)生物遺傳中基因變異的原理，以變異概率Pm對某些個體的某些位執(zhí)行變異。在變異時，對執(zhí)行變異的串的對應(yīng)位求反，即把1變?yōu)?，把0變?yōu)?。變異概率Pm與生物變異極小的情況一致，所以，Pm的取值較小，一般取0.01-0.2。例如有個體S=101011。對其的第1，4位置的基因進行變異，則有S'=001111。

（5）全局最優(yōu)收斂：最優(yōu)個體的適應(yīng)度達到給定的閾值，或者最優(yōu)個體適應(yīng)度和群體適應(yīng)度不再上升時，則算法迭代過程收斂、算法結(jié)束。否則，用經(jīng)過選擇、交叉、變異所得到的新一代群體取代上一代群體，并返回到第2步繼續(xù)循環(huán)。

對原始數(shù)據(jù)進行了預(yù)處理之后利用遺傳算法，應(yīng)用C語言得到結(jié)果如下：

圖一 求解結(jié)果地圖呈現(xiàn)

3.結(jié)果分析

根據(jù)本文求解，我們可以應(yīng)用到各種物流的具（下轉(zhuǎn)第215頁）（上接第186頁）體分配工作方面，可以在理論上幫助降低成本，給出較優(yōu)的規(guī)劃方案。 [科]

【參考文獻】

[1]王赟，李仁旺，倪夏靜，陳昆昌，莫燦林.基于遺傳算法的服裝配送路徑優(yōu)化策略[J].浙江理工大學(xué)學(xué)報，杭州：2013.03.

[2]殷銘，張興華，戴先忠.基于MATLAB的遺傳算法.南京東南大學(xué)自動控制系（210096）.計算機應(yīng)用.