基于遺傳算法的生鮮同城配送路徑優化研究

唐佩佩 馮曉威 宮英麗

（同濟大學 經濟與管理學院，上海 201800）

1 研究目的

在同城配送中，運輸成本是總配送成本的一大部分。目前，電子商務下生鮮同城配送取得了一些成就，但同時由于受經營管理、城市配送條件、小批量、多頻次、生鮮易腐等特點的制約，導致生鮮同城配送存在一些問題，影響著同城配送的進一步發展。

（1）不能滿足客戶時間窗的需求

客戶通過網絡在電子商務平臺訂購生鮮品，很多情況下客戶都無法在配送網點長時間等待，一般是約定某一時間段內將農產品送到，但企業由于車輛調度、路況異常、同一時間段內要求配送訂單較多等原因，往往無法滿足客戶的時間窗需要。這會造成客戶的滿意度問題，長此以往將會造成客戶流失，影響企業的品牌形象。

（2）單位配送成本高

這種模式一般來說在一個城市只有一個配送中心，而城市的半徑往往達到幾十公里、上百公里，在農產品電子商務化剛剛起步的今天，由于平均每天收到的訂單不多，而且配送點很可能在城市的各個角度，這就增加了車輛路程，從而提高了生鮮的配送成本，降低了企業的經濟效益。

（3）生鮮農產品的食品質量問題

在農產品電子商務同城配送的過程中，配送車輛一天很可能只出車一次。在這種情況下，有些客戶的需求送達時間較晚，而配送車輛出發時間較早；客戶所需要的生鮮品存放在車輛的儲藏箱中，有些生鮮品具有易腐、易蝕、易爛的特性，經過一天的運輸，送到客戶手中時，往往不是很新鮮，食品質量達不到客戶的需求，影響客戶的滿意度。

（4）車輛平均負載率低

在安排電子商務的配送路徑時，需要考慮顧客的時間窗、食品質量等問題，往往有些車輛負載率很高，另一些車輛負載率很低，是因為企業缺乏對整個運輸路徑的總體規劃。因此，要對電子商務下生鮮品同城配送路徑進行優化，得出符合企業需求的配送車輛行駛路徑。

在盡量滿足客戶需求的前提下降低配送成本是生鮮同城配送中急需解決的問題，本研究進行同城配送路徑優化，同時考慮時間窗要求，旨在降低生鮮同城配送成本，以使電子商務環境下生鮮同城配送能夠更好地發展。

2 生鮮同城配送路徑優化模型的構建

2.1 問題概述

本文研究生鮮物流配送中心將生鮮產品送達各收貨方的路徑選擇問題，由于生鮮產品需要保證一定的新鮮度，各收貨方也有自己的收貨時間規定，運輸車輛必須在規定的時間將產品送到，否則就會因為產品過保鮮期或是錯過收貨方要求送達時間而產生額外的損失，包括產品腐爛損失、收貨方因缺貨導致的損失、服務和信譽損失、車輛等候造成的人員閑置成本和機會成本損失等。因此，本文在構建物流配送路徑優化模型時，選取的是有時間窗限制的車輛路徑優化問題（Vehicle Routing Problem with Time Windows，VRPTW）。

在有時間窗約束的配送路徑優化問題中，所關注的成本分為三部分：一是配送車輛的運輸成本，這一部分與配送距離相關；二是因違反客戶時間窗約束的懲罰成本，這一部分與到達客戶處的時間有關；三是時間的推移和裝卸過程造成的不可避免的損耗。

2.2 目標描述

配送路徑合理與否對配送速度、成本、效益的影響頗大，無論采取何種優化方法，我們首先都要明確物流配送路徑的優化目標，才能有效地針對目標進行優化。因此，采用科學合理的方法確定配送路線是配送活動中非常重要的一項工作。

根據配送的具體要求、配送中心的實力及客觀條件制定配送目標，目標有多種選擇：效益最高、成本最低、路程最短、噸公里最小、準時性最高、運力利用最合理等。針對不同的物流配送問題，要根據具體情況選擇優化目標。

本文研究的是市域連鎖業的冷鏈物流，冷鏈物流本身具備其特殊性，不能簡單地只考慮配送路徑問題，還應該考慮時間問題。因此，本文選取了3個關鍵的配送目標：運輸費用最低、配送服務水平最優和貨損最小，并都轉換成關于費用的函數形式，最后優化成一個目標，即總費用最小。

