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

鄧世發(fā) 劉林

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

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

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

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

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

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

設(shè)置約束條件，目標(biāo)單元格和可變單元格。

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

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

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

作者簡介：

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

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