基于客戶信用度的物流配送車輛路徑問題研究

王 勇, 范 舉, 劉 永, 許茂增

(重慶交通大學(xué) 經(jīng)濟(jì)與管理學(xué)院,重慶 400074)

0 引言

隨著物流業(yè)的快速發(fā)展，客戶信用受到物流企業(yè)的日趨重視，信用作為市場經(jīng)濟(jì)的基石，對物流行業(yè)的發(fā)展尤為重要。近年來，在物流配送過程中，頻繁出現(xiàn)的客戶交易違約失信問題，已經(jīng)給物流企業(yè)造成了一定程度的損失，然而，基于客戶信用度的車輛路徑問題研究可以實(shí)現(xiàn)物流配送企業(yè)的高效率運(yùn)作,進(jìn)而降低物流企業(yè)的運(yùn)營成本。因此，研究基于客戶信用度的物流配送車輛路徑問題，有利于構(gòu)建城市物流配送的客戶服務(wù)信用體系，并有助于城市物流配送系統(tǒng)的可持續(xù)發(fā)展。國內(nèi)外學(xué)者在基于客戶信用度的物流配送車輛路徑優(yōu)化問題研究主要集中在基于客戶需求屬性和基于客戶重要度的車輛路徑問題兩個(gè)方面。

在基于客戶需求屬性的車輛路徑問題研究方面，Panchamgam等[1]考慮客戶需求屬性和服務(wù)優(yōu)先級研究了人道主義救援路線設(shè)計(jì)的層次旅行商問題，并進(jìn)行了服務(wù)效率和優(yōu)先級之間的均衡研究。朱莉等[2]研究了考慮災(zāi)民需求屬性和決策者異質(zhì)性行為的多階段災(zāi)后救援物資分配和應(yīng)急路徑優(yōu)化問題，并與不考慮異質(zhì)性行為的傳統(tǒng)救援調(diào)度方案進(jìn)行了對比分析研究。胡曉偉等[3]研究了突發(fā)公共衛(wèi)生事件下城市應(yīng)急醫(yī)療物資優(yōu)化調(diào)度問題，并研究了應(yīng)急醫(yī)療物資供給不足情況下需求差異對公平分配的影響。Huang等[4]在人道主義救援行動中，設(shè)計(jì)了包含受援者需求屬性的績效指標(biāo)，并研究了效率、效能和公平對車輛路線訪問順序和救濟(jì)物資分配的影響。李珍萍等[5]考慮客戶需求服務(wù)時(shí)間窗和客戶不同需求的服務(wù)順序構(gòu)建了一種混合整數(shù)規(guī)劃模型，并應(yīng)用聯(lián)合優(yōu)化遺傳算法研究了帶時(shí)間窗和服務(wù)順序約束的車輛路徑問題。符卓等[6]針對軟時(shí)間窗的客戶需求訂單拆分的車輛路徑問題構(gòu)建了數(shù)學(xué)規(guī)劃模型，提出了禁忌搜索算法進(jìn)行求解。根據(jù)上述研究文獻(xiàn)可以發(fā)現(xiàn)，在物流配送過程中考慮客戶需求、服務(wù)時(shí)間窗和車輛容量限制等屬性為基于客戶信用度的車輛訪問序列優(yōu)化和車輛路徑優(yōu)化模型構(gòu)建提供了研究切入。

在基于客戶重要度的車輛路徑問題研究方面，Ma等[7]通過考慮客戶重要性和客戶聚集密度研究確定了客戶服務(wù)順序，構(gòu)建了危險(xiǎn)品運(yùn)輸中多站點(diǎn)車輛路徑問題的多目標(biāo)優(yōu)化模型，并提出了一種求解模型的混合遺傳算法。Bai等[8]在異質(zhì)車輛包裹配送問題中考慮客戶的重要性和緊急程度進(jìn)行了客戶服務(wù)排序，構(gòu)建了一種基于客戶優(yōu)先約束的異質(zhì)車輛配送優(yōu)化模型，并提出考慮任務(wù)分配的啟發(fā)式算法進(jìn)行求解。王勇等[9]基于客戶重要度進(jìn)行了聚類分析，將客戶重要度與服務(wù)時(shí)間窗相結(jié)合構(gòu)建了一種雙層數(shù)學(xué)規(guī)劃模型，并提出GA-TS混合算法研究了基于客戶重要度的混合時(shí)間窗車輛路徑問題。于江霞等[10]根據(jù)客戶消費(fèi)頻次和消費(fèi)金額對客戶進(jìn)行了重要性分類，構(gòu)建了一種基于客戶分類的即時(shí)配送路徑優(yōu)化模型，并設(shè)計(jì)了遺傳算法進(jìn)行模型求解。丁秋雷等[11]針對易逝品物流配送中出現(xiàn)的干擾事件影響問題提出了優(yōu)先服務(wù)重要客戶的策略，構(gòu)建了一種多目標(biāo)干擾管理模型，并應(yīng)用改進(jìn)的蟻群算法進(jìn)行模型求解。由上述相關(guān)研究可知，當(dāng)前基于客戶重要度的車輛路徑問題研究主要集中在考慮客戶重要性和緊急性構(gòu)建車輛路徑優(yōu)化模型，進(jìn)而確定客戶服務(wù)訪問序列問題等方面，而結(jié)合客戶信用度研究物流配送車輛路徑問題還有待進(jìn)一步深入。

