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

張 璇，陳 峰

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

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

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

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

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

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

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

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

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

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

1.1 問題描述

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

給定：

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

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

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

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

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

1.2 數(shù)學(xué)模型

為了降低總成本(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ā)式算法.該算法的特點(diǎn)是計算速度快，占用系統(tǒng)資源少且可得到較好的計算結(jié)果，可為分支定界算法提供初始上界.步驟如下.

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

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

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

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

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

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

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

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

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

2.2 分支定界算法

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

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

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

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

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

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

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

2.2.4算法流程

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

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

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

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

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

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

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

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

3 數(shù)值實(shí)驗(yàn)與結(jié)果分析

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

3.1 算法對比

表1 承運(yùn)車信息Tab.1 Information of carrier vehicle

表2 實(shí)驗(yàn)設(shè)計Tab.2 Design of experiments

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

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

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

(12)

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

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

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

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

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

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

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

4 結(jié)語

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