高鐵快運城市配送優(yōu)化模型及算法研究

楊博文，金哲宇

(蘭州交通大學 交通運輸學院，甘肅 蘭州 730070)

0 引言

自2014 年起，鐵路運營企業(yè)推出一系列高鐵快運產(chǎn)品，積極打造高速鐵路物流品牌，目前的合作體系中多為與第三方物流進行合作，物流配送體系還不完善，從“門到站”和“站到門”有一部分要依靠第三方物流配送，配送質(zhì)量有待提升，“最后一公里”的問題尚未有效解決[1-2]，亟需對高鐵快運城市配送問題展開研究，以更好減少配送成本，提高快件配送的時效性和客戶滿意度，提升高鐵快運形象。

高鐵快運城市配送問題屬于車輛路徑規(guī)劃問題，對于城市配送的車輛路徑問題，國內(nèi)外學者展開了廣泛研究。楊黎朝[3]基于國家政策和京東平臺發(fā)展現(xiàn)狀，分析了京東自營配送物流的必要性，建立了帶軟時間窗的京東生鮮食品電動車物流路徑優(yōu)化模型，提出了最佳的充電策略。袁濤等[4]在考慮解決應急物資物流配送問題時，構(gòu)建了多式聯(lián)運多級應急物流網(wǎng)絡(luò)，考慮了災后道路損毀對通行時間和可靠度的影響，以救援總成本最小為目標，生成路徑方案。李偉等[5]針對高鐵快運末端物流城市配送成本過高的問題，考慮時間懲罰成本，建立帶軟時間窗的城市末端物流配送路徑優(yōu)化模型。蔣叢萃[6]在尋找高鐵快運配送最短路上，設(shè)計一種針對電子商務物流的配送路徑優(yōu)化算法，建立物流配送路徑優(yōu)化多目標函數(shù)，尋找到最優(yōu)的目標路徑。常樂等[7]針對電動汽車配送問題，以客戶滿意度最大和運輸距離最短等為目標，建立電動汽車多目標配送模型，設(shè)計一種改進蟻群算法解決模型。Carina 等[8]為了最大程度地減少總服務時間和確保服務同步，提出城市物流配送服務運營規(guī)劃的數(shù)學模型。吳耕銳等[9]以運輸安全和運輸距離為目標，建立雙目標路徑優(yōu)化模型，設(shè)計自適應隨機多目標路徑選擇算法。

可見，針對高鐵快運城市配送的路徑優(yōu)化問題研究需要對高鐵快運的服務特點和市場定位充分考慮，故基于高鐵快運業(yè)務小批量、多頻次、高品質(zhì)的特點和高鐵快運業(yè)務的發(fā)展方向，提出服務質(zhì)量目標和成本目標，構(gòu)建高鐵快運城市配送多目標優(yōu)化模型，決策車輛配送路徑。

1 高鐵快運城市配送優(yōu)化模型構(gòu)建

1.1 問題描述

高鐵快運物流配送是高鐵快遞在營業(yè)部完成到達作業(yè)后與客戶進行快遞交付的一個關(guān)鍵環(huán)節(jié)，主要包括確定客戶配送區(qū)域、配送順序、配載車輛、配送車輛路徑、進行車輛配送和問題件處理等環(huán)節(jié)。高鐵快運城市配送的目標客戶為對時間要求敏感的客戶，高鐵快運城市配送貨物的特點為小批量、多頻次和高品質(zhì)，配送客戶的特點為分布分散且服務需求多元化，配送的關(guān)鍵決策是提供優(yōu)質(zhì)快運配送服務，提升服務質(zhì)量水平。目前高鐵快運物流配送主要存在以下問題：①配送成本較高，常因司機的主觀意識強、習慣走某條道路或其他原因使配送路徑變長，造成較高的配送成本；②配送中心單一，由于業(yè)務量不足，高鐵快運快遞市場有待發(fā)掘，目前在辦理高鐵快運業(yè)務的城市大多為配送中心—客戶的二級城市配送結(jié)構(gòu)；③服務質(zhì)量較低，高鐵快運城市配送的目標客戶為對時間要求敏感的客戶，不同客戶對配送時間的要求不同，過早或過晚的配送服務使配送服務質(zhì)量變低。在生成配送路徑方案時，要考慮到配送中心和客戶雙方的利益，既要保證高鐵快遞準時送達到客戶手中，又要保證配送中心的配送收益，故在進行模型構(gòu)建時主要本著“高時效性”和“物流成本低”2個原則。

高鐵快運城市配送優(yōu)化問題可被描述為：在高鐵快運城市配送網(wǎng)絡(luò)中有1 個配送中心(高鐵快運營業(yè)部)、多個客戶點和多個配送車輛，配送車輛從配送中心出發(fā)，有且只經(jīng)過1 次各客戶點且每個客戶均被服務1 次，最后返回配送中心。配送車輛送達客戶的時間必須早于客戶要求的最晚時間，故配送車輛必須在客戶規(guī)定的服務時間或早于服務時間到達客戶點進行配送服務。模型構(gòu)建基于以下假設(shè)：①城市配送道路的各個時間段的擁擠度相同，各配送車輛的平均速度一致；②每個高鐵快件的最晚配送時間不超過客戶提出的服務提供時間；③配送車輛返回的最晚時間不能超過配送中心規(guī)定的下班時間。

