基于時間約束的生鮮產(chǎn)品配送路徑優(yōu)化

湯 齊，張亞麗

TANG Qi, ZHANG Ya-li

（天津工業(yè)大學(xué) 管理學(xué)院，天津 300387）

(School of Administration, Tianjin Polytechnic University, Tianjin 300387, China)

基于時間約束的生鮮產(chǎn)品配送路徑優(yōu)化

湯 齊，張亞麗

TANG Qi, ZHANG Ya-li

（天津工業(yè)大學(xué) 管理學(xué)院，天津 300387）

(School of Administration, Tianjin Polytechnic University, Tianjin 300387, China)

配送作為物流中的末端環(huán)節(jié)在保障物流效率及服務(wù)水平方面起著關(guān)鍵作用，其運作時間及成本直接影響物流整體的運作質(zhì)量和成效。針對生鮮產(chǎn)品配送對車輛路徑優(yōu)化選擇進(jìn)行研究，在時間約束條件下以配送總成本最小為目標(biāo)建立數(shù)學(xué)模型，經(jīng)過 Matlab 編程進(jìn)行求解運算，得到最優(yōu)配送路徑方案，通過案例來證明算法的有效性和可行性。

生鮮產(chǎn)品；配送路徑；節(jié)約里程法；時間約束

在滿足配送時效的基礎(chǔ)上降低運作成本是物流企業(yè)追求的目標(biāo)，配送路徑的選擇是實現(xiàn)該目標(biāo)的關(guān)鍵途徑之一，也是物流配送中的一個非確定性多項式難題，研究方法有禁忌搜索算法、蟻群算法、遺傳算法、粒子群算法、節(jié)約里程法等[1]。這些方法在解決配送路徑選擇問題時，多數(shù)只考慮節(jié)約里程數(shù)、時間約束、客戶滿意度等影響因素，未考慮運輸車輛單位成本，而運輸車輛單位成本作為配送成本中重要的影響因素，對生鮮產(chǎn)品配送成本的影響尤為突出。因此，綜合考慮運輸成本、制冷成本及懲罰成本，結(jié)合時間約束建立模型，運用節(jié)約里程法對生鮮產(chǎn)品配送路徑進(jìn)行優(yōu)化，對提升配送時效、降低物流配送成本有重要意義[2]。

1　基于時間約束的配送路徑優(yōu)化

配送是指將物資從配送中心運到一個或多個需求點的過程。假設(shè) 1 個配送中心向幾個需求量不同的需求點進(jìn)行物資配送，在配送活動中會有多種路線和車輛可供選擇。如果配送中心事先規(guī)劃不合理，在運送過程中可能會發(fā)生重復(fù)、迂回、倒流運輸?shù)痊F(xiàn)象，造成配送時間增加，配送成本提升，配送效率降低。在生鮮產(chǎn)品配送中，配送時間對于提高物流服務(wù)水平、降低物流成本的影響很大，因而基于時間約束對生鮮產(chǎn)品配送路徑優(yōu)化選擇問題進(jìn)行研究。

1.1基于 Dijkstra 算法的最短路徑分析

迪杰斯特拉 (Dijkstra) 算法的基本思想是從出發(fā)點 vs開始，逐步給每個節(jié)點 vj標(biāo)號為，其中 dj是出發(fā)點 vs到節(jié)點 vj的最短路徑里程 (從節(jié)點到自身的最短路徑的距離為零)，vi是節(jié)點 vj的前個節(jié)點。從出發(fā)點 vs到點 vj的最短路徑算法步驟如下。

（1）給出發(fā)點 v1標(biāo)號

（2）將所有的節(jié)點分為已標(biāo)號節(jié)點和未標(biāo)號節(jié)點。

（3）從已標(biāo)號節(jié)點 vi到所有未標(biāo)號點中選擇路徑最短的節(jié)點 vj，節(jié)點 vj標(biāo)號中的 dj= min (di+ cik)，其中 cik為點 vi到未標(biāo)號 k 節(jié)點的直接最短路線，計算 dj，對 vj進(jìn)行標(biāo)號。

（4）重復(fù)上述步驟，直至所有節(jié)點都標(biāo)號，終點節(jié)點 vn對應(yīng)的 dn為出發(fā)點 v1至節(jié)點 vn的最短路徑，反向追蹤可求出最短路徑。

在物流配送過程中，配送中心到每個需求點及需求點之間可以選擇多種路線進(jìn)行運輸。將配送中心作為起始點 v1，vn作為一個需求點，其余節(jié)點作為路線拐角節(jié)點，每個拐角間路線為 vi到 vj的直接最短路徑，這樣可以通過 Dijkstra 算法得出配送中心到各需求點的最短路徑，各需求點間最短路徑也可同理求出。

1.2基于時間約束的配送路徑優(yōu)化模型

