煙草物流配送中心選址優化問題研究

[摘 要] 物流配送是煙草銷售業務的重要環節，也是業務成本的主要組成部分。煙草物流大系統中存在很多復雜的優化問題，本文研究了其中的配送中心的數量、配送中心的選址的優化問題的求解方法。對這些問題的深入研究將有利于提高煙草配送業務的效益和服務水平，向精益物流逐步邁進。

ddoi : 10 . 3969 / j . issn . 1673 - 0194 . 2009 . 21 . 018

[中圖分類號]TP393;C931.6[文獻標識碼]A[文章編號]1673 - 0194(2009)21 - 0059 - 03

目前煙草行業的核心競爭力主要由兩個方面構成:其一是產品技術，也就是生產各式卷煙所需的各項技術;其二就是物流技術。在生產設備、原輔材料趨于同質的今天，如何做到比競爭對手更及時、更有效地滿足市場需要已成為企業競爭的重要內容。二者相比，物流技術更具戰略價值。

配送是煙草物流一個重要環節，從煙草企業的層面上看，煙草配送是關系到企業經濟效益實現，關系到卷煙零售戶的滿意度提高，進而關系到企業核心競爭能力提升以及企業和生存、發展的大問題。所以，研究配送中心優化問題具有相當的現實意義。配送中心的優化可以分解為兩個問題:一是配送中心的數量，二是配送中心的位置。

1配送中心數量

1.1問題描述

煙草物流配送中心數量的優化問題可以描述為:對于每一個確定的煙草配送區域，確定在該區域內應該設置多少個物流配送中心，在滿足該區域總物流需求的條件下，使總成本最少。

在實際規劃中，確定物流配送中心的數量需綜合考慮各種因素，本文只在理論上給出一個最佳的配送中心數目計算方法。為研究問題方便起見，做如下假設:首先，設區域內的物流需求量是平均分布的，各物流配送中心的規模相同而且位于其服務區域的中心;其次，設相同規模的物流配送中心在區域內各處的建設費用相等，即物流配送中心的建設費與位置無關。

煙草物流配送中心數量可用覆蓋模型來確定。

1.2覆蓋模型

所謂覆蓋模型，就是對于需求已知的一些需求，如何確定一組服務設施來滿足這些需求點的需求。在這個模型中，需要確定服務設施的最小數量和合適的位置。根據解決問題的方法不同，可以分為兩種不同的主要模型:集合覆蓋模型與最大覆蓋模型。本文主要介紹最大覆蓋模型的建立及對模型求解。

(1) 最大覆蓋模型

最大覆蓋模型的目標是對有限的服務網點進行選址，為盡可能多的對象提供服務(參見圖1)。

(2) 建立模型

目標函數:

max■ ■di yij(1)

約束條件:

■yij ≤ 1， i ?綴 N(2)

■di yij ≤ Cj xj， j ?綴 N(3)

■xj = p(4)

