□劉 虹 傅曉敏

[福州大學(xué) 福州 350108]

引言

城市物流行業(yè)發(fā)展日益快速，促使物流企業(yè)競(jìng)爭(zhēng)愈加激烈，為提高競(jìng)爭(zhēng)優(yōu)勢(shì)，車輛路徑作為物流配送的關(guān)鍵環(huán)節(jié)，必須具備更大的靈活性才能適用多變、激烈的物流市場(chǎng)。在城市配送系統(tǒng)中，貨物經(jīng)由車輛從城市配送中心交付至客戶，考慮城市路況的局限性，一般采用小型容量車執(zhí)行配送任務(wù)，同時(shí)又存在車輛更早于工作日結(jié)束前返回配送中心的情況，在Olivera和Viera[1]發(fā)現(xiàn)單行程車輛路徑問題不適于較低車輛容量限制及配送時(shí)間較長(zhǎng)的路徑后，多行程車輛配送開始受到廣泛的關(guān)注。

多行程（Multi-Trip，MT）配送由于允許車輛中途返回配送中心，可在配送中心和配送點(diǎn)之間多次往返完成任務(wù)[2]，在提高服務(wù)效率、降低車輛啟動(dòng)成本和司機(jī)雇傭費(fèi)用等方面占有明顯優(yōu)勢(shì)。隨著城市經(jīng)濟(jì)規(guī)模擴(kuò)大、新興技術(shù)發(fā)展，研究多行程車輛路徑在復(fù)雜配送環(huán)境中的優(yōu)化問題，對(duì)科學(xué)規(guī)劃城市配送具有重要意義。

在多行程物流中，MTVRP研究?jī)?nèi)容主要集中于分配路線數(shù)量、限制車輛服務(wù)時(shí)間、求解優(yōu)化算法和調(diào)整策略等方面。Francois等學(xué)者先構(gòu)造初始路徑集合后單獨(dú)分配給車輛，并采用大規(guī)模鄰域搜索算法尋求最優(yōu)解[3]；Hernandez等學(xué)者開放車輛服務(wù)時(shí)間限制，研究了帶時(shí)間窗的多行程路徑問題，并設(shè)計(jì)分支定價(jià)算法尋求路徑最優(yōu)[4]；宋強(qiáng)等學(xué)者在時(shí)間約束條件下構(gòu)建MTVRP數(shù)學(xué)模型，并分別改進(jìn)了混合遺傳算法、迭代局部搜索算法和變鄰域搜索算法進(jìn)行求解，尋求運(yùn)行成本最小化[5～7]；Ampol等學(xué)者改進(jìn)了插入啟發(fā)式算法求解帶有時(shí)間窗、班次時(shí)間限制和可變交貨時(shí)間的多行程庫存路徑問題[8]；學(xué)者李陽和范厚明針對(duì)客戶的不確定需求，引入不確定相關(guān)理論，提出點(diǎn)返回多行程策略進(jìn)行路徑優(yōu)化，研究了尋求總成本最小的MTVRP問題[9～10]；張曉楠等學(xué)者在客戶模糊需求和時(shí)間窗偏好約束下，以物流成本和時(shí)間成本總和最小為目標(biāo)構(gòu)建MTVRP模型，并提出“基于成本期望值”的實(shí)時(shí)調(diào)整策略[11]。

綜上所述，已有多行程路徑問題研究文獻(xiàn)主要集中以降低運(yùn)輸成本為主要目標(biāo)的模型求解優(yōu)化上，考慮客戶滿意度的多行程配送的研究較少，且多行程路徑允許多次配送的特征直接影響車輛配送時(shí)間和次數(shù)，進(jìn)而會(huì)導(dǎo)致客戶滿意度發(fā)生變化，加之隨著物流配送的多樣化，客戶滿意度將作為企業(yè)提高核心競(jìng)爭(zhēng)力的一個(gè)關(guān)鍵，因此研究考慮客戶滿意度的多行程車輛路徑優(yōu)化具有實(shí)際意義。根據(jù)多行程的特點(diǎn)，本文從配送時(shí)間窗、服務(wù)次數(shù)兩方面衡量客戶滿意度并建立相應(yīng)的客戶滿意度函數(shù)，同時(shí)兼顧客戶取送雙向隨機(jī)需求，構(gòu)建同時(shí)考慮運(yùn)輸成本和滿意度的多目標(biāo)多行程路徑優(yōu)化模型，并設(shè)計(jì)求解算法尋求最佳車輛配送路徑?jīng)Q策。

