湯 齊，張亞麗

TANG Qi, ZHANG Ya-li

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

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

基于時(shí)間約束的生鮮產(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)鍵作用，其運(yùn)作時(shí)間及成本直接影響物流整體的運(yùn)作質(zhì)量和成效。針對(duì)生鮮產(chǎn)品配送對(duì)車輛路徑優(yōu)化選擇進(jìn)行研究，在時(shí)間約束條件下以配送總成本最小為目標(biāo)建立數(shù)學(xué)模型，經(jīng)過(guò) Matlab 編程進(jìn)行求解運(yùn)算，得到最優(yōu)配送路徑方案，通過(guò)案例來(lái)證明算法的有效性和可行性。

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

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

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

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

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

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

（1）給出發(fā)點(diǎn) v1標(biāo)號(hào)

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

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

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

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

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

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

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

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

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

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

2　案例分析

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

表1　各分銷點(diǎn)需求量及時(shí)間上限列表

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

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

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

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

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

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

3　結(jié)束語(yǔ)

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

[1] 李 松，劉 興，李瑞彩. 基于混合禁忌搜索算法的物流配送路徑優(yōu)化問(wèn)題研究[J]. 鐵道運(yùn)輸與經(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] 姚卓順. 帶時(shí)間窗的連鎖超市生鮮品配送車輛路徑優(yōu)化[J].商業(yè)時(shí)代，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ì)[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] 鄭 靜，程幼明. 基于時(shí)間約束的節(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)品配送中帶時(shí)窗的 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] 李 軍. 有時(shí)間窗的車輛路線安排問(wèn)題的啟發(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é)約里程法的北京市家樂(lè)福超市配送線路優(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

天津市教委社會(huì)科學(xué)重大項(xiàng)目 (2014ZD34)