□ 田 亮,李亞東

(昆明理工大學(xué) 管理與經(jīng)濟(jì)學(xué)院，云南 昆明 650000)

1 引言

節(jié)約算法作為一種經(jīng)典的啟發(fā)式算法，在解決小規(guī)模的車輛配送路線優(yōu)化的問題上很有優(yōu)勢(shì)。但涉及到實(shí)際生活中的各種食品，尤其是生鮮類產(chǎn)品的配送時(shí)，配送的及時(shí)與否直接導(dǎo)致了產(chǎn)品的新鮮度從而會(huì)影響需求點(diǎn)對(duì)供應(yīng)商的滿意程度，進(jìn)而影響供應(yīng)商總體的收益。本文用帶時(shí)間窗的節(jié)約算法結(jié)合時(shí)間懲罰成本來研究配送路線安排問題。

2 模型建立

本文要解決的優(yōu)化問題是單個(gè)配送中心的車輛配送安排問題，即典型的起點(diǎn)和終點(diǎn)相同的單車場(chǎng)非滿載有時(shí)間窗約束的車輛路徑優(yōu)化問題[1]。要在單個(gè)車輛的容量限制、總運(yùn)輸里程限制、滿足各個(gè)需求點(diǎn)需求量、時(shí)間限制等約束條件下，以選定好的配送中心為中心，對(duì)車輛進(jìn)行安排，組織合適的行車路線，在盡可能滿足每一個(gè)客戶時(shí)間窗口的前提下,有序的通過各個(gè)需求點(diǎn)并滿足各個(gè)需求點(diǎn)的需求量，并達(dá)到一定的目的。

2.1 模型的假設(shè)及約束條件

①每個(gè)客戶即需求點(diǎn)的需求只能由一輛車來滿足。

②每個(gè)客戶的需求量不大于單輛車的裝載總量。

③配送中心及客戶的位置已知，且知道配送中心與客戶之間的距離、各個(gè)客戶之間的距離。

④已知每個(gè)客戶的需求量及時(shí)間約束。

⑤假設(shè)所有路況都正常，在配送期間不會(huì)出現(xiàn)堵車或其他意外情況，所有配送車輛均勻速行駛，且駕駛員的技術(shù)相當(dāng)，即所有配送車輛都是等價(jià)的。

⑥配送車輛從配送中心出發(fā)，最終要返回配送中心。

⑦配送中心的車輛總數(shù)不小于客戶的總數(shù)。

⑧配送中心每輛車都是滿載出發(fā)。

2.2 模型描述

P為配送中心，Di為第i個(gè)客戶的需求量，配送中心每輛車的最大容量為Q，dij為客戶i和j之間的距離，d0i為配送中心P與客戶i之間的距離，配送車輛從配送中心向客戶出發(fā)每一單位距離的運(yùn)輸都會(huì)產(chǎn)生一定的成本，a為這里單位距離的成本。每個(gè)客戶有一個(gè)對(duì)于自己收貨時(shí)間的時(shí)間窗，那么對(duì)于不在時(shí)間窗內(nèi)的到貨時(shí)間點(diǎn)會(huì)產(chǎn)生相對(duì)應(yīng)的延遲收貨的懲罰成本[5]，設(shè)系數(shù)為α，還有相應(yīng)的提前到貨的等待成本，設(shè)系數(shù)為β。即模型的目標(biāo)就是合理的安排每輛車的行駛路線，最終使得總的配送成本加上懲罰及等待成本的總和最小。

對(duì)模型中的參數(shù)及相關(guān)變量進(jìn)行定義

Q為每輛車的最大容量；

Di為客戶i的需求量；

M為客戶的集合，{0,1,2...i,..m}其中客戶0指的是配送中心；

K為配送車輛的集合，{1,2..k}；

d0i為配送中心與客戶點(diǎn)i的距離；

dij為客戶點(diǎn)i和j之間的距離；

V為配送車輛的平均行駛速度；

Vd為單位卸貨速度；

[Ei,Li]為客戶i的時(shí)間窗；

T0i為車輛從配送中心到客戶i的時(shí)間；

Tij為配送車輛從i到j(luò)的時(shí)間；

Ti為車輛在客戶i點(diǎn)的卸貨時(shí)間；

RTi為車輛到達(dá)客戶i的時(shí)間點(diǎn)；

LTi為車輛離開客戶i的時(shí)間點(diǎn)；

a為單位運(yùn)輸成本；

c為單位時(shí)間成本；

