同城生鮮配送線路優(yōu)化問題研究

張令甜，敖飛翔，涂傳清 ZHANG Lingtian， AO Feixiang， TU Chuanqing

（1. 江西農(nóng)業(yè)大學(xué) 經(jīng)濟(jì)管理學(xué)院，江西 南昌330045；2. 江西農(nóng)業(yè)大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，江西 南昌330045）

0 引 言

近年來，中國生鮮電商市場規(guī)模發(fā)展迅速，但生鮮產(chǎn)品保質(zhì)期短、易損耗的特征使其對(duì)物流配送要求較高，物流成本在生鮮電商的成本結(jié)構(gòu)中占比巨大，因此，物流配送成為影響生鮮電商發(fā)展的重要制約因素[1]。提高配送效率、降低物流成本是所有生鮮電子商務(wù)公司需要解決的關(guān)鍵問題，而優(yōu)化配送車輛行駛路徑是提高配送效率的重要手段。

同城生鮮配送線路優(yōu)化問題可以看作是一個(gè)經(jīng)典的旅行商問題（TSP）。而旅行商問題是一個(gè)NP 完全問題，當(dāng)被訪問的點(diǎn)（配送點(diǎn)） 數(shù)量較多時(shí)，如果通過搜索全局，精確地求得最優(yōu)解，其復(fù)雜度將會(huì)極高，所以此類問題通常是運(yùn)用智能優(yōu)化算法（又稱啟發(fā)式算法） 求得近似解。高海昌等（2006） 對(duì)常見的用于求解TSP 問題的智能優(yōu)化算法進(jìn)行了綜述，他們分析了蟻群算法、遺傳算法、模擬退火算法、禁忌搜索算法、Hopfield 神經(jīng)網(wǎng)絡(luò)、粒子群優(yōu)化算法、免疫算法等7 種算法在解決TSP 問題時(shí)各自的優(yōu)缺點(diǎn)以及改進(jìn)建議[2]。后續(xù)學(xué)者們對(duì)同城生鮮配送線路優(yōu)化問題的研究基本上都是對(duì)上述智能算法的應(yīng)用與改進(jìn)，文獻(xiàn)[3]-[11]分別運(yùn)用蟻群算法、遺傳算法和節(jié)約算法求解配送車輛路徑優(yōu)化問題，并通過算例分析論證計(jì)算結(jié)果的有效性。這些研究成果對(duì)我們具有極大的啟發(fā)意義，但是當(dāng)我們想將他們設(shè)計(jì)的算法直接套用到本文面臨的問題——為某生鮮電商公司100 多位客戶指派送貨車輛和規(guī)劃配送路線時(shí)，發(fā)現(xiàn)上述研究存在以下不足：（1） 對(duì)蟻群算法的改進(jìn)雖然解決了蟻群算法的收斂速度慢的問題，也增強(qiáng)了蟻群算法的魯棒性，未解決此算法容易陷入局部最優(yōu)的問題；（2） 未能很好地改進(jìn)遺傳算法局部尋優(yōu)能力不足的缺點(diǎn)；（3） 節(jié)約算法在求解小規(guī)模的配送線路優(yōu)化問題上能夠得到較理想的結(jié)果，其特點(diǎn)是運(yùn)算速度較快，但是當(dāng)需要配送的站點(diǎn)數(shù)量較多時(shí)，則獲得結(jié)果不大理想。另外，上述研究還存在一個(gè)共同的問題就是算例過于簡單，因此不能發(fā)現(xiàn)當(dāng)配送站點(diǎn)數(shù)量擴(kuò)大10 倍時(shí)可能引發(fā)的問題，且未解決快速獲取各個(gè)配送站點(diǎn)之間距離的問題。

