基于線路優(yōu)化算法的卷煙配送調(diào)度系統(tǒng)

孫壯志，鄢烈虎，要學(xué)瑋

北京煙草物流中心，北京市通州區(qū)九棵樹西路198號(hào) 101101

基于線路優(yōu)化算法的卷煙配送調(diào)度系統(tǒng)

孫壯志，鄢烈虎，要學(xué)瑋

北京煙草物流中心，北京市通州區(qū)九棵樹西路198號(hào) 101101

為研究線路優(yōu)化算法在卷煙配送中的應(yīng)用，以北京卷煙配送市場(chǎng)為背景，結(jié)合配送條件的限制，采用中心聚類、禁忌搜索、局部搜索等多種專業(yè)算法，提出了一套適應(yīng)性強(qiáng)、運(yùn)算速度快、可實(shí)施性高的解決方案。同時(shí)，通過選擇性地取用原有固定線路的數(shù)據(jù)作為最終路順的參考，結(jié)合配送車型和配送員的工作負(fù)荷，強(qiáng)化了動(dòng)態(tài)調(diào)度結(jié)果的可實(shí)施性。方案實(shí)施測(cè)試效果良好，月平均裝載率達(dá)90%以上。

線路優(yōu)化；中心聚類；禁忌搜索；局部搜索

隨著物流相關(guān)技術(shù)的蓬勃發(fā)展，物流行業(yè)正在經(jīng)歷一場(chǎng)深刻的變革。以先進(jìn)的算法輔助實(shí)現(xiàn)物流配送線路優(yōu)化是新技術(shù)應(yīng)用的一項(xiàng)重要措施。

優(yōu)化技術(shù)是一種以數(shù)學(xué)為基礎(chǔ)的，用于求解各種工程問題優(yōu)化解的應(yīng)用技術(shù)。所謂優(yōu)化算法，就是一種搜索過程或規(guī)則，它是基于某種思想和機(jī)制，通過一定的途徑或規(guī)則來得到滿足用戶要求的問題的解[1]。聚類算法是一種數(shù)據(jù)簡(jiǎn)化技術(shù)，把基于相似數(shù)據(jù)特征的變量和個(gè)案組合在一起[2]。禁忌搜索是彌補(bǔ)局部搜索先天弱點(diǎn)的一種改進(jìn)算法，局部搜索算法的先天弱點(diǎn)在于會(huì)陷入局部最優(yōu)，所以設(shè)計(jì)好的跳離局部最優(yōu)的啟發(fā)策略是設(shè)計(jì)局部搜索算法的關(guān)鍵[3]。禁忌搜索算法基本思想相當(dāng)簡(jiǎn)單，它采用一種“記憶”裝置驅(qū)使算法去探索搜索空間的新的區(qū)域[4]。我們可以記住最近被檢查過的解，它們將成為下一個(gè)解的禁忌（被禁止）。貪婪法是一種對(duì)某些求最優(yōu)解問題的更簡(jiǎn)單、更迅速的設(shè)計(jì)技術(shù)，其特點(diǎn)是一步一步地按策略進(jìn)行，常以以前情況為基礎(chǔ)根據(jù)某個(gè)優(yōu)化測(cè)度作最優(yōu)選擇，而不是考慮各種可能的整體情況[5]。

論文以設(shè)計(jì)和開發(fā)一個(gè)以線路優(yōu)化算法為基礎(chǔ)的卷煙配送線路調(diào)度系統(tǒng)為目標(biāo)，根據(jù)需求分析，進(jìn)行線路優(yōu)化算法的選擇，最終期望完成一個(gè)線路調(diào)度系統(tǒng)，并對(duì)結(jié)果進(jìn)行理論驗(yàn)證。

1 系統(tǒng)需求分析

1.1 實(shí)際業(yè)務(wù)需求情況

