基于動態(tài)規(guī)劃的物流配送優(yōu)化研究

[摘要] 針對物流配送費用最小化問題，統(tǒng)籌運輸費和存轉(zhuǎn)費，依據(jù)動態(tài)規(guī)劃和貝爾曼最優(yōu)化原理，提出基于矩陣運算的最小費用配送求解方法，為決策者提供了一種新的優(yōu)化方案。

[關(guān)鍵詞] 物流配送 動態(tài)規(guī)劃 優(yōu)化

一、問題的提出

物流配送是物流管理活動的一項核心技術(shù)。要高效地完成配送任務(wù)就得對配送路線進行合理安排。目前，出現(xiàn)了較多關(guān)于物流配送的研究，如物流網(wǎng)絡(luò)及其優(yōu)化、物流配送的動態(tài)規(guī)劃算法等。

但上述的研究僅將配送路徑最短作為目標函數(shù)，有其局限性且過于簡化。在實際的運作中，貨物經(jīng)過每層配送時中，并非只是簡單地流經(jīng)、通過，而是要進行存儲、裝卸、轉(zhuǎn)運等必要的運作，這就產(chǎn)生了不可忽視的費用（統(tǒng)稱為存轉(zhuǎn)費）。故物流配送是一個多層次運作，不光考慮運輸費用，還要關(guān)注存貯費用，且兩者必須統(tǒng)籌兼顧。

二、物流配送優(yōu)化模型

物流配送的運營方式從本質(zhì)上講是運輸、存轉(zhuǎn)、運輸、存轉(zhuǎn)……循環(huán)交替的復雜的多階段過程。故可以利用動態(tài)規(guī)劃的思維來考慮問題。

該動態(tài)規(guī)劃可分為N個階段，第i(1≤i≤N)個階段可供選擇的狀態(tài)(分銷商)有Si個，任意階段i的狀態(tài)和目標狀態(tài)之間的費用關(guān)系可以用費用矩陣M(r)（共有Si×Si+1個）來表示，每個元素表示階段i的狀態(tài)mi和階段i的目標狀態(tài)mi+1之間的費用消耗。特別地，規(guī)定表示第i階段目標狀態(tài)的存轉(zhuǎn)費。如果mi到mi+1沒有配送路線的設(shè)計，則可認為其間的費用為a∞(mi，mi+1)。則物流配送優(yōu)化模型為一個二元函數(shù):min F=K+C （K為總運輸費，C為總存轉(zhuǎn)費）。

三、模型求解

依據(jù)動態(tài)規(guī)劃思維及貝爾曼最優(yōu)化原理，則模型的求解可化為特殊的矩陣運算。其求解思想是：將存轉(zhuǎn)費轉(zhuǎn)化到運輸費當中去，再利用矩陣運算進行問題的求解。

定義1階段i的狀態(tài)到階段i+1的目標狀態(tài)之間的費用在經(jīng)過階段i+1時的狀態(tài)t(同時也是階段i的目標狀態(tài))時第i階段目標狀態(tài)的存轉(zhuǎn)費的轉(zhuǎn)化為:

存轉(zhuǎn)費的前向化:

存轉(zhuǎn)費的后向化:

定義2階段i的狀態(tài)到階段i+1的目標狀態(tài)之間的費用在經(jīng)過階段i+1時的狀態(tài)t(同時也是階段i的目標狀態(tài))時為:

定義3階段i到階段i+1的的費用矩陣可以通過如下的計算求得:

M(i)M(i+1)=

定理 多個連續(xù)階段i，i+1，L，j的費用矩陣的復合關(guān)系記為。

四、實例分析

上圖是一個簡單的有向網(wǎng)絡(luò)圖。具體的計算過程如下:

1.存轉(zhuǎn)費的轉(zhuǎn)化。（本文采用存轉(zhuǎn)費前向化方法）

則有：

2.費用矩陣為:

3.利用逆序解法，有

同理有：

可見，圖中的最小費用為51，而且最優(yōu)的配送路線為A，B1，C3，D2，E。

五、結(jié)束語

本文提出的基于矩陣運算的最小費用配送路線求解方法，為決策者提供了一種新的優(yōu)化方案。另外，還可以進一步研究多品種、分批量的配送優(yōu)化等問題。

參考文獻:

[1]石永澤:物流技術(shù)應用講座[J].物流技術(shù)，1996，(5)

[2]劉虹孫金梅陳德運:一種基于供應鏈管理的動態(tài)規(guī)劃算法[J].哈爾濱理工大學學報，2003.(4)

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