因此，本文通過考慮客戶信用度對物流配送路線的影響，研究在配送路線安排中將客戶服務(wù)分為不同信用等級并結(jié)合服務(wù)時(shí)間窗進(jìn)行合理的運(yùn)輸調(diào)度，構(gòu)建了基于客戶信用度的物流配送車輛路徑優(yōu)化模型，并在模型中引入客戶信用度作為影響違反時(shí)間窗懲罰成本的參數(shù)。同時(shí)設(shè)計(jì)了一種GA-TS混合算法進(jìn)行模型求解，進(jìn)而研究了基于客戶信用度的物流配送車輛路徑問題。

1 客戶信用度計(jì)算

針對部分外賣平臺嘗試通過外賣歷史數(shù)據(jù)獲得客戶的信用等級，進(jìn)而給予不同等級客戶不同的服務(wù)權(quán)限，如等級高的客戶購買同樣的外賣產(chǎn)品可以獲得更多的積分服務(wù)，且在繁忙時(shí)段可以優(yōu)先享受平臺派單服務(wù)等。不同的客戶信用等級對應(yīng)著不同的信用值范圍，而不同的信用值范圍對應(yīng)不同的客戶信用度。本文將客戶在配送時(shí)間內(nèi)取消訂單、無故退換貨、拒收貨、被賣家投訴和惡意差評等看作客戶交易違約。假設(shè)選取客戶中的樣本總數(shù)為n，第i(i≤n)個(gè)客戶3年內(nèi)在網(wǎng)上訂購商品總數(shù)記為Ai，發(fā)生交易違約的次數(shù)記為Bi，則第i個(gè)客戶的信用值Pi(其中Pi∈[0,1])可以通過式(1)計(jì)算：

(1)

本文將客戶信用等級劃分為9類進(jìn)行研究，并將信用值劃分為9個(gè)區(qū)間，每個(gè)信用值區(qū)間對應(yīng)相應(yīng)的信用度值，則客戶i的信用度γi可以通過式(2)計(jì)算得到，其中，e表示客戶信用等級總數(shù)，λi為客戶信用等級分類數(shù)?？蛻粜庞玫燃壴u價(jià)如表1所示。

表1 客戶信用等級評價(jià)表

(1)

2 模型建立

2.1 變量定義

相關(guān)變量定義如表2所示。

表2 變量定義

2.2 模型構(gòu)建

本文以配送中心的物流配送總成本最小化為目標(biāo)，結(jié)合客戶信用等級劃分表計(jì)算得到客戶信用度，進(jìn)而建立基于客戶信用度的物流配送車輛路徑優(yōu)化模型如下：

minZ=TC1+TC2+PC

(3)

TC1：配送成本，配送車輛將商品送達(dá)客戶的成本。

(4)

TC2：配送車輛的租賃成本。

(5)

PC：基于客戶信用度的配送車輛違反服務(wù)時(shí)間窗的懲罰成本。

(6)

約束條件:

(19)

式(7)表示每一輛車從配送中心出發(fā)且最終返回配送中心；式(8)表示配送車輛將商品送達(dá)客戶點(diǎn)后必須離開客戶點(diǎn)；式(9)表示消除配送路線上的子回路；式(10)表示配送線路內(nèi)需求商品的總量不超過車輛的最大裝載量；式(11)表示所有配送客戶的商品需求總量不超過配送中心的最大配送量；式(12)和(13)表示對于任一客戶點(diǎn)，僅能有一輛車訪問并離開；式(14)～(15)表示配送車輛離開和到達(dá)配送中心的時(shí)間必須在其服務(wù)時(shí)間窗內(nèi)；式(16)表示配送過程的連續(xù)性；式(17)、(18)和(19)表示變量約束。

