李珍萍，毛小寸

(北京物資學(xué)院 信息學(xué)院，北京 101149)

0 引言

自提服務(wù)可以解決投遞時間不對稱、快遞員等待時間長、包裹丟失等問題，有效提高一次配送成功率，是解決快遞配送“最后一公里”問題的有效途徑。從顧客角度而言，顧客在網(wǎng)上購物時可以選擇自提服務(wù)并根據(jù)配送地點選擇便利的自提點位置；從快遞企業(yè)角度而言，將選擇自提服務(wù)的客戶需求以相對大批量的方式集中配送至自提點，可以實現(xiàn)規(guī)模經(jīng)濟(jì)效應(yīng)。目前已有的自提點類型包括便利店自提點、智能快件箱、小區(qū)物業(yè)自提點、校園自提點、Amazon Locker、DHL Packstation等，主要劃分為有人值守和無人值守兩類[1]，不同類型自提點的處理能力(容量、服務(wù)種類)、建設(shè)成本、覆蓋半徑、對顧客的吸引力(服務(wù)時間、便利性)均不相同。因此，快遞企業(yè)如何確定各種類型自提點的建設(shè)位置以及每個自提點的服務(wù)范圍，是提高市場顧客占有率、解決最后一公里問題的關(guān)鍵。

國外對自提點相關(guān)問題的研究主要集中于自提模式、自提意愿、配送服務(wù)選擇均衡問題等方面，Xu等[2]提出聯(lián)合投資模式來運營“集中交付點”;Visser等[3]研究城市駕車購物、送貨上門和就近取貨點3種配送服務(wù)策略的行程次數(shù)和行駛里程，得出配合使用送貨到家和就近取貨點可減少城區(qū)內(nèi)13%的道路占有率；Hübner等[4]在全渠道零售雜貨店的最后一公里交付的戰(zhàn)略規(guī)劃框架中，對配送模式中的雜貨店自提模式分店內(nèi)(in-store)，附加(attached)和孤立(solitary)3種具體的模式進(jìn)行研究；Wang等[5]根據(jù)配送模式的操作流程建立不同類型的配送車輛路徑規(guī)劃模型和K-means聚類模型，研究電子商務(wù)物流最后一公里送貨上門(Attended Home Delivery, AHD)模式、自助收發(fā)箱Reception Box, RB)模式和顧客自提站(Collection-And-Delivery Points, CDPs)模式?jīng)Q策問題；陳義友等[6]將顧客有限理性行為引入最后一公里配送服務(wù)的研究中，認(rèn)為顧客根據(jù)自身期望的效用最大目標(biāo)選擇收貨方式是基于顧客不完全理性行為的決策。

由于國內(nèi)與國外在人口分布及生活方式等方面的巨大差異，國內(nèi)學(xué)者主要借鑒國外學(xué)者在配送模式方面的研究成果研究符合中國特色的自提點選址問題。

周林等[7]綜合考慮送貨上門和顧客自提兩種服務(wù)，建模并設(shè)計兩階段模擬退火算法求解多容量終端選址—多車型路徑集成的優(yōu)化問題;李梅[8]以運輸成本、建站成本和距離懲罰成本最小化為目標(biāo)建立自提點的選址模型；楊朋玨等[9]針對送貨上門和自行取貨配送模式構(gòu)建滿意度、效率的多目標(biāo)城市末端網(wǎng)點選址模型,但未考慮自提點類型不同對顧客選擇的影響;陳義友等[10]用多項 Logit模型(MultiNomial Logit model, MNL)模型刻畫顧客的有限理性行為，用Erlang-B模型描述自提點擁堵情形構(gòu)建自提點選址模型，并用多種算法求解；陳義友等[11]考慮自提點類型，用凹凸函數(shù)刻畫消費者的滿意度，通過設(shè)計拉格朗日松弛算法求解基于逐漸覆蓋的自提點選址模型，但是未考慮不同類型自提點服務(wù)功能差異對選址結(jié)果的影響。已有研究成果表明，影響顧客選擇自提服務(wù)的因素很多，其中包括自提點的類型、覆蓋半徑[12]、處理能力、服務(wù)能力、建設(shè)成本、自提點的吸引力、顧客滿意度等，現(xiàn)有的關(guān)于自提點選址問題的研究中，大部分只考慮了一兩個因素的影響，而且都是針對顧客只有一種需求的情況開展研究。