一、問題描述及模型建立

（一）問題描述與假設(shè)

本文研究的是包含配送中心和客戶點(diǎn)的配送網(wǎng)絡(luò)中的多行程車輛路徑問題。貨物在配送中心進(jìn)行集中送貨，客戶為同時(shí)取送貨及其需求具有隨機(jī)性，配送中心派遣車輛采用同時(shí)取送的多行程配送模式服務(wù)客戶點(diǎn)?？蛻舾鶕?jù)貨物送達(dá)時(shí)間的不同會(huì)產(chǎn)生不同程度的滿意度，客戶接受車輛服務(wù)次數(shù)的不同也會(huì)影響滿意度，多行程車輛配送需進(jìn)行路徑?jīng)Q策，使得客戶滿意度最大和運(yùn)輸成本最小。

為突出多行程配送的特性，做出如下假設(shè)：

1. 配送中心的坐標(biāo)以及客戶點(diǎn)數(shù)量、坐標(biāo)、配送時(shí)間窗、服務(wù)次數(shù)要求已知；

2. 客戶取送貨需求均服從隨機(jī)分布，且只有當(dāng)車輛到達(dá)客戶點(diǎn)時(shí)其需求才會(huì)被確認(rèn)；

3. 每輛車僅有一條配送路線，且每條路線上的客戶取送貨需求總量不能超過車輛容量能力；

4. 取送貨物可以進(jìn)行混合運(yùn)輸，車輛從配送中心出發(fā)，完成配送任務(wù)之后需要返回配送中心；

5. 配送途中勻速行駛且速度已知，配送途中的運(yùn)輸成本只與配送路程相關(guān)；

6. 預(yù)優(yōu)化中每個(gè)客戶點(diǎn)僅能接受一輛車服務(wù)，且車輛首次從配送中心出發(fā)時(shí)均處于滿載狀態(tài)；

7. 實(shí)際配送中可采用部分服務(wù)策略，即客戶允許同一輛車多次配送。

（二）符號(hào)和變量說明

1. 參數(shù)符號(hào)

TB：車輛k在配送中心處的補(bǔ)貨時(shí)間；

2. 決策變量

（三）滿意度測(cè)度

在多行程配送活動(dòng)中，客戶具有自己的期望配送時(shí)間窗和服務(wù)次數(shù)要求，為兼顧客戶的服務(wù)需求，考慮客戶對(duì)車輛到達(dá)時(shí)間和實(shí)際配送次數(shù)的不同心理感受，分別建立客戶滿意度測(cè)度函數(shù)，綜合衡量客戶服務(wù)水平。

1. 時(shí)間窗滿意度函數(shù)

定義1比較車輛到達(dá)客戶時(shí)刻與客戶配送時(shí)間窗以背離配送時(shí)間窗程度衡量客戶滿意度，見圖1，客戶滿意度函數(shù)表達(dá)式詳見式（1）。

圖 1 時(shí)間窗滿意度函數(shù)

不同時(shí)間區(qū)間的滿意度如下：

2. 服務(wù)次數(shù)滿意度函數(shù)

定義2服務(wù)次數(shù)與客戶滿意度呈負(fù)相關(guān)，服務(wù)次數(shù)越多，客戶滿意度越低，比較車輛實(shí)際配送次數(shù)與客戶服務(wù)次數(shù)范圍，對(duì)客戶滿意度函數(shù)描述詳見式（2）。

不同次數(shù)區(qū)間的滿意度如下：

3. 客戶綜合滿意度函數(shù)

定義3客戶綜合滿意度由基于配送時(shí)間窗的滿意度式（1）和基于服務(wù)次數(shù)的滿意度式（2）共同決定，客戶綜合滿意度函數(shù)表現(xiàn)為式（3）。

（四）數(shù)學(xué)模型

1. 目標(biāo)函數(shù)