針對(duì)現(xiàn)有研究存在的不足，結(jié)合本文所關(guān)注的南昌市某生鮮電商公司為100 多個(gè)企事業(yè)單位食堂提供生鮮農(nóng)產(chǎn)品配送服務(wù)時(shí)所面臨的實(shí)際問題——由工作人員憑經(jīng)驗(yàn)和手工計(jì)算進(jìn)行配送車輛調(diào)度和配送路線安排，因而導(dǎo)致配送效率低下。具體表現(xiàn)為不能根據(jù)客戶需求變化及時(shí)調(diào)整配送路線導(dǎo)致配送車輛滿載率低、配送距離長；本文擬從滿足實(shí)際配送需求出發(fā)，以減少配送車輛和節(jié)約配送路程為目標(biāo)；不設(shè)置單個(gè)時(shí)間窗，只要求在客戶上午開始準(zhǔn)備午餐之前將生鮮農(nóng)產(chǎn)品送到即可，因此只是統(tǒng)一設(shè)置最晚送達(dá)時(shí)間點(diǎn)；由于完成整個(gè)配送工作的時(shí)間較短，所以不考慮生鮮農(nóng)產(chǎn)品的損耗問題，并據(jù)此建立數(shù)學(xué)模型；然后將具有較強(qiáng)局部尋優(yōu)能力的爬山算法嵌入到全局尋優(yōu)能力優(yōu)良的遺傳算法中用于對(duì)模型求解，取得了非常好的實(shí)際效果。

1 同城生鮮配送線路優(yōu)化問題數(shù)學(xué)模型

問題描述：生鮮電商公司專門為企事業(yè)單位提供生鮮農(nóng)產(chǎn)品采購和配送服務(wù)，企事業(yè)單位每天下午六點(diǎn)以前告知電商公司第二天需要的食材種類和數(shù)量，晚上八點(diǎn)電商公司所屬配送中心根據(jù)每個(gè)客戶的需求對(duì)生鮮食材進(jìn)行分揀，并裝入規(guī)格統(tǒng)一的塑料筐，每個(gè)客戶所需的物品不合用同一個(gè)塑料筐；早上六點(diǎn)開始，電商公司用多臺(tái)型號(hào)相同的車按事先規(guī)劃好的路徑為客戶送貨，完成配送任務(wù)后所有車輛回到配送中心。要求合理安排所有投入運(yùn)行車輛的配送線路，即確定每輛車依次為哪些客戶送貨，使得所有車輛行駛里程總和最小，并滿足以下條件：（1） 每條配送線路上客戶的需求量之和不超過車輛的裝載數(shù)量；（2） 每個(gè)客戶的需求只由一輛車進(jìn)行配送，且每天只送貨一次；（3） 車輛在配送途中不進(jìn)行加油服務(wù)，受油箱容量的限制，車輛有最大的行駛距離，故規(guī)定每條配送路線上各點(diǎn)的距離之和不大于車輛的最大行駛距離；（4） 所有配送車輛在規(guī)定的時(shí)間T內(nèi)完成各自的配送工作后回到配送中心。

為建立此問題的數(shù)學(xué)模型，本文做如下符號(hào)假設(shè)：①給配送中心和各個(gè)客戶進(jìn)行編碼。設(shè)企業(yè)需要給n個(gè)客戶配送，配送中心編碼為“0”，各個(gè)客戶的編碼為1，2，…，n。②qi（i=1，2，…，n）為每個(gè)客戶的需求量；dij（i,j=0，1，2，…，n）表示從客戶i（或配送中心） 到客戶j（或配送中心） 配送車輛所需行駛的距離；tij（i,j=0，1，2，…，n）表示從客戶i（或配送中心） 到客戶j（或配送中心） 配送車輛所需行駛的時(shí)間。③參與配送工作車輛的裝載量為Q（裝載數(shù)量的單位為筐，因?yàn)樵趯?shí)際操作中，將每個(gè)客戶需求的物品全部裝入統(tǒng)一規(guī)格的塑料筐中進(jìn)行配送），每天實(shí)際投入運(yùn)營的配送車輛數(shù)為K。④每輛車的最大行駛距離為L。⑤配送車輛為每個(gè)客戶送貨時(shí)卸貨所需時(shí)間為t。⑥設(shè)決策變量xijk（i，j=0，1，2，…，n，k=1，2，3，…，K）為邏輯變量，當(dāng)xijk=1 時(shí)，表示第k輛車送貨從客戶i（或配送中心） 到客戶j（或配送中心），否則xijk等于0；設(shè)決策變量yik（i=1，2，…，n，k=1，2，3，…，K）為邏輯變量，當(dāng)yik=1 時(shí)，表示客戶i由第k輛車完成配送，否則yik=0。每輛車在T時(shí)間內(nèi)完成配送并回到配送中心。⑦完成配送工作后，所有車輛的總旅程數(shù)為D。