本文主要考慮顧客同時有自提和退換貨兩種需求下的自提柜、快遞企業(yè)自建網(wǎng)點和與便民機(jī)構(gòu)合作3種類型的自提點選址分配問題。在綜合考慮不同類型自提點的建設(shè)成本、服務(wù)功能、服務(wù)能力、顧客滿意度等因素的前提下，建立自提點選址—分配問題的數(shù)學(xué)模型并設(shè)計求解模型的算法，以降低企業(yè)總的運行成本。

1 問題描述及數(shù)學(xué)模型

網(wǎng)絡(luò)消費者在地理空間上除了分布范圍廣之外，還呈現(xiàn)顯著的空間集聚性，即在同一細(xì)粒度地理空間會存在多個客戶，如學(xué)校、商場、小區(qū)等[13]。為研究多需求多類型自提點選址分配問題，本文將每個細(xì)粒度地理空間看作為一個客戶群，每個客戶群為一個需求點，每個需求點的顧客有一種或兩種不同類型的需求(取貨、退換貨)，圍繞物流最后一公里配送需求特征展開以總建設(shè)成本極小化為目標(biāo)的選址—分配方案研究。

多需求多類型自提點選址分配問題可以描述為：在給定的物流末端配送網(wǎng)絡(luò)中有n個需求點，一個需求點存在一種或兩種不同類型的需求(取貨、退換貨)，已知各個需求點的位置和對兩種不同類型服務(wù)的需求量;配送網(wǎng)絡(luò)中有3種不同類型的備選自提點(自提柜、自建網(wǎng)點型、便利店型)共m個，每個備選點可以提供一種或兩種服務(wù);已知各個備選自提點的位置、建設(shè)成本、可提供的服務(wù)類型和最大服務(wù)能力等，在一定的顧客滿意度水平下，企業(yè)如何確定各種類型自提點的建設(shè)數(shù)量、建設(shè)位置和每個自提點的服務(wù)范圍，才能使總建設(shè)成本最小。

1.1 模型假設(shè)

(1)自提柜型自提點只能提供自提服務(wù)，快遞企業(yè)自建網(wǎng)點型和與便民機(jī)構(gòu)合作型兩類自提點可以提供自提和退換貨兩種服務(wù)。

(2)每個需求點的同一種需求由一個自提點滿足，不同服務(wù)需求可由多個類型的自提點滿足。

(3)需求點對自提點的服務(wù)滿意度是需求點到自提點的距離rij的非增函數(shù)，本文采用凹凸覆蓋函數(shù)刻畫的距離引力[10]計算顧客滿意度，具體函數(shù)關(guān)系為

(1)

其中：r和R為已知參數(shù)，且r

1.2 符號和變量說明

為了建立多需求多類型自提點選址分配問題的數(shù)學(xué)模型，定義如下符號：

I表示需求點的集合；

J表示候選自提點的集合；

K表示自提點類型的集合；

L表示服務(wù)類型的集合，L={1，2}；

B表示企業(yè)計劃的投資金額；

ηk表示k類型自提點對顧客的吸引力,ηk∈[0,1],k∈K；

Rk表示第k種類型自提點的最大覆蓋半徑；

rk表示第k種類型自提點的最小覆蓋半徑；

αk表示對第k類候選自提點設(shè)置的最低顧客滿意度值；

i∈I,j∈J,k∈K。

(2)

定義如下決策變量：

1.3 模型建立

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

其中：目標(biāo)函數(shù)(3)表示極小化自提點的總建設(shè)成本；約束(4)表示各種類型自提點服務(wù)需求點的總需求量不超過各個自提點的最大處理能力；約束(5)表示每個需求點若有某一種服務(wù)需求，則這種需求恰好由一個自提點滿足；約束(6)保證提供服務(wù)的自提點到需求點的顧客滿意度大于預(yù)先設(shè)定值；約束(7)表示若某個備選點對應(yīng)需要提供服務(wù)的需求點，則必須在該備選點建立自提點；約束(8)表示建立的自提點至少滿足一個需求點的一種服務(wù)需求；約束(9)和(10)表示變量的取值約束。

