基于時間窗約束的生鮮電商LRP問題研究

王　晶，岳慧麗

（北京工商大學(xué)　商學(xué)院，北京　100048）

?

基于時間窗約束的生鮮電商LRP問題研究

王晶，岳慧麗

（北京工商大學(xué)商學(xué)院，北京100048）

首先分析生鮮電商物流配送系統(tǒng)存在的問題，其次以系統(tǒng)總成本最低為目標(biāo)，從多配送中心選址、時間窗約束以及路徑優(yōu)化三方面進(jìn)行了LRP模型的構(gòu)建，最后用包含16個物流節(jié)點(diǎn)的21cake北京配送系統(tǒng)規(guī)劃為例，對構(gòu)建的模型仿真分析。研究結(jié)果表明，構(gòu)建的LRP模型能夠在客戶時間滿意度要求下合理降低生鮮電商的配送成本。

生鮮電商；時間窗約束；LRP；配送系統(tǒng)；遺傳算法

1　引言

隨著社會的進(jìn)步，“第三利潤源”物流業(yè)的發(fā)展，以及互聯(lián)網(wǎng)的普及，各種純天然的生鮮食品越來越受到人們的青睞，消費(fèi)者可以通過天貓，淘寶以及京東等電商平臺直接與生鮮食品的生產(chǎn)者聯(lián)系，使得生鮮食品可以從原產(chǎn)地直接到達(dá)消費(fèi)者的家中［1］。然而，快速發(fā)展的生鮮電商同樣存在著許多問題，例如由于配送中心選址和配送路徑選擇的不合理，造成的配送時間長，食品損耗高，顧客滿意度低等。由此可見，構(gòu)建合理的生鮮電商配送系統(tǒng)是提高其核心競爭力的重要途徑［2］。

現(xiàn)代生鮮電商配送系統(tǒng)規(guī)劃時一般要考慮三方面因素。第一，多配送中心選址，單一配送中心很難輻射到所有的消費(fèi)人群；第二，時間窗約束，顧客通過電商平臺購物時會要求在一定的時間段內(nèi)收到貨物；第三，配送路徑的選擇，企業(yè)必須選擇合理的配送路徑來提高物流的時效性，保證食品新鮮度。

近年來，國內(nèi)外對LRP（Location-routing problem）和生鮮食品的配送系統(tǒng)也做了很多研究，例如：F.Dabbene，p.Gay和N.Sacco（2008）［3］兼顧生鮮食品的品質(zhì)和物流成本最低為目標(biāo)，對生鮮食品的供應(yīng)鏈流程進(jìn)行了優(yōu)化，郭曉峰（2001）［4］考慮運(yùn)輸成本，對單個物流設(shè)施選址問題進(jìn)行了研究。此外，國內(nèi)外對LRP的求解，多采用啟發(fā)式算法，模擬退火算法和遺傳算法等。然而在電商平臺下，結(jié)合LRP，考慮多配送中心選址，時間窗約束和配送路徑選擇三方面因素，針對生鮮電商配送系統(tǒng)的研究較少，因此本文將兼顧這三個因素，在相關(guān)研究基礎(chǔ)上，對基于時間窗約束的生鮮電商配送系統(tǒng)LRP問題進(jìn)行研究。

2　基于時間窗約束的生鮮電商配送系統(tǒng)LRP模型的構(gòu)建

2.1問題描述

生鮮電商接受顧客訂單，在規(guī)定的時間段內(nèi)送貨上門，若配送員提前送達(dá)，產(chǎn)生等待費(fèi)用，若配送員推遲送達(dá)，產(chǎn)生延遲費(fèi)用。生鮮電商有多個開放的配送中心可以處理訂單，配送員從配送中心出發(fā)向顧客進(jìn)行送貨，最后返回原配送中心，整個配送過程車輛的行駛費(fèi)用由公司根據(jù)實(shí)際的經(jīng)營核算得出。規(guī)定每天配送員的工作時間為8h，超過規(guī)定工作時間后，企業(yè)必須向配送員支付一定的加班費(fèi)。

2.2基本假設(shè)

（1）企業(yè)有多個候選配送中心可以開放；

（2）配送中心的開放固定成本已知，且處理訂單能力有限制；

（3）配送中心車輛沒有規(guī)模限制，車載容量有限制；

（4）每個顧客只能由指定的一個配送中心的一個配送員服務(wù)；

（5）一個配送員可以沿著一條行車路線服務(wù)多個顧客，返回配送中心；

（6）顧客與顧客，顧客與配送中心的距離，車的平均速度都是已知的；

（7）每個顧客的需求量是已知的，配送有時間窗約束；

（8）每輛車由一個配送員駕駛；

（9）配送中心之間不進(jìn)行互相調(diào)貨。

