面向汽車入廠物流系統(tǒng)的訂單量協(xié)同模型及其算法

張 璇，陳 峰

(上海交通大學 機械與動力工程學院，上海 200240)

汽車零部件入廠物流是汽車物流的重要組成部分，汽車制造商根據(jù)生產(chǎn)計劃確定每段時間每種零部件的需求量，第三方物流公司根據(jù)需求從供應商處取貨并配送到制造商倉庫，該過程需要制造商、供應商和第三方物流的有效合作，方可避免不必要的費用支出.入廠物流對于減少庫存和實現(xiàn)準時制生產(chǎn)都是至關重要的.

目前，有關物流協(xié)同模式的研究主要集中在庫存路徑的問題上.所采用的方法主要有以下幾種.

(1)基于分解的啟發(fā)式算法.該方法一般將原問題分解為多個子問題，如將庫存路徑問題分解為庫存問題和路徑問題，再分階段進行求解.例如：Lei等[1]提出兩階段算法，第一階段得到直運問題的解，第二階段對第一階段的解進行改善；Raa[2]提出基于插入構造和局部搜索的啟發(fā)式算法；Absi等[3]提出兩階段迭代算法，基于批量大小和分配決策進行迭代.

(2)搜索算法.例如：Moin等[4]提出的分散搜索算法；Belo-Filho等[5]提出的改進的領域搜索法；Vansteenwegen等[6]提出的迭代局部搜索算法.

(3)元啟發(fā)式算法.例如：陳譽文等[7]提出的基于聚類算法構造初始解的禁忌搜索啟發(fā)式算法；Mirzaei等[8]提出的基于模擬退火以及禁忌搜索的啟發(fā)式算法；Azadeh等[9]提出的基于遺傳算法的求解方法.

(4)精確算法.例如：Berman等[10]提出基于非線性規(guī)劃的Lagrange松弛啟發(fā)式和分支定界法；Archetti等[11]提出分支剪枝算法.

(5)其他方法.例如：Soysal等[12]建立了問題的數(shù)學模型并用CPLEX進行求解；Zhong等[13]提出結合DC(Difference of Convex)規(guī)劃和分支定界法的最速下降混合算法.

以上研究并未考慮訂單配送量與需求量的差異可能會對成本產(chǎn)生的影響.因此，本文研究基于訂單量的入廠物流協(xié)同問題，建立數(shù)學模型并提出相應算法，以期降低生產(chǎn)系統(tǒng)的總成本.

1 問題描述與數(shù)學模型

1.1 問題描述

本文考慮訂單配送量與需求量的差異可能帶來的成本增加或減少.對于每個訂單，如果配送量小于需求量，會產(chǎn)生缺貨帶來的風險成本，但可降低其庫存成本；如果配送量大于需求量，會產(chǎn)生多余貨量的庫存成本，但可降低缺貨造成的風險成本.此外，考慮到目前物流領域存在貨車空載率較高的狀況，通過調整訂單的配送量，可降低貨車的空載率，減少貨車的非滿載成本.

給定：

承運車的集合{Vk|k=1,2,…,K}，其中每輛車的屬性包括最大可用容積、固定成本、單位運輸成本和單位空載成本；

經(jīng)銷商的集合{Ai|i=1,2,…,S}，其中每個經(jīng)銷商可能有1個或多個入廠訂單，經(jīng)銷商的屬性包括經(jīng)度和緯度；

入廠訂單的集合{On|n=1,2,…,N}，其中每個訂單屬于1個經(jīng)銷商且僅由1輛承運車配送，訂單屬性包括所屬供應商、需求量、單位缺貨成本、單位庫存成本和最低配送量；

1個入廠物流倉庫，所有訂單最終配送到該倉庫，其屬性包括經(jīng)度和緯度，訂單和訂單之間、訂單和倉庫之間的距離通過經(jīng)緯度計算得到.

