李方方

摘 要：貨運(yùn)公司在運(yùn)輸貨物時(shí)，由于貨物大小、重量不一樣，為了降低貨物損失，必須按照一定順序擺放；而位于路線不同點(diǎn)上的公司對(duì)貨物種類、數(shù)量的需求有差異。為了實(shí)現(xiàn)貨運(yùn)公司的利潤(rùn)最大化以及客戶需求被很好的滿足，必須合理安排車輛以及車上所載貨物，爭(zhēng)取用最少車輛滿足客戶的需求。本文使用貪心算法，利用其最優(yōu)子結(jié)構(gòu)和貪心選擇構(gòu)造出貪心解，并且該貪心解是足以解決本問題，從而得出動(dòng)態(tài)規(guī)劃的最優(yōu)解，最后使用啟發(fā)式策略合理分配派車方案，實(shí)現(xiàn)貨運(yùn)公司利潤(rùn)最大化。

關(guān)鍵詞：動(dòng)態(tài)規(guī)劃；貪心算法；啟發(fā)式算法；構(gòu)造解的結(jié)構(gòu)；最短路徑求解

1.引言

貨運(yùn)公司在運(yùn)輸貨物時(shí)，由于貨物大小、重量不一樣，為了降低貨物損失，必須按照一定順序擺放；而位于路線不同點(diǎn)上的公司對(duì)貨物種類、數(shù)量的需求有差異。為了實(shí)現(xiàn)貨運(yùn)公司的利潤(rùn)最大化以及客戶需求被很好的滿足，必須合理安排車輛以及車上所載貨物，爭(zhēng)取用最少車輛滿足客戶的需求和到達(dá)相應(yīng)客戶點(diǎn)時(shí)卸貨的方便。

本文通過使用貪心算法，利用其最優(yōu)子結(jié)構(gòu)和貪心選擇構(gòu)造出貪心解，并且該貪心解是足以解決本問題，從而得出動(dòng)態(tài)規(guī)劃的最優(yōu)解，最后使用啟發(fā)式策略合理分配派車方案。

2.實(shí)例研究

2.1 問題描述

某地區(qū)有8個(gè)公司，某天某貨運(yùn)公司要派車將各公司所需的三種原材料A，B，C 從某港口分別運(yùn)往這些公司。路線是唯一的雙向道路。貨運(yùn)公司現(xiàn)有一種載重 6 噸的運(yùn)輸車，派車有固定成本20元/輛，從港口出車有固定成本為10元/車次。每輛車平均需要用 15min的時(shí)間裝車，到每個(gè)公司卸車時(shí)間平均為10min，運(yùn)輸車平均速度為 60km/h，每日工作不超過8h。車載重運(yùn)費(fèi) 1.8 元/噸公里，空載費(fèi)用 0.4 元/公里。一個(gè)單位的原材料 A，B，C分別毛重4t、3t、1t，原材料不能拆分，為了安全，大小件同車時(shí)必須小件在上，大件在下。卸貨時(shí)必須先卸小件，而且不允許卸下來的材料再裝上車，另外必須要滿足各公司當(dāng)天的需求量，需求量見下圖。 在這些給定的條件下，求最佳的調(diào)度方案，使得成本最小。

2.2 問題假設(shè)

每輛車裝車時(shí)彼此獨(dú)立，不需等待；每輛車進(jìn)出港口彼此獨(dú)立，不會(huì)堵塞；運(yùn)輸?shù)缆烦鋾常欢萝?；車行駛過程不發(fā)生突發(fā)事件；每家公司對(duì)貨物種類和數(shù)量需求無(wú)時(shí)間上優(yōu)先級(jí)，即當(dāng)天滿足即可；車輛不調(diào)頭。

2.3優(yōu)化方案及方法

2.3.1符號(hào)說明：W（i，j）：第i次送貨到第j公司貨物的重量；D（i，j）：第i次送貨到第j公司貨物的載重路徑；N：出車次數(shù)；E（i，j）：第i次送貨到第j公司的后產(chǎn)生的空載費(fèi)用；A（i，j，k）：一輛車上載i單位A，j單位B，k單位C

