徐西嘯

摘要計(jì)算機(jī)的應(yīng)用觸及到了生活的各個(gè)方面，它的優(yōu)點(diǎn)之一就在于強(qiáng)大的計(jì)算處理能力上，這也正是物流領(lǐng)域配送路線(xiàn)的問(wèn)題所需要的。如何選擇最佳路線(xiàn)，如何節(jié)約物流運(yùn)輸成本，即選擇配送的最短路線(xiàn)，我們可以通過(guò)貪心算法和動(dòng)態(tài)規(guī)劃算法來(lái)做決定。本文對(duì)于中國(guó)現(xiàn)今發(fā)展蓬勃的電子商務(wù)的線(xiàn)下運(yùn)輸問(wèn)題提出了見(jiàn)解，以一個(gè)簡(jiǎn)化的模型介紹了貪心算法以及動(dòng)態(tài)規(guī)劃法的應(yīng)用，為線(xiàn)下運(yùn)輸問(wèn)題提出了解決方案，有著十分重要的現(xiàn)實(shí)意義。

關(guān)鍵詞物流問(wèn)題；最短路徑；最小時(shí)間；貪心算法；動(dòng)態(tài)規(guī)劃

計(jì)算機(jī)自誕生以來(lái)，發(fā)展迅速，在社會(huì)中的各個(gè)領(lǐng)域都得到了廣泛的應(yīng)用。使用計(jì)算機(jī)快速處理問(wèn)題成為當(dāng)今社會(huì)發(fā)展的需要。筆者運(yùn)用計(jì)算機(jī)知識(shí)為現(xiàn)實(shí)問(wèn)題提供一些意見(jiàn)和建議。筆者在今年“雙十一”期間親身經(jīng)歷了爆倉(cāng)問(wèn)題，發(fā)現(xiàn)物體配送效率低下，“雙十一”期間物流速度極慢，形式十分嚴(yán)峻。據(jù)官方所提供的數(shù)據(jù)，買(mǎi)家每秒創(chuàng)建訂單數(shù)額達(dá)到17.5萬(wàn)筆，有些貨物甚至預(yù)計(jì)需要1個(gè)月左右的時(shí)間才能配送完畢。

對(duì)于現(xiàn)今的物流配送，人們大多選擇第三方物流。當(dāng)貨物運(yùn)送到某地區(qū)時(shí)，物流公司的將貨物囤積在一處，再通過(guò)快遞員將快遞送往千家萬(wàn)戶(hù)。筆者在此希望對(duì)快遞員的派送路線(xiàn)進(jìn)行合理化選擇，以最短路程，最小時(shí)間完成貨物的配送。

以城市中的快遞配送為例，現(xiàn)簡(jiǎn)化模型如下：快遞員在某地區(qū)配送快遞，快遞公司（貨物囤積地）位于0點(diǎn)，快遞員需要派送6份快遞，分別送往A，B，C，D，E，F(xiàn)六個(gè)地點(diǎn)，每?jī)蓚€(gè)地點(diǎn)之間的距離已標(biāo)出，快遞員如何快速規(guī)劃路線(xiàn)，以最短路徑、最小時(shí)間完成快遞的配送，這不僅可以節(jié)約勞動(dòng)力提高工作效率，也會(huì)使網(wǎng)購(gòu)用戶(hù)收貨速度更快。

在具體代碼實(shí)現(xiàn)中配送需求地映射為編號(hào)：0-0，A-1，B-2，C-3，D-4，E-5，F(xiàn)-6：

城市之間的距離用二維數(shù)組來(lái)表示，記為D[i][j]，如：D[0][1]表示0與A之間的距離，于是D[0][1]=6；設(shè)置flag[][]，初始為0，表示此變量未被訪(fǎng)問(wèn)（配送需求地未到達(dá)過(guò)），若被訪(fǎng)問(wèn)（已到達(dá)過(guò)配送完畢）則修改為1。

本文中筆者選擇貪心算法、動(dòng)態(tài)規(guī)劃法來(lái)解決這一實(shí)際問(wèn)題。

1貪心算法