每天從訪銷中心接收訪銷數(shù)據(jù)，包括訂單日期、零售戶信息、訂貨量。根據(jù)配送實(shí)際情況，需設(shè)計(jì)一套算法，根據(jù)北京市地理情況、配送車輛最大裝載量限制、考慮配送員熟悉度，在盡量短的時(shí)間內(nèi)對(duì)當(dāng)日訂單進(jìn)行配送線路優(yōu)化，為每位配送人員提供相對(duì)合理、科學(xué)的配送線路。同時(shí)要求計(jì)算結(jié)果線路可人工調(diào)整，并使月平均裝載率達(dá)到90%以上。

1.2 基礎(chǔ)數(shù)據(jù)需求

根據(jù)實(shí)際業(yè)務(wù)需求，調(diào)度系統(tǒng)需要以下6方面的基礎(chǔ)數(shù)據(jù)支撐：

1)城市道路基礎(chǔ)信息：北京市道路網(wǎng)絡(luò)圖，即GIS地圖；

2)零售戶信息：零售戶地理坐標(biāo)點(diǎn)，并將其投影在北京市道路網(wǎng)絡(luò)圖上；訂貨量；送貨車型限制；

3)車輛基礎(chǔ)信息：車型、最大裝載量；

4)人員信息：司機(jī)以及配送員的基礎(chǔ)信息；他們?cè)谇耙欢螘r(shí)間的歷史工作負(fù)荷；

5)送貨區(qū)域信息：所屬區(qū)域組；是否進(jìn)行融合；區(qū)域內(nèi)線路最大送貨時(shí)間；區(qū)域內(nèi)可用配送資源（指司機(jī)、配送員及車輛合成一個(gè)組合關(guān)系）；

6)原送貨線路信息：客戶原屬線路信息。

1.3 返回結(jié)果需求

根據(jù)業(yè)務(wù)需求，在計(jì)算結(jié)果時(shí)需要返回的信息有以下8類：每條線路的司機(jī)、配送員、送貨車輛、包含的客戶以及其送貨順序、預(yù)計(jì)里程、預(yù)計(jì)送貨時(shí)間、送貨量、裝載率。

2 系統(tǒng)設(shè)計(jì)

2.1 整體設(shè)計(jì)

動(dòng)態(tài)線路調(diào)度包含客戶區(qū)域分配、區(qū)域識(shí)別、線路生成與區(qū)域間調(diào)整三個(gè)步驟。其中線路生成以及區(qū)域間調(diào)整被分成2條獨(dú)立的路徑，一條采用以中心聚類為核心的算法進(jìn)行計(jì)算，另一條是采用線路串接的方式進(jìn)行計(jì)算，如圖1所示。

圖1 整體設(shè)計(jì)思路Fig.1 Integrated design map

2.2 詳細(xì)設(shè)計(jì)

2.2.1 客戶區(qū)域分配

獲取營(yíng)銷訂單后，根據(jù)系統(tǒng)內(nèi)劃定的區(qū)域，將訂單分拆到各個(gè)區(qū)域內(nèi)進(jìn)行運(yùn)算。

2.2.2 區(qū)域識(shí)別

線路優(yōu)化針對(duì)不同的客戶分布情況，采用不同的算法加以應(yīng)對(duì)。

如果區(qū)塊內(nèi)的客戶基本上是按照訪銷周期訂貨的，都是捆綁得比較好的一整條的線路，那么采用配送人員比較認(rèn)可、熟悉度較高的線路進(jìn)行串接，將多條線路頭尾相接串聯(lián)到一起,切割拆分生成多個(gè)車次。

如果區(qū)塊內(nèi)的客戶是隨機(jī)訪問的，七零八落地分布在各個(gè)線路中，那么采用中心聚類的算法加以聚類分割，生成多條線路。

分類判定算法是分析整線路的客戶所占的比例。根據(jù)區(qū)塊內(nèi)已有的原線路，將客戶分配到各條原線路上去，生成多個(gè)客戶序列。如果序列內(nèi)客戶數(shù)最多的8個(gè)客戶序列的總客戶數(shù)占全部客戶數(shù)的80%以上，就說明該區(qū)域中被綁定在原有固定線路中的客戶占所有客戶的大多數(shù)。

2.2.3 線路生成與區(qū)域間調(diào)整

2.2.3.1 客戶群生成

