基于SVM的生鮮食品冷鏈共配實時訂單分類模型*

□ 高 甜，伍景瓊，徐浩然，蘇 娜

(1.昆明理工大學 交通工程學院，云南 昆明 650500；2.上海德邦物流有限公司，上海 200000)

1 引言

隨著人民生活水平的不斷提高，人民對于生鮮食品的品質也越來越重視。但是，由于生鮮食品的易腐性以及時效性等，使得生鮮食品冷鏈共配發(fā)展滯后，導致客戶日益增長的優(yōu)質生鮮食品需求與落后的生鮮食品冷鏈共配現狀存在顯著矛盾。

為有效緩解這一矛盾，大量學者從客戶生鮮食品訂單需求角度展開研究。Jean-Charles Créput等[1]針對新的客戶需求，利用自組織映射神經網絡對客戶訂單進行聚類分析。張潛等[2]提出先用優(yōu)先級綜合聚類分析法對客戶進行分類，再用改進遺傳算法來求解多目標車輛路徑問題的優(yōu)化方法。崔麗[3]針對需求驅動下動態(tài)城市車輛調度問題，提出先對客戶需求訂單進行分類，然后再對車輛調度問題進行求解。Alan Slater[4]針對新客戶需求，提出基于需求預測的動態(tài)調度系統(tǒng)，用閉環(huán)的專家系統(tǒng)對需求進行預測。Naccache[5]基于B2C電子商務對訂單合并運輸問題進行了研究，以運輸成本最小為目標，求解最佳車輛調度方案。Chen等[6]針對實時訂單需求，提出了采用列生成的動態(tài)辦法來求解帶時間窗的車輛路徑問題。李琳等[7]提出了將禁忌搜索算法與插入算法相結合進行求解訂單預測模型，可以有效地利用電子訂貨系統(tǒng)預測訂單的未來信息。孫劉誠，孫焰[8]研究了帶訂單選擇車輛路徑問題，以最大化企業(yè)經濟效益為優(yōu)化目標，建立了混合整數規(guī)劃模型，發(fā)現通過訂單交換和協(xié)調，不僅能夠提高企業(yè)的利潤，并能夠一定程度上減少車輛的行駛距離。Chen[9]則考慮了組合拍賣機制中的運輸企業(yè)的訂單選擇行為，并將其剝離出來形成獨立的子問題進行研究。

現有研究主要針對一般商品的共同配送訂單進行分析與預測，而生鮮食品具有時效性、多樣性、易腐性等特點，現實配送中不僅需要考慮個別客戶的緊急訂單，還要考慮某些生鮮食品易腐敗的特點。因此，本文建立以實時客戶訂單為基礎的生鮮食品冷鏈共配實時訂單分類模型，從訂單篩選、訂單分類及確定服務優(yōu)先級三個階段對實時訂單進行分析，以保證生鮮食品冷鏈共配的準確性與時效性。

2 支持向量機分類算法

支持向量機(Support Vector Machine，SVM)是由Vapnik基于統(tǒng)計學習理論的提出的一種針對分類和回歸問題的新型機器學習方法[10]。SVM具備較為完全整的數學理論，其具有較強的泛化能力，在解決小樣本、非線性及高維空間模式識別的問題上具有較好的效果。支持向量機是一種監(jiān)督學習模型，可以通過對歷史數據的學習，來解決分類問題。

支持向量機的原理是隨機產生一個超平面，然后移動它直至不同分類的點剛好位于超平面的不同側面，并且保證分類的精度。根據SVM的原理，支持向量機可以完美的實現對線性可分數據的分類。SVM的數學模型如下：把兩類數據輸入到在一個n維空間中，支持向量機通過構造一個和這兩類數據邊界距離最遠的超平面，來實現對這兩類數據的分類。給定一個SVM的訓練集{xi,yi}，其中i=1,2,L，l，yi∈{-1,1},xi∈RD(xi包含D個特征)。用來區(qū)分兩類數據的超平面可以表示為wx+b=0，其中w是超平面的法向量，|b|/‖w‖是超平面距原點的垂直距離。全部的訓練樣本滿足條件：