xj?綴 {0，1｝，j ?綴 N(5)

yij ≥ 0，j ?綴 N(6)

式中， N = {1，2，…，n｝，在研究對象中有n個需求點;di 為第i個節點需求量;Cj 為假如設施位于節點j時相應的容量;A(j)為可以被位于節點j的設施覆蓋所有節點的集合;B(i) = {j | i ?綴 A( j)｝ ，其相應的設施可以覆蓋節點i的節點集合;p為允許投建的設施數目;yij為節點i需求中被分配給節點j的部分;

xj = 1，假如該設施位于節點j;0，假如該設施不位于節點j。

式(1)是滿足最大可能的對需求提供服務，也是目標;式(2)是需求的限制，服務不可能大于當前需求的總和;式(3)是設施的服務能力的限制;式(4)則是問題本身的限制，也就是說最多可能投資建設的設施數目。其他兩式同集合覆蓋模型。

(3) 模型的求解

最大覆蓋模型是NP-困難問題，雖然當規模較小時，可設計枚舉法(如分支定界法等)求模型的最優解，但實際問題中往往需求點數n和可供選擇的候選點數m較大(也可能m = n)，一般仍需要設計近似算法來對模型進行求解。最常用的算法是Richard Church 和Charles Re Velle 設計的貪婪算法，該算法是以一個空集合作為原始的解結合，然后在剩下所有的其他候選點中選中一個具有滿足能力的候選點加入到原來的候選集合中。如此往復，直至到了設施數目的限制或者全部的需求都滿足為止。

2配送中心選址

2.1 問題描述

在確定配送中心數目后，更重要的問題是配送中心選址問題。問題可描述為:在配送對象位置和需求量已知的前提下，在固定區域內選定確定k個配送中心的位置，使得總體配送成本最低。

這個問題可歸結為一個有距離約束的P-median問題[2]。P-median問題最先由Hakimi于1965年提出，并隨后被證明是一個NP難題[3]。因此對于大規模問題，最優解很難得到。這里用P-中值模型來尋找最優解(或近似最優解)。

2.2P-中值模型

P-中值模型是指在確定區域內應建的物流設施數p之后，需進一步從若干個候選點中選取p個位置作為設施的地址，并確定各設施的服務對象(客戶)，使運輸成本最少。圖2說明了當p = 3時的P-中值模型的一個可行解。設施數P可能是由物流設施規模定位模型所確定。P-中值的圖形表達式如圖2所示。

(1) 建立模型

它的相應目標函數是:

max■ ■diyij(7)

約束條件為:

■yij = 1， i ?綴 N(8)

■xj = p(9)

yij ≤ xj(i ?綴 N，j ?綴 M)(10)

xj ?綴{0，1｝，j?綴M;yij ?綴{0，1｝，i ?綴 N，j ?綴 M

式中，N為系統中的需求點(客戶)，N = {1，2，…，n｝;M為可建設設施的候選地點，M = {1，2，…，m｝;di 為第i個需求點的需求量;Cij 為從點i到點j的單位運輸費用;p為將建設的設施總數(p < m);

xj = 1，在j點建設;0，否則。(j ?綴 M)

xj = 1，客戶i由設施j來提供;0，否則。(i ?綴 N，j ?綴 M)

模型中，式(7)是P-中值模型的目標函數，約束條件式(8)保證每個客戶(需求點)只有一個設施來提供相應的服務，約束條件式(9)限制了總的設施數目為p個，約束條件式(10)有效地保證沒有設施的地點不會有客戶對應。

(2) 模型求解

求解一個P-中值模型需要解決兩個方面的問題:第一，選擇合適的設施位置(數學表達式中的x變量);第二，指派客戶到相應的設施中去(表達式中的y變量)。

目前主要有兩大類方法，即精確計算法和啟發式算法。下面介紹一種求解P-中值模型的啟發式算法——貪婪取走啟發式算法(Greedy Dropping Heuristic Algorithm)。這種算法的基本步驟如下。

步驟1 令當前選中設施點數k = m，即將所有m個候選位置都選中。

步驟2 將每個客戶指派給k個設施點中距離其最近的一個設施點。求出總運費Z。

步驟3 若k = p，輸出k個設施點及客戶的指派結果，停止;否則，轉步驟4。

步驟4 從k個設施點中確定一個取走點，滿足:假如將它取走并將它的客戶指派給其他的最近設施點后，總費用增加量最小。

步驟5 從候選點集合中刪去取走點，令k = k - 1，轉步驟2。

3選址應用研究

內蒙古煙草公司目前有14個配送中心為所屬101個縣市配送卷煙，由于配送中心建設時只按照自然行政區劃來設置，沒有考慮優化的問題。為降低成本，該煙草公司決定重新考慮配送中心的設置。此時，管理者要考慮以下問題:

1) 需要建設多少個配送中心。

2) 這些配送中心應該布置在哪里。

通過分析了解到，目前內蒙古煙草行業實行的是“一庫制、大配送”的配送模式。“一庫制、大配送”是指在一定區域內如一個地市，只保留一個倉庫，建設一個規模較大、功能齊全的配送中心，包括信息管理、分銷、倉儲、分揀、噴碼，運輸等功能，稱為區域性配送中心RDC，其他縣市作為分發站，稱為HRS，只保留運輸功能，即HRS只負責暫存，并向終端卷煙零售客戶運送卷煙(如圖3所示)。

因此，在考慮物流配送中心選址問題時，首先使用最大覆蓋模型。最大覆蓋模型的目標函數是在服務網點給定覆蓋范圍內使其覆蓋到的需求點數目最大。可以將內蒙古行政區劃內的101個縣市公司作為配送客戶，以200千米為配送半徑(以200千米為配送半徑的主要依據是因為配送車輛以70~80千米/小時的速度行駛，當天可以往返)，以每個縣市的客戶需求量總和為配送量，建立最大覆蓋模型，求解模型，得到最多可能投資建設的配送中心數目p。

運用P-中值模型來確定配送中心的最佳位置。目標是選擇p個配送中心，使配送中心與需求點的配送距離總和最小。

為了使用P-中值模型，需要以下4部分數據:

1) 需求點位置。

2) 每個需求點的需求量。

3) 候選的配送中心位置。

4) 需求點和候選位置點之間的距離。

需求點的位置是101個縣市公司的位置，需求點的需求量是每個縣市公司服務范圍內的零售客戶的需求量的總和，候選配送中心的位置由以上最大覆蓋模型求出，需求點和候選位置點之間的距離也容易求出。所以運用P-中值模型可求出內蒙古煙草行業設置配送中心的最佳位置。

4結語

煙草物流是一個復雜的系統，本文對其中的兩個優化問題進行了研究。總體來說，研究都不夠深入，表現在:① 相關算法都沒有在真實數據環境中得到完全的驗證;② 一些求解模型的假設損害了算法的實際可操作性或效果;③ 雖然大多數的啟發式算法都可對同一個優化問題進行求解，但其適應性和效果也存在差別，本文未對此進行討論。

主要參考文獻

[1] 蔡臨寧. 物流系統規劃——建模及實例分析[M]. 北京:機械工業出版社，2007.

[2] 左元斌. 物流配送中心選址問題的理論、方法與實踐[M]. 北京:中國鐵道出版社，經濟科學出版社，2007.

[3] 鄭暢.物流中心選址方法研究[D].武漢:武漢理工大學，2004.

注:本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文