2.2.1 運輸費用

運輸需要用到車輛和人員等，這部分產生的費用包括固定費用和變動費用。其中，每臺車輛的固定損耗、駕駛員的工資成本等，基本是不隨路線、時間等因素的改變而改變的，因此被稱為固定成本。合理地安排配送車輛的配送路徑可以節約運輸變動成本，包括油耗、過路費、維修費、保養費等，基本和車輛行駛的距離成正比。由于車輛的折舊往往主要與行駛距離相關聯，可近似于成正比，駕駛員工作時間也可以換算成與距離成正比的函數，為了簡化運輸，我們根據以往經驗將固定成本也換算成與距離成正比的函數。最后，總的運輸費用可表示為距離與單位運輸費用的乘積。

2.2.2 配送服務水平

由于冷鏈產品有保質期限，各收貨方也有自己的收貨時間規定，運輸車輛必須在規定的時間將產品送到，否則就會因為產品過保鮮期或是餐飲企業、超市這類的收貨方因過了其銷售的高峰期而產生額外的損失。因此，每個收貨方都會有一個規定貨物送達的時間窗，合理安排配送時間，提高顧客滿意度是冷鏈配送的一個重要目標。如果超過時間窗限制，則要考慮懲罰成本，在這里我們用懲罰成本來衡量這一目標實現的優劣。

對于收貨時間的限制，本文考慮的是軟時間窗限制。在規定的時間段內送達，滿足了客戶的時間需求，則懲罰成本為0；如果產品的送達時間提前或是推遲，但是在一定允許時間范圍內，其懲罰值會隨時間跨度增大，相應的懲罰成本也會增加；當產品的送達時間超過了產品保鮮期或收貨方所能容忍的范圍時，超市可以拒絕接收產品并加以重罰，其懲罰值趨向于無窮大。在多數情況下，懲罰成本的額度是按照配送中心和超市雙方之間約定的合同而定的。本文將在時間跨度內的懲罰函數定位線性增加函數，是為了降低問題的研究難度，如圖1所示。

圖1 懲罰費用與送達時間的分段線性函數圖

圖1中，M為最大懲罰成本，區間［b，c］為客戶規定的貨物送達時間段，區間［a，d］為客戶可接受的送達時間段，當送達時間超出客戶的可接受送達時間段時，懲罰成本最大。

2.2.3 貨損成本

冷鏈產品因其本身具備特殊性而和其他普通貨物不一樣，在配送過程中，冷鏈食品會因為時間、保存溫度、空氣的氧含量、產品水分活性、產品p H值，及腐敗過程中引起的代謝產物、運輸過程中道路顛簸程度等因素導致腐爛變質，造成了一定程度上的貨物質量和數量的損失，我們將這種損失稱為貨損成本。導致貨損成本發生的原因有很多，但是我們為了研究的方便，其他因素均不考慮，僅選取最大的影響貨損成本兩個因素：一是配送時間的長短；二是裝卸過程中的貨損。

2.3 模型的建立

2.3.1 假設條件

結合配送的具體流程和實際情況，本文對具體模型作出以下假設：

（1）只考慮單一配送中心的情況，所有配送車輛均從配送中心出發，完成配送任務后返回配送中心；

（2）配送中心及各個客戶的地理位置已知，由此配送中心到各客戶，以及各客戶之間的距離已知；

（3）每個客戶的需求量是已知的且不會發生改變，每個客戶的需求必須得到滿足；

（4）配送中心的庫存量可以滿足客戶的需求，不會出現缺貨的現象；

（5）只考慮車輛對貨物的配送情況；

（6）配送中心有一定數量的配送車輛，且每輛車的載重量一定，在配送過程中不能發生超載現象；

（7）每輛車可以為多個客戶配送，但每個客戶的配送僅由一輛車來完成，不考慮多輛車同時為一個客戶配送的情況；

（8）每一條路線上客戶的總需求量不超過配送車輛的最大載重量；