α為延遲收貨的懲罰成本系數(shù)；

β為提前到貨的等待成本系數(shù)；

決策變量表示如下[2]：

所以,由于延遲或提前到貨而產(chǎn)生的成本上的損失可由下式表達(dá)：

目標(biāo)函數(shù)：minC=λ1C(T)+λ2C(D)

其中λ1和λ2表示從配送系統(tǒng)整體去考慮客戶滿意度(懲罰成本)及運(yùn)輸成本在整個(gè)配送系統(tǒng)中的重要程度，并且有λ1+λ2=1。

(2)

(3)

(4)

(5)

(6)

(7)

(8)

其中式(1)保證每條配送路徑上的客戶需求量之和不超過配送車輛的最大載重量；(2)、(3)、(4)三式保證每個(gè)客戶點(diǎn)的需求只能有一輛車來服務(wù)；(5)式保證了所有客戶點(diǎn)的需求都能得到滿足；(6)、(7)兩式保證了每輛配送車輛都由配送中心出發(fā)，且最終都回到了配送中心；(8)式保證了單輛配送車輛配送的客戶數(shù)不超過客戶總數(shù)m。

3 C-W節(jié)約算法

ΔD=2*(D02+D01)-(D02+D01+D12)=D02+D01-D12

節(jié)約里程法是用來解決運(yùn)輸車輛數(shù)目不確定的問題的最有名的啟發(fā)式算法[2]，又稱節(jié)約算法。

它的核心思想在于依次將車輛運(yùn)輸問題中的兩個(gè)回路合并成一個(gè)回路，使每次合并之后的總運(yùn)輸距離減少，直到達(dá)到該車的裝載限制時(shí)，再進(jìn)行下一輛車的優(yōu)化。

即假設(shè)若配送中心P到客戶1的距離為D01，到客戶2的距離為D02，客戶1到客戶2的距離為D12。若車輛本來是從P到客戶1再返回P，然后從P到客戶2再返回P，那么總路程S=2*(D02+D01)；若車輛從P到客戶1然后到客戶2，再返回配送中心P，那么總路程S=D02+D01+D12。

而ΔD=D02+D01-D12>0(兩邊之和大于第三邊)，也就是說理論上只要在車輛的裝載限制之內(nèi)，任意兩條回路都可以合并成一條并且使總路程變??；然而現(xiàn)實(shí)中，由于車輛的裝載限制，由于路況的各種因素，兩點(diǎn)之間距離通常都不能用直線距離來表示，所以要根據(jù)實(shí)際情況進(jìn)行分析。

見下圖1就是根據(jù)現(xiàn)實(shí)路況模擬出的路線圖。

圖1

表1 配送中心到客戶及客戶之間最短距離

表2 各客戶之間的節(jié)約里程值

例：S(P1,P2)=2(8+8)-(8+8+12)=4

表3 節(jié)約里程值按從大到小排列

假設(shè)最初每個(gè)客戶點(diǎn)都由一輛車來配送，即需要5輛車，此時(shí)總里程為2*(8+8+6+7+10)=78，并且假設(shè)這里的一輛車的載重量為4。

從節(jié)約量最大的對(duì)應(yīng)節(jié)點(diǎn)入手，S(p2,p3)D,p2和p3不在一條路線上，均為各自所在路線的外點(diǎn)，且0.8+1.5=2.3<4，沒有超過車載限制，所以可以連接，形成路線P0-P2-P3-P0，此時(shí)一共需要4輛車，節(jié)約里程為10；然后考慮節(jié)約量次之的對(duì)應(yīng)節(jié)點(diǎn)，s(P3,p4)D,P3和P4不在一條路線上，均為各自所在路線的外點(diǎn)，且0.8+1.5+1.5=3.8<4，所以可以連接，形成路線P0-P2-P3-P4-P0,此時(shí)一共需要三輛車，節(jié)約里程為18。

下面同理。

最終得出路線，共需要兩輛車。

車輛1：P0-P2-P3-P4-P0 車輛2：P0-P1-P5-P0

總節(jié)約值為10+8+2=20

最終總里程為：10+16+8+7+8+5+4=58=78-20

4 模型求解

傳統(tǒng)的C-W節(jié)約算法是指在車載限制的情況下，將兩個(gè)回路合并成一個(gè)回路，達(dá)到減少總里程量及派送車輛的數(shù)目進(jìn)而縮減總成本的效果。而本文要在多一個(gè)時(shí)間窗限制的條件下，實(shí)現(xiàn)總成本最小的效果。