3 GA-TS混合算法研究

3.1 算法描述

本文設(shè)計(jì)了遺傳-禁忌搜索(GA-TS)混合算法求解基于客戶信用度的物流配送車輛路徑優(yōu)化模型。由于禁忌搜索算法對初始解具有較強(qiáng)的依賴性[12]，為了提高算法的搜索能力，本算法設(shè)計(jì)過程先通過遺傳算法進(jìn)行全局搜索，提高種群規(guī)模的多樣性，再應(yīng)用禁忌搜索算法進(jìn)行局部搜索，并采用精英保留策略返回遺傳算法階段進(jìn)行循環(huán)迭代優(yōu)化。該混合算法結(jié)合了遺傳算法的全局搜索能力和禁忌搜索算法的局部搜索能力，進(jìn)而拓展了算法的局部搜索空間和提高了算法的全局收斂性能。GA-TS混合算法操作流程圖如圖1所示。

3.2 算法檢驗(yàn)

為了驗(yàn)證GA-TS混合算法的有效性，將GA-TS混合算法分別與混合遺傳算法(HGA)[13]、禁忌搜索粒子群算法(TS-PSO)[14]和改進(jìn)的蟻群優(yōu)化算法(IACO)[15]進(jìn)行比較。本文從Solomon數(shù)據(jù)集[16]選取了20組不同規(guī)模的隨機(jī)測試數(shù)據(jù)，并將客戶分為不同的信用等級分類方案進(jìn)行研究。實(shí)驗(yàn)數(shù)據(jù)對應(yīng)的數(shù)據(jù)集、客戶數(shù)量、客戶信用等級分類方案如表3所示。

通過表3的實(shí)驗(yàn)數(shù)據(jù)，分別從物流配送總成本、車輛使用數(shù)和算法運(yùn)行時(shí)間三個(gè)方面比較四種算法的優(yōu)化結(jié)果。四種算法的各項(xiàng)參數(shù)設(shè)置如下：GA-TS和HGA算法中的種群規(guī)模popsize=100，最大迭代次數(shù)maxgen=200，選擇概率ps=0.9，交叉概率pc=0.9，變異概率pm=0.1；GA-TS和TS-PSO算法中禁忌搜索迭代次數(shù)tsin=40，禁忌表長度TL=28；TS-PSO算法中的慣性權(quán)重ω=0.9，學(xué)習(xí)因子c1=1.2，c2=1.4;IACO算法中的信息素權(quán)重α=1，啟發(fā)因子β=2，信息素?fù)]發(fā)系數(shù)ρ=0.5。將每種算法分別運(yùn)行20次，提取20次計(jì)算過程的物流配送總成本最優(yōu)解以及其對應(yīng)的車輛使用數(shù)和算法運(yùn)行時(shí)間，如表4所示。

表3 數(shù)據(jù)集特征

表4 不同算法優(yōu)化結(jié)果的比較

由表4可知，其他三種算法相對于GA-TS混合算法求解的物流配送總成本對應(yīng)的t檢驗(yàn)值和p值具有明顯差異性。GA-TS混合算法在配送總成本均優(yōu)于HGA、TS-PSO和IACO算法，GA-TS混合算法的配送總成本平均值為11756元，而其他三種算法分別為12049元、11934元和12151元；四種算法求解的平均車輛使用數(shù)分別為16輛，18輛，17輛和19輛；此外，GA-TS混合算法求解20組數(shù)據(jù)的平均運(yùn)行時(shí)間均優(yōu)于其他3種算法。因此，本文所提的GA-TS混合算法相對于其他三種算法具有較好的穩(wěn)定性和可靠性。

4 算例分析

4.1 案例相關(guān)數(shù)據(jù)

本文在重慶市選取了由一個(gè)配送中心(DC)和200個(gè)客戶點(diǎn)(D1,D2,……，D200)組成的實(shí)際外賣物流配送網(wǎng)絡(luò)作為研究對象，相應(yīng)的地理位置分布情況如圖2所示。

在現(xiàn)有文獻(xiàn)[9,13,16]和多次計(jì)算實(shí)驗(yàn)的基礎(chǔ)上，相關(guān)參數(shù)設(shè)置如下：車輛最大裝載量Qk=20，百公里油耗量fk=2.89，汽油價(jià)格ρc=6.09，車輛租賃成本σk=50，種群規(guī)模pepsize=100，最大迭代次數(shù)maxgen=200，選擇、交叉和變異概率ps=0.9，pc=0.9，pm=0.1，禁忌搜索迭代次數(shù)tsin=40，禁忌表長度TL=28。

