[摘 要] 針對(duì)物流企業(yè)分揀配貨業(yè)務(wù)流程的特點(diǎn)，提出了一種基于優(yōu)先級(jí)的分揀配貨算法思想，給出了優(yōu)先級(jí)的構(gòu)造方法，并采用貪心算法思想來實(shí)現(xiàn)基于優(yōu)先級(jí)的分揀配貨算法，將此算法應(yīng)用于實(shí)踐中有助于提高企業(yè)的經(jīng)濟(jì)與社會(huì)效益#65377;

[關(guān)鍵詞] 優(yōu)先級(jí);分揀配貨;算法設(shè)計(jì)

[中圖分類號(hào)]F270.7[文獻(xiàn)標(biāo)識(shí)碼]A[文章編號(hào)]1673-0194(2009)03-0064-02

隨著我國(guó)物流行業(yè)的快速發(fā)展，中小型物流企業(yè)面臨的競(jìng)爭(zhēng)越來越激烈，只有依靠高效的管理#65380;良好的信譽(yù)才能贏得市場(chǎng)，取得更好的經(jīng)濟(jì)效益#65377;因此越來越多的企業(yè)開始使用計(jì)算機(jī)技術(shù)，建立起相應(yīng)的物流配送管理信息系統(tǒng)，對(duì)企業(yè)的業(yè)務(wù)流程進(jìn)行全面管理#65377;分揀配貨是物流配送管理過程中的一個(gè)重要環(huán)節(jié)，分檢配貨子系統(tǒng)自然是配送管理信息系統(tǒng)中的一個(gè)重要組成部分，而分檢配貨算法則是分檢配貨子系統(tǒng)的靈魂，算法的優(yōu)劣直接影響企業(yè)的經(jīng)濟(jì)效益和社會(huì)聲譽(yù)#65377;

1 分揀配貨業(yè)務(wù)分析

分揀配貨按照客戶的要求，從物流貨倉中分揀出客戶的貨物，進(jìn)行配貨，配齊客戶的貨物后進(jìn)行裝運(yùn)#65377;物流配送就是利用有效的分揀配貨等理貨工作，使送貨達(dá)到一定的規(guī)模，以利用規(guī)?；瘍?yōu)勢(shì)取得較低的送貨成本，從而提高企業(yè)的效益[1]#65377;

為了兼顧客戶的合理要求，同時(shí)又能提高企業(yè)的效益，在設(shè)計(jì)分揀配貨算法時(shí)需從兩方面考慮:一是客戶的需求;二是企業(yè)的內(nèi)部管理#65377;

從客戶的角度來看，主要有以下幾方面的需求:一是滿足客戶對(duì)貨物的保管需求;二是滿足客戶對(duì)貨物種類齊全性的需求;三是滿足客戶對(duì)貨運(yùn)時(shí)間的需求;四是滿足客戶對(duì)貨運(yùn)的安全性需求;五是滿足客戶對(duì)收貨地點(diǎn)的需求#65377;

從物流企業(yè)的角度來看，首先要保證所有客戶的貨物能在規(guī)定的期限內(nèi)送達(dá)目的地，有力提高企業(yè)的社會(huì)聲譽(yù);二是能提高企業(yè)的管理水平，降低管理成本;三是形成規(guī)模效應(yīng)，降低經(jīng)營(yíng)成本，提高企業(yè)經(jīng)濟(jì)效益#65377;

2 算法設(shè)計(jì)

根據(jù)對(duì)分揀配貨業(yè)務(wù)的分析可知，在設(shè)計(jì)算法時(shí)必須綜合考慮企業(yè)與客戶間的多方面需求，既要保證企業(yè)的經(jīng)濟(jì)利益，又要盡可能滿足客戶的需求，因而在設(shè)計(jì)分揀配貨算法時(shí)提出了基于優(yōu)先級(jí)的算法設(shè)計(jì)思想#65377;

2. 1算法思想