2 遺傳算法設(shè)計

雖然多需求多類型自提點選址分配問題可以表示為一個整數(shù)規(guī)劃模型，但由于模型中的約束條件和變量較多，很難在短時間內(nèi)通過直接求解整數(shù)規(guī)劃模型得到最優(yōu)解。本章根據(jù)整數(shù)規(guī)劃模型的特點設(shè)計遺傳算法(Genetic Algorithms, GA)求解多需求多類型自提點的選址分配問題，并通過MATLAB軟件編程計算，驗證模型和算法的有效性。

考慮3種類型自提點和兩種類型服務(wù)需求(自提、退換貨)。3種類型自提點中的自提柜型自提點只能提供自提服務(wù)，首先計算各個需求點到各類型候選自提點的顧客滿意度矩陣，其中行表示需求點，列表示候選自提點，3種類型自提點的排列順序依次為自提柜型、快遞企業(yè)自建網(wǎng)點型和與便民機(jī)構(gòu)合作型，根據(jù)多需求多類型自提點選址分配問題的特點設(shè)計染色體編碼規(guī)則，并根據(jù)滿意度矩陣進(jìn)行染色體編碼，生成初始種群。

遺傳算法操作規(guī)則如下：

(1)染色體編碼

結(jié)合本文所建立的數(shù)學(xué)模型，定義染色體編碼規(guī)則如下：

1)根據(jù)需求類型劃分，每一條染色體由第Ⅰ類染色體片段即(自提類)和第Ⅱ類染色體片段(即退換貨類)組成，如圖1所示。圖中：列表示有A，B，C 3種類型自提點，其數(shù)量分別為3，2，3；行表示有4個需求點，前4行表示4個需求點的自提需求，后4行表示4個需求點的退換貨需求；第1行第1列的1表示第1個需求點的自提需求由A類型的第1個候選自提點服務(wù)，以此類推。解碼得到多需求多類型自提點選址分配模型的一個可行解。

2)每一條染色體片段均是一個0-1矩陣，矩陣的每行對應(yīng)一個需求點，每列對應(yīng)一個自提點，如果需求點i的相應(yīng)類型需求由自提點j提供服務(wù)，則矩陣中第i行第j列的元素等于1，否則等于0。 例如，圖1中矩陣第1行第1列的元素1表示需求點1的自提需求由A類型中的1號自提柜提供服務(wù)；矩陣第5行第1列的元素0表示需求點1的退換貨服務(wù)不是由A類型中的1號自提柜提供。

3)因為需求點的一種服務(wù)需求只能由一個自提點提供服務(wù)，所以染色體矩陣中每行有且只有一個元素(基因位)的值為1。

(2)初始種群的生成

采用將某些先驗知識轉(zhuǎn)化為必須滿足的條件，并在滿足約束條件的解中隨機(jī)抽取個體構(gòu)成初始種群的方法[14]。本文采用0-1矩陣編碼方式，將需求點到對應(yīng)服務(wù)類型自提點的顧客滿意度值小于給定值αk的位置賦值為0，根據(jù)自提點服務(wù)能力約束和顧客滿意度約束，按照輪盤賭法確定為需求點服務(wù)的自提點，將對應(yīng)位置賦值為1，其余位置賦值為0。以此類推，按照預(yù)先設(shè)計的編碼規(guī)則隨機(jī)生成相應(yīng)的染色體編碼矩陣，直至生成足夠多的個體構(gòu)成GA的初始種群。

(3)適應(yīng)度函數(shù)

根據(jù)將每個個體對應(yīng)的染色體解碼后的解可以求出每個個體對應(yīng)的目標(biāo)函數(shù)值，即各類型自提點建設(shè)總成本，第s個個體對應(yīng)的目標(biāo)函數(shù)值

(11)

由于模型中的目標(biāo)函數(shù)為最小化問題，本文采用種群對應(yīng)的最大目標(biāo)函數(shù)值的兩倍(即2max(objv))減去objv(s)，作為對應(yīng)個體的適應(yīng)度值[15]，即

FitV(s)=2max(objv)-objv(s)。