總成本包括承運車的固定成本、運輸成本、空載成本和訂單的缺貨成本以及庫存成本.承運車的運輸成本為承運車單位運輸成本與總運輸距離的乘積；空載成本為承運車單位空載成本與空載容積的乘積；訂單的缺貨成本為訂單單位缺貨成本與訂單需求量超過實際配送量的部分的乘積；庫存成本為訂單單位庫存成本與訂單實際配送量超過需求量的部分的乘積.

1.2 數(shù)學模型

為了降低總成本(C)，建立混合整數(shù)規(guī)劃優(yōu)化模型：

(1)

(2)

(3)

(4)

(5)

x0jk=0

(6)

(7)

(8)

(9)

(10)

Nxijk+ui-uj≤N-1

(11)

式中：

2 優(yōu)化算法

2.1 啟發(fā)式算法

本文提出基于貪婪規(guī)則的啟發(fā)式算法.該算法的特點是計算速度快，占用系統(tǒng)資源少且可得到較好的計算結果，可為分支定界算法提供初始上界.步驟如下.

(1)將供應商按訂單總量的大小進行降序排列，將每個供應商的訂單按訂單量多少進行降序排列，得到未裝載訂單序列(I)并初始化可用承運車序列(D)；

(3)嘗試將與Oi′同屬1個供應商的其他未裝載訂單按照需求量裝入Vk；

(4)比較以下3個方案：

① 裝載Oi′，裝載量為Vk的剩余可用容積(vk)，則

② 選擇Vk已經(jīng)裝載的某個訂單Oj，多裝載一部分貨量，則

③ Vk非滿載，則Vk的非滿載成本

(5)如果某輛車的裝載量比較小，則可以將其換為成本比較低的小型車.對于每輛車的運輸路徑，選擇所有的可行路徑中運輸成本最小的路徑，算法結束.

啟發(fā)式算法流程如圖1所示.

圖1 啟發(fā)式算法流程圖Fig.1 Heuristics flow chart

2.2 分支定界算法

分支定界算法是整數(shù)規(guī)劃中一種常用的精確算法，主要包括分支策略、上下界設計以及搜索模式與支配規(guī)則3部分，其基本思想是基于分支策略，將原問題分解成規(guī)模較小的子問題.

2.2.1分支策略 分支策略是將問題分割成子問題的方法，即如何確定分支節(jié)點，每個節(jié)點對應1個子問題和相應的子空間.本文將承運車配送訂單視為1個裝箱問題，每個訂單的每種可能的配送量作為1個節(jié)點.

解的搜索從第1層開始，第1個訂單選擇1種可能配送量和可能裝入的車，如果該訂單有Q1種可能的配送量，則第1層可能會有Q1K個節(jié)點；如果第2個訂單有Q2種可能的配送量，對應Q2K種選擇方案，則第2層可能有Q1Q2K2個節(jié)點，依此類推.如果Q1=Q2=…=QN=Q，則N個訂單最終最多會產(chǎn)生QNKN個節(jié)點.實際中，部分節(jié)點不可行或者節(jié)點的下界大于全局上界(Bu)，則該部分節(jié)點會被剪枝，所以實際節(jié)點數(shù)Nr

2.2.2上下界設計 合理的上下界設計可以有效剪枝，縮小搜索空間，從而提高搜索效率.本文模型的優(yōu)化目標為總成本最小，當1個節(jié)點的局部下界大于Bu時，該分支將被剪除.以啟發(fā)式算法的解作為初始上界進行搜索，當尋找到比當前上界更小的解時，更新Bu.

對于1個節(jié)點的下界，首先計算該節(jié)點全部尚未裝載訂單的最低配送量qL和所有承運車的剩余可用容積vR.如果qL≤vR，則節(jié)點的下界為當前已裝載訂單的缺貨成本和庫存成本，以及已經(jīng)裝載了訂單的承運車的固定成本和最小運輸成本.如果節(jié)點的下界不小于Bu，則該節(jié)點被剪除.

2.2.3搜索模式與支配規(guī)則 分支定界的搜索模式包括深度優(yōu)先模式以及廣度優(yōu)先模式.深度優(yōu)先模式優(yōu)先搜索深層節(jié)點直到葉節(jié)點或者剪枝；廣度優(yōu)先模式則同時計算同一層的多個節(jié)點，將會占用更多的系統(tǒng)內存.因此，本文選擇深度優(yōu)先模式進行搜索.