2. 約束條件

其中，式（4）和（5）為目標(biāo)函數(shù)，式（4）為最小化車輛派遣成本和配送成本之和；式（5）為最大化客戶平均滿意度，包括時(shí)間窗滿意度和服務(wù)次數(shù)滿意度；式（6）表示配送路線上需求點(diǎn)的正向配送總量小于等于車輛載重限制；式（7）表示配送路線上需求點(diǎn)的逆向攬收總量小于等于車輛載重限制；式（8）表示車輛在配送途中的負(fù)載量不超過車輛最大載重限制；式（9）為車輛在服務(wù)客戶點(diǎn)j后的動(dòng)態(tài)負(fù)載量的計(jì)算等式；式（10）～（11）保證預(yù)階段路徑方案中任一客戶點(diǎn)有且僅有一條車輛配送路線，且車輛只能從配送中心出發(fā)一次；式（12）～（13）消除不合理回路，且保證同一個(gè)客戶點(diǎn)之間沒有車輛配送路線；式（14）表示車輛配送時(shí)間先后要與客戶配送順序一致；式（15）為車輛配送客戶前后的時(shí)間計(jì)算式；式（16）～（17）表明決策變量屬性。

二、模型轉(zhuǎn)換與求解

（一）隨機(jī)機(jī)會(huì)約束規(guī)劃模型

1. 目標(biāo)函數(shù)

同目標(biāo)函數(shù)式（4）～（5）。

2. 約束條件

其余約束同式（10）～（17）。

（二）點(diǎn)判斷實(shí)時(shí)策略

定理1車輛服務(wù)下一客戶點(diǎn)，擬選擇方案一，則客戶點(diǎn)的成本期望值和滿意度期望值詳見如下：

證明：

由將式（24）代入式（3）得

由將式（25）代入式（3）得

將式（25）～（26）、式（28）～（29）、式（31）代入式（30）可得式（23），至此式（23）得證。

定理2車輛服務(wù)下一客戶點(diǎn)，擬選擇方案二，則客戶點(diǎn)的成本期望值和滿意度期望值詳見如下：

證明：

由將式（34）代入式（3）得

由將式（37）代入式（3）得

將式（34）～（35）、式（37）～（38）、式（40）代入式（39）可得式（32），至此式（32）得證。

針對(duì)不同方案下得到的客戶點(diǎn)期望值結(jié)果，選擇配送成本期望值較小且客戶滿意度較高的方案作為車輛在服務(wù)客戶點(diǎn)之后的路徑優(yōu)化選擇。

（三）模型求解

多行程車輛路徑問題屬于NP難題，考慮多目標(biāo)優(yōu)化的MTVRP模型求解難度增加，禁忌搜索算法可通過使用禁忌規(guī)則使算法跳出局部迂回，實(shí)現(xiàn)全局最優(yōu)化[14～15]，故本文針對(duì)多目標(biāo)優(yōu)化模型，設(shè)計(jì)了嵌套調(diào)整策略的灰關(guān)聯(lián)分析多目標(biāo)禁忌搜索算法進(jìn)行求解。

1. 灰關(guān)聯(lián)分析

灰關(guān)聯(lián)分析主要通過灰關(guān)聯(lián)度判斷序列間關(guān)聯(lián)程度。確定一個(gè)序列作為參考標(biāo)準(zhǔn)，然后將其他序列與參考序列進(jìn)行比較，與參考序列越接近，表示該序列效果越好，反之則表示效果越差。基于傳統(tǒng)灰色關(guān)聯(lián)分析，引入信息熵理論，用均衡接近度代替灰關(guān)聯(lián)度，有效彌補(bǔ)了關(guān)聯(lián)傾向的缺陷[16～17]。

灰關(guān)聯(lián)分析的具體步驟如下：

2. 嵌套調(diào)整策略的灰關(guān)聯(lián)分析多目標(biāo)禁忌搜索算法

針對(duì)MTVRP多目標(biāo)優(yōu)化模型設(shè)計(jì)的算法如下：

Step 9：生成最終解。通過點(diǎn)判斷實(shí)時(shí)策略進(jìn)行多行程路徑調(diào)整，生成實(shí)際路徑?jīng)Q策，輸出最終解。