yi(xiw+b)-1+ξi≥0,ξi≥0,?i

(1)

引入松弛變量來解決線性不可分的問題，其中，ξi≥0，i=1,2,L,l。通過式(1)，可以將最大化支持向量機的界線轉換成解決如下的最優(yōu)化問題：

(2)

s.t.yi(xiw+b)-1+ξi≥0,ξi≥0,?i

(3)

式中：C為懲罰系數，C具有平衡松弛變量和分類范圍的大小的作用。(3) 式是一個凸二次優(yōu)化的問題，其解為：

(4)

常用的支持向量機核函數有多項式函數、徑向基函數、復合核函數和Sigmoid函數等，通過這些不一樣的核函數可以構造出相應的支持向量機。核函數的選擇對構造支持向量機有著至關重要的影響，選用適合的核函數，可以降低計算的復雜度，得到更好的分類結果。

支持向量機在求解多類分類問題時，主要的解決辦法有兩種：一種是基于原來的SVM優(yōu)化函數，引入多類機制對其進行改進，使其擴展為多類支持向量機，改進后的SVM可以直接進行多類分類。但是，這種解決多類分類問題方法具有較為復雜的目標函數，很難實現。另一種是通過結合多個兩類SVM組成一個多類分類器，通過這些兩類SVM間接的進行多類分類。經常用到的組合多個兩類SVM的方法有四種：一對多法、一對一法、導向無環(huán)圖法和二叉樹法。本文采用一對一法來解決客戶訂單的多類分類問題。

一對一法中每一個二值分類器僅對所有類別中的兩類進行分類處理，可以減少樣本學習的時間。同時，每一個兩類分類器的學習樣本是均衡的，訓練精度較高。

3 生鮮食品冷鏈共配實時訂單分類模型

建立以實時客戶訂單為基礎的生鮮食品冷鏈共配實時訂單分類模型，從訂單篩選、訂單分類及確定服務優(yōu)先級三個階段對實時訂單進行分析，及時響應客戶的實時需求，保證生鮮食品冷鏈共配的準確性與合理性。

3.1 需求訂單篩選

需求訂單篩選，是以客戶訂單處理周期為依據，確定每個周期內所需要處理的相關客戶訂單。為了方便建模，本文假定配送中心的客戶訂單處理周期是T(包括訂單分類時間和車輛調度時間)，在周期T開始時，配送中心需要將該周期內處理的訂單篩選出來，為之后的客戶訂單處理階段做準備。

在周期T內處理的訂單需要滿足以下條件：

(5)

(6)

通式(5)和(6)篩選出生鮮食品客戶訂單，將篩選出的訂單輸入到下一個階段，對其進行分類。每個訂單處理周期都不斷地重復這個過程，訂單篩選的過程如圖1所示。

圖1 訂單篩選示意圖

3.2 需求訂單分類

需求訂單分類階段主要是針對通過篩選階段的實時訂單，根據其相似屬性(內在與外在屬性)對其進行聚類分組。該階段主要分為兩個部分，首先進行特征參數的選取分析，然后采用支持向量機(SVM)對客戶訂單進行聚類分析。

3.2.1 特征參數的選取

基于生鮮食品的屬性和車輛調度的需求，本文選取了6個特征參數進行訂單分類處理。具體如下所示：

3.2.2 SVM算法聚類分組

使用支持向量機對生鮮食品客戶訂單進行分類，是通過對歷史生鮮食品訂單數支持向量機據的學習后，對訂單進行分類，得到訂單分類結果具有較好的客觀性?；谥С窒蛄繖C的訂單分類過程如下：

①對歷史客戶訂單進行分析，選取相關的特征參數，建立指標體系。

②根據指標體系中的特征參數，收集相關的歷史客戶訂單，構成支持向量機的訓練樣本集。

③根據支持向量機的分類算法對訓練樣本集進行訓練，獲取訂單分類的客觀規(guī)律。

④找到訓練集中的支持向量構造支持向量機決策函數。

⑤將待分類的客戶訂單輸入到決策函數中，從而得到分類結果。