貪心算法（Greedy algorithm）是一種對(duì)某些動(dòng)態(tài)規(guī)劃中求優(yōu)秀解的簡(jiǎn)單、迅速的算法，以當(dāng)前情況為基礎(chǔ)根據(jù)某個(gè)標(biāo)準(zhǔn)作最優(yōu)選擇，而不考慮整體情況，省去大量時(shí)間。

貪心算法在解決問(wèn)題的策略上缺點(diǎn)是目光短淺，只根據(jù)當(dāng)前已有的信息就做出選擇，而且一旦做出了選擇，不管將來(lái)有什么結(jié)果，這個(gè)選擇都不會(huì)改變。換言之，貪心算法并不是從整體最優(yōu)考慮，它所做出的選擇只是在某種意義上的局部最優(yōu)。這種局部最優(yōu)選擇并不總能獲得整體最優(yōu)解，但通常能獲得近似最優(yōu)解。但由于其處理問(wèn)題簡(jiǎn)單高效、節(jié)省空間，非常適合實(shí)際問(wèn)題的解決。

現(xiàn)在我們通過(guò)來(lái)解決這一問(wèn)題，采用最近鄰點(diǎn)策略：從某地點(diǎn)（初始為快遞公司，即0點(diǎn)）出發(fā)，每次在沒(méi)有到過(guò)的中選擇距離當(dāng)前所在地中最近的一個(gè)，直到經(jīng)過(guò)了所有的配送需求地，完成了所有配送任務(wù)，最后回到快遞公司，即0點(diǎn)。

貪心算法具體求解流程如下：1）了解要求送達(dá)地點(diǎn)的的數(shù)量與各地點(diǎn)之間的距離。2）重復(fù)以下兩步直至已全部送達(dá)：（1）循環(huán)遍歷找到與當(dāng)前出發(fā)地點(diǎn)最近的未到達(dá)過(guò)的配送需求地；（2）以當(dāng)前找到的（最近一次找到的）送達(dá)地點(diǎn)為出發(fā)地點(diǎn)，重復(fù)步驟（1）。3）回到出發(fā)地點(diǎn)。

在本題中貪心算法選擇路線(xiàn)經(jīng)過(guò)如下：快遞員從0點(diǎn)選擇較近的A點(diǎn)作為目的地。到達(dá)后選擇距離當(dāng)前出發(fā)點(diǎn)A較近的點(diǎn)，0點(diǎn)當(dāng)前已訪(fǎng)問(wèn)，選擇B點(diǎn)。而后依次按照此規(guī)則選擇配送需求點(diǎn)，當(dāng)所有快遞配送完畢返回0點(diǎn)，即快遞公司所在地。路線(xiàn)為0->AV>B->C->D>E->F->0。路程為44。

從本例中也可以看出，貪心算法簡(jiǎn)單便捷，對(duì)于問(wèn)題的解決有很大的幫助。同時(shí)我們清楚地看出，使用貪心算法只能考慮當(dāng)前的選擇，當(dāng)面對(duì)復(fù)雜的整體問(wèn)題時(shí)，貪心算法未必能給出最優(yōu)解只求出了近似最優(yōu)解。

2動(dòng)態(tài)規(guī)劃算法

動(dòng)態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質(zhì)的問(wèn)題。在這類(lèi)問(wèn)題中，可能會(huì)有許多可行解。每一個(gè)解都對(duì)應(yīng)于一個(gè)值，我們希望找到具有最優(yōu)值的解。如本問(wèn)題的簡(jiǎn)化模型有許多可以把貨物送達(dá)的可行解，但我們希望找到能實(shí)現(xiàn)最短路程最小時(shí)間的最優(yōu)解。

動(dòng)態(tài)規(guī)劃算法與分治法類(lèi)似，其基本思想也是將待求解問(wèn)題分解成若干個(gè)子問(wèn)題，先求解子問(wèn)題，然后從這些子問(wèn)題的解得到原問(wèn)題的解。與分治法不同的是，適合于用動(dòng)態(tài)規(guī)劃求解的問(wèn)題，經(jīng)分解得到子問(wèn)題往往不是互相獨(dú)立的。若用分治法來(lái)解這類(lèi)問(wèn)題，則分解得到的子問(wèn)題數(shù)目太多，有些子問(wèn)題被重復(fù)計(jì)算了很多次。