三、算例驗(yàn)證與結(jié)果分析

（一）實(shí)驗(yàn)算例

本文研究的考慮客戶滿意度的同時(shí)取送貨多行程車輛路徑問題模型，尚無標(biāo)準(zhǔn)測(cè)試算例，針對(duì)所建模型特點(diǎn)，參考Prodhon的選址-路徑問題標(biāo)準(zhǔn)算例集50-5-1，進(jìn)行適當(dāng)選取和擴(kuò)展得到本文測(cè)試算例。設(shè)客戶點(diǎn)送貨需求和取貨需求分別服從為50和35的泊松分布，參考文獻(xiàn)[18]增加時(shí)間窗限制，具體數(shù)據(jù)如表1所示。此外，配送中心坐標(biāo)為（43,3），車輛派遣成本=2 500，單位配送成本=25，車容量能力=220，客戶點(diǎn)服務(wù)時(shí)間=10，補(bǔ)貨時(shí)間=10，車輛速度=1。由于本文的多行程配送方式，對(duì)于參數(shù)、需根據(jù)配送中客戶對(duì)服務(wù)次數(shù)的接受程度來設(shè)定，本實(shí)驗(yàn)設(shè)定參數(shù)= 1，=3來測(cè)試算例。

表 1 客戶節(jié)點(diǎn)坐標(biāo)及配送時(shí)間窗數(shù)據(jù)

（二）實(shí)驗(yàn)結(jié)果與分析

1. 預(yù)先優(yōu)化階段

對(duì)算例進(jìn)行仿真實(shí)驗(yàn)，得到的Pareto解集結(jié)果如表2所示。為了更好分析，通過客戶滿意度公式，計(jì)算以運(yùn)輸成本為單目標(biāo)求得最優(yōu)解對(duì)應(yīng)的客戶滿意度為86.87%，并將其標(biāo)注于Pareto解集坐標(biāo)圖上，如圖2所示。

從空間分布對(duì)比圖中可以看出：只關(guān)注成本的單目標(biāo)多行程路徑模型在配送成本上取得了比同時(shí)考慮成本和客戶滿意度的多目標(biāo)多行程路徑模型的所有決策方案都更好的表現(xiàn)。然而在客戶滿意度上的表現(xiàn)均劣于多目標(biāo)多行程路徑模型的所有方案。由此可見，運(yùn)輸成本和服務(wù)水平兩個(gè)目標(biāo)是不能同時(shí)達(dá)到最優(yōu)，追求低成本需要以降低客戶滿意度為代價(jià)，提高滿意度通常也會(huì)增加物流成本。企業(yè)可根據(jù)自身發(fā)展需求選擇合適的決策方案。

圖 2 單目標(biāo)最優(yōu)解與Pareto解集空間圖

表 2 Pareto解集

針對(duì)模型求解所得的Pareto解集所對(duì)應(yīng)的方案很難進(jìn)行優(yōu)劣之分，但決策者總是需要從中選擇一個(gè)用以指導(dǎo)路徑規(guī)劃。本文分別將運(yùn)輸成本、客戶滿意度作為單目標(biāo)進(jìn)行優(yōu)化，仿真15次求得最優(yōu)解26 368、1（作為灰關(guān)聯(lián)參考序列），通過計(jì)算并比較Pareto解集所對(duì)應(yīng)的目標(biāo)函數(shù)值序列與參考序列（26 368，1）的均衡接近度，確定最優(yōu)方案，為企業(yè)提供最佳參考。Pareto解集對(duì)應(yīng)的均衡接近度如表3所示。

表 3 Pareto解集均衡接近度

由表3可知，Pareto解6與最優(yōu)解（26 368,1）的均衡接近度為0.715 6最大，根據(jù)灰關(guān)聯(lián)分析理論可知，均衡接近度越大，表明Pareto解6越接近理想最優(yōu)解。由此，選擇Pareto解6作為預(yù)優(yōu)化階段最佳參考解，具體決策方案為車輛1：0-6-24-7-11-0，車輛2：0-8-23-22-20-0，車輛3：0-19-9-1-2-0，車輛4：0-4-10-15-12-0，車輛5：0-5-17-14-16-0，車輛6：0-21-13-18-3-0，總成本為28 443.99，客戶滿意度為99.82%。