3.3 確定客戶服務優(yōu)先級

確定客戶服務優(yōu)先級是在訂單分類確定后各個客戶組別的服務順序，然后根據服務順序制定合理的生鮮食品配送方案。生鮮食品具有時效性、多樣性、易腐性等特點，現實配送中不僅需要考慮個別客戶的緊急訂單，還要考慮某些生鮮食品易腐敗的特點。因此，配送企業(yè)需要綜合考慮各種影響因素，合理確定訂單的服務優(yōu)先級，來提高企業(yè)的服務水平和整體效益。

表1 多因素法確定客戶優(yōu)先級量化值計算

根據表1的計算結果，來確定客戶的服務優(yōu)先級，然后根據優(yōu)先級制定車輛調度方案。采用多因素法確定服務優(yōu)先級，可以較為全面的考慮各種影響因素，提高企業(yè)的效益。因此，生鮮食品企業(yè)需要綜合考慮各種影響因素，以快速響應客戶需求和企業(yè)效益水平為目標，科學地確定客戶服務優(yōu)先級。

3 算例分析

3.1 算例概述

本文假設某區(qū)域有3個生鮮食品配送中心，對周圍邊長為20km的正方形地域內的30個客戶提供配送服務，每個客戶的生鮮食品需求量都在2t以下，配送中心有10臺配送車輛，配送車輛的最大載重量為5t，蓄冷保溫箱的容量為1t，最大配送距離為60km。將客戶需求量按照常溫、冷藏、冷凍三個溫層的生鮮食品的比例(0.25:0.65：0.1)拆分[11]，每個生鮮食品的客戶訂單中包含3種溫層的生鮮食品。利用MATLAB隨機生成30個初始客戶的坐標和需求量，配送中心與初始客戶的坐標如表2所示。初始客戶的需求量如表3所示。

表2 配送中心與初始客戶位置坐標

表3 初始客戶需求量

3.2 算例求解

通過實時訂單分配模型對客戶訂單進行分組并確定其服務優(yōu)先級。為了方便操作，本論文假設訂單商品價值相差不大，商品的內兼容性和外兼容性均較好。因此，本文選擇客戶位置、時間窗和客戶的需求量3個指標作為聚類參數。在對客戶訂單進行分類之前，需要量化這些指標，如表4所示。

表4 初始客戶訂單分類指標量化值

采用MATLAB軟件在LibSVM工具包的基礎上對30個初始客戶訂單進行分類，選取多分類SVM中一對一組合方法，選擇RBF核函數。懲罰系數C和核參數的選擇主要采用網格搜索尋優(yōu)法。其基本思路是：分別選定C和的一個區(qū)間，確定步長，在選定的區(qū)間內，讓C和呈指數增長，不斷改變C和的組合，初步尋找兩者的最佳組合，然后確定準確率出現最高的一個小區(qū)間，并逐步縮短步長重復搜索，直至搜索結果精度變化不大為止，所得結果即為最優(yōu)化參數。利用MATLAB對客戶訂單進行分類，結果如圖2所示，驗證精度達93.333%，如圖3所示。

圖2 客戶訂單SVM分類結果

圖3 客戶訂單SVM分類精度

最終，客戶生鮮冷鏈共配實時訂單分配結果如表5所示，30個客戶被分成了7個組別。其中，組別1、組別3和組別6優(yōu)先配送；組別2和組別5次之；組別4中客戶數量最多，其優(yōu)先級為3；組別7則最后配送。

表5 客戶訂單分類結果

4 結論

為了高效妥善地解決隨機性、零散化的動態(tài)客戶需求，建立了基于支持向量機的生鮮食品冷鏈共配實時訂單分類模型，用來對訂單進行篩選、分類和確定服務優(yōu)先級，并通過算例驗證模型的有效性。該模型中支持向量機分類法能在較短的時間內求得共配訂單的分類結果，同時根據客戶位置、時間窗和客戶的需求量科學安排服務的先后順序，在節(jié)約企業(yè)成本的同時，最大程度地滿足了客戶的個性化需求。