(12)

(4)選擇操作

本文采用輪盤賭法對個體進(jìn)行選擇操作。

(5)交叉操作

由于每個染色體由兩類染色體片段組成，進(jìn)行交叉操作時，選擇同類片段染色體進(jìn)行位點交換，一個個體對應(yīng)的兩個染色體片段的交叉位點相同。交叉規(guī)則設(shè)計如下：本文交叉采用雙親雙子單點交叉，從種群中取出奇數(shù)位的個體和相鄰的偶數(shù)位個體組成個體對，即父代P1和父代P2，按照給定的交叉概率選擇一部分個體對進(jìn)行交叉操作。對于需要進(jìn)行交叉的個體對，隨機(jī)選擇交叉點位置pos，將父代P1中第Ⅰ類染色體片段的[pos:n]行與父代P2中第Ⅰ類染色體片段的[pos:n]行互換,同時將父代P1中第Ⅱ類染色體片段的[n+pos:2n]行與父代P2中第Ⅱ類染色體片段的[n+pos:2n]行互換產(chǎn)生兩個子代個體S1,S2,如圖2所示。

判斷生成的兩個子代個體對應(yīng)的解是否都滿足自提點處理能力約束和顧客滿意度約束，若不滿足則重新進(jìn)行交叉操作，直至生成滿足約束條件的子代個體。若對兩個個體交叉若干次后(本文設(shè)置最大交叉次數(shù)n1=100次)仍未產(chǎn)生都滿足約束條件的子代個體，則這兩個個體不再進(jìn)行交叉操作。交叉操作完成后計算個體的目標(biāo)函數(shù)值，判斷交叉操作后最優(yōu)個體的目標(biāo)函數(shù)值是否優(yōu)于上代種群中最優(yōu)個體的目標(biāo)函數(shù)值，若是則不再進(jìn)行變異操作直接進(jìn)入下一代，否則進(jìn)行變異操作。

GA交叉部分的計算步驟如下：

步驟2按照交叉概率隨機(jī)選取若干對父代個體參與交叉操作。算法偽代碼如下：

步驟3當(dāng)累計交叉次數(shù)小于100時，whilen1<100，令n1=n1+1，隨機(jī)選擇交叉位置，對兩個父代個體中的兩類染色體分別進(jìn)行交叉操作，產(chǎn)生兩個臨時子代個體，將兩個臨時子代個體解碼形成兩個解。

步驟4判斷交叉后的兩個臨時子代個體對應(yīng)的解是否滿足容量約束。若不滿足容量約束，則返回步驟3；若滿足容量約束，則轉(zhuǎn)步驟5。

步驟5判斷滿足容量約束的兩個臨時子代對應(yīng)的解是否滿足顧客最低滿意度約束。若不滿足顧客最低滿意度約束，則返回步驟3；若滿足顧客最低滿意度約束，則保留交叉后的兩個臨時子代個體，令i=i+1,轉(zhuǎn)步驟2。

步驟6如果n1=100,即個體交叉100次仍未產(chǎn)生滿足約束條件的子代個體，則不再進(jìn)行交叉操作，直接保留交叉前的兩個父代個體，令i=i+1,轉(zhuǎn)步驟2。

步驟7當(dāng)n1=100時，結(jié)束while循環(huán)，返回步驟2。

步驟8結(jié)束for循環(huán)。

步驟9計算交叉后的種群中每個個體對應(yīng)的目標(biāo)函數(shù)值和適應(yīng)度函數(shù)值，求出交叉后種群對應(yīng)的最優(yōu)目標(biāo)函數(shù)值min(new_objv)。判斷交叉后種群的最優(yōu)目標(biāo)函數(shù)值min(new_objv)是否小于種群進(jìn)化過程中產(chǎn)生的最優(yōu)個體對應(yīng)的目標(biāo)函數(shù)值min(objv)，若min(new_objv)

(6)變異操作

變異操作是改變?nèi)旧w編碼串上的部分基因值，從而提高種群的多樣性。本文采用在兩段染色體片段中分別交換行向量的變異方法，即在選定個體的染色體片段中隨機(jī)產(chǎn)生兩個交叉點，互換兩個交叉點對應(yīng)的行，得到新的子代個體。例如將上例的染色體A進(jìn)行變異，如圖3所示。