式（1） 為目標(biāo)函數(shù)，求配送車輛總旅程的最小值；式（2） 確保車輛在時(shí)間T內(nèi)完成配送并回到配送中心；式（3） 約束每輛車行駛的距離不超過其最大的行駛里程數(shù)L；式（4） 保證每輛車的裝運(yùn)量不大于其最大裝載量Q；式（5） 確保每個(gè)客戶的需求只由一輛車進(jìn)行配送；式（6） 確保每個(gè)客戶的需求都有車輛進(jìn)行配送。另外，需要說明的是，在建模時(shí)沒有將公司現(xiàn)有配送車輛數(shù)M作為一個(gè)硬約束，因?yàn)樵趯?shí)際運(yùn)作中如果配送任務(wù)重，公司很容易臨時(shí)在市場上找到車輛來完成配送任務(wù)，而且可以合理地推斷將目標(biāo)函數(shù)設(shè)置為求所有配送車輛總行程的最小值，通?？梢员ＷC投入運(yùn)行的配送車輛數(shù)最少。

2 混合遺傳算法設(shè)計(jì)

遺傳算法（Genetic Algorithm） 是一種啟發(fā)式算法，是Holland[3]在1973 年模擬達(dá)爾文生物進(jìn)化論中的“自然選擇”和“遺傳學(xué)機(jī)制”首次提出的。在20 世紀(jì)90 年代初遺傳算法被引用到求解TSP 問題中，將一條路線抽象地看著是一條染色體（個(gè)體），而路線中的點(diǎn)抽象成染色體（個(gè)體） 上的基因。在求解TSP 問題中，遺傳算法中的選擇操作、交叉操作和變異操作都是對(duì)路線上的點(diǎn)進(jìn)行操作。標(biāo)準(zhǔn)的遺傳算法中包括染色體編碼、生成初始種群、計(jì)算適應(yīng)度、選擇操作、交叉操作和變異操作。在求解TSP 問題上，相較于其他啟發(fā)式算法，遺傳算法具有編碼簡單，易懂的特點(diǎn)。自然數(shù)編碼以一種直觀的方式展示點(diǎn)在路線中被訪問的順序。隨機(jī)地產(chǎn)生一定數(shù)量的無序數(shù)列，即生成一個(gè)初始種群。適應(yīng)度值可以通過計(jì)算路線距離的倒數(shù)獲得，然后對(duì)個(gè)體的適應(yīng)度進(jìn)行評(píng)估，選擇出較優(yōu)良的個(gè)體遺傳到下一代，進(jìn)而將選擇出來的個(gè)體進(jìn)行交叉和變異操作。隨機(jī)地交叉操作和變異操作為路線的選擇提供了更多的可能性。交叉操作是模擬生物有性繁殖過程中基因重組機(jī)制，而變異操作則是模擬生物在遺傳環(huán)境中因偶然因素引起的基因突變。經(jīng)過一代接一代地選擇、交叉、變異使種群向越來越優(yōu)（種群個(gè)體適應(yīng)度越來越高） 的方向進(jìn)化，直至終止條件結(jié)束遺傳算法操作，最后輸出適應(yīng)度最高的個(gè)體，則該個(gè)體為當(dāng)前最優(yōu)解，終止計(jì)算。

遺傳算法具有內(nèi)在的隱并行性和更好的全局尋優(yōu)能力的特點(diǎn)。其缺點(diǎn)是在求解結(jié)構(gòu)復(fù)雜的組合優(yōu)化問題中，因?yàn)樗阉骺臻g大，搜索時(shí)間長，往往會(huì)出現(xiàn)“早熟”的情況，局部尋優(yōu)能力較弱。而爬山算法具有優(yōu)良的局部擇優(yōu)能力。爬山算法從當(dāng)前位置出發(fā)，與鄰域位置的高度（適應(yīng)度） 比較，若發(fā)現(xiàn)鄰域位置的高度大于當(dāng)前位置的高度，則將該鄰域位置取代當(dāng)前位置，否則留在原位，以此方式向高處攀登。爬山算法局部擇優(yōu)能力強(qiáng)的特點(diǎn)能夠彌補(bǔ)遺傳算法局部尋優(yōu)能力較弱的缺陷。此外，本文采用期望值輪賭選擇法執(zhí)行選擇操作，輪賭選擇法能夠避免種群中一個(gè)性狀優(yōu)良的個(gè)體被選擇多次，從而讓更多的個(gè)體被選擇進(jìn)入到下一代，以提高種群的多樣性。因此，輪賭法可以緩解遺傳算法容易出現(xiàn)“早熟”的情況。