節(jié)約里程法是解決配送中路徑選擇問題的啟發(fā)式算法，對配送中心向需求點逐一往返配送模式進(jìn)行改進(jìn)，采用車輛在一定約束條件限制下，如車輛載重量限制、行駛里程數(shù)限制、交發(fā)貨時間限制、發(fā)送量限制等，連續(xù)對多個需求點進(jìn)行配送，達(dá)到一定的優(yōu)化目標(biāo)，如減少運輸車輛數(shù)量、提高車輛滿載率、降低人工及運輸成本、縮短配送里程、節(jié)省時間等。

節(jié)約里程法根據(jù)三角形任一邊之長小于其他兩邊之和的原理，采用將配送網(wǎng)絡(luò)中的 2 個回路拆分合成 1 個回路的方法，依次將配送中心向多個需求點的單獨配送路線合并成 1 個連續(xù)配送多個需求點的路線，當(dāng)配送路線上的各需求點需求量之和達(dá)到配送車輛的最大載重上限，或者合并路線達(dá)到運輸里程上限，或者配送時間達(dá)到配送中心到各需求點的時間上限時，返回需求中心[3]，繼續(xù)優(yōu)化下一輛車的配送路線。例如，由配送中心 P 向 2 個需求點 A 和 B 進(jìn)行配送，根據(jù) Dijkstra 算法求出配送中心到 2 個需求點的最短路徑分別為 PA 和 PB，2 個需求點 A 與 B 間的最短路徑為 AB，方案 1 配送中心用 2 臺車輛分別對 2 個需求點各自往返配送，運輸總里程為：s1= 2 (PA + PB)，其配送路線如圖1a 所示。方案 2 用 1 輛車在條件允許的情況下連續(xù)送貨，則運輸總里程為：s2= PA + AB + BP，其配送路線如圖1b 所示。比較 2 種方案，方案 2 較方案 1 節(jié)約運輸里程為：Δs = PA + PB - AB[4]。

運用節(jié)約里程法對配送中心向各需求點配送生鮮產(chǎn)品的路徑進(jìn)行優(yōu)化，以配送總成本最小為目標(biāo)建立數(shù)學(xué)模型[5-6]為

圖1　節(jié)約里程法原理

式中：CT為總的運輸成本，元；CP為總的懲罰成本，元；CM為總的制冷成本，元；N 為需求點數(shù)量，個；K 為需要的車輛數(shù)，輛；ck為第 k 輛車的單位運輸成本，元/h；dij為從 i 地到 j 地的距離，km；cp為單位時間延遲的懲罰成本，元/h；ti為車輛實際到達(dá) i 地的時間，h；Ti為規(guī)定到達(dá) i 地的時間上限，h；β 為制冷成本系數(shù)；Qk為第 k 輛車最大載貨量，t；v 為車輛單位時間的速度，km/h；t 為單位物資卸車時間，h/t；qi為第 i 處的需求量，t；Q0是配送中心的總儲存量，t；Sk為第 k 輛車最大行駛里程量，km；sk是第 k 輛車實際行駛里程量，km；xijk=

2　案例分析

某配送中心需要向 8 個分銷點配送生鮮產(chǎn)品，共有 3 種冷藏車型可以選擇，分別為 2 t 冷藏車 4輛、4 t 冷藏車 3 輛和 6 t 冷藏車 2 輛，3 種類型冷藏車的單位運輸成本分別為 2.5 元/h、2.8 元/h和 3.0 元/h，車輛平均速度為 40 km/h，單位物資卸車時間為 0.25 h/t，制冷成本系數(shù)為 12，車輛最大行駛里程量為200 km，單位懲罰成本為 40 元/h，不足 1 h 按 1 h 計算。各分銷點需求量及時間上限如表1 所示[7]。利用 Dijkstra算法求出配送中心點 P 與各分銷點及各分銷點之間最短距離如表2 所示。

表1　各分銷點需求量及時間上限列表

表2　配送中心點 P 與各分銷點及各分銷點之間的最短距離列表km

根據(jù)模型 ⑴，經(jīng)過 Matlab 編程進(jìn)行總成本最小的最優(yōu)車輛路徑選擇求解運算，可以得到最優(yōu)配送路徑方案如表3 所示[8]。

表3　最優(yōu)配送方案表

優(yōu)化后的配送路徑方案與配送中心向需求點逐一往返配送方案結(jié)果比較如表4 所示。

表4　優(yōu)化前后路徑選擇成本比較分析 　　元

從表4 中可以看出優(yōu)化后的方案成本更小，選擇合適的車輛給合適的客戶經(jīng)過合適的路線進(jìn)行配送，可以有效降低配送成本。模型 ⑴ 中沒有考慮車輛購買、損耗和員工工資等影響因素，案例中配送中心向需求點逐一往返配送方案用 8 輛車 8 個司機(jī)，而優(yōu)化后用 4 輛車 4 個司機(jī)，如果考慮車輛購買、損耗和員工工資等影響因素，可以更好的比較出配送路徑優(yōu)化后的優(yōu)勢。