變異操作是在交叉操作生成的子代最優(yōu)個體不如上一代最優(yōu)個體的情況下進(jìn)行的。預(yù)先設(shè)置變異概率參數(shù)pm，根據(jù)變異概率選擇一部分個體進(jìn)行變異操作。對于每一個參與變異操作的個體，判斷變異后對應(yīng)的解是否滿足自提點處理能力約束和顧客滿意度約束，若不滿足則重新進(jìn)行變異操作，直至生成滿足約束條件的子代個體。若對某個個體變異若干次后(本文設(shè)置最大變異次數(shù)n2=100次)仍未產(chǎn)生滿足約束條件的子代個體，則不再進(jìn)行變異操作。變異操作完成后計算每個個體的目標(biāo)函數(shù)值，判斷變異操作后最優(yōu)個體的目標(biāo)函數(shù)值是否優(yōu)于上代種群中最優(yōu)個體的目標(biāo)函數(shù)值，若是，則保留該種群進(jìn)入下一代;否則,先用上代最優(yōu)個體替換變異后的最壞個體，然后進(jìn)入下一代。

(7)終止規(guī)則

當(dāng)?shù)螖?shù)達(dá)到設(shè)定的最大次數(shù)后，算法終止。

(8)遺傳算法流程圖

遺傳算法的具體流程如圖4所示。

3 算例分析

3.1 算例描述

根據(jù)某城區(qū)的居民分布情況將該城區(qū)劃分為10個需求點，其中需求點8只有自提需求，需求點9只有退換貨需求，其余8個需求點均有自提和退換貨服務(wù)兩種需求。已知每個需求點的自提需求量qi(件)和退換貨服務(wù)需求量pi(件)，該區(qū)域有3種類型候選自提點，其中只能提供自提服務(wù)的自提柜型候選點(A類)為nA(個)，可以提供自提和退換貨服務(wù)的企業(yè)自建網(wǎng)點型候選自提點(B類)為nB(個)，可以提供自提和退換貨服務(wù)的與便民機(jī)構(gòu)合作型候選自提點(C類)為nC(個)；根據(jù)對各個小區(qū)居民的問卷調(diào)查，設(shè)置最低顧客滿意度值αk和不同備選自提點對顧客的吸引力ηk。不考慮快件的體積和重量，不同類型自提點服務(wù)參數(shù)(建設(shè)成本、服務(wù)能力，以及最小、最大覆蓋半徑)的設(shè)置如表1所示；不同備選自提點對顧客的吸引力ηk如表2所示;各個需求點的位置坐標(biāo)已知，各個需求點對應(yīng)的各類型需求量如表3所示。需求點到備選自提點的距離rij可以根據(jù)位置分布算出。

表1 不同類型自提點服務(wù)參數(shù)設(shè)置

表2 不同類型自提點對應(yīng)的吸引力指數(shù)η值

表3 各個需求點對應(yīng)的兩種類型服務(wù)的需求量 件

3.2 求解結(jié)果

本文設(shè)定初始種群大小為50，最大進(jìn)化代數(shù)為100，交叉概率為0.8，變異概率為0.02，各類型自提點的最低顧客滿意度值αk均為0.85，無效交叉次數(shù)最大值n1=100，無效變異次數(shù)最大值n2=100。利用MATLAB R2012a軟件編程，在Intel(R)Core(TM)i5-480M@2.67 GHz CPU，4 GB內(nèi)存電腦上運行5 s，得到的最優(yōu)計算結(jié)果如表4所示。

表4 最低顧客滿意度為0.85時的選址結(jié)果