如果我們能夠保存已解決的子問(wèn)題的答案，而在需要時(shí)再找出已求得的答案，這樣就可以避免大量的重復(fù)計(jì)算，節(jié)省時(shí)間。我們可以用一個(gè)表來(lái)記錄所有已解的子問(wèn)題的答案。不管該子問(wèn)題以后是否被用到，只要它被計(jì)算過(guò)，就將其結(jié)果填入表中。

在利用動(dòng)態(tài)規(guī)劃求解的過(guò)程中值得注意的就是是否包含最優(yōu)子結(jié)構(gòu)，簡(jiǎn)單來(lái)講就是一個(gè)問(wèn)題的最優(yōu)解是不是包含著子問(wèn)題的最優(yōu)解。利用求解子問(wèn)題的最優(yōu)解最后得到整個(gè)問(wèn)題的最優(yōu)解，這是利用動(dòng)態(tài)規(guī)劃求解問(wèn)題的基本前提。

動(dòng)態(tài)規(guī)劃的求解過(guò)程主要分為如下的四步：1）描述最優(yōu)解的結(jié)構(gòu)；2）遞歸定義最優(yōu)解的值；3）按白底向上的方式計(jì)算最優(yōu)解的值；4）由計(jì)算出的結(jié)果構(gòu)造一個(gè)最優(yōu)解。

在本快遞配送問(wèn)題的簡(jiǎn)單模型中求解過(guò)程具體如下：假設(shè)從頂點(diǎn)0出發(fā)，令stM表示從頂點(diǎn)0出發(fā)經(jīng)過(guò)圖中各個(gè)頂點(diǎn)，即配送需求地一次且僅一次最后回到出發(fā)點(diǎn)的最短路徑長(zhǎng)度。

2.1描述最優(yōu)解的結(jié)構(gòu)

要使得從0（以0表示出發(fā)處0節(jié)點(diǎn)）點(diǎn)出發(fā)配送完畢回到0（以7表示返回處0節(jié)點(diǎn)，D[7][k]=D[0][k]）點(diǎn)的路程最短，令f（i）為到第i個(gè)節(jié)點(diǎn)的最短距離，則f（7）=min{D[7][1]，D17][5]，D[7][6]），用同樣的方法可以求得f（1），f（5），f（6）等。

2.2遞歸定義最優(yōu)解的值

f（i）=min（f（j）+D[i][j]），其中j表示與i邊有連接的節(jié)點(diǎn)。

2.3按自底向上的方式計(jì)算每個(gè)節(jié)點(diǎn)的最優(yōu)值

此時(shí)我們就得利用遞歸公式分別求解f（0），f（1），f（2）…f（7），這樣最終便能得到最終的解。

2.4由計(jì)算出的結(jié)果構(gòu)造一個(gè)最優(yōu)解

本模型最終解為路線(xiàn)為0-（0）>A（1）->B（2）->c（3）->D（4）->E（5）->F（6）->0（7）。路程為44。

動(dòng)態(tài)規(guī)劃算法關(guān)鍵在于解決了重復(fù)計(jì)算的問(wèn)題，大大提高了代碼運(yùn)行效率?？傮w來(lái)說(shuō)，動(dòng)態(tài)規(guī)劃算法就是一系列以空間換取時(shí)間的算法。

3結(jié)論

中國(guó)電商業(yè)發(fā)展十分迅速，但長(zhǎng)期以來(lái)，線(xiàn)下運(yùn)輸物流配送速度為人所詬病，筆者認(rèn)為應(yīng)該有著更高效的配送方式。本文主要利用貪心算法和動(dòng)態(tài)規(guī)劃算法來(lái)進(jìn)行求解，快速而準(zhǔn)確地得出流配送的近似最佳或最佳路線(xiàn)選擇，節(jié)約物流運(yùn)輸成本，提高消費(fèi)者滿(mǎn)意度，對(duì)快遞公司派發(fā)快遞的路線(xiàn)考慮有很強(qiáng)的現(xiàn)實(shí)參考意義。endprint