1.2 模型變量參數(shù)設(shè)置

設(shè)高鐵快運城市配送網(wǎng)絡(luò)為G=(N，A)，其中高鐵快運配送中心0 和所有客戶點i 的集合N=

{0，1，2，...，n}。 各 節(jié) 點 間 有 向 弧 的 集 合 為A={＜ni，nj＞|ni，nj∈N，i ≠ }j ，其中＜ni，nj＞表示客戶點ni到客戶點nj的幾何路徑。模型相關(guān)符號及含義如表1所示。

表1 模型相關(guān)符號及含義Tab.1 Related symbols in the model and their meaning

1.3 模型構(gòu)建

高鐵快運主要提供2 大類服務：時效快遞和經(jīng)濟快遞。其中，時效快遞主要有4 種產(chǎn)品：當日達、次晨達、次日達與隔日達。經(jīng)濟快遞分為2 種產(chǎn)品：普通快遞和同城快遞。其中當日達、次晨達、次日達、隔日達分別是指在客戶要求的城市之間為客戶提供快遞服務，并承諾在當日22：00、次日11：00、次日18：00、第三日18：00 前送達收件人。

高鐵快運客戶辦理業(yè)務的不同會影響到在服務質(zhì)量目標中客戶的重要性，故提出快運服務客戶重要度的概念，用于評價高鐵快運業(yè)務辦理客戶的重要程度。客戶點ni的快運服務客戶重要度θi的計算公式為

式中：λ1，λ2，λ3，λ4分別表示辦理當日達、次晨達、次日達和隔日達業(yè)務的運價首重，kg；zi表示客戶ni辦理的高鐵快運業(yè)務類型，z1，z2，z3，z4分別表示客戶辦理的業(yè)務為當日達、次晨達、次日達和隔日達。

客戶不滿意度與車輛到達客戶點的時間關(guān)系如圖1 所示。關(guān)于客戶不滿意度sij隨著時間t 的變化產(chǎn)生2段函數(shù)。

圖1 客戶不滿意度與車輛到達客戶點的時間關(guān)系Fig.1 Relationship between customer dissatisfaction and the time vehicles arrive at customer points

考慮以下2 種情況：①當配送車輛到達客戶點nj的時刻aij早于客戶規(guī)定的時間窗[bi，ei]時，客戶將產(chǎn)生不滿意度，由于高鐵快運辦理的業(yè)務是定時服務，如與客戶所辦理的定時服務有所偏差，會引起客戶的不滿，偏差結(jié)果越大，旅客的不滿意度越高；②當配送車輛到達客戶點nj的時刻aij在客戶規(guī)定的時間窗[bi，ei]內(nèi)，客戶將不產(chǎn)生不滿意度，考慮到客戶在規(guī)定的時間窗內(nèi)收到高鐵快運快件會對高鐵快運業(yè)務產(chǎn)生滿意感，但s 代表客戶不滿意度，所以s ≡0。此外配送車輛到達客戶點nj的時間aij晚于客戶規(guī)定的時間窗[bi，ei]將不被考慮在內(nèi)。sij計算公式為

每個客戶點服務的起始時間要早于客戶終止服務的時間，可表示為

配送車輛從配送中心出發(fā)的時間小于車輛返回配送中心的時間，可表示為

2 算法設(shè)計

針對高鐵快運城市配送多目標優(yōu)化模型，采用帶精英策略的非支配排序遺傳算法(Elitist Non-Dominated Sorting Genetic Algorithm，NSGA-Ⅱ)，對高鐵快運城市配送優(yōu)化模型進行算法設(shè)計。NSGA-Ⅱ是基于帕累托(Pareto)最優(yōu)解優(yōu)化，與其他算法相比，NSGA-Ⅱ的種群多樣性和分布性較優(yōu)，收斂性更快，求解速度也相對較快，主要體現(xiàn)在快速非支配排序、擁擠度因子和精英策略3大核心思想，使得算法可在解決多目標問題上具有良好的表現(xiàn)性，算法流程圖如圖2所示。

圖2 算法流程圖Fig.2 Algorithm flow chart

（1）構(gòu)造非支配集。NSGA-Ⅱ中通過快速非支配排序構(gòu)造非支配集，首先，找出該種群中的所有非支配染色體，得到第一個非支配最優(yōu)層；然后對種群中的其他個體繼續(xù)按照支配與非支配關(guān)系進行分層，對剩下的個體繼續(xù)上述操作，直到種群中的所有個體都被分層。

（2）擁擠度排列比較。NSGA-Ⅱ中的擁擠度是引入擁擠度nd和擁擠度比較算子，先對種群個體p 進行無距離化處理，隨后以擁擠度比較算子對種群個體進行排列，然后用擁擠度公式求出每個種群個體p的擁擠度，最后比較個體間的擁擠度nd并進行升序排列。