在利用MATLAB運行GA求解的同時，本文也利用Lingo 11.0軟件編寫了直接求解整數(shù)規(guī)劃模型的程序，結(jié)果發(fā)現(xiàn)Lingo程序求出來的全局最優(yōu)解與GA得到的最優(yōu)解相同(如表4)，可見利用本文設(shè)計的GA求得的最優(yōu)解即為全局最優(yōu)解。最優(yōu)目標(biāo)函數(shù)值為29萬元，最優(yōu)解對應(yīng)的自提柜類型(A類)、快遞企業(yè)自建網(wǎng)點型(B類)、與便民機(jī)構(gòu)合作型自提點(C類)的建設(shè)數(shù)量分別為1，1，2；表5所示為各類型自提點的最優(yōu)選址—分配結(jié)果；圖5所示為利用GA求解過程中最優(yōu)目標(biāo)函數(shù)值與迭代次數(shù)之間的變化關(guān)系；圖6所示為GA求出的每個自提點與服務(wù)需求點之間的分配關(guān)系。與Lingo程序直接求解整數(shù)規(guī)劃模型相比，利用GA可以在較短時間內(nèi)得到問題的最優(yōu)解，特別是隨著問題規(guī)模的增大，采用GA求解的優(yōu)勢更加明顯。

表5 遺傳算法求出的最優(yōu)選址—分配結(jié)果

3.3 結(jié)果分析

本文模型以自提點的總建設(shè)成本極小化為目標(biāo)，約束條件為顧客滿意度不低于最低滿意度值αk，而顧客滿意度和自提點總建設(shè)成本之間存在密切聯(lián)系，下面重點分析顧客的最低滿意度αk與自提點總建設(shè)成本之間的關(guān)系。

由式(2)可以看出，顧客滿意度是顧客到自提點距離的非增函數(shù)，提高顧客最低滿意度值αk相當(dāng)于減小了各個自提點的有效服務(wù)半徑，由此需要建設(shè)更多自提點才能覆蓋所有需求點，從而需要更多的建設(shè)成本?？梢姡Ｐ椭性O(shè)定的最低滿意度值αk越大，最優(yōu)解對應(yīng)的自提點總建設(shè)成本越大。

本例通過選取不同的顧客最低滿意度值分別求解模型，得到最低顧客滿意度值αk與自提點建設(shè)總成本之間的關(guān)系，如圖7所示?？梢钥闯?，當(dāng)企業(yè)將最低滿意度設(shè)為91.2%時，各類型自提點的總建設(shè)成本最優(yōu)值為29萬元;當(dāng)企業(yè)將最低顧客滿意度設(shè)為100%時，各類型自提點的總建設(shè)成本最優(yōu)值為39萬元。實際中，快遞企業(yè)可根據(jù)對顧客群體的調(diào)查，確定滿意度最低值αk的設(shè)定方案，根據(jù)模型計算自提點總建設(shè)成本，再結(jié)合企業(yè)投資預(yù)算進(jìn)一步確定有利于提高顧客最低滿意度的自提點選址—分配方案。如在上述案例中，當(dāng)設(shè)定顧客最低滿意度為0.85時，用本文模型和算法得出的最優(yōu)選址分配方案對應(yīng)的總建設(shè)成本為29萬元，根據(jù)最低顧客滿意度和總建設(shè)成本的靈敏度分析圖可知，在保持總建設(shè)成本為29萬元的前提下，通過優(yōu)化選址分配方案可以使顧客的最低滿意度提高到91.2%。

4 結(jié)束語

與一般選址問題不同的是，多需求多類型自提點選址分配問題考慮顧客需求的多樣性，以及不同類型自提點的服務(wù)功能、覆蓋半徑、容量大小、建設(shè)成本、對顧客的吸引力等多方面因素。本文考慮自提與退換貨服務(wù)兩種需求，并在一定顧客滿意度約束下設(shè)計GA求解建設(shè)成本最小的多類型自提點選址—分配方案。算例分析結(jié)果顯示，GA能在較短時間內(nèi)求得問題的近似最優(yōu)解，驗證了模型和算法的有效性，通過多類型自提點的組合布局能更有效、更經(jīng)濟(jì)地滿足顧客需求，為快遞企業(yè)快速搶占末端市場、提高競爭力提供了理論依據(jù)。但由于不同類型自提點的處理能力在實際生活中具有較大差異，容量差異對自提點的建設(shè)成本也存在較大影響，未來可以在考慮同一類型自提點容量設(shè)置的情況下研究多類型自提點選址分配問題，以及同時考慮顧客滿意度最大化與建設(shè)成本最小化的多目標(biāo)多需求多類型自提點選址分配問題。