車載限制和傳統(tǒng)情況相同；綜合去考慮里程的節(jié)約量和時(shí)間成本的節(jié)約量。

連接i，j兩個(gè)客戶點(diǎn)(P0-i-j-p0)對(duì)于RTj的影響有如下幾種：

令RTi+Di/Vd+Tij-T0j=ΔRTj

若ΔRTj=0，說明對(duì)于RTj沒有影響；

若ΔRTj>0，說明會(huì)延遲到達(dá)客戶點(diǎn)j；

若ΔRTj<0，說明會(huì)提前到達(dá)客戶點(diǎn)j。

符號(hào)說明：

Δijβ-表示連接ij后等待時(shí)間的減少量；

Δijβ+表示連接ij后等待時(shí)間的增加量；

Δijα+表示連接ij后延遲收貨時(shí)間的增加量；

Δijα-表示連接ij后延遲收貨時(shí)間的減少量；

S(i,j)β表示連接ij后等待時(shí)間成本的節(jié)約量；

S(i,j)α表示連接ij后延遲收貨成本的節(jié)約量；

S(i,j)T表示連接ij后時(shí)間成本的總節(jié)約量。

對(duì)于以上三種ΔRTj的值來說，

①ΔRTj=0，對(duì)于時(shí)間成本沒有任何影響，不存在節(jié)約量。

②ΔRTj>0，考慮三種情況：

第一種情況：當(dāng)Ej<=T0j<=Lj，即直接從配送中心向j點(diǎn)出發(fā)的到貨時(shí)間是滿足j本身的時(shí)間窗的。

此時(shí)比較T0j+ΔRTj與Lj的大小，

若T0j+ΔRTj<=Lj，則對(duì)于時(shí)間成本沒有影響;若T0j+ΔRTj>Lj，則會(huì)產(chǎn)生額外的延遲收貨成本，此時(shí)Δijα+=T0j+ΔRTj-Lj，從而產(chǎn)生延遲收貨的懲罰成本為α*Δijα+。此時(shí)可看做節(jié)約量為負(fù)，即S(i,j)T=-α*Δijα+。

即在Ej<=T0j<=Lj的情況下：

第二種情況：當(dāng)T0j>Lj，即直接從配送中心向j點(diǎn)出發(fā)會(huì)產(chǎn)生延遲收貨成本。而ΔRTj>0，說明連接ij點(diǎn)之后只會(huì)更晚的到達(dá)j點(diǎn)，所以只會(huì)產(chǎn)生額外的時(shí)間成本，此時(shí)Δijα+=ΔRTj，從而產(chǎn)生延遲收貨的懲罰成本為α*Δijα+。

此時(shí)可看做節(jié)約量為負(fù)，即S(i,j)T=-α*Δijα+

即在T0j>Lj的情況下：

第三種情況：當(dāng)T0j0，說明連接ij點(diǎn)之后使得到j(luò)點(diǎn)的時(shí)間變晚，從而減少了等待時(shí)間成本。

在此情況下再考慮兩種條件下的不同：

第二種：T0j+ΔRTj>Lj：

此時(shí)一定會(huì)產(chǎn)生大小為Ej-T0j的等待時(shí)間節(jié)約量，S(i,j)β=β*Δijβ-，這里Δijβ-=min(ΔRTj,Ej-T0j);但同時(shí)也會(huì)造成多余的延遲收貨時(shí)間，此時(shí)Δijα+=T0j+ΔRTj-Lj，從而產(chǎn)生延遲收貨的懲罰成本為α*Δijα+，所以在此種情況下會(huì)產(chǎn)生可正可負(fù)的節(jié)約量，S(i,j)T=S(i,j)β-α*Δijα+。

即在ΔRTj>0的情況下，只有在T0j

即在T0j

③ΔRTj<0,同ΔRTj>0時(shí)，考慮三種情況。

最終結(jié)論：

在Ej<=T0j<=Lj的情況下：

在T0j>Lj的情況下：

在T0j

連接任意兩個(gè)客戶點(diǎn)之間都可能會(huì)產(chǎn)生時(shí)間成本節(jié)約量及里程節(jié)約量，綜合考慮兩種節(jié)約量；因?yàn)樵谠撆渌拖到y(tǒng)中對(duì)客戶時(shí)間窗的滿足程度(時(shí)間成本)及運(yùn)輸成本的相對(duì)重要程度是λ1：λ2，且λ1+λ2=1。所以對(duì)于總成本節(jié)約量可表示為：