（1） 染色體編碼?？紤]到配送線路優(yōu)化問題的特點(diǎn)，本文采用自然數(shù)編碼方式給每個(gè)客戶按順序進(jìn)行編碼，客戶依次編碼為：1，2，3，…，n。由1…n之間的自然數(shù)隨機(jī)地生成一個(gè)無重復(fù)數(shù)字的序列，然后根據(jù)約束條件將配送中心的編碼“0”插入到序列中得到新的序列。例如完成9 個(gè)客戶的配送，隨機(jī)產(chǎn)生一個(gè)序列“872134956”，根據(jù)約束條件將“0”插入到序列中，得到新的序列“087213049560”。具體如何根據(jù)約束條件插入編碼“0”，將在下文中的確定適應(yīng)度函數(shù)部分中闡述。因?yàn)榫幋a“0”代表配送中心，所以新序列“087213049560”意味著需要調(diào)用2 輛車投入配送工作?？蛻?，7，2，1，3 由車輛1 完成配送，行駛線路為“0-8-7-2-1-3-0”；客戶4，9，5，6 由車輛2 完成配送，行駛線路為“0-4-9-5-6-0”。本文混合遺傳算法中的選擇操作、變異操作、交叉操作和爬山操作都是對(duì)未插入“0”的序列進(jìn)行操作，而計(jì)算個(gè)體和種群的適應(yīng)度則是使用插入“0”后的新序列。

（2） 生成初始種群。根據(jù)上文染色體編碼的過程重復(fù)地生成U（U是設(shè)定的初始種群的個(gè)體數(shù)量） 個(gè)序列。一個(gè)序列就代表了一個(gè)個(gè)體，這U個(gè)序列組成一個(gè)初始種群。

（3） 確定適應(yīng)度函數(shù)。遺傳算法通過計(jì)算個(gè)體的適應(yīng)度值來衡量個(gè)體的優(yōu)劣。依據(jù)個(gè)體的適應(yīng)度值對(duì)個(gè)體做選擇操作，個(gè)體的適應(yīng)度值越高，其被選擇保留到下一代的概率就越大。本文通過對(duì)所有車輛的總旅程數(shù)D進(jìn)行數(shù)值變換得到種群個(gè)體的適應(yīng)度值。

計(jì)算所有車輛的總旅程數(shù)時(shí)，車輛完成配送需要滿足以下約束條件：①每輛車需要在時(shí)間T內(nèi)從配送中心出發(fā)，完成各自的配送任務(wù)后再回到配送中心；②每輛車配送的客戶的需求量之和不大于其最大裝載數(shù)量Q；③每輛車沿特定線路為客戶配送貨物所行駛的距離之和不大于其最大行駛距離L。根據(jù)以上三個(gè)約束條件將配送中心的編碼“0”插入到序列中，產(chǎn)生新的序列。其插入步驟如下：設(shè)“872134956”為一個(gè)序列。①在序列的第一個(gè)客戶編碼前插入配送中心“0”，得到“0872134956”。②再將一個(gè)“0”插入到第一個(gè)客戶編碼的后面，得到“08072134956”，判斷配送線路“0-8-0”是否滿足上面三個(gè)約束條件；若滿足，則將“0”右移一位得到“08702134956”，判斷配送線路“0-8-7-0”是否滿足約束條件；若還是滿足，將“0”再右移一位，得到“08720134956”，繼續(xù)判斷配送線路“0-8-7-2-0”是否滿足約束條件；若還是滿足，又將“0”右移一位得到“08721034956”，判斷配送路線“0-8-7-2-1-0”約束條件；設(shè)此時(shí)不滿足，則將“0”左移一位得到“08720134956”，由此得到第一輛車的配送線路“0-8-7-2-0”。③插入第三個(gè)“0”得到“087201034956”，此時(shí)判斷“0-1-0”是否滿足約束條件。以這樣的方式進(jìn)行下去，直至最后一個(gè)客戶編碼的后面插入了“0”，得到若干條配送路線，這若干條配送線路組成了一個(gè)配送方案。設(shè)得到配送線路的條數(shù)為K，因此這個(gè)配送方案需要使用K輛車完成配送工作。計(jì)算每輛車的行駛距離，然后將每輛車的行駛距離相加，求得總和為D。式（7） 對(duì)D進(jìn)行數(shù)值變換得到個(gè)體的適應(yīng)度函數(shù)fi，其中Di表示的是個(gè)體i的所有參與配送工作車輛行駛距離的總和。