2.3符號定義

R=｛r=1，2，…，r｝—表示一系列可行的，配送中心節(jié)點(diǎn)集合；

V=｛v=1，2，…，k｝—表示配送車輛集合；

N1—表示代表開放配送中心的節(jié)點(diǎn)集合；

N2—表示代表一個開放的配送中心以及由它所服務(wù)的客戶的節(jié)點(diǎn)集合；

Fr—表示配送中心r開放的固定成本；

Vr—表示配送中心r開放的可變成本；

Qi—表示第i個客戶的需求量，其時間窗為［ETi，LTi］；

Ci—表示顧客i每小時的延遲費(fèi)用；

i，j—表示需要服務(wù)的客戶i=0時表示配送中心；

Dij—表示i，j兩點(diǎn)的距離；

Qk—表示車輛k的容載量；

Qr—表示配送中心處理訂單的最大能力；

Vij—表示車輛在i、j兩點(diǎn)的行車平均速度，i=0時表示配送中心；

fk—表示單位距離車輛k的行駛費(fèi)用；

C—表示配送員每小時的等待費(fèi)用；

s—表示配送員每小時的工資；

es—表示配送員加班時每小時的加班工資；

2.4數(shù)學(xué)模型

其中：

t0表示配送員的發(fā)車時間；t0′表示配送員的收車時間；wtk表示配送員的正常工作時間；wtk=min（t0′-t0，8）；ewtk表示配送員的加班時間；ewtk=max（t0′-t0-8，0）。

目標(biāo)函數(shù)（1）表示總成本最小，其中總成本=開放配送中心的固定成本+配送中心的可變成本+車輛行駛費(fèi)用+配送員工資及加班費(fèi)+延遲費(fèi)用+等待費(fèi)用；約束（2）表示每一個運(yùn)輸車輛k最多從一個配送中心出發(fā)；約束（3）保證任意兩個開放的配送中心之間不進(jìn)行連接；約束（4）表示車輛k的車載容量限制；約束（5）表示配送中心的最大處理訂單能力限制；約束（6）保證每個顧客只能由一個運(yùn)輸車輛服務(wù)；約束（7）表示若顧客j由車輛k送貨，則車輛k必由某點(diǎn)i到達(dá)；約束（8）表示若顧客i由車輛k送貨，則車輛k送完必到達(dá)另一點(diǎn)j。

3　算例分析

3.1算例概述

在北京，選取21cake某天從上午10點(diǎn)到下午13點(diǎn)配送訂單作為樣本進(jìn)行仿真分析［5］。在該時間段內(nèi)每個配送站只需安排一次配送即可，21cake的3個配送站和該時間段內(nèi)需要服務(wù)的顧客位置分布如圖1所示：

圖1　配送站及顧客位置分布示意圖

為了方便下面的計算，對這三個配送中心進(jìn)行編號，田村配送站：D1，亞運(yùn)村配送站：D2，陶然亭配送站：D3，配送站和顧客之間的距離見表1。

表1　配送站和顧客之間的距離表

對配送站的最大處理訂單能力和顧客的需求統(tǒng)一按照蛋糕重量單位“磅”來進(jìn)行計算。21cake蛋糕有1磅，1.5磅，2磅，3磅以及5磅五種類型。各配送站在10：00到13：00時間段內(nèi)處理訂單能力均為10磅。各顧客的需求量和送貨時間要求見表2。

表2　顧客需求量和送貨時間要求表

計算用到的21cake相關(guān)數(shù)據(jù)：

（1）配送員正常工資：20元/h，加班工資：30元/h；

（2）配送員在10：00到13：00時間段內(nèi)，可在任意時間發(fā)車；

（3）配送車型為配有保溫包的小型電動車；

（4）為了防止蛋糕擠壓損壞，車載容量最大為10磅；

（5）車輛行駛費(fèi)用：5元/km；

（6）車輛的行駛速度：30km/h；

（7）顧客的延遲費(fèi)用：50元/h，配送車輛的等待費(fèi)用：20元/h；

（8）配送站開放使用的固定成本為40元/h；

（9）配送站配送1磅蛋糕的可變成本為30元；

（10）每位顧客平均訪問時間5min。

3.2計算結(jié)果分析

本文運(yùn)用遺傳算法進(jìn)行求解，選取種群數(shù)為20，交叉概率Pc=0.8，變異概率Pm=0.05，最大進(jìn)化代數(shù)T=1 200［6］。運(yùn)用matlab軟件計算可得最優(yōu)的配送路線為：路徑1：D1-1-3-10-D1；路徑2：D2-2-13-4-5-D2；路徑3：D3-11-12-6-7-8-D3，3條路徑上：車輛行駛的總距離分別為：57km、86km、89km；車輛行駛費(fèi)用分別為：285元、430元、445元；配送量分別為：6磅、6.5磅、9.5磅；可變成本分別為：180元、195元、285元。各路徑上訪問各節(jié)點(diǎn)的時間為：