4.2 結(jié)果及分析

應(yīng)用GA-TS混合算法求解基于客戶信用度的物流配送車輛路徑，計(jì)算得到的優(yōu)化方案如表5所示。

由表5可知，以考慮物流配送總成本最小化為目標(biāo)的基于客戶信用度的外賣物流配送優(yōu)化方案中,配送中心需要派遣27輛車對200個(gè)客戶點(diǎn)進(jìn)行配送服務(wù)。結(jié)合前期調(diào)研獲取的客戶點(diǎn)配送線路(優(yōu)化前)，通過本文構(gòu)建的模型和算法計(jì)算獲得客戶點(diǎn)配送線路(優(yōu)化后)，進(jìn)而得到基于客戶信用度的外賣物流配送成本?；诳蛻粜庞枚鹊耐赓u物流配送優(yōu)化前后的對比結(jié)果如表6所示。

表5 基于客戶信用度的外賣物流配送優(yōu)化方案

從表6可知，相比優(yōu)化前的配送方案，考慮客戶信用度的優(yōu)化方案有效降低了物流配送總成本。其中，配送成本、車輛租賃成本和基于客戶信用度的違反時(shí)間窗懲罰成本分別降低了49%、18%和70%，車輛使用數(shù)由33輛減少到27輛，違反時(shí)間窗的客戶點(diǎn)數(shù)由24個(gè)減少到9個(gè)。因此，在物流配送車輛路徑優(yōu)化中結(jié)合服務(wù)時(shí)間窗將客戶服務(wù)劃分為不同信用等級進(jìn)行配送，可以有效降低物流配送成本，進(jìn)而提高城市物流配送效率。

表6 基于客戶信用度的外賣物流配送優(yōu)化前后結(jié)果對比

4.3 分析與討論

基于客戶信用度的物流配送車輛路徑問題是以物流配送總成本為優(yōu)化目標(biāo)，在優(yōu)化過程中基于客戶信用度的違反時(shí)間窗懲罰成本是物流配送總成本的重要組成部分。為了進(jìn)一步研究客戶信用度高低對物流配送總成本的影響，設(shè)定車輛路徑優(yōu)化過程中，優(yōu)先服務(wù)信用度高的客戶點(diǎn)，對于信用度相同的客戶結(jié)合客戶服務(wù)時(shí)間窗進(jìn)行車輛路徑優(yōu)化，進(jìn)而計(jì)算得到配送成本，車輛租賃成本，違反時(shí)間窗的客戶點(diǎn)數(shù)，車輛使用數(shù)和物流配送總成本?？蛻襞渌头?wù)方案調(diào)整前后優(yōu)化結(jié)果對比如表7所示。

由表7可知，優(yōu)先服務(wù)信用度高的客戶方案調(diào)整后，物流配送總成本增加了6%，車輛使用數(shù)增加了3輛，違反時(shí)間窗的客戶點(diǎn)數(shù)增加了5個(gè)，而由于調(diào)整了客戶服務(wù)策略(即優(yōu)先服務(wù)信用度高的客戶)，使得基于客戶信用度的違反時(shí)間窗懲罰成本反而減少。因此，結(jié)合客戶服務(wù)時(shí)間窗和客戶信用度進(jìn)行物流配送車輛調(diào)度有利于進(jìn)行有效的客戶配送服務(wù)和進(jìn)一步降低系統(tǒng)的物流配送總成本。

表7 優(yōu)先服務(wù)信用度高的客戶方案調(diào)整前后結(jié)果對比

4.4 敏感度分析

本文的敏感度分析包括客戶不同信用等級變化的敏感度分析和客戶信用等級分類方案的敏感度分析。客戶不同信用等級變化的敏感度分析是將客戶的不同信用等級依次全部統(tǒng)一調(diào)整為Ⅰ級、Ⅱ級、Ⅲ級、Ⅳ級、Ⅴ級、Ⅵ級、Ⅶ級、Ⅷ級和Ⅸ級，計(jì)算每次調(diào)整后的物流配送總成本、違反時(shí)間窗的客戶點(diǎn)數(shù)和車輛使用數(shù)，計(jì)算結(jié)果如圖3所示。