（4） 選擇操作。標(biāo)準(zhǔn)的遺傳算法中，選擇操作通常使用輪賭選擇法，而輪賭法在種群進(jìn)化到一定的代數(shù)后，種群中各個(gè)體間的適應(yīng)度差距很小，被選擇的概率相差微乎其微，因此傳統(tǒng)的輪賭法很難體現(xiàn)出擇優(yōu)的特性，并且再次進(jìn)行選擇時(shí)，被選擇過的較優(yōu)個(gè)體可能再次以較大的概率被選中。此乃遺傳算法出現(xiàn)“早熟”現(xiàn)象的重要原因之一。本文將期望值嵌入到輪賭選擇中，這種選擇方式使較優(yōu)個(gè)體以更大的概率被選擇保留下來，并且當(dāng)再次執(zhí)行選擇操作時(shí)，被選擇過的個(gè)體將以更小的概率被選擇，以此改進(jìn)傳統(tǒng)輪賭選擇法的不足。期望值輪賭選擇法通過降低被選擇個(gè)體的期望值的方式，使下一次做選擇操作時(shí)，被選擇過的個(gè)體將以較低的概率再一次被選中，進(jìn)而提高新種群的多樣性。期望值輪賭選擇法的應(yīng)用步驟如下：

①計(jì)算當(dāng)前種群中每個(gè)個(gè)體的生存期望值，計(jì)算個(gè)體i的生存期望值Ei見公式（8），U是種群中個(gè)體的數(shù)量，fi為個(gè)體i的適應(yīng)度值。

②根據(jù)個(gè)體的期望值，使用輪賭法選擇出1 個(gè)個(gè)體，判斷被選擇個(gè)體的生存期望值是否小于0，若小于0 則使用輪賭法重新選擇。如果種群中所有個(gè)體的期望值都小于0，那么就選擇期望值最大的個(gè)體。

③將被選擇的個(gè)體的期望值都減去0.5。例如，當(dāng)個(gè)體的期望值為0.3 時(shí)，被選擇后，其期望值為-0.2，下一次執(zhí)行選擇操作時(shí)該個(gè)體將不會(huì)被選中（種群中所有個(gè)體的期望值都小于0 時(shí)例外）。

④重復(fù)步驟②、③，再選擇1 個(gè)個(gè)體出來，得到2 個(gè)個(gè)體。將選擇出來的2 個(gè)個(gè)體進(jìn)入交叉操作。

（5） 交叉操作。對(duì)選擇出來的2 個(gè)個(gè)體進(jìn)行交叉操作。本文用的是部分匹配交叉法（PMX）。具體步驟結(jié)合圖1 說明如下：

①根據(jù)給定的交叉概率Pc判斷是否對(duì)選擇出來的兩個(gè)個(gè)體進(jìn)行交叉，若交叉則進(jìn)行交叉操作，若不交叉則直接保留這2 個(gè)個(gè)體做下一步變異操作。

②假設(shè)需要進(jìn)行交叉的兩個(gè)序列分別是：A=4598320671，B=1487965032。隨機(jī)產(chǎn)生2 個(gè)不同序號(hào)的交叉位，假設(shè)隨機(jī)交叉位是3 和6。

