基于遺傳算法的生鮮同城配送路徑優(yōu)化研究

唐佩佩 馮曉威 宮英麗

（同濟(jì)大學(xué) 經(jīng)濟(jì)與管理學(xué)院，上海 201800）

1 研究目的

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

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

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

（2）單位配送成本高

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

（3）生鮮農(nóng)產(chǎn)品的食品質(zhì)量問題

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

（4）車輛平均負(fù)載率低

在安排電子商務(wù)的配送路徑時，需要考慮顧客的時間窗、食品質(zhì)量等問題，往往有些車輛負(fù)載率很高，另一些車輛負(fù)載率很低，是因?yàn)槠髽I(yè)缺乏對整個運(yùn)輸路徑的總體規(guī)劃。因此，要對電子商務(wù)下生鮮品同城配送路徑進(jìn)行優(yōu)化，得出符合企業(yè)需求的配送車輛行駛路徑。

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

2 生鮮同城配送路徑優(yōu)化模型的構(gòu)建

2.1 問題概述

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

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

2.2 目標(biāo)描述

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

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

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

2.2.1 運(yùn)輸費(fèi)用

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

2.2.2 配送服務(wù)水平

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

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

圖1 懲罰費(fèi)用與送達(dá)時間的分段線性函數(shù)圖

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

2.2.3 貨損成本

冷鏈產(chǎn)品因其本身具備特殊性而和其他普通貨物不一樣，在配送過程中，冷鏈?zhǔn)称窌驗(yàn)闀r間、保存溫度、空氣的氧含量、產(chǎn)品水分活性、產(chǎn)品p H值，及腐敗過程中引起的代謝產(chǎn)物、運(yùn)輸過程中道路顛簸程度等因素導(dǎo)致腐爛變質(zhì)，造成了一定程度上的貨物質(zhì)量和數(shù)量的損失，我們將這種損失稱為貨損成本。導(dǎo)致貨損成本發(fā)生的原因有很多，但是我們?yōu)榱搜芯康姆奖?，其他因素均不考慮，僅選取最大的影響貨損成本兩個因素：一是配送時間的長短；二是裝卸過程中的貨損。

2.3 模型的建立

2.3.1 假設(shè)條件

結(jié)合配送的具體流程和實(shí)際情況，本文對具體模型作出以下假設(shè)：

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

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

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

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

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

（6）配送中心有一定數(shù)量的配送車輛，且每輛車的載重量一定，在配送過程中不能發(fā)生超載現(xiàn)象；

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

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

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

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

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

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

2.3.2 參數(shù)定義

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

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

Gk：車輛k的載重量；

n：客戶數(shù)量；

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

c：每輛車每公里的行駛費(fèi)用；

gi：客戶i的需求量；

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

r：配送的冷鏈產(chǎn)品的單位成本；

M：足夠大的處罰成本；

nk：第k輛車所配送的客戶數(shù)量；

θ1：冷鏈產(chǎn)品在運(yùn)輸途中的貨損比例；

θ2：冷鏈產(chǎn)品在裝卸途中的貨損比例；

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

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

p：車輛提前到達(dá)客戶處發(fā)生的等待單位時間成本；

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

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

2.3.3 目標(biāo)函數(shù)

（1）運(yùn)輸費(fèi)用

運(yùn)輸費(fèi)用與運(yùn)輸距離成正比，總的運(yùn)輸費(fèi)用可表示為：

（2）懲罰費(fèi)用

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

則總的懲罰費(fèi)用可表示為：

（3）貨損成本

車輛k從服務(wù)完客戶i去往客戶j并完成服務(wù)所造成的冷鏈產(chǎn)品的貨損成本為：

則總的貨損成本Z3為：

將多目標(biāo)問題化為單目標(biāo)問題，目標(biāo)函數(shù)如下：

2.3.4 約束條件

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

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

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

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

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

3 生鮮同城配送路線優(yōu)化實(shí)證分析

以某地某生鮮農(nóng)產(chǎn)品配送中心為實(shí)例來驗(yàn)證算法的合理性。我們通過網(wǎng)上調(diào)查、查閱相關(guān)資料，了解該配送中心的實(shí)際情況并收集、整理相關(guān)數(shù)據(jù)。另外，通過MATLAB語言進(jìn)行編程，以期得出一個優(yōu)化結(jié)果，并通過對優(yōu)化結(jié)果的分析，來考察模型和算法的實(shí)效性，希望生鮮配送中心在生鮮產(chǎn)品物流配送路線規(guī)劃中有所借鑒。

3.1 數(shù)據(jù)收集

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

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

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

在很多研究中，客戶點(diǎn)之間的距離采用直線距離，采用客戶X與Y坐標(biāo)來計(jì)算兩點(diǎn)距離。而在實(shí)際生活中客戶之間、客戶與配送中心的距離通常會因?yàn)榈厣辖ㄖ?、路線等的影響大于直線距離。本文測量距離的方法是，通過將配送中心及各客戶的（x，y）位 置 標(biāo) 注 出 來，通 過 公 式 dij=計(jì)算各門店與配送中心以及各門店間的距離。結(jié)果如表2所示。

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

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

表3 各分店時間窗信息表

計(jì)算需要用到的相關(guān)數(shù)據(jù)如下：

車型：廂式冷藏車；

車輛最大裝載量：2噸；

每輛車每公里的運(yùn)輸費(fèi)用：3元；

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

最早發(fā)車時間：3∶00；

配送的生鮮產(chǎn)品的平均單位成本：10元；

冷鏈產(chǎn)品在運(yùn)輸途中的貨損比例：1%；冷鏈產(chǎn)品在裝卸過程中的貨損比例：0.5%；

車輛提前到達(dá)客戶處的等待費(fèi)用為30元每小時，客戶延遲費(fèi)用為90元每小時。

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

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

圖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

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

圖3 配送路徑圖

各路線具體運(yùn)行情況如表4所示。

表4 配送時間核對表

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

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

表5 車輛載重量情況

4 總結(jié)及不足

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

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

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

（2）在實(shí)際的車輛路徑問題中，對于不同等級的客戶響應(yīng)服務(wù)的速度是有差別的，如必須優(yōu)先服務(wù)某些VIP客戶，這就是具優(yōu)先次序的車輛路徑問題，應(yīng)以適當(dāng)?shù)哪Ｐ图右员磉_(dá)。

（3）構(gòu)造數(shù)學(xué)模型中的時間懲罰函數(shù)時，為簡化問題，僅構(gòu)造了一線性分段函數(shù)來粗略表示，但實(shí)際上，時間懲罰函數(shù)應(yīng)該呈拋物線或指數(shù)關(guān)系或其他函數(shù)關(guān)系增長，而不是單純的線性關(guān)系，日后也可將在一定的客戶服務(wù)軟時間窗前提下，懲罰成本與送達(dá)時間的函數(shù)關(guān)系作為研究點(diǎn)。

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

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