由圖3可知，當(dāng)所有客戶的信用等級依次從Ⅰ級改變至Ⅸ級時(shí)，物流配送總成本、違反時(shí)間窗的客戶點(diǎn)數(shù)和車輛使用數(shù)均會隨之改變。當(dāng)將所有信用等級調(diào)整為Ⅰ級，II級和Ⅸ級后進(jìn)行配送服務(wù)時(shí)，物流配送總成本會增加。由于對信用等級全為Ⅰ和II級的客戶進(jìn)行配送服務(wù)時(shí)，雖然違反時(shí)間窗的客戶點(diǎn)數(shù)較少，但單位時(shí)間的懲罰成本系數(shù)大，也將產(chǎn)生較高的懲罰成本，進(jìn)而導(dǎo)致物流配送總成本增加；對信用等級為Ⅸ級的客戶進(jìn)行配送服務(wù)時(shí)，雖然單位時(shí)間的懲罰成本系數(shù)小，但違反時(shí)間窗的客戶點(diǎn)數(shù)較多，產(chǎn)生的懲罰成本也隨之增加，進(jìn)而導(dǎo)致物流配送總成本增加。而將所有信用等級調(diào)整為Ⅳ級后的客戶進(jìn)行配送服務(wù)時(shí)，物流配送總成本和車輛使用數(shù)均最小。

客戶信用等級分類方案的敏感度分析主要是研究客戶信用等級不同分類模式下應(yīng)用本文構(gòu)建的模型和提出的混合算法計(jì)算比較物流配送總成本、違反時(shí)間窗的客戶點(diǎn)數(shù)和車輛使用數(shù)的變化。將客戶信用等級分別分為2～12個(gè)分類方案，進(jìn)行計(jì)算結(jié)果比較，如圖4所示。隨著客戶信用等級分類方案的增加，物流配送總成本、違反時(shí)間窗的客戶點(diǎn)數(shù)和車輛使用數(shù)均會隨之改變，當(dāng)客戶信用等級分類為7、8和9時(shí)，對應(yīng)的車輛使用數(shù)相同，但客戶信用等級分類為9時(shí)，對應(yīng)的物流配送總成本和違反時(shí)間窗的客戶點(diǎn)數(shù)均優(yōu)于客戶信用等級分類為7和8時(shí)的對應(yīng)方案；當(dāng)客戶信用等級分類為9和10時(shí)，對應(yīng)的違反時(shí)間窗的客戶點(diǎn)數(shù)相同，但客戶信用等級分類為9時(shí)對應(yīng)的物流配送總成本和車輛使用數(shù)均優(yōu)于客戶信用等級分類為10時(shí)的對應(yīng)方案。本文的優(yōu)化目標(biāo)是基于客戶信用度的物流配送總成本最小，因此，客戶信用等級分類結(jié)果為9時(shí)對應(yīng)的物流配送方案最佳，同時(shí)也表明對客戶信用等級進(jìn)行合理分類，可以有效降低物流配送總成本，減少違反時(shí)間窗的客戶點(diǎn)數(shù)和車輛使用數(shù)。

5 結(jié)論

本文研究了基于客戶信用度的物流配送車輛路徑優(yōu)化問題，將客戶分為不同信用等級并結(jié)合服務(wù)時(shí)間窗進(jìn)行合理的配送線路調(diào)度，通過引入客戶信用度作為影響違反時(shí)間窗懲罰成本的參數(shù)，建立包含物流配送車輛的運(yùn)輸成本、租賃成本以及基于客戶信用度的懲罰成本的物流配送總成本最小的優(yōu)化模型，并設(shè)計(jì)了GA-TS混合算法進(jìn)行模型求解，該混合算法通過有效利用GA的全局搜索能力和TS的局部搜索能力拓展了算法的局部搜索空間和提高了算法的全局收斂性能。將GA-TS混合算法與HGA算法、TS-PSO算法和IACO算法的求解結(jié)果進(jìn)行對比分析，結(jié)果表明本研究提出的GA-TS混合算法優(yōu)于其他算法。

本文通過基于客戶信用度的模型求解對物流配送路線進(jìn)行了優(yōu)化設(shè)計(jì)，并以重慶市某外賣物流配送網(wǎng)絡(luò)為例，驗(yàn)證了模型和算法的有效性。計(jì)算結(jié)果表明，優(yōu)化后基于客戶信用度的配送方案使物流配送總成本、違反時(shí)間窗的客戶點(diǎn)數(shù)和車輛使用數(shù)分別減少了38%、63%和13%。此外，客戶不同信用等級變化和客戶信用等級分類方案的敏感度分析表明：客戶信用等級全部調(diào)整為Ⅳ級時(shí)，物流配送總成本最小；客戶信用等級分類方案為9時(shí)，對應(yīng)的配送方案最優(yōu)。本文為物流配送車輛路徑優(yōu)化問題提供了新的研究思路，且具有較強(qiáng)的應(yīng)用價(jià)值。