③交叉區(qū)域?yàn)椋篈=45|98320|671，B=14|87965|032。將A 中的交叉區(qū)域與B 中的交叉區(qū)域互換，交叉后的序列為A=45|87965|671 和B=14|98320|032。

④對(duì)于交叉后的序列A=45|87965|671 中交叉區(qū)域以外的序列中出現(xiàn)的重復(fù)編碼，取A 序列中交叉區(qū)域內(nèi)的編碼位置所對(duì)應(yīng)B 序列的位置上的數(shù)字做替換。A 序列中只替換交叉區(qū)域外的編碼，交叉區(qū)域內(nèi)的編碼不做替換。本例中，A 中出現(xiàn)的重復(fù)編碼有“7”、“6”、“5”。交叉區(qū)域的編碼不動(dòng)，交叉區(qū)域以外的編碼段做替換：7→8；6→2；5→0。執(zhí)行上述操作后得到：A=40|87965|281。繼續(xù)檢查到A 序列存在重復(fù)編碼“8”，做替換8→9，得到A=40|87965|291。再次檢查到A 序列中存在重復(fù)編碼“9”，做替換9→3，得到A=40|87965|231。此時(shí)A 序列中沒有重復(fù)的編碼了。同樣也對(duì)B=14|98320|32 重復(fù)編碼進(jìn)行檢查并做替換。

（6） 變異操作。對(duì)執(zhí)行完交叉操作后的個(gè)體進(jìn)行逆轉(zhuǎn)變異操作。逆轉(zhuǎn)變異操作是對(duì)單個(gè)個(gè)體的部分序列進(jìn)行重新排序操作。逆轉(zhuǎn)變異操作一方面可以提高了遺傳算法的局部搜索能力，另一方面在一定程度上豐富種群的多樣性。逆轉(zhuǎn)變異操作具體步驟是：

①根據(jù)給定的變異概率Pm判斷是否對(duì)個(gè)體進(jìn)行變異操作。對(duì)于不做變異操作的個(gè)體直接保留下來。對(duì)于執(zhí)行過變異操作的個(gè)體，進(jìn)行變異操作后再保留下來。

②隨機(jī)生成兩個(gè)范圍在1，…，n且不相等自然數(shù)，將這兩個(gè)自然數(shù)作為變異的逆轉(zhuǎn)點(diǎn)，然后翻轉(zhuǎn)兩個(gè)逆轉(zhuǎn)點(diǎn)之間的編碼值。例如：隨機(jī)生成的逆轉(zhuǎn)點(diǎn)是3 和6，A=87|2314|956。逆轉(zhuǎn)變異后，A=87|4132|956。

（7） 嵌入爬山算法。當(dāng)前種群所有個(gè)體執(zhí)行完選擇、交叉和變異操作后，重新計(jì)算種群中各個(gè)體的適應(yīng)度值，選出適應(yīng)度值最高（最優(yōu)） 的個(gè)體進(jìn)入如下的爬山操作。①隨機(jī)生成兩個(gè)不相等自然數(shù)且取值范圍在1，…，n。將這兩個(gè)自然數(shù)作為交換位，并交換這兩個(gè)自然數(shù)對(duì)應(yīng)序列位置上數(shù)值。②利用適應(yīng)度函數(shù)計(jì)算交換位置后的個(gè)體的適應(yīng)度值是否增加，若增加則將交換位置后的個(gè)體替換當(dāng)前最優(yōu)個(gè)體。否則，不進(jìn)行替換。③重復(fù)①、②操作，直至達(dá)到設(shè)定的循環(huán)次數(shù)ClimbNum（ClimbNum為設(shè)定的爬山次數(shù)）。

（8） 記錄最優(yōu)個(gè)體。設(shè)置一個(gè)記憶器，將做完爬山操作的個(gè)體記錄下來（做完爬山操作后的個(gè)體，其適應(yīng)度值是當(dāng)前種群中適應(yīng)度值最高的個(gè)體）。該操作能夠?qū)⒚恳淮N群中最優(yōu)個(gè)體保留下來。