2.3.2 模型的建立

（1）描述動(dòng)態(tài)規(guī)劃解的算法：費(fèi)用組成由載重費(fèi)用、空載費(fèi)用、港口出車費(fèi)用和固定出車費(fèi)用組成，具體計(jì)算公式如下：1）固定出車費(fèi)：6*20=120元；2）港口出車費(fèi)：10*N；3）載重費(fèi)用：1.8*W（i，j）*D（i，j），表示第i次送貨到j(luò)公司載重費(fèi)用，其總費(fèi)用可在EXCEL里實(shí)現(xiàn)。4）空載費(fèi)用：0.4*（60-D（i，j）），表示第i次送貨到j(luò)公司后產(chǎn)生空載費(fèi)用；其總費(fèi)用可在EXCEL里實(shí)現(xiàn)；

（2）最優(yōu)子結(jié)構(gòu)描述：1）每次派車都應(yīng)該充分發(fā)揮其運(yùn)載能力；2）、每次派車的貨物都盡可能的運(yùn)往一個(gè)公司；3）、載重的路程應(yīng)盡量按就近原則；4）、每次派車的貨物種類或數(shù)量應(yīng)盡量滿足大部分的公司的貨物種類和數(shù)量 需求。

（3）貪心選擇：因?yàn)楣镜奈恢煤退柝浳锕潭?，影響其費(fèi)用的僅為該公司的車次和運(yùn)載方向；我們可以貪心的選擇在最優(yōu)子結(jié)構(gòu)條件下，是該家公司所需車次最少，并合理選擇其出車方向。在運(yùn)輸車滿載的情況下有以下方案：A（1，0，2），A（0，0，6），A（0，2，0），A（0，1，3），所特別的是8家公司的B貨物需求為18單位，恰可通過派車方案A（0，2，0）9次完成；下面則只討論A和C貨物的，A的需求為18單位C需求為26，若只用A（1，0，2）則C超出，則可以考慮（1，0，1）（1，0，0）（0，0，3）（0，0，2）（0，01），使每家公司可以用最少車次完成所需。下面是通過貪心選擇的A和C的派車方案如下表一：

其中的每車次運(yùn)輸方向按載貨路程的就近原則，我們通過表格很容易看出最優(yōu)選擇之一總是貪心的選擇，那么貪心選擇是安全的，可以最終得出最優(yōu)的貪心解。

（4）合并最優(yōu)子結(jié)構(gòu)和貪心選擇：通過表一我們可以得出5、6、7公司分別需要一輛車次來運(yùn)2、3、1單位的的C，我們可以將以一車次的A（0，2，0）與之合并產(chǎn)生兩次的A（0，1，3）則可以減少車次，最終得出A、B、C的最終運(yùn)輸方案如下（表2）：

（5）求最后貪心解：建立EXCEL表格，利用啟發(fā)式算法合理安排派車方案，算出貪心解，即最后可以替代的動(dòng)態(tài)規(guī)劃解

3.結(jié)束語(yǔ)

對(duì)于本案例的解決，采用了貪心解直接給出了動(dòng)態(tài)規(guī)劃解。但最后給出的是貪心解的結(jié)構(gòu)，從而得出的優(yōu)化解只是在滿足最優(yōu)值的條件下一種解的結(jié)構(gòu)，無(wú)法給出符合最優(yōu)值的全部解的結(jié)構(gòu)。在不考慮解的結(jié)構(gòu)約束的情況下，是可取的，并不一定是最優(yōu)值的解，但確很逼近該最優(yōu)解，且這種貪心解的結(jié)構(gòu)是合理的。（作者單位：南京農(nóng)業(yè)大學(xué)）

參考文獻(xiàn)

[1] 算法導(dǎo)論，（美）Thomas.Cormen Charles E.Leiseron Ronald L.Rivest Clifford Stein 著，潘金貴 顧鐵成 李成法 譯 機(jī)械工業(yè)出版社。

[2] 百度百科