唐佩佩 馮曉威 宮英麗

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

1 研究目的

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

（1）不能滿足客戶時(shí)間窗的需求

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

（2）單位配送成本高

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

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

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

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

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

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

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

2.1 問(wèn)題概述

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

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

2.2 目標(biāo)描述

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

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

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

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

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

2.2.2 配送服務(wù)水平

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

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

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

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

2.2.3 貨損成本

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

2.3 模型的建立

2.3.1 假設(shè)條件

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

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

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

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

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

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

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

（7）每輛車可以為多個(gè)客戶配送，但每個(gè)客戶的配送僅由一輛車來(lái)完成，不考慮多輛車同時(shí)為一個(gè)客戶配送的情況；

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

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

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

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

（12）在對(duì)各客戶進(jìn)行配送時(shí)，配送路線上的繁華地段不會(huì)出現(xiàn)交通堵塞、城市道路改建等現(xiàn)象，而配送車輛在各客戶之間的運(yùn)輸過(guò)程中，配送路線上不會(huì)出現(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á)的時(shí)間窗；

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

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

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

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

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

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

（3）貨損成本

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

則總的貨損成本Z3為：

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

2.3.4 約束條件

（1）車輛載重量約束。每臺(tái)車上所配送的總貨物量不超過(guò)配送車輛的最大載重量：

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

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

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

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

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

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

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

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

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

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

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

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

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

表3 各分店時(shí)間窗信息表

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

車型：廂式冷藏車；

車輛最大裝載量：2噸；

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

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

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

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

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

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

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

根據(jù)求解結(jié)果，可得出該生鮮農(nóng)產(chǎn)品配送中心為16家餐飲企業(yè)進(jìn)行配送活動(dòng)所消耗的最小總配送成本為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 配送時(shí)間核對(duì)表

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

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

表5 車輛載重量情況

4 總結(jié)及不足

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

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

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

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

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

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

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