執(zhí)行完上述選擇、交叉、變異操作和爬山操作后得到了一個(gè)新的種群。對(duì)新的種群循環(huán)執(zhí)行選擇、交叉、變異操作、爬山操作和記錄最優(yōu)個(gè)體，直至達(dá)到循環(huán)終止條件。本文設(shè)定當(dāng)種群進(jìn)化到最大代數(shù)Gmax作為循環(huán)終止條件。終止條件結(jié)束后，選擇出記憶器中的最優(yōu)個(gè)體，即得到混合遺傳算法的最優(yōu)解。上述混合遺傳算法的過程可以用圖2 來描述。

圖1 交叉實(shí)例操作流程

圖2 混合遺傳算法流程

3 算例分析

3.1 需求描述

本文以南昌某生鮮電子商務(wù)公司的日常生鮮農(nóng)產(chǎn)品配送工作為案例，進(jìn)行算例分析。該公司有一個(gè)配送中心，某日需要對(duì)95 個(gè)客戶配送生鮮農(nóng)產(chǎn)品。配送時(shí)使用塑料筐的尺寸為：長85cm、寬60cm、高45cm。每個(gè)客戶的需求量見表1。統(tǒng)一使用江鈴全順8 座GLX型車輛進(jìn)行配送，車輛最大裝載量為Q=19 筐，車輛的最大行駛距離為L=600 公里。所有客戶的訂單在前一天晚上完成打包裝筐。配送車輛于早上6:00 出發(fā)，在上午10 點(diǎn)前完成配送并回到配送中心。因此配送車輛需在240 分鐘時(shí)間內(nèi)從配送中心出發(fā)完成配送，并回到配送中心，即T=240 分鐘。

3.2 實(shí)驗(yàn)前準(zhǔn)備工作

本文通過百度坐標(biāo)拾取系統(tǒng)獲取每個(gè)客戶的經(jīng)緯度，然后利用經(jīng)緯度通過百度地圖“JavaScript API v3.0”接口編寫JavaScript 語言程序批量獲取配送中心到每個(gè)客戶以及每兩個(gè)客戶之間的車輛行駛距離和行駛時(shí)間。因?yàn)樵趯?shí)際配送中，車輛從A 點(diǎn)到B 點(diǎn)和從B 點(diǎn)到A 點(diǎn)行駛的可能不是同一條道路，即車輛從A 點(diǎn)到B 點(diǎn)和從B 點(diǎn)到A 點(diǎn)的行駛距離和時(shí)間是不同的，故本文需要獲取雙向距離和時(shí)間。本文獲取的行駛距離和行駛時(shí)間數(shù)據(jù)為早上7～8 點(diǎn)百度地圖導(dǎo)航提供的數(shù)據(jù)，此時(shí)間段正好是配送時(shí)間；但獲取車輛行駛距離和行駛時(shí)間信息涉及的數(shù)據(jù)量較大，篇幅受限，故此過程不在文中展示。本文使用Java 語言編寫程序，實(shí)現(xiàn)混合遺傳算法。執(zhí)行算法使用的是普通桌面辦公臺(tái)式計(jì)算機(jī)，性能中等，搭載的是Windows7 操作系統(tǒng)。

表1 客戶的需求量 單位：筐

3.3 實(shí)驗(yàn)數(shù)據(jù)分析

給配送中心和95 個(gè)客戶依次編碼為0，1，2，3，…，95。設(shè)初始種群數(shù)量U=10 000，最大進(jìn)化代數(shù)Gmax=1 000，交叉概率Pc=0.3，變異概率Pm=0.3，爬山操作的循環(huán)次數(shù)ClimbNum=90，車輛在每個(gè)配送點(diǎn)停留t=5 分鐘，在220 分鐘內(nèi)完成配送，預(yù)留20 分鐘預(yù)防突發(fā)事件的發(fā)生。