在每個(gè)區(qū)塊中，再次根據(jù)區(qū)塊內(nèi)已有的原線路，將客戶分配到各條原線路上去（根據(jù)訂單情況不同，有可能出現(xiàn)大部分客戶都集中于某幾條線路，也有可能出現(xiàn)客戶分散于區(qū)塊內(nèi)的所有原線路）。分析各條原線路，倘若發(fā)現(xiàn)其客戶序列中，前后兩戶不是相對(duì)接近的，就進(jìn)行分拆，最終形成若干個(gè)連續(xù)并互相靠近的客戶群。（有可能因?yàn)榭蛻舴稚⒌年P(guān)系，大多數(shù)客戶組都只包含了單個(gè)客戶）。

2.2.3.2 線路裝填

根據(jù)前面區(qū)域分析的結(jié)果，用不同的算法（聚類分析或者線路串接），對(duì)生成的客戶群進(jìn)行合并以及拆分，將彼此靠近的客戶群根據(jù)車輛的容量，以及最大送貨時(shí)間，合并為一條線路。歸并的同時(shí)，允許對(duì)那些“整個(gè)加進(jìn)去太多，不加又太少”的客戶群進(jìn)行分拆，以最大程度提高裝載率。根據(jù)當(dāng)前客戶的情況選擇合適的車型進(jìn)行配送，避免無法配送到戶的情況。同時(shí)在選擇出車車輛時(shí)，對(duì)司機(jī)的工作負(fù)荷進(jìn)行一定的均衡（因?yàn)檐囕v和司機(jī)是綁定的），確保各人的勞動(dòng)時(shí)間不會(huì)差異太大。

（1）聚類分析算法

其基本策略是先對(duì)每個(gè)簇任意選擇一個(gè)代表對(duì)象，剩余的對(duì)象根據(jù)其與代表對(duì)象的距離分配給最近的一個(gè)簇。然后反復(fù)利用非代表對(duì)象來代替代表對(duì)象，以改進(jìn)聚類的質(zhì)量。聚類結(jié)果的質(zhì)量用一個(gè)代價(jià)函數(shù)估算，該函數(shù)度量對(duì)象與參照對(duì)象之間的平均相異度。為了判定一個(gè)非代表對(duì)象是否是當(dāng)前一個(gè)代表對(duì)象的好的代表，對(duì)于每一個(gè)非中心對(duì)象p，需要分為四種情況考慮：① p當(dāng)前隸屬于中心點(diǎn)對(duì)象。如果被所代替，且p離一個(gè)最近，，那么p被中心分配給。② p當(dāng)前隸屬于中心點(diǎn)對(duì)象。如果被所代替，且p離最近，那么p被中心分配給。③ p當(dāng)前隸屬于中心點(diǎn)對(duì)象，。如果被代替作為一個(gè)中心點(diǎn)，且p仍離最近，那么對(duì)象的隸屬不發(fā)生變化。④ p當(dāng)前隸屬于中心點(diǎn)對(duì)象，。如果被代替作為一個(gè)中心點(diǎn)，且p離最近，那么p被重新分配給。

計(jì)算時(shí)，輸入：簇的數(shù)目k和包涵n個(gè)對(duì)象的數(shù)據(jù)庫。其中，簇就是線路，而對(duì)象就是客戶群。輸出：k個(gè)簇，使得所有對(duì)象與其最近中心點(diǎn)的相異度總和最小。

計(jì)算方法：任意選擇k個(gè)對(duì)象為初始的簇中心。指派每個(gè)剩余對(duì)象給離它最近的中心點(diǎn)所代表的簇。隨機(jī)地選擇一個(gè)非中心點(diǎn)的對(duì)象，計(jì)算用代替的總代價(jià)S，如果S＜0，那么代替，形成新的k個(gè)中心點(diǎn)的集合。直到不發(fā)生變化。本算法以裝載率盡量接近滿載為代價(jià)函數(shù)f(x)，即f(x)=|Loading Rate-1|其中Loading Rate為裝載率。如果沒裝滿送貨時(shí)間就超標(biāo)了，則代價(jià)函數(shù)f(x)改為時(shí)間上接近最大送貨時(shí)間，即f(x)=|Time-Max Time|其中Time為送貨時(shí)間，Max Time為最大送貨時(shí)間。