3　結(jié)束語

在配送中選擇合理的路線與車輛對節(jié)約配送成本具有很大影響，基于時間約束的配送路徑優(yōu)化模型能夠為配送車路徑選擇問題提供可以借鑒的理論指導(dǎo)和依據(jù)。模型 ⑴ 考慮了生鮮配送中的主要影響因素，在實際問題中，可以根據(jù)自身配送特點結(jié)合其他重要因素進(jìn)行運用，在盡量滿足客戶要求的條件下，優(yōu)化選擇配送路徑，減少配送車輛數(shù)和人工投入，降低配送成本，提高車輛利用率及配送中心的工作效率。

[1] 李 松，劉 興，李瑞彩. 基于混合禁忌搜索算法的物流配送路徑優(yōu)化問題研究[J]. 鐵道運輸與經(jīng)濟(jì)，2007，29(3)：66-69. LI Song，LIU Xing，LI Rui-cai. Study on Optimization of Logistics Distribution Route based on Mixed Tabu Search Algorithm[J]. Railway Transport and Economy，2007，29(3)：66-69.

[2] 姚卓順. 帶時間窗的連鎖超市生鮮品配送車輛路徑優(yōu)化[J].商業(yè)時代，2014(29)：28-29. YAO Zhuo-shun. Optimization Design of the Delivery Vehicle Route by Supermarket Chains with Time Windows[J]. Journal of Commercial Times，2014 (29)：28-29.

[3] 張文華. 基于節(jié)約里程法的物流配送路線優(yōu)化[J]. 物流工程與管理，2012，34(3)：143-144，146. ZHANG Wen-hua. Route Optimization of Logistics Distribution based on Saving Algorithm[J]. Logistics Engineering and Management，2012，34(3)：143-144，146.

[4] 于 航，張 凱. 基于節(jié)約里程法的鮮活農(nóng)產(chǎn)品物流配送車輛路線的最優(yōu)設(shè)計[J]. 安徽農(nóng)業(yè)科學(xué)，2011，39(28)：17701-17703. YU Hang，ZHANG Kai. Optimal Design of Fresh Produce Logistics Vehicle Route based on the Method of Mileage Saving Method[J]. Journal of Anhui Agricultural Sciences，2011，39(28)：17701-17703.

[5] 鄭 靜，程幼明. 基于時間約束的節(jié)約里程法配送路徑優(yōu)化研究[J]. 物流工程與管理，2010，32(10)：89-90. ZHENG Jing，CHENG You-ming. Optimization Design of the Delivery Route by Vehicles Scheduling Program with Time Windows[J]. Logistics Engineering and Management，2010，32(10)：89-90.

[6] 邵舉平. 生鮮農(nóng)產(chǎn)品配送中帶時窗的 VRP 模型與算法[J]. 工業(yè)工程與管理，2015，20(1)：122-127，134. SHAO Ju-ping. Research on Multi-objective Optimization for Fresh Agricultural Products VRP Problem[J]. Industrial Engineering and Management，2015，20(1)：122-127，134.

[7] 李 軍. 有時間窗的車輛路線安排問題的啟發(fā)式算法[J]. 系統(tǒng)工程，1996，14(5)：45-50. LI Jun. A Heuristic Algorithm for Vehicle Routing Scheduling Problem with Time Windows[J]. Systems Engineering，1996，14(5)：45-50.

[8] 劉俊娥，李 奇. 基于節(jié)約里程法的北京市家樂福超市配送線路優(yōu)化方案[J]. 物流技術(shù)，2015，34(1)：107-109. LIU Jun-e，LI Qi. Study on Distribution Route Optimization Plan of Beijing Carrefour Supermarket based on Saving Algorithm[J]. Journal of Logistics Technology，2015，34(1)：107-109.

責(zé)任編輯：王 靜

Route Optimization of Fresh Product Delivery based on Time Constraints

Delivery, as the last link of logistics, has the key roles on ensuring logistic efficiency and service level, and its operation time and cost have direct influence on overall operation quality and effects of logistics. Targeting with the optimized selection of vehicle routes of fresh product delivery was studied, the mathematical model was established under time constraints by taking minimization of total delivery cost as the object, optimized program of delivery route was achieved by means of matlab programming, and the validity and feasibility of the calculation method was proved by example.

Fresh Product; Delivery Route; Saving Algorithm; Time Constraints

1003-1421(2016)06-0040-04

U295

B

10.16668/j.cnki.issn.1003-1421.2016.06.08

2015-12-25

天津市教委社會科學(xué)重大項目 (2014ZD34)