根據(jù)以上參數(shù)多次執(zhí)行算法，都能夠得出較優(yōu)的配送方案，配送距離分布在600～700 公里之間，使用車輛數(shù)在11～13 臺(tái)之間，算法執(zhí)行時(shí)間耗時(shí)220 秒左右。表2 給出的是使用車輛數(shù)最少的一次計(jì)算結(jié)果。表3 是該公司當(dāng)天實(shí)際使用的配送方案，該方案是公司配送人員通過多次送貨經(jīng)驗(yàn)總結(jié)出來的線路。對(duì)比兩套配送方案可見，使用混合遺傳算法得出的配送方案少使用了3 輛車，車輛的總里程也縮短了285.6 公里，并且配送時(shí)間最長的車耗時(shí)218 分鐘，即所有車輛均可在上午9:40 之前完成配送任務(wù)，并回到配送中心；而該公司實(shí)際使用的配送方案中，配送時(shí)間最長的車耗時(shí)255 分鐘，比混合遺傳算法得出的配送方案多了37 分鐘，并且不能在上午10 點(diǎn)前回到配送中心。

4 結(jié)論與展望

本文從分析南昌市某生鮮電商公司面臨的同城生鮮農(nóng)產(chǎn)品配送線路優(yōu)化問題入手，建立了該問題的數(shù)學(xué)模型，并創(chuàng)造性地設(shè)計(jì)了一種混合遺傳算法用于對(duì)同城生鮮農(nóng)產(chǎn)品配送線路優(yōu)化問題求解。此算法的新穎之處在于：（1） 局部尋優(yōu)能力較強(qiáng)的爬山算法嵌入到遺傳算法當(dāng)中，從而改善了遺傳算法局部尋優(yōu)能力不足的缺點(diǎn)；（2） 使用期望值輪賭法執(zhí)行遺傳算法中的選擇操作，有效避免了遺傳算法中的早熟現(xiàn)象。

筆者根據(jù)此算法開發(fā)了一個(gè)WEB 應(yīng)用程序。該系統(tǒng)可以根據(jù)生鮮農(nóng)產(chǎn)品電商公司的實(shí)際業(yè)務(wù)發(fā)展情況，添加和刪減客戶，修改客戶的需求量。在新增客戶時(shí)，先通過百度坐標(biāo)拾取系統(tǒng)獲取客戶位置的經(jīng)緯度，然后將客戶的準(zhǔn)確經(jīng)緯度添加進(jìn)數(shù)據(jù)庫，系統(tǒng)就能通過百度地圖導(dǎo)航系統(tǒng)快速地獲取配送車輛從配送中心到新客戶以及新客戶與其他客戶之間的行駛距離和行駛時(shí)間，根據(jù)這些新數(shù)據(jù)，設(shè)置相應(yīng)的參數(shù)就能夠迅速地重新規(guī)劃出新的送貨線路。將通過混合遺傳算法求得的配送路線與公司當(dāng)前實(shí)際采用的配送路線對(duì)比，發(fā)現(xiàn)按照混合遺傳算法求得的路線進(jìn)行配送，既可以減少投入運(yùn)行的配送車輛，又可以節(jié)約配送車輛的行駛距離，從而幫助生鮮電商公司節(jié)省配送成本。

最后，需要指出的是，雖然本文提出的數(shù)學(xué)模型和混合遺傳算法能夠快速地幫助生鮮電商公司提供配送線路優(yōu)化方案，但是還存在以下兩個(gè)問題需要進(jìn)一步探討：①種群數(shù)量、繁殖次數(shù)、變異率和交叉率等參數(shù)是如何影響算法尋優(yōu)能力的？要如何根據(jù)客戶的數(shù)量來設(shè)置恰當(dāng)?shù)姆N群數(shù)量、繁殖次數(shù)、變異率和交叉率等參數(shù)才能提高算法的執(zhí)行效率并使算法有較強(qiáng)的尋優(yōu)能力？②如何在算法中整合進(jìn)路況信息，以便使系統(tǒng)更加適合企業(yè)的實(shí)際情形？因?yàn)榻?jīng)常存在某些路段出現(xiàn)臨時(shí)修路的情況，這時(shí)通過百度地圖獲得的數(shù)據(jù)往往與實(shí)際配送情況不符。能否讓送貨司機(jī)記錄實(shí)際的送貨時(shí)間和車輛碼表行駛的里程數(shù)，并將這些數(shù)據(jù)更新進(jìn)系統(tǒng)，作為計(jì)算配送線路的依據(jù)。

表2 混合遺傳算法得出的優(yōu)化結(jié)果

表3 現(xiàn)公司使用配送方案