首先根據(jù)物流企業(yè)的經(jīng)營(yíng)范圍與規(guī)模，確定出若干條貨運(yùn)線路，并配備一定數(shù)量的貨運(yùn)車輛#65377;然后綜合考慮企業(yè)經(jīng)營(yíng)與客戶需求等因素，對(duì)每條貨運(yùn)線路上的客戶貨物設(shè)置相應(yīng)的貨物分揀優(yōu)先級(jí)，再采用貪心算法依據(jù)優(yōu)先級(jí)的大小順序進(jìn)行貨物的分揀配貨，生成裝運(yùn)計(jì)劃#65377;

2. 2優(yōu)先級(jí)設(shè)置

貨物分揀優(yōu)先級(jí)的設(shè)置既要考慮企業(yè)的經(jīng)營(yíng)成本與社會(huì)聲譽(yù)，又要考慮客戶的合理要求#65377;經(jīng)過對(duì)物流企業(yè)的調(diào)研分析得出，影響企業(yè)經(jīng)營(yíng)效益的因素主要有以下幾個(gè):一是貨運(yùn)車輛的實(shí)際裝載量;二是同一車貨物卸貨點(diǎn)的安排;三是不同種貨物混裝方式;四是送達(dá)貨物的時(shí)間#65377;而客戶的要求主要是兩個(gè)方面:一是貨物能在指定時(shí)間內(nèi)送到;二是能保證貨物的安全，減少損耗#65377;

綜合以上各方面的因素，貨物分揀優(yōu)先級(jí)由下面幾部分組成:

一是與貨物卸貨地點(diǎn)有關(guān)的部分P1，取值規(guī)則是到貨運(yùn)線路終點(diǎn)卸貨的優(yōu)先級(jí)為n1，沿途卸貨的由遠(yuǎn)到近依次減少d1，即P1 = n1 - s× d1，s表示由終點(diǎn)至起點(diǎn)間的卸貨點(diǎn)序數(shù)，取值依次為0，1，2，… #65377;

二是與交貨時(shí)間有關(guān)的部分P2，設(shè)其初值為n2，貨物在貨倉中每等待一天，則優(yōu)先級(jí)增加一個(gè)增量d2，即P2 =n2 + t × d2，t表示等待的天數(shù)#65377;

三是與運(yùn)費(fèi)有關(guān)的部分P3，設(shè)正常收費(fèi)的優(yōu)先級(jí)為n3，辦理特快運(yùn)送的貨物在收取特快費(fèi)后增加一個(gè)增量d3，即P3 = n3 + j× d3， j表示貨運(yùn)等級(jí)#65377;

貨物分揀優(yōu)先級(jí)為各部分優(yōu)先級(jí)之和，即P = P1 + P2 + P3 #65377;

2. 3算法實(shí)現(xiàn)

分揀配貨子系統(tǒng)是一個(gè)圍繞數(shù)據(jù)庫進(jìn)行操作的管理系統(tǒng)，為了便于有關(guān)操作算法的實(shí)現(xiàn)，建立如下與分揀配貨有關(guān)的數(shù)據(jù)庫表#65377;

貨物信息表(GoodsTable):貨物編號(hào)#65380;貨物名稱#65380;貨物類型#65380;貨物價(jià)值#65380;貨物重量#65380;貨物體積#65380;貨物數(shù)量#65380;客戶名#65380;貨運(yùn)地點(diǎn)#65380;貨運(yùn)線路#65380;貨運(yùn)等級(jí)#65380;登記時(shí)間#65380;時(shí)間期限#65380;經(jīng)辦人名#65377;

車輛信息表(TruckTable):車輛編號(hào)#65380;車輛類型#65380;車輛牌號(hào)#65380;載重量#65380;車廂容積#65380;車輛狀態(tài)#65380;司機(jī)名#65377;

優(yōu)先級(jí)表(PriTable):貨物編號(hào)#65380;分揀優(yōu)先級(jí)#65380;貨物狀態(tài)#65377;

貨運(yùn)計(jì)劃表(GplanTable):序號(hào)#65380;貨運(yùn)線路#65380;貨運(yùn)車牌號(hào)#65380;貨物編號(hào)#65380;貨物重量#65380;貨物體積#65380;客戶名#65380;發(fā)車時(shí)間#65377;