2. 實(shí)際配送階段

（1）實(shí)際配送中，在沒有采取任何實(shí)時(shí)策略的前提下，車輛按預(yù)優(yōu)化階段參考路徑服務(wù)客戶，由于取送貨需求的隨機(jī)性，車輛的剩余載貨量或者空余可載貨量可能不足導(dǎo)致客戶點(diǎn)配送失敗，造成配送路徑的中斷，具體情況如圖3所示。在路線1中，客戶11為配送失敗的中斷點(diǎn)，致使客戶點(diǎn)11前后相鄰路徑為無效配送路徑；在路線4中，客戶4為中斷點(diǎn)，客戶4作為車輛服務(wù)首個(gè)客戶點(diǎn)，導(dǎo)致整個(gè)車輛服務(wù)路線4為無效路徑；在路線5中，客戶16為配送失敗的中斷點(diǎn)，因此客戶點(diǎn)16前后相鄰配送路徑無效。

圖 3 配送中斷路徑圖

（2）在實(shí)際配送中，采取本文提出的“點(diǎn)判斷”多行程策略進(jìn)行實(shí)時(shí)路徑調(diào)整，實(shí)際配送路徑方案為車輛1：0-6-24-7-0-11-0，車輛2：0-8-23-22-20-0，車輛3：0-19-9-1-2-0，車輛4：0-4-0-4-10-15-12-0，車輛5：0-5-17-14-0-16-0，車輛6：0-21-13-18-3-0，總成本為31 838，客戶滿意度為92.15%。“點(diǎn)判斷”實(shí)時(shí)調(diào)整策略基于預(yù)先優(yōu)化最佳路徑方案進(jìn)行調(diào)整，較于無任何調(diào)整策略下實(shí)際配送產(chǎn)生中斷，可避免因客戶需求隨機(jī)導(dǎo)致路徑中斷。

四、結(jié)論

在多行程配送網(wǎng)絡(luò)中，綜合考慮客戶滿意度和運(yùn)輸成本建立多行程路徑多目標(biāo)優(yōu)化模型，針對(duì)模型具有同時(shí)取送、隨機(jī)參數(shù)、多行程動(dòng)態(tài)以及多目標(biāo)等特征，提出“點(diǎn)判斷”實(shí)時(shí)調(diào)整策略，引入隨機(jī)機(jī)會(huì)約束規(guī)則和灰關(guān)聯(lián)分析理論，設(shè)計(jì)了嵌套調(diào)整策略的灰關(guān)聯(lián)多目標(biāo)禁忌搜索算法尋求最佳配送路徑。通過算例實(shí)驗(yàn)，驗(yàn)證了模型和算法的有效性。得出以下結(jié)論：

1. 低成本運(yùn)輸是物流企業(yè)追求的長(zhǎng)期目標(biāo)，而隨著物流行業(yè)間競(jìng)爭(zhēng)的愈發(fā)激烈，服務(wù)水平將成為企業(yè)提高核心競(jìng)爭(zhēng)力的一個(gè)關(guān)鍵。多行程路徑配送模型同時(shí)考慮成本和客戶滿意度進(jìn)行多目標(biāo)優(yōu)化，可為企業(yè)如何同時(shí)兼顧物流成本和服務(wù)水平提供參考。

2. 采用“點(diǎn)判斷”實(shí)時(shí)策略調(diào)整進(jìn)行多行程配送，可有效避免配送路徑中斷，同時(shí)多行程配送會(huì)產(chǎn)生基于服務(wù)次數(shù)的客戶滿意度，符合實(shí)際情境。

3. 用灰關(guān)聯(lián)分析理論和禁忌搜索算法相結(jié)合，能有效尋求路徑最優(yōu)，提高算法求解質(zhì)量。

在多方因素的影響下，現(xiàn)實(shí)中的多行程配送網(wǎng)絡(luò)較為復(fù)雜，進(jìn)一步研究多行程配送系統(tǒng)中的多動(dòng)態(tài)模型將是下一步的研究重點(diǎn)。