（9）每條路徑由一輛車輛進行配送，且每輛車只配送一條路線，如果某路徑貨物超過車輛載重量，則需另開辟配送路徑，新增車輛完成配送任務，如果某客戶需求量過大，需要兩臺配送車輛，則可視為同一地理位置的兩個客戶對貨物有配送需求，其中，一臺車輛滿載，配送后立即返回配送中心，另一臺車輛可搭載其他客戶的貨物；

（10）每個客戶都有其接受配送的時間窗且時間窗已知，每個配送車輛送達貨物的時間要在客戶指定的時間窗內；

（11）在車輛對各客戶進行配送的過程中，不考慮天氣惡化、車輛故障等突發因素的影響；

（12）在對各客戶進行配送時，配送路線上的繁華地段不會出現交通堵塞、城市道路改建等現象，而配送車輛在各客戶之間的運輸過程中，配送路線上不會出現道路中斷等突發現象。

2.3.2 參數定義

m：配送中心可以使用的車輛數目；

k：可配送的車輛集合k=（1，2，L，m）

Gk：車輛k的載重量；

n：客戶數量；

i，j：客戶集合i，j=（1，2，…，n），i=0表示配送中心；

c：每輛車每公里的行駛費用；

gi：客戶i的需求量；

dij：客戶i，j之間的距離；

r：配送的冷鏈產品的單位成本；

M：足夠大的處罰成本；

nk：第k輛車所配送的客戶數量；

θ1：冷鏈產品在運輸途中的貨損比例；

θ2：冷鏈產品在裝卸途中的貨損比例；

［ai，di］：客戶i可接受的貨物送達的時間窗；

［bi，ci］：客戶i理想的貨物送達的時間窗；

p：車輛提前到達客戶處發生的等待單位時間成本；

q：車輛晚于理想時間窗到達客戶處發生的單位時間懲罰成本；

tk0：車輛k從配送中心出發時刻；tk00：車輛k返回配送中心的時刻；

2.3.3 目標函數

（1）運輸費用

運輸費用與運輸距離成正比，總的運輸費用可表示為：

（2）懲罰費用

該部分費用是對配送中心未能在規定的時間窗范圍內送達的客戶付出的懲罰費用，懲罰成本的最大值為M，由客戶和配送中心協商決定數值。p（tki）為車輛k在tki時刻到達客戶i的懲罰成本。由圖1可得出下列分段函數：

則總的懲罰費用可表示為：

（3）貨損成本

車輛k從服務完客戶i去往客戶j并完成服務所造成的冷鏈產品的貨損成本為：

則總的貨損成本Z3為：

將多目標問題化為單目標問題，目標函數如下：

2.3.4 約束條件

（1）車輛載重量約束。每臺車上所配送的總貨物量不超過配送車輛的最大載重量：

（2）配送車輛約束。在配送過程中，每輛車可以給多個客戶進行配送，但每個客戶有且僅有一輛配送車輛進行配送。

（3）客戶數量約束。每輛車所配送的客戶數量小于總的客戶數量：

（4）每臺車輛都必須從配送中心出發：

（5）每次配送活動結束后車輛必須回到配送中心：

3 生鮮同城配送路線優化實證分析

以某地某生鮮農產品配送中心為實例來驗證算法的合理性。我們通過網上調查、查閱相關資料，了解該配送中心的實際情況并收集、整理相關數據。另外，通過MATLAB語言進行編程，以期得出一個優化結果，并通過對優化結果的分析，來考察模型和算法的實效性，希望生鮮配送中心在生鮮產品物流配送路線規劃中有所借鑒。

3.1 數據收集

本文選取了該配送中心配送范圍內的16家餐飲企業為研究對象進行研究分析，并對所獲取的數據進行處理、整理以方便研究的進行。

配送中心和客戶的編號、地理位置以及客戶的需求量如表1所示。

表1 各門店及配送中心地理位置及需求量表

在很多研究中，客戶點之間的距離采用直線距離，采用客戶X與Y坐標來計算兩點距離。而在實際生活中客戶之間、客戶與配送中心的距離通常會因為地上建筑物、路線等的影響大于直線距離。本文測量距離的方法是，通過將配送中心及各客戶的（x，y）位 置 標 注 出 來，通 過 公 式 dij=計算各門店與配送中心以及各門店間的距離。結果如表2所示。

表2 各門店與配送中心及其他門店間的距離（單位：m）