路徑1：10：00-10：50-11：21-11：34-11：59-12：24；

路徑2：10：00-10：34-11：13-12：04-12：23-13：07；

路徑3：10：00-10：56-11：31-12：01-12：36-13：05-13：23；

行駛費(fèi)用=285+430+445=1 160元；

配送員工資=20×3×3+35×（7+23）×30/60=195元；

固定成本=40×3×3=360元；

可變成本=180+195+285=660元；

等待延遲費(fèi)用=50×5/60≈21元；

總成本=固定成本+可變成本+行駛費(fèi)用+配送員工資+等待延遲費(fèi)用=360+660+1 160+195+21=2 396元。

4　結(jié)語

在“互聯(lián)網(wǎng)+”概念的影響下，更多的傳統(tǒng)生鮮企業(yè)會看到商機(jī)，加入生鮮電商的行列，未來該領(lǐng)域的市場競爭必將更加激烈，此時對于每個生鮮電商來說，如何降低配送成本將至關(guān)重要。針對生鮮電商配送系統(tǒng)，所構(gòu)建的LRP模型，能夠科學(xué)選取最合適的配送中心，規(guī)劃最優(yōu)的配送路線，在保證生鮮食品新鮮度的同時，有效的將生鮮電商的配送成本控制在最低，提高企業(yè)的市場競爭力，增加企業(yè)的利潤。

在以后的研究中，考慮做以下兩方面的深入研究：一是本文只考慮了一種車型，下一步的研究應(yīng)考慮多種型號的車輛來承擔(dān)不同類別生鮮食品的配送，以適應(yīng)消費(fèi)者需求的不斷變化。二是本文從配送系統(tǒng)優(yōu)化方面進(jìn)行了研究，下一步研究可考慮冷鏈溫控技術(shù)在生鮮食品運(yùn)輸領(lǐng)域的應(yīng)用，來降低生鮮食品在運(yùn)輸途中的損耗，從而適應(yīng)消費(fèi)者對食品質(zhì)量要求的不斷提高。

［1］謬新紅，周新年，巫志龍.生鮮食品冷鏈物流研究進(jìn)展探討［J］.物流技術(shù)，2009，（2）：1-2.

［2］H chen，N S Flann.Parallel Simulated annealing and genetic algorithms：Aspace of hybrid methods parallel problem sovling from Nature3［J］.Spring-verrlag，2001，（3）：428-438.

［3］F Dabbene，P Gay，N Sacon.Optimazation of fresh-food supply chains in uncertain environments［J］.Biosytems Engineering，2008，99：348-359.

［4］郭曉峰.車輛路徑問題的研究現(xiàn)狀和展望［J］.物流技術(shù)，2010，（10）：181-184.

［5］王曉博，李一軍.協(xié)同配送路線優(yōu)化研究［J］.計算機(jī)工程與應(yīng)用，2007，43：184-186.

［6］H Arturo，B Salvador，A Carlos，et al.Handing Constraints using Multiobjective optimization Concepts［J］.International Journal for Numerical Methods in Engineering，2004，59（15）：1 989-2 017.

Study on LRP Problem of Fresh Product E-businesses with Time Window Constraint

Wang Jing， Yue Huili
（School of Business， Beijing Technology Business University， Beijing 100048， China）

In this paper， we first analyzed the problems existing in the fresh product e- business logistics distribution system， thentargeting at the minimization of the total cost of the distribution system， established the corresponding LRP model from the aspects of multipledistribution center location allocation， time window constraint and route optimization， and at the end， in the case of the planning of the 21cakeBeijing distribution system which involved 16 logistics nodes as example， simulated the model established in this paper.

fresh product e-business； time window constraint； LRP； distribution system； genetic algorithm

F724.6；F224

A

1005-152X（2016）01-0067-04

10.3969/j.issn.1005-152X.2016.01.018

2015-09-28

國家科技支撐計劃農(nóng)村關(guān)鍵農(nóng)資物流關(guān)鍵技術(shù)及裝備研究與示范；北京市教育委員會創(chuàng)新能力提升計劃項(xiàng)目“科技成果轉(zhuǎn)化和產(chǎn)業(yè)化—北京市城市共同配送體系建設(shè)對策及建議”（PXM2014_014213_000050）

王晶（1982-），男，河北人，副教授，主要研究方向：物流與供應(yīng)鏈管理；岳慧麗（1993-），女，河南人，碩士研究生，主要研究方向：物流與供應(yīng)鏈管理。