貨運(yùn)線路表(GlineTable):線路編號(hào)#65380;起點(diǎn)#65380;終點(diǎn)#65380;卸貨點(diǎn)1#65380;卸貨點(diǎn)2#65380;卸貨點(diǎn)3#65380;卸貨點(diǎn)4#65380;卸貨點(diǎn)5#65377;

其中貨物信息表#65380;貨運(yùn)計(jì)劃表#65380;優(yōu)先級(jí)表這3個(gè)數(shù)據(jù)表通過貨物編號(hào)建立起相應(yīng)的關(guān)聯(lián)關(guān)系#65377;

整個(gè)算法的主要步驟如下:

(1)循環(huán)執(zhí)行a至d步，直到貨運(yùn)線路或貨運(yùn)車輛為零:

a. 選定貨運(yùn)線路和貨運(yùn)車輛;

b. 計(jì)算屬于選定貨運(yùn)線路上貨物分揀優(yōu)先級(jí)P;

c. 以優(yōu)先級(jí)為關(guān)鍵字建立優(yōu)先級(jí)表的索引表(IndexTable);

d. 采用貪心算法思想，按優(yōu)先級(jí)從大到小順序給指定車輛分揀待裝貨物，并將揀出貨物信息填入貨運(yùn)計(jì)劃表(GplanTable)中;

(2)打印貨運(yùn)計(jì)劃表;

(3)結(jié)束#65377;

貨運(yùn)線路的選定可根據(jù)貨運(yùn)線路表(GlineTable)依次選擇，貨運(yùn)車輛則根據(jù)可用車輛的數(shù)量與類型按比例預(yù)先分配到各條貨運(yùn)線路#65377;

為了便于計(jì)算貨物分揀優(yōu)先級(jí)，根據(jù)貨運(yùn)線路的不同分別建立相應(yīng)的貨物信息表及對(duì)應(yīng)的優(yōu)先級(jí)表，兩表按貨物編號(hào)建立關(guān)聯(lián)關(guān)系，計(jì)算貨物分揀優(yōu)先級(jí)的算法的主要步驟如下:

(1)打開選定線路的貨物信息表#65380;優(yōu)先級(jí)表與貨運(yùn)線路表;

(2)設(shè)定n1，n2，n3，d1，d2，d3的值;

(3)循環(huán)執(zhí)行，直到貨物信息表底部:

a. 計(jì)算出貨物信息表當(dāng)前記錄的s，t， j值;

b. P1 = n1 - s × d1，P2 = n2 + t × d2，P3 = n3 + j × d3;

c. P = P1 + P2 + P3;

d. 優(yōu)先級(jí)表增加一條新記錄，字段值為貨物信息表當(dāng)前記錄的貨物編號(hào)與優(yōu)先級(jí)P#65377;

(4)結(jié)束#65377;

計(jì)算出貨物分揀優(yōu)先級(jí)并建立相應(yīng)的索引表后，就可采用貪心算法思想進(jìn)行貨物的分揀，從而保證每輛貨車能夠滿載#65377;貪心算法的基本思想是通過一系列的選擇得到問題的解，所作出的每一個(gè)選擇都是當(dāng)前狀態(tài)下局部最好選擇，即貪心選擇[2]#65377;在貨物的分揀過程中，利用這一算法思想，總是優(yōu)先選出優(yōu)先級(jí)高的貨物進(jìn)行裝運(yùn)，直到車輛滿載為止，其算法主要步驟如下:

(1)打開貨物信息表#65380;優(yōu)先級(jí)表及其索引表#65380;貨運(yùn)計(jì)劃表#65380;車輛信息表;

(2)從車輛信息表中選取一輛車，裝載能力G=該車載重量;

(3)循環(huán)，直到裝載能力G小于或等于零:

a.選取索引表當(dāng)前記錄，根據(jù)貨物編號(hào)從貨物信息表中取出貨物重量W;