分割完畢后，選擇包含有計(jì)算起點(diǎn)的線路作為原始線路（此線路內(nèi)包含有多個(gè)客戶群），進(jìn)入客戶群拆分階段。由于中心聚類不可能獲得非常精密的結(jié)果，上面的原始線路很有可能會(huì)出現(xiàn)超出最大裝載量（超出最大工作時(shí)間）的情況。此時(shí)就需要對(duì)原始線路內(nèi)的客戶群進(jìn)行排序，按照順序逐個(gè)將客戶進(jìn)行裝車，直到裝不下為止。剩余的原始線路內(nèi)客戶重新組成客戶群，返還到待計(jì)算客戶中，與其他線路中的客戶群一起回爐，等待下一次計(jì)算，這樣就得到了一條線路的結(jié)果。

接下來，對(duì)剩余待計(jì)算的客戶群重新開始這一輪步驟：首先預(yù)估所需的車輛，再次取離區(qū)域中心最遠(yuǎn)的客戶群作為計(jì)算起點(diǎn)，繼續(xù)中心聚類計(jì)算，獲取原始線路后，再做客戶群拆分。如此迭代，直到只剩下2條線路為止。

（2）線路串接算法

線路串接并非簡(jiǎn)單的把區(qū)域的客戶群從頭到尾串到一起，然后根據(jù)車容量和工作時(shí)間來切分車輛，它是直達(dá)目標(biāo)的。也就是說，它并不是通過事先優(yōu)化客戶群的連接順序來間接的優(yōu)化最終的線路，而是使用禁忌搜索嘗試各種客戶群排序的組合方式，對(duì)此排序下的客戶序列進(jìn)行裝車切割，以實(shí)際得出的線路結(jié)果作為最終的評(píng)估對(duì)象。通過評(píng)估不同客戶群排序組合下實(shí)際的切分裝車結(jié)果，來找出較優(yōu)的客戶群排序方式。

① 禁忌搜索：為了得到更優(yōu)的計(jì)算結(jié)果，擴(kuò)大計(jì)算范圍，減少計(jì)算量，本算法引入了禁忌搜索。首先，對(duì)置換問題定義一種鄰域搜索結(jié)構(gòu)，如互換操作（SWAP），即隨機(jī)交換兩個(gè)點(diǎn)的位置，則每個(gè)狀態(tài)的鄰域解有Cn2=n（n-1）/2個(gè)其中n為點(diǎn)數(shù)。稱從一個(gè)狀態(tài)轉(zhuǎn)移到其鄰域中的另一個(gè)狀態(tài)為一次移動(dòng)（move），顯然每次移動(dòng)將導(dǎo)致適配值（反比于目標(biāo)函數(shù)值）的變化。其次，采用一個(gè)存儲(chǔ)結(jié)構(gòu)來區(qū)分移動(dòng) 的屬性，即是否為禁忌“對(duì)象”。需要指出的是，由于當(dāng)前的禁忌對(duì)象對(duì)應(yīng)狀態(tài)的適配值可能很好，因此在算法中設(shè)置判斷，若禁忌對(duì)象對(duì)應(yīng)的適配值優(yōu)于“best so far”狀態(tài)，則無視其禁忌屬性而仍采納其為當(dāng)前選擇，也就是通常所說的藐視準(zhǔn)則（或稱特赦準(zhǔn)則）。

② 評(píng)估參數(shù)：評(píng)估的基本參數(shù)是所有線路的總工作時(shí)間。如果需要和其它區(qū)域連接，那么還需要加上尾車的最后一戶到下一個(gè)區(qū)域的連結(jié)點(diǎn)客戶的時(shí)間，總時(shí)間越短越好。此外，如果有區(qū)域融合的要求，還會(huì)附加上盡量能使尾車和與其它區(qū)域相連這個(gè)條件。