S(i,j)=λ12*S(i,j)T+λ2*a*S(i,j)D而總成本節(jié)約量越大，則目標(biāo)函數(shù)總成本C越小。

所以，對(duì)于一個(gè)配送系統(tǒng)來說，分別考慮任意兩客戶點(diǎn)(涉及到時(shí)間窗口要考慮先后順序)的綜合節(jié)約量，并進(jìn)行排序，逐次考慮可操作性，得出最優(yōu)的配送路線。

5 算例分析

有10項(xiàng)貨物運(yùn)輸任務(wù)(編號(hào)為1…10)，各客戶的需求量(單位：噸)、卸貨時(shí)間(單位：小時(shí))、每個(gè)客戶的時(shí)間窗口為[Ei,Li](單位：時(shí)刻)由下表給出。

卸載速度Vd為2噸/小時(shí)，單位運(yùn)輸成本a為1，車輛最大容量Q為10噸，配送車輛的平均行駛速度V為50公里/小時(shí)；

表4

表5 各客戶點(diǎn)之間的最短距離表 (單位：公里)

對(duì)于距離的節(jié)約量來說配送順序是無(wú)差別的(因?yàn)榧僭O(shè)所有的路徑都非單行道)。

表6 各個(gè)客戶點(diǎn)之間的節(jié)約里程量表 (單位：公里)

α為延遲收貨的懲罰成本系數(shù)，取值50；β為提前到貨的等待成本系數(shù)，取值40。

表7 各個(gè)客戶點(diǎn)之間的時(shí)間成本節(jié)約量表

注：加粗加下劃線意味著配送順序要顛倒(對(duì)于距離的節(jié)約量來說沒有區(qū)別，因?yàn)閷?duì)于距離來說顛倒順序無(wú)差別，但是時(shí)間成本的節(jié)約量與配送順序有關(guān)系，取時(shí)間成本節(jié)約量最大的那個(gè)配送順序)

在這里假設(shè)時(shí)間成本與運(yùn)輸成本對(duì)于整個(gè)配送系統(tǒng)來說同等重要。

即在式S(i,j)=λ1*S(i,j)T+λ2*a*S(i,j)D中假設(shè)λ1=λ2=0.5。

根據(jù)上面兩個(gè)表，可算出：

表8 各個(gè)客戶點(diǎn)之間的總成本節(jié)約量表

表9 各個(gè)客戶點(diǎn)之間的總成本節(jié)約量表(按從大到小排序)

根據(jù)總節(jié)約值得大小排序，得到初步的五條路線。5-6 7-8 4-10 9-1 3-2，即在只派出五輛車的條件下，該路線是最優(yōu)的(綜合總成本最低)。下面再考慮每條路線第三第四個(gè)節(jié)點(diǎn)的可能性(優(yōu)先考慮客戶時(shí)間窗口,在考慮車載限制的條件)如線路0-5-6-0，從6出發(fā)時(shí)的時(shí)間節(jié)點(diǎn)是8.9，考慮除客戶5 6 外其他客戶的時(shí)間窗口，8.9不在任何一個(gè)客戶節(jié)點(diǎn)的時(shí)間窗口之內(nèi)，考慮三四節(jié)點(diǎn)只會(huì)帶來負(fù)的時(shí)間成本的收益，所以5-6是單條最優(yōu)路線，下面不再考慮由5向別的客戶點(diǎn)出發(fā)的路線，也不考慮由別的客戶點(diǎn)向6出發(fā)的路線。下面同理，最終得出在優(yōu)先考慮客戶時(shí)間窗口的前提下，該五條路線已經(jīng)是最優(yōu)路線。

所以該算例的最優(yōu)路線為：車輛1：0-5-6-0

車輛2：0-7-8-0

車輛3：0-4-10-0

車輛4：0-9-1-0

車輛5：0-3-2-0

6 結(jié)論

本文通過結(jié)合整個(gè)配送系統(tǒng)對(duì)于各客戶點(diǎn)時(shí)間窗口的滿足程度及運(yùn)輸成本兩個(gè)方面，用c-w節(jié)約算法的思想，解決了配送路線優(yōu)化的問題，且通過研究對(duì)于客戶時(shí)間窗口滿足程度的方式在一定層面上解決了部分客戶滿意度的問題(客戶對(duì)于送達(dá)時(shí)間的滿意度是客戶滿意度的一部分)，更加貼近現(xiàn)實(shí)。