同城配送最短時間-最大流量問題分析

張 瑞

(西安交通工程學院,西安 710300)

同城配送是一種特殊的物流方式,適用于小范圍內的分揀、配貨及運輸,可以在短時間內將物品準確高效地送給客戶,提高客戶滿意度,但其適用范圍有限,需要進一步改進。陳琳琳等研究構建了多供貨點智能配送VRP模型,得出最優配送方案[1]。吳樺研究了蟻群算法在時間窗物流配送路徑問題中的應用[2]。本研究基于某超市分店的送貨上門服務選取10個需求點調研配送需求量和配送路線,并建立最短時間-最大流量模型。該模型利用時間為長度,計算最短路徑,求出第1條增廣鏈,不斷增廣直至達到最大流量。使用LINGO軟件求解,優化超市貨物配送線路,使其運輸量最大化的同時所需時間最短。

1 最短時間-最大流量模型的構建

1)目標函數。以每條路線能夠承受的最大貨流量通過時間最短為優化目標構建目標函數,詳見式(1)。

(1)

2)約束條件。由表1可得模型的約束條件,詳見式2。

表1 模型中的參數和變量

(2)

3)模型在案例中的應用。客戶需求點位置坐標分布如圖1所示。假定超市把商品貨物運輸到需求點J,運用其代號可以將數據整理成網絡圖,括號中數字依次代表容量、時間、流量。詳見圖2。

圖1 超市及各需求點的直角坐標系分布

圖2 最短時間-最大貨流量原始網絡圖

圖3 修訂后的最短時間-最大貨流量網絡圖

在圖3中的每一條弧(Vi,Vj)上添加一條方向相反的弧(Vj,Vi),得到賦權網絡。詳見圖4。將時間當作長度,繼續求解最短路徑,得出增廣鏈,其增加流量相應的時間也會增加,按照規則繼續構造賦權網絡圖,直至求不出最短路徑時,算法停止,得到最大流量和最短時間。

圖4 最短時間-最大貨流量賦權網絡圖

2 基于LINGO算法的模型求解

1)最大貨流量模型求解。運行源程序代碼,結果表明,整個有向圖的最大貨流量為14,即配送中心最多能運送14 t的貨物。詳見圖5。

圖5 最大流求解狀態

2)最短時間-最大貨流量模型求解。以最大貨流量的結果分析得出最大貨流量f=14為模型中的約束條件,將運輸總成本費用最少作為目標函數,得到整個有向圖的最短時間為215,即運送最短時間為215 min。詳見圖6。

圖6 最短時間求解狀態

3 結論

由程序的運行結果可知,從A到J最大流量為14,運輸方案詳見表2,流量運輸網絡詳見圖7。

圖7 貨流量運輸網絡

表2 運輸方案

求出最大流量后,將其作為約束條件求出最短時間,最終選取費用最少的運輸方案。與表2的運輸方案相比,C→F由4變為6,E→G由1變為3。改正后的運輸流量時間詳見圖8。

圖8 改正后的貨物運輸流量時間

超市向需求點J最多可以配送14 t的貨物,用時215 min。優化網絡圖去掉了路線A→B、E→F、H→I,能夠使運輸流量最大化,運輸時間最小化,大大提高了配送效率,避免了資源浪費。