b.如果G≥W，則該貨物被分揀，修改其貨物狀態(tài)為“分揀”，貨運(yùn)計(jì)劃表增加一條新記錄，其值為該貨物的有關(guān)字段值，G= G -W，索引表指針后移一位;

c.如果G< W，則查詢車輛信息表是否有空車，有則選取一輛，G= G+該車載重量，轉(zhuǎn)b，沒有則索引表指針后移一位，轉(zhuǎn)a ;

(4)結(jié)束#65377;

3 算法分析

為了實(shí)現(xiàn)基于優(yōu)先級(jí)的算法，在設(shè)計(jì)系統(tǒng)數(shù)據(jù)庫時(shí)增加一個(gè)貨物分揀優(yōu)先級(jí)表，對(duì)應(yīng)每一個(gè)客戶的貨物設(shè)置相應(yīng)的分揀優(yōu)先級(jí)，再按優(yōu)先級(jí)順序建立一個(gè)索引表，便于按優(yōu)先級(jí)大小進(jìn)行貨物的分揀，提高分揀效率，雖然增加了一個(gè)數(shù)據(jù)庫表和一個(gè)索引表，但這兩個(gè)表只有幾個(gè)字段，且其中的數(shù)據(jù)量不大，不需要系統(tǒng)增加太多的存儲(chǔ)空間#65377;

貨物分揀優(yōu)先級(jí)的計(jì)算是本算法的核心，它決定著算法質(zhì)量的優(yōu)劣#65377;由于與優(yōu)先級(jí)有關(guān)聯(lián)的因素較多，在設(shè)計(jì)優(yōu)先級(jí)的計(jì)算方法時(shí)只考慮對(duì)其有重大影響的時(shí)間#65380;卸貨點(diǎn)#65380;運(yùn)費(fèi)3個(gè)因素，將優(yōu)先級(jí)分為3個(gè)部分，為了確定各部分的n與d的取值，通過對(duì)廣東韶關(guān)幾家物流企業(yè)日常經(jīng)營(yíng)情況調(diào)研總結(jié)，決定ni的取值相同，均為整數(shù)30，即n1 =30，n2 =30，n3 =30，增量d則按比例1∶1∶2確定，初步設(shè)定d1 =3，d2 =3，d3 =6，并將其應(yīng)用于開發(fā)的物流管理系統(tǒng)中，經(jīng)過韶關(guān)兩家物流企業(yè)的實(shí)際應(yīng)用，基本達(dá)到預(yù)期的目標(biāo)，提高了企業(yè)的管理水平和經(jīng)濟(jì)效益，各企業(yè)可以根據(jù)實(shí)際情況調(diào)整數(shù)據(jù)取值#65377;

算法存在的問題主要有以下方面:一是由于沒有一個(gè)計(jì)算貨物分揀優(yōu)先級(jí)的成熟模型，已給出的計(jì)算方法無法適應(yīng)所有物流企業(yè)的業(yè)務(wù)需求，需要尋求一種更科學(xué)有效的計(jì)算方法;二是在每次進(jìn)行分揀配貨時(shí)需要重新計(jì)算貨物的分揀優(yōu)先級(jí)，重建索引表，增加了系統(tǒng)的運(yùn)行時(shí)間，降低了運(yùn)行效率#65377;

4 結(jié) 論

基于優(yōu)先級(jí)的分揀配貨算法具有結(jié)構(gòu)簡(jiǎn)單#65380;易于實(shí)現(xiàn)的特點(diǎn)，能有效地完成物流企業(yè)的分揀配貨業(yè)務(wù)，提高企業(yè)的管理水平，為企業(yè)帶來更好的經(jīng)濟(jì)與社會(huì)效益#65377;

主要參考文獻(xiàn)

[1] 張曉川. 物流配送系統(tǒng)規(guī)劃[M]. 北京:中國(guó)水利水電出版社，2007:65-67.

[2] 王曉東. 算法設(shè)計(jì)與分析[M]. 北京:清華大學(xué)出版社，2005:110-112.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”