③對(duì)于特定客戶群序的裝車切割流程：裝車時(shí)，默認(rèn)方法為安排好的客戶順序裝車，假如碰到自己車子無法配送的客戶，將這一戶剔出來，繼續(xù)裝后面的，這幾戶被剔除的客戶留待后面的車子來嘗試配送。倘若裝車中碰到一個(gè)訂貨大戶，如果加上去，車子裝不下，如果不加，車子裝載率又太低，這時(shí)候?qū)⑻^此戶，繼續(xù)裝后面訂貨量沒這么大的，保證裝載率不會(huì)太低。

④ 車型匹配：將起始客戶初始化為第一個(gè)客戶，進(jìn)行車型適配度的評(píng)估。其做法是，嘗試使用各種車型進(jìn)行裝車，把生成的各個(gè)線路結(jié)果作為評(píng)估對(duì)象。生成線路的時(shí)候，由于車型關(guān)系剔除的客戶越多，說明此車型的適配度越低。取適配度較好的幾個(gè)車型作為待選車型，從中選出一輛駕駛員歷史累計(jì)送貨時(shí)間較低的作為最終選擇結(jié)果。另外，如果可能的話，區(qū)域內(nèi)的每個(gè)駕駛員都需要至少出車一次。所以選擇時(shí)，優(yōu)先從今天沒有出過車的駕駛員里選擇。

⑤ 標(biāo)記：一條線路生成后，將線路中的客戶作上已計(jì)算標(biāo)記，繼續(xù)按照上面的算法，選擇車型，選擇車輛，計(jì)算剩下的客戶序列中的客戶，直到所有的客戶都被計(jì)算完成。

2.2.3.3 路順優(yōu)化

線路生成后，分別以全體打亂重排的方式和保留客戶群內(nèi)客戶順序進(jìn)行路順計(jì)算。默認(rèn)為保留客戶群內(nèi)的順序，但如果默認(rèn)結(jié)果與打亂重算的結(jié)果差很多，那么以打亂重排后的順序?yàn)樽罱K的線路路順。打亂重排涉及局部搜索和禁忌搜索算法。

基本思想是在搜索過程中沿著某一方向搜索，該方向是從當(dāng)前點(diǎn)到該點(diǎn)的所有鄰居中離目標(biāo)點(diǎn)最近的那一點(diǎn)的方向。

① 隨機(jī)選擇一個(gè)初始的可能解

② 如果不滿足結(jié)束條件，則開始循環(huán)。

③ Begin

⑦ End

⑧ 輸出計(jì)算結(jié)果。

而禁忌搜索是對(duì)局部搜索的擴(kuò)展，是一種局部搜索能力很強(qiáng)的全局迭代尋優(yōu)算法，其詳細(xì)計(jì)算機(jī)制如前所述。與局部搜索相比具有以下特點(diǎn)：一是在搜索過程中可以接受劣解。二是新解不是在當(dāng)前鄰域中隨機(jī)產(chǎn)生，而是優(yōu)于“best so far”的解，或是非禁忌的最優(yōu)解，因此選取優(yōu)良解的概率遠(yuǎn)大于其它解。

2.2.3.4 尾車劃撥

假如該區(qū)域（區(qū)塊）開啟了區(qū)域融合，那么首先要通過設(shè)置獲取信息，判斷該區(qū)域（區(qū)塊）能和哪些其他區(qū)域（區(qū)塊）交換客戶。

接下來，查看本區(qū)域是否需要往外劃撥的尾車，如果需要，那么查找距離這個(gè)尾車最近的可交換區(qū)域，將尾車的所有客戶劃撥給到那個(gè)區(qū)域去(或者抓取足夠的客戶填充)。假如需要將尾車交給其他區(qū)域，程序運(yùn)算時(shí)會(huì)將尾車客戶盡量放置在本區(qū)域的邊緣地區(qū)，跟將要?jiǎng)潛艿降泥従訁^(qū)域盡量接近。

