基于EXCEL規(guī)劃求解的M公司配送路徑優(yōu)化

鄧世發(fā) 劉林

M公司要對其負責區(qū)域內(nèi)的9個客戶進行配送服務，從其配送中心出發(fā)，在完成9個客戶的配送后返回配送中心，這是個典型的旅行商問題，這時我們選擇用EXCEL規(guī)劃求解的辦法來對配送路徑進行優(yōu)化。

首先我們要明確M公司是指定區(qū)域單車輛配送，車輛在對每個客戶點進行配送后要返回配送中心形成的一個回路，此回路為HAMILION回路，這時我們可以把配送中心看做一個客戶點，令其為中心0，其余客戶分別為客戶1-9，實際距離在圖表內(nèi)表示。我們可以用0-1整數(shù)規(guī)劃建立數(shù)學模型如下：

令配送中心和各客戶點分別為V0，V1，V2...V9，假設dij，表示Vi到Vj的路程，定義0-1整數(shù)型變量Xij=1表示從i到j，否則Xij=0

式-1，式-2，保證了各客戶只被經(jīng)過一次，只有一條路進，一條路出，式-3保證了沒有子回路產(chǎn)生。

由此可用EXCEL建立以下模型。（在客戶分布圖中客戶之間或配送中心與客戶之間無直接連線的表示車輛無法直達，在模型中用足夠大的距離100表示）

先建立距離的矩陣，客戶點之間車輛無法直達的和陰影部分輸入值為100。

設置約束條件，目標單元格和可變單元格。

設置唯一來源下面9個單元格的公式為=sum...，最小路程下的單元格為=SUMPRODUCT...主要用于將線性規(guī)劃求出來的值替換矩陣中的值并求和。合計路程后的單元格用以對最小路程下各單元格求和也是線性規(guī)劃求解的目標單元格。

第一次求解得出結(jié)果如上圖所示，當前規(guī)劃求解找到一條最短的路線方案，考察這條路線的具體走法，如果能夠形成一個獨立的封閉回路，即從中心0出發(fā)能夠訪問到其他9個客戶最后再返回中心0，說明此路線即為滿足配送要求的最佳路線方案，否則需要根據(jù)情況繼續(xù)規(guī)劃求解過程以求取滿足條件的答案。通過上圖中的解答可以發(fā)現(xiàn)，當前解法路線包含四個回路：1-3-1，0-2-5-2-0，4-7-6-4，8-9-8。合計路程（最小）為69，但是無法滿足從中心0出發(fā)給每個客戶配送牛肉再回到配送中心的要求，所以要繼續(xù)進行規(guī)劃求解。采用人為設置障礙的方法，使得“0-2-5-2-0”和“1-3-1”的路線不可選，從而打斷原有的回路，讓規(guī)劃求解找到更合理的最佳路線。具體約束條件設置如下：

再次求解后得出最優(yōu)路徑為0-1-3-4-7-6-9-8-2-5-0，反之也可，總的最短路程為78。

作者簡介：

鄧世發(fā)（1996-），男，新疆和碩，西華大學管理學院物流管理專業(yè)，本科在讀。

劉林（1997-），男，四川德陽，西華大學管理學院物流管理專業(yè)，本科在讀。