式中：M 為目標個數(shù)；fm(i+1)表示該個體在對應的Pareto 等級的下一個個體對應的目標函數(shù)值；fm(i-1)表示該個體在對應的Pareto 等級的上一個個體對應的目標函數(shù)值。

以二維目標為例，種群個體p 在Pareto 域中按等級進行分層，擁擠度是在該目標空間每個個體p 不觸碰其他同等級個體所生成的最大矩形的邊長之和。

（3）選擇優(yōu)質(zhì)解。NSGA-Ⅱ中通過精英策略選擇優(yōu)質(zhì)解，將經(jīng)過選擇的父代的優(yōu)良種群的個體與經(jīng)過交叉變異的子代種群進行混合，然后進行選擇后形成新的優(yōu)良種群，這樣生成的下一代種群會保留父代種群的優(yōu)良個體，維持種群的多樣性，提高了種群水平。

（4）算法流程。算法首先定義相關(guān)變量參數(shù)，迭代次數(shù)Gen 初始為0，初始化種群Rt生成初代種群。通過快速非支配排序得到非支配集Z，通過擁擠度比較算子對Fi從大到小排列，精英策略將Fi的非支配解放入到種群Ct+1中。對父代種群Ct+1進行選擇、交叉和變異操作得到子代種群Dt+1。將子代種群Dt+1和父代種群Ct+1混合成個體數(shù)為2N 的種群，并按照錦標賽準則選擇個體生成種群Rt。反復迭代直到生成滿意的非支配集，當Gen 等于最大迭代次數(shù)max(Gen)時，跳出循環(huán)、算法結(jié)束。

3 算例分析

以某城市一次高鐵快運配送為例，該高鐵快運配送網(wǎng)絡(luò)包含21 個節(jié)點，包含1 個配送中心和20 個客戶點，基本參數(shù)取值如表2 所示，將各配送中心和客戶點置于坐標系內(nèi)進行計算。

設(shè)置初始種群數(shù)量為100，最大迭代次數(shù)500，交叉概率為0.9，變異概率為0.1。運行此算法對優(yōu)化模型求解。在求得的Pareto 解集中，考慮到高鐵快運配送中心決策者在不同情況下所側(cè)重方向不同，分別選取服務質(zhì)量目標最優(yōu)和配送成本最優(yōu)的解作為高鐵快運城市配送路徑方案，其中配送方案Ⅰ是在保證一定成本的基礎(chǔ)上使服務質(zhì)量目標最小的方案；配送方案Ⅱ為保證一定服務質(zhì)量的基礎(chǔ)上使成本最小的方案，2個方案配送車輛數(shù)均為4輛，得到2個配送方案情況對比如表3 所示。在服務質(zhì)量目標方面，配送方案Ⅰ的服務質(zhì)量目標數(shù)值為51.32，較配送方案Ⅱ低37.83；在成本目標方面，配送方案Ⅰ的快件配送成本為1 034.24元，配送方案Ⅰ的成本較方案Ⅱ高63.78元。

2個配送方案車輛路線軌跡圖如圖3所示，配送車輛從配送中心出發(fā)經(jīng)過多個客戶點，最終回到配送中心。配送方案Ⅰ中，配送車輛為了服務質(zhì)量最大化，犧牲了配送車輛的行駛距離；配送方案Ⅱ中配送車輛是在滿足客戶規(guī)定的配送時間窗的等條件下進行配送，此方案在路徑選擇上犧牲了客戶一定的滿意度，將配送總成本降到最低。高鐵快運配送中心決策者可考慮不同的目標側(cè)重，結(jié)合相關(guān)情況選擇不同方案：偏向配送成本選擇配送方案Ⅰ，偏向服務質(zhì)量選擇配送方案Ⅱ。

圖3 2個方案車輛路線軌跡圖Fig.3 Vehicle route trajectories of two schemes

表2 基本參數(shù)取值Tab.2 List of basic parameters

表3 2個配送方案情況對比Tab.3 Comparison between two distribution schemes

4 結(jié)束語

高鐵快運依托現(xiàn)有高速鐵路網(wǎng)運輸資源和運力優(yōu)勢，向客戶提供中小快件的中高端運輸服務，實現(xiàn)“門到門”之間運輸，為鐵路貨運現(xiàn)代物流模式轉(zhuǎn)變提供了新的方向。目前高鐵快運處于發(fā)展階段，日均快件配送量不高，因此在研究時只考慮了單個配送中心、二級配送網(wǎng)絡(luò)進行配送，當高鐵快運業(yè)務發(fā)展到一定階段后，還需考慮多個配送中心、三級配送網(wǎng)絡(luò)進行配送的情況。在進行配送服務時，將客戶服務時間窗固定，在實際情況中，某些客戶可能因特殊情況導致無法配送，需要問題件處理進行二次配送，可做進一步優(yōu)化研究。