如果找不到其他可劃撥的區(qū)域了，尾車將獨(dú)自成為一條線路。這種情形通常出現(xiàn)在幾種情況下：這個(gè)區(qū)域與其他的任何區(qū)域都很遠(yuǎn)，距離太遠(yuǎn)的話是不會(huì)劃撥過去的；這個(gè)區(qū)域是所有可交換區(qū)域中，最后一個(gè)待計(jì)算的區(qū)域了；尾車的客戶附近的其他車輛都無法配送。

2.3 曾使用的其它算法及遇到的問題

2.3.1 第一版算法

粗略預(yù)估一個(gè)月平均裝載率大致能達(dá)到90%左右的車輛數(shù)，根據(jù)車輛列表獲取所用的車輛。采用中心聚類，以裝載率越平均越好為目標(biāo)，對(duì)整個(gè)區(qū)域進(jìn)行一次性的分割計(jì)算得到初步結(jié)果，然后使用滲透模擬的方式，在線路之間調(diào)整客戶。

這種方式比單純的中心聚類分割線路，穩(wěn)定性要好不少。但由于僅僅考慮客戶點(diǎn)的地理信息來安排路順，不參考其原線路，所以路順都是重新計(jì)算的。在基礎(chǔ)信息不準(zhǔn)確的情況下，路順的計(jì)算結(jié)果往往不如人意。

另外，由于中心聚類天生的穩(wěn)定性的缺陷，以及滲透模擬無法進(jìn)行大范圍調(diào)節(jié)的劣勢(shì)，偶爾會(huì)可能出現(xiàn)一些穿插的很遠(yuǎn)的較劣結(jié)果。

2.3.2 第二版算法

參照原線路，把區(qū)域內(nèi)的客戶劃分成一個(gè)個(gè)客戶群，然后對(duì)客戶群進(jìn)行排序，生成一個(gè)很大的客戶序列，之后，使用區(qū)域內(nèi)車輛列表，對(duì)這個(gè)客戶序列進(jìn)行逐次裝車，以車輛的最大裝載量和最大送貨時(shí)間為限制條件，分割成一條條線路。

分割完畢后，檢查每個(gè)區(qū)域的尾車是否能和其他區(qū)域尾車進(jìn)行合并，通過最大連接距離來限制尾車的合并范圍，避免與過遠(yuǎn)的尾車連接。倘若無法簡(jiǎn)單合并，將嘗試將尾車拆成多份，分配到附近區(qū)域的其他尾車上面去，以減少尾車數(shù)目，提高裝載率。

這個(gè)做法在客戶群較少的情況下效果較好，但如果客戶群數(shù)量較多，通過簡(jiǎn)單的串接排序生成的線路，其聚團(tuán)性較差，線路之間穿插較嚴(yán)重。另外，由于每個(gè)區(qū)域之間的尾車一般相距較遠(yuǎn)，尾車所能交互的對(duì)象并不多，所以其合并相對(duì)的有限。在開啟全區(qū)合并的情況下，只能減少一半不到的尾車。

3 系統(tǒng)測(cè)試與結(jié)果分析

3.1 系統(tǒng)的測(cè)試環(huán)境

編程語言為C#，編譯環(huán)境為Visual Studio 2012，基于.NET Framework4.5 ，操作系統(tǒng)為Win7 32bit。

部署軟件環(huán)境，操作系統(tǒng)為Windows Server 2008 R2 64bit，安裝.NET Framework4.5框架。

部署硬件環(huán)境為IBM X3650 M4服務(wù)器 （至強(qiáng)CPU，內(nèi)存32G）。

3.2 測(cè)試結(jié)果

以2014年2月訂貨量為實(shí)驗(yàn)數(shù)據(jù)，計(jì)算原有送貨模式和線路優(yōu)化新模式下兩種配送結(jié)果，以裝載率和出車趟次作為比較指標(biāo)進(jìn)行分析。選取10天的訂單量進(jìn)行測(cè)試，數(shù)據(jù)結(jié)果如表1所示。

由表1數(shù)據(jù)繪制圖2、3的曲線圖，其中橫坐標(biāo)為序號(hào)值，圖2為裝載率對(duì)比曲線圖，圖3為出車趟次對(duì)比曲線圖。