支配規(guī)則為優(yōu)先選擇排序較為靠前的訂單進行分支.

2.2.4算法流程

(1)以啟發(fā)式算法的解為初始上界，初始化I.

(2)如果存在未裝載訂單，選擇I中的第1個訂單Oi，并將Oi從I中刪除；否則轉步驟(5).

(3)如果已遍歷Oi的所有可能配送量和選車方案，轉步驟(2)；否則選擇一個方案作為一個分支節(jié)點.

(4)如果選擇的配送量不超過所選車的剩余可用容積且節(jié)點下界(Bl)小于Bu，轉步驟(2)；否則轉步驟(3).

(5)以所有可能配送路徑中運輸成本最低的路徑作為該節(jié)點的路徑，計算該節(jié)點的總成本，如果C

(6)Bu為最優(yōu)解，算法結束.

分支定界算法流程如圖2所示.

圖2 分支定界算法流程圖Fig.2 Branch and Bound algorithm flow chart

3 數(shù)值實驗與結果分析

用C#語言在Visual Studio平臺開發(fā)測試程序，調用ILOG CPLEX求解混合整數(shù)規(guī)劃模型進行數(shù)值實驗.

3.1 算法對比

表1 承運車信息Tab.1 Information of carrier vehicle

表2 實驗設計Tab.2 Design of experiments

表3 模型與算法總成本對比Tab.3 Comparation of model and algorithms total cost

3.2 訂單量協(xié)同效應

為分析訂單量協(xié)同對總成本的影響，將式(9)替換為

(12)

上式表示每個訂單的配送量等于需求量，即得到非訂單量協(xié)同問題的數(shù)學模型.

利用表2中的數(shù)據(jù)以及CPLEX模型求解非訂單量協(xié)同問題的數(shù)學模型，求解時間上限為30 min.將計算結果與訂單量協(xié)同問題的總成本進行比較，結果如表4所示.可以看出，訂單量協(xié)同可以有效降低系統(tǒng)的總成本.

表4 訂單量協(xié)同與非訂單量協(xié)同的總成本對比Tab.4 Comparation of collaborative and non-collaborative total cost

3.3 訂單總需求量對成本因素的影響

為了分析訂單總需求量對固定成本、運輸成本、庫存成本、缺貨成本、空載成本和總成本的影響，指定可用承運車的集合為{C60,C40,C40}，選擇同一個供應商的15個訂單，適當調整訂單總需求量，分析總成本的變化趨勢.對于每組數(shù)據(jù)，分別用CPLEX數(shù)學模型以及分支定界算法進行求解，時間上限為30 min，選擇兩者中總成本較低者進行對比，結果如表5所示.

表5 訂單總需求量對成本的影響Tab.5 Impact of total order quantity on costs

可以看出，當訂單總需求量較小時，只使用2輛承運車運輸所有訂單.此時，有些訂單配送量小于其需求量，即產(chǎn)生缺貨成本，但缺貨成本小于多使用1輛承運車對應的固定成本、運輸成本和空載成本.隨著訂單總需求量的增加，缺貨成本的增加量超過了多使用1輛承運車對應的固定成本、運輸成本和空載成本，故使用3輛承運車.此時，固定成本和運輸成本增加，缺貨成本為0并產(chǎn)生庫存成本和空載成本.可見，訂單的總需求量對總成本的影響主要體現(xiàn)為權衡不同的成本因素，以使總成本最低.

4 結語

本文研究了基于訂單量的入廠物流協(xié)同，建立了混合整數(shù)規(guī)劃模型，提出了啟發(fā)式算法和分支定界法.通過數(shù)值實驗驗證了模型和算法的有效性.結果表明，訂單量協(xié)同可以有效降低系統(tǒng)的總成本；訂單的總需求量對總成本的影響主要體現(xiàn)為權衡不同成本因素以使總成本最低.