16個客戶具體的時間窗要求及服務時間如表3所示。

表3 各分店時間窗信息表

計算需要用到的相關數據如下：

車型：廂式冷藏車；

車輛最大裝載量：2噸；

每輛車每公里的運輸費用：3元；

車輛平均速度：50km／h；

最早發車時間：3∶00；

配送的生鮮產品的平均單位成本：10元；

冷鏈產品在運輸途中的貨損比例：1%；冷鏈產品在裝卸過程中的貨損比例：0.5%；

車輛提前到達客戶處的等待費用為30元每小時，客戶延遲費用為90元每小時。

3.2 基于遺傳算法利用MATLAB求解結果及分析

根據求解結果，可得出該生鮮農產品配送中心為16家餐飲企業進行配送活動所消耗的最小總配送成本為857.98元，由4輛載重量為2噸的廂式冷藏車進行配送，各路線信息如下：

圖2 MATLAB迭代逼近真值圖

第一條路線：0-4-5-12-9-0

第二條路線：0-1-3-13-0

第三條路線：0-15-16-11-8-0

第四條路線：0-2-6-7-10-14-0

運用CAD繪制了配送路線示意圖，如圖3所示。其中，路線1、2、3、4分別用紅色、綠色、藍色、白色表示。

圖3 配送路徑圖

各路線具體運行情況如表4所示。

表4 配送時間核對表

由表4可知，第一輛配送車①于早上3：00出發從配送中心0出發，3：09到達目的地4，停留10min后（配送車從到達直到離開持續10min，主要用于完成裝卸貨物等工作），于3：42從目的地5出發；3：52到達目的地12，停留11min后，于4：03從目的地1出發；4：09到達目的地9，停留10min后返回配送中心0，配送車輛②、③、④按照類似的形式配送產品。

如表5所示，四輛車的裝載量均超過了90%，資源得到了極大的利用，反映了使用遺傳算法對路徑優化問題的解決具有一定的實際意義。

表5 車輛載重量情況

4 總結及不足

車輛路徑問題（VRP）是物流配送過程中的關鍵環節，配送路徑是否合理直接影響到配送速度、成本和效益。帶有時間窗約束的車輛路徑問題是典型的組合優化問題，具有很大的計算復雜性。本文對時間窗車輛路徑優化問題（VRPTW）進行了探索和研究。

雖然本文在構建生鮮同城配送的路徑規劃模型時，將時間、成本以及貨物的新鮮度都考慮其中，且根據遺傳算法成功求解，但是，由于時間和理論水平的局限，本文的研究還存在一些不足之處，可作為未來改進的方向：

（1）雖然本文研究時考慮了車輛載重及時間窗限制，比一般車輛路徑問題更接近現實，但總體來說與實際問題還存在一定差距。在實際配送活動中，經常會遇到隨機型的物流配送問題，如客戶需求的不確定（如臨時更改訂貨量或收貨時間等）以及車輛行駛時間的不確定（如交通擁堵、車輛故障等）、不同車型車輛的載重量不同等。因此，今后應針對隨機型的車輛路徑問題開展深入研究。

（2）在實際的車輛路徑問題中，對于不同等級的客戶響應服務的速度是有差別的，如必須優先服務某些VIP客戶，這就是具優先次序的車輛路徑問題，應以適當的模型加以表達。

（3）構造數學模型中的時間懲罰函數時，為簡化問題，僅構造了一線性分段函數來粗略表示，但實際上，時間懲罰函數應該呈拋物線或指數關系或其他函數關系增長，而不是單純的線性關系，日后也可將在一定的客戶服務軟時間窗前提下，懲罰成本與送達時間的函數關系作為研究點。

（4）在計算物流中心與客戶以及客戶與客戶之間的距離時較為粗糙，僅根據位置坐標算出兩者之間的直線距離，然而在實際生活中，由于城市路網規劃，實際行駛距離要遠大于兩點間的直線距離，而且某些路段的往返配送距離也是不等的。在今后的研究中，應該采用實際路線的行駛距離或者根據一定的模型加以修正。

（5）本文采用了原始遺傳算法，由于能力與時間的限制，未能對遺傳算法進行改進，也未將其與蟻群算法、模擬退火算法得出的結果進行對比，從而未得出解決該問題的最優算法。