表1 2014年2月測(cè)試數(shù)據(jù)結(jié)果Tab.1 Test results of February 2014

圖2 裝載率對(duì)比曲線圖Fig.2 Comparison graph of loading rates

圖3 出車趟次對(duì)比曲線圖Fig.3 Comparison graph of department quantity

3.3 結(jié)果分析

（1）如圖2所示，在訂單量一定的情況下，優(yōu)化后裝載率全部高于原有線路裝載率，平均增加20.1%。優(yōu)化后，平均裝載率達(dá)到了90%以上的指標(biāo)要求。

（2）如圖3所示，在訂單量一定的情況下，優(yōu)化后出車趟次全部少于原有線路出車趟次，平均減少超過20%。

（3）在線路裝填時(shí)，本算法通過評(píng)估不同客戶群排序組合下，實(shí)際的切分裝車結(jié)果，來找出較優(yōu)的客戶群排序方式。一般來說，很少有人會(huì)用這種系統(tǒng)資源巨大的方式來實(shí)現(xiàn)這個(gè)要求，但由于已經(jīng)作了區(qū)域識(shí)別分析，能夠確保區(qū)域內(nèi)的客戶基本上都是整線的，客戶群的數(shù)目不會(huì)太多，計(jì)算負(fù)荷不至于無法接受。

（4）本算法中心聚類算法與普通中心聚類不同，最大的區(qū)別是在于計(jì)算的次數(shù)。普通中心聚類，是一次性計(jì)算出所有的線路；而這個(gè)算法，每次只取包含有計(jì)算起點(diǎn)的線路作為結(jié)果，剩余的線路統(tǒng)統(tǒng)回爐重算，需要逐次計(jì)算N-1次，才能獲取N條線路。保證尾車的線路與其他區(qū)域很接近，方便進(jìn)行區(qū)域間的客戶調(diào)配。

4 結(jié)論

本算法滿足了業(yè)務(wù)指標(biāo)要求，突破了原有行政區(qū)縣劃分的界限限制，優(yōu)化了配送調(diào)度結(jié)果，在大計(jì)算量的情況下仍能滿足計(jì)算要求。對(duì)卷煙配送裝載率和出車趟次具有良好的改善效果。同時(shí)，本算法具有普適性，在適應(yīng)北京復(fù)雜路線的情況下仍能適應(yīng)業(yè)務(wù)需求，具有較好的推廣價(jià)值。

[1]張曉輝.禁忌搜索算法研究及其在電磁場(chǎng)優(yōu)化問題中的應(yīng)用 [D].碩士學(xué)位論文，河北工業(yè)大學(xué)，2003.

[2]劉志成，文全剛.K-中心點(diǎn)聚類算法分析及其實(shí)現(xiàn)[J]電腦知識(shí)與技術(shù)，2005（2）：20-24.

[3]朱建中.求解可滿足性問題的局部搜索算法[D].碩士學(xué)位論文，南京大學(xué)，2004.

[4]郭娜.基于節(jié)約算法和移動(dòng)方向的禁忌搜索算法[D].碩士學(xué)位論文，大連理工大學(xué)，2009.

[5]李少芳.連續(xù)背包問題貪婪算法最優(yōu)解的實(shí)現(xiàn) [J].福建電腦，2003（11）：12-13.

Cigarette distribution scheduling system based on route optimization algorithm

SUN Zhuangzhi,YAN Liehu,YAO Xuewei
Beijing Tobacco Logistics Center,Beijing 101101，China

An adaptable,quick-responsive and feasible real-time solution was introduced by applying algorithms such as central clustering,tabu search and local search on the basis of cigarette distribution market in Beijing.Dynamic scheduling was fully achievable by taking original delivery map as reference and work load of delivery vehicles and working staff into full consideration.The solution was proved to be effective with monthly average loading rate exceeding 90%.

route optimization; central clustering; tabu search; local search

10.3969/j.issn.1004-5708.2014.05.021

TP315 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1004-5708（2014）05-0128-06

孫壯志（1971—），高級(jí)工程師 ，主要從事卷煙物流等方面的研究，Email:349890782@qq.com

2014-03-12