金成成，閔嘉寧

（無(wú)錫太湖學(xué)院，無(wú)錫 214064）

0 引言

我國(guó)是一個(gè)能源消耗和碳排放大國(guó)，物流運(yùn)輸是碳排放的大戶之一。在“雙碳目標(biāo)”下，車(chē)輛路徑問(wèn)題 (vehicle routing problem，VRP) 在現(xiàn)代物流運(yùn)輸中起著更為重要的作用。車(chē)輛路徑優(yōu)化對(duì)提高車(chē)輛負(fù)載率、削減運(yùn)輸車(chē)輛的使用數(shù)量、降低運(yùn)輸距離、減少碳排放以及相應(yīng)的環(huán)境破壞具有相當(dāng)大的影響[1]。

集送貨一體的VRP (VRP with simultaneous delivery and pickup，VRPSDP) 可以在送貨的同時(shí)完成集貨 (回收)，減少由于車(chē)輛回程放空引起的燃油消耗，從而降低運(yùn)輸成本，增加企業(yè)收益，因此，近年來(lái)VRPSDP已成為VRP中的研究熱點(diǎn)。隨著經(jīng)典VRPSDP中每個(gè)客戶可以被訪問(wèn)一次且僅一次的約束放寬，每個(gè)客戶可以被多次訪問(wèn)，客戶的配送和集貨需求可以被拆分，從而提高了車(chē)輛的負(fù)載率、減少使用的車(chē)輛數(shù)并節(jié)省行駛路徑[2]。因此，求解需求可拆分VRP受到越來(lái)越多的關(guān)注。有兩種拆分需求：一是拆分配送需求，相應(yīng)的問(wèn)題稱(chēng)為配送可拆分VRP (Split Delivery VRP，SDVRP)，二是拆分集貨和送貨雙需求，相應(yīng)的問(wèn)題稱(chēng)為集送貨可拆分VRP (split VRP with deliveries and pickups，VRPSPDP)。

SDVRP最早是由Dror和Trudeau[3]于1989年提出的，在SDVRP中，一個(gè)點(diǎn)的送貨需求可以由任意數(shù)量的車(chē)輛完成。學(xué)者們開(kāi)發(fā)了許多算法來(lái)求解SDVRP，研究主要集中在通過(guò)采用啟發(fā)式和精確求解方法來(lái)解決這個(gè)問(wèn)題[4～12]。

VRPSPDP則由Mitra[13]于2005年提出，采用一種混合整數(shù)線性規(guī)劃模型來(lái)描述該問(wèn)題，并提出一種低成本的插入準(zhǔn)則、使用車(chē)輛最少的構(gòu)造啟發(fā)式路徑方法進(jìn)行求解；2008年[14]其又提出了更優(yōu)的并行聚類(lèi)技術(shù)和新的路徑構(gòu)造啟發(fā)式算法。王科峰[15]為無(wú)車(chē)輛數(shù)限制的VRPSPDP設(shè)計(jì)了兩個(gè)構(gòu)造啟發(fā)式算法（最遠(yuǎn)節(jié)點(diǎn)需求拆分算法和競(jìng)爭(zhēng)決策算法），以及具有車(chē)輛數(shù)量限制的VRPSPDP的兩個(gè)構(gòu)造啟發(fā)式算法 (最遠(yuǎn)節(jié)點(diǎn)全拆分算法和最近節(jié)點(diǎn)全拆分算法)。Yin等人[16]提出了一個(gè)具有兩個(gè)特殊前提條件的VRPSPDP數(shù)學(xué)模型，這兩個(gè)條件分別是：最大行程距離約束以及每個(gè)客戶的需求只能拆分一次的限制。Wang等人[17]開(kāi)發(fā)了一種兩階段啟發(fā)式方法，將初始啟發(fā)式算法和混合啟發(fā)式算法相結(jié)合，求解VRPSPDP問(wèn)題。Qiu等人[18]設(shè)計(jì)了一個(gè)基于弧的混合整數(shù)模型，并采用分支-切割算法進(jìn)行求解。

迄今為止，研究人員主要關(guān)注SDVRP，有較多的研究成果；而對(duì)VRPSPDP的研究較少，解決方案不夠全面，或附加了一些限制條件，或計(jì)算所需時(shí)間較長(zhǎng)。因此，在VRPSPDP的優(yōu)化效果方面仍存在相當(dāng)大的提升空間。鑒于此，本文提出了一種基于“先聚類(lèi)后路徑”策略的兩階段方法：第一階段采用一種擴(kuò)展的多重啟動(dòng)迭代掃描算法和微調(diào)系數(shù)對(duì)客戶進(jìn)行聚類(lèi)，確定拆分點(diǎn)和拆分值，將問(wèn)題域分成若干個(gè)子域；第二階段采用改進(jìn)的節(jié)約算法，最小化各子域的的運(yùn)輸距離和使用車(chē)輛。使用重構(gòu)的Solomon基準(zhǔn)數(shù)據(jù)集來(lái)評(píng)估所提出算法的可行性和有效性，并與VRPSDP的計(jì)算結(jié)果進(jìn)行比較，說(shuō)明VRPSPDP的優(yōu)越性。

本文的其余部分安排如下。第2節(jié)描述了VRPSPDP。第3節(jié)詳細(xì)描述了兩階段啟發(fā)式方法。第4節(jié)介紹并討論了使用基準(zhǔn)數(shù)據(jù)集獲得的計(jì)算結(jié)果。最后，第5節(jié)對(duì)研究作了總結(jié)并指出進(jìn)一步研究的方向。

1 問(wèn)題描述

本文所說(shuō)的VRPSPDP是指：?jiǎn)栴}域中有n個(gè)客戶和 m輛車(chē)，所有車(chē)輛都是同一型號(hào)。每輛車(chē)k|k=（1，2，...，m）裝載了車(chē)輛行駛中容量Q所限的配送貨物∑ni=1di≤Q離開(kāi)車(chē)場(chǎng)，沿途為客戶i，j|i，j=（0，1，2，...，n）（0是車(chē)場(chǎng)）送貨di并同時(shí)集貨（回收）pi，最后攜帶容量所限的集貨返回車(chē)場(chǎng)?？蛻鬷和j之間的距離為cij，客戶自身不存在環(huán)路cii=0，且路徑無(wú)向cij=cji?？蛻鬷和j之間的送貨量0≤dij≤Q，客戶i和j之間的集貨量0≤pij≤Q。使用的最小車(chē)輛數(shù)是[max(Σni=1di，Σni=1pi)/Q]，其中[x]表示等于或大于x的最小整數(shù)[18，19]。每位客戶可能同時(shí)具有集/送貨需求，其中任何一個(gè)都可能超過(guò)車(chē)輛容量。每位客戶的配送和集貨都可以進(jìn)行拆分；也就是說(shuō)，每個(gè)客戶可能被多個(gè)車(chē)輛訪問(wèn)或者被同一車(chē)輛訪問(wèn)多次。車(chē)輛k從客戶i行駛到j(luò)，則xijk=1；否則xijk=0?？蛻鬷由車(chē)輛k服務(wù)，則yik=1；否則yik=0。為簡(jiǎn)單起見(jiàn)，本文假設(shè)沒(méi)有時(shí)間窗口限制，也沒(méi)有最大行駛時(shí)間和距離的限制。求解的目標(biāo)是最小化總行駛距離[13，14]。

其中：

式(1)是目標(biāo)函數(shù)，表示最小化總行駛距離。

式(2)和式(3)是客戶需求約束：確保通過(guò)多次訪問(wèn)滿足客戶j的配送/收集需求。

式(4)和式(5)是車(chē)輛裝載約束：確保一次行駛中的車(chē)輛的配送/收集量不超過(guò)車(chē)輛容量。

式(6)是車(chē)輛裝載實(shí)時(shí)約束：由于在各客戶節(jié)點(diǎn)處可能有卸貨和裝貨，車(chē)載量是動(dòng)態(tài)、上下波動(dòng)的，因此，為確保一次行駛中在任何節(jié)點(diǎn)處的配送/收集的總裝載不超過(guò)車(chē)輛容量，必須隨時(shí)檢測(cè)車(chē)載約束?？蛻艄?jié)點(diǎn)θq（含節(jié)點(diǎn)θ）之前的集貨數(shù)量和客戶節(jié)點(diǎn)θ之后的配送數(shù)量（從節(jié)點(diǎn)θ+1開(kāi)始）沿車(chē)輛k的路線的總和不能超過(guò)車(chē)輛容量。

式(7)和式(8)是車(chē)場(chǎng)貨物類(lèi)型約束：確保沒(méi)有送貨進(jìn)入車(chē)場(chǎng)，并且沒(méi)有集貨來(lái)自車(chē)場(chǎng)。

式(9)是車(chē)輛出入守恒約束：確保到達(dá)客戶位置j的車(chē)輛也離開(kāi)該位置。

式(10)是車(chē)場(chǎng)出入約束：表明每個(gè)車(chē)輛每次行駛僅駛?cè)?駛出車(chē)場(chǎng)一次。

2 兩階段方法

本文基于“先聚類(lèi)后路徑”策略提出了一種兩階段方法來(lái)求解VRPSPDP問(wèn)題。第一階段，采用擴(kuò)展的多重啟動(dòng)迭代掃描算法（Multi-Restart Iterative Sweep Algorithm，MRISA）對(duì)客戶進(jìn)行聚類(lèi)，確定拆分點(diǎn)和拆分的值；第二階段，采用經(jīng)過(guò)改進(jìn)、符合VRPSDP要求的節(jié)約算法（Clarke-Wright，C-W），優(yōu)化行駛距離。

2.1 第一階段

掃描算法是Gillett和Miller[19]提出的一種構(gòu)造啟發(fā)式算法，本質(zhì)上是在滿足一定前提條件下將距離最近的客戶集群到一個(gè)分區(qū)中。通過(guò)多重迭代執(zhí)行，可以找到最優(yōu)的分區(qū)。

掃描算法是在極坐標(biāo)下執(zhí)行的，所以首先對(duì)直角坐標(biāo)系下的空間域以車(chē)場(chǎng)為原點(diǎn)轉(zhuǎn)換成極坐標(biāo)系，然后按升序?qū)蛻酎c(diǎn)的所有角度進(jìn)行排序，并設(shè)置變量組optimal存儲(chǔ)各分區(qū)的客戶點(diǎn) (集送貨值)、拆分點(diǎn) (拆分值) 以及最佳距離[20]。

2.1.1集送貨掃描算法

集送貨掃描算法 (Sweep Algorithm for Delivery and Pickup，SA-DP) 是對(duì)基本的Gillett和Miller掃描算法的改進(jìn)，使之應(yīng)用于客戶具有集送貨都不可拆分的情況下。在執(zhí)行SA-DP之前，需要檢查每個(gè)點(diǎn)的送貨需求di和集貨需求pi。如果di，pi≥Q，則單獨(dú)派送數(shù)量Q，剩余部分參與SA-DP執(zhí)行，對(duì)客戶域進(jìn)行分區(qū)。

步驟1：選擇角度0°作為起始點(diǎn)。

步驟2：按順時(shí)針將點(diǎn)掃描進(jìn)入初始分區(qū)，直到（max(Σlpi=1di，Σlpi=1pi)）≥Q：

1）如果Σii=1di=QandΣii=1pi=Q，i就作為當(dāng)前M分區(qū)的最后一個(gè)點(diǎn)（Last Point，lp），當(dāng)前分區(qū)的最大累積值 (Maximum Cumulative Value，MCV) MCVlpd=Σii=1di=Q，MCVlpp=Σii=1pi=Q。

2）如果Σii=1di=QandΣii=1pi=Q，i就作為當(dāng)前分區(qū)的最后一個(gè)點(diǎn)lp，當(dāng)前分區(qū)的MCVlpd=Σii=1di=Q，MCVlpp=Σii=1pi。

3）如果Σii=1pi=QandΣii=1di＜Q，i就作為當(dāng)前分區(qū)的最后一個(gè)點(diǎn)lp，當(dāng)前分區(qū)的MCVlpd=Σii=1pi=Q，MCVlpd=Σii=1di。

4）如果Σii=1di＞QandΣii=1pi＜Q，i的前一個(gè)點(diǎn)（i-1）就作為當(dāng)前分區(qū)最后一個(gè)點(diǎn)lp，當(dāng)前分區(qū)的MCVlpd=Σii=1di，MCVlpp=Σi-1i=1pi。

5）如果Σii=1pi＞QandΣii=1di＜Q，（i-1）就作為當(dāng)前分區(qū)最后一個(gè)點(diǎn)lp，于是當(dāng)前分區(qū)的最大累積值MCVlpp=Σi-1i=1pi，MCVlpd=Σi-1i=1di。

6）如果Σii=1di＞QandΣii=1pi＞Q，（i-1）就作為當(dāng)前分區(qū)的最后一個(gè)點(diǎn)lp，當(dāng)前分區(qū)的MCVlpd=Σi-1i=1di，MCVlpp=Σi-1i=1pi。

終止當(dāng)前分區(qū)。

步驟3：從lp的下一個(gè)點(diǎn)出發(fā)開(kāi)始下一個(gè)分區(qū)的掃描，重復(fù)步驟2。

步驟4：重復(fù)步驟2～3，直至最后一個(gè)客戶點(diǎn)。

步驟5：終止本次掃描，將各分區(qū)的客戶點(diǎn) (集送貨值)、拆分點(diǎn) (拆分值) 以及最佳距離存入變量組optimal。

2.1.2 集送貨可拆分掃描算法

針對(duì)集送貨需求都可拆分，我們對(duì)SA-DP進(jìn)行了改進(jìn)，形成了集送貨可拆分的掃描算法 (Sweep Algorithm for Delivery and pickup split，SA-DP-Split)。在這種情況下，每位客戶可能同時(shí)具有集送貨需求，其中任何一個(gè)都可能超過(guò)車(chē)輛容量。

步驟1：選擇角度0°作為起始點(diǎn)。

步驟2：按順時(shí)針將點(diǎn)掃描進(jìn)入初始分區(qū)，直到（max(Σlpi=1di，Σlpi=1pi））≥Q：

1）如果Σii=1di=QandΣii=1pi=Q，i就作為當(dāng)前分區(qū)的最后一個(gè)點(diǎn)lp，當(dāng)前分區(qū)的MCVlpd=Σii=1di=Q，MCVlpp=Σii=1pi=Q，i+1是下一個(gè)分區(qū)的起始點(diǎn)。

2）如果Σii=1di=QandΣii=1pi＜Q，i就作為當(dāng)前分區(qū)的最后一個(gè)點(diǎn)lp，當(dāng)前分區(qū)的MCVlpd=Σii=1di=Q，MCVlpp=Σii=1pi；i+1是下一個(gè)分區(qū)的起始點(diǎn)。

3）如果Σii=1pi=QandΣii=1di＜Q，i就作為當(dāng)前分區(qū)的最后一個(gè)點(diǎn)lp，當(dāng)前分區(qū)的MCVlpd=Σii=1pi=Q，MCVlpd=Σii=1di；i+1是下一個(gè)分區(qū)的起始點(diǎn)。

4）如果Σii=1di＞QandΣii=1pi＜Q，i就作為當(dāng)前分區(qū)最后一個(gè)點(diǎn)lp，分裂lp為lp1和lp2，最大累積值MCVlp1d=Q，CVlp2d=Σii=1di-Q，MCVlp1p=Σii=1pi，MCVlp2p=0；lp2是下一個(gè)分區(qū)的起始點(diǎn)。

5）如果Σii=1pi＞QandΣii=1di＜Q，i就作為當(dāng)前分區(qū)最后一個(gè)點(diǎn)lp，分裂lp為lp1和lp2，最大累積值MCVlp1p=Q，MCVlp2p=Σii=1pi-Q，MCVlp1d=Σii=1di，MCVlp2d=0；lp2是下一個(gè)分區(qū)的起始點(diǎn)。

6）如果Σii=1di＞QandΣii=1pi＜Q，i就作為當(dāng)前分區(qū)的最后一個(gè)點(diǎn)lp，分裂lp為lp1和lp2，最大累積值MCVlp1d=Q，MCVlp1p=Q，MCVlp2d=Σii=1di-Q，MCVlp2p=Σii=1pi-Q；lp2是下一個(gè)分區(qū)的起始點(diǎn)。

終止當(dāng)前分區(qū)。

步驟3：從下一個(gè)分區(qū)的起始點(diǎn)出發(fā)開(kāi)始下一個(gè)分區(qū)的掃描，重復(fù)步驟2。

步驟4：重復(fù)步驟2～3，直至最后一個(gè)客戶點(diǎn)。

步驟5：終止本次掃描，將各分區(qū)的客戶點(diǎn) (集送貨值)、拆分點(diǎn) (拆分值) 以及最佳距離存入變量組optimal。

2.1.3 微調(diào)系數(shù)

SA-DP-Split中，當(dāng)（Σii=1di＞QandΣii=1pi＜Q) 或者（Σii=1di＜QandΣii=1pi＞Q) 時(shí)，i+1就是下一個(gè)分區(qū)的起始點(diǎn)，而無(wú)論Σii=1pi或Σii=1di與Q相差多少。這樣可能會(huì)影響車(chē)輛的負(fù)載率，造成使用的車(chē)輛數(shù)增加。為此，我們引入了系數(shù)coef對(duì)‘差多少’進(jìn)行控制，形成增強(qiáng)的SA-DP-Split (SA-Enhanced-DP-Split，SA-E-DPSplit)：如果Σii=1xi＜coef·Q，(此處的x表示d或p)，則x 不在該點(diǎn)終止分區(qū)、繼續(xù)掃描；如果Σii=1xi≥coef·Q，則x在該點(diǎn)終止分區(qū)、停止掃描。這就意味著d和p可以有各自獨(dú)立的分區(qū)終止點(diǎn)。以步驟2的2）為例：

步驟2：按順時(shí)針將點(diǎn)掃描進(jìn)入初始分區(qū)，直到（max(Σlpi=1di，Σlpi=1pi））≥Q：

1) 如果Σii=1di=QandΣii=1pi＜coef·Q，i就作為當(dāng)前分區(qū)d的最后一個(gè)點(diǎn)lp，當(dāng)前分區(qū)的最大累積值MCVlpd=Σii=1di=Q，MCVlp=Σii=1pi；i+1是下一個(gè)分區(qū)累計(jì)d的起始點(diǎn)，而p繼續(xù)掃描并累計(jì)MCVl+1p=Σi+1i=1pi。

2) 如果Σii=1di=QandΣii=1pi≥coef·Q，i就作為當(dāng)前分區(qū)d和p的最后一個(gè)點(diǎn)lp，當(dāng)前分區(qū)的最大累積值MCVlpd=Σii=1di=Q，MCVlpp=Σii=1pi；i+1是下一個(gè)分區(qū)的起始點(diǎn)。

2.1.4 多重迭代

多重迭代 (Multi Restart Iteritive，MRI) 地執(zhí)行SA-DP/SA-DP-Split/SA-E-DP-Split，操作分別成為MRISA for DP/MRISA for DP-Split/MRISA for E-DP-Split：

步驟1：依次以0o～360o中各客戶點(diǎn)為起始點(diǎn)執(zhí)行SADP/SA-DP-Split/E-SA-DP-Split，并與optimal中的最佳距離比較，存入最佳值。

步驟2：依次以360o～0o中各客戶點(diǎn)為起始點(diǎn)執(zhí)行SADP/SA-DP-Split/E-SA-DP-Split，并與optimal中的最佳距離比較，存入最佳值。

步驟3：提取optimal中的最佳客戶點(diǎn) (集送貨值)、拆分點(diǎn) (拆分值) 以及最佳距離，并終止操作。

2.2 第二階段

執(zhí)行第一階段的操作后，每個(gè)子分區(qū)中都只有一條路線，每個(gè)客戶點(diǎn)都有集送貨需求。因此，問(wèn)題變成了VRPSDP。采用改進(jìn)的C-W算法(Modified C-W，M-C-W)滿足VRPSDP要求，改進(jìn)的C-W算法的過(guò)程如下。

步驟1：形成初始解集L={Li}，Ai∈{1，2，…，n}，其中Li表示直接集送貨點(diǎn)i。

步驟2：計(jì)算距離節(jié)省度Δcij=c0i+c0j-Δcij。對(duì)Δcij（i，j=1，2，...，n）進(jìn)行降序排序，得到Dcij。

步驟3：構(gòu)造新的路徑集L'0=φ，并設(shè)置初始送貨/集貨需求裝載量R'0=0。

步驟4：從頂部到底部掃描Dcij并終止在底部。

步驟5：在掃描中根據(jù)以下判別條件尋找每個(gè)點(diǎn)對(duì)（i，j）的合并可能性。

如果i是路徑的末端，則將點(diǎn)j合并在點(diǎn)i后面。

如果i是路線的開(kāi)始，則在點(diǎn)i前合并點(diǎn)j。

如果j是路線的末端，則將點(diǎn)i合并在點(diǎn)j后面。

如果j是路線的開(kāi)始，則在點(diǎn)j之前合并點(diǎn)i。

4) 車(chē)輛的總裝載隨著沿路徑的裝載增加或減少而波動(dòng)，因此必須檢查每個(gè)點(diǎn)的裝載約束：如果當(dāng)前路徑的裝載量滿足以下條件，則轉(zhuǎn)到下一個(gè)點(diǎn)對(duì)；否則，刪除步驟5中的所有操作并返回步驟4：

3 案例研究

為了驗(yàn)證所提出的兩階段方法在減少行駛距離、降低運(yùn)輸車(chē)輛數(shù)量和提高裝載率方面的可行性和有效性，我們選用了VRP Web Solomon數(shù)據(jù)集中25、50和100個(gè)客戶的數(shù)據(jù)[21]。但是，Solomon數(shù)據(jù)集不能直接用于VRPSPDP，因?yàn)樗鼈儾话浶枨髷?shù)據(jù)。通過(guò)合并兩個(gè)數(shù)據(jù)集來(lái)構(gòu)建完整的新數(shù)據(jù)集：一個(gè)作為送貨需求而另一個(gè)作為集貨需求。例如，新構(gòu)建的原始數(shù)據(jù)集CR101中的送貨需求和集貨需求分別是由原始數(shù)據(jù)集C101中的送貨需求和原始數(shù)據(jù)集R101的送貨需求構(gòu)成的。同時(shí)，進(jìn)一步增大集送貨值占車(chē)輛容量的比例：保留數(shù)據(jù)集中各點(diǎn)的地理位置數(shù)據(jù)不變，對(duì)每個(gè)奇數(shù)點(diǎn)，給送貨值加0.75·Q并給集貨值加0.2·Q；對(duì)每個(gè)偶數(shù)點(diǎn)，給送貨值加0.2·Q并給集貨值加0.75·Q，使得新構(gòu)建數(shù)據(jù)集的集送貨值占車(chē)輛容量在20.5%和95%之間。驗(yàn)證是在64位Windows 7計(jì)算機(jī)上使用C實(shí)現(xiàn)的，該計(jì)算機(jī)具有Intel?Core處理器2.50 GHz和8GB內(nèi)存。

在新構(gòu)建的數(shù)據(jù)集上分別執(zhí)行MRISA for DP/DPSplit/E-DP-Split+M-C-W（簡(jiǎn)稱(chēng)為DP、DP-Split和E-DP-Split），結(jié)果如表1所示。表中距離減少ΔDist.%計(jì)算如下。

表1 在新構(gòu)建的數(shù)據(jù)集上執(zhí)行的結(jié)果

結(jié)果表明，E-DP-Split相比其他兩個(gè)算法 (DP-Split和DP) 具有明顯的優(yōu)勢(shì)：

E-DP-Split比DP算法的距離減少ΔDist.%在30.65% 和38.35%之間，平均值為33.91%。DP-Split比DP算法的距離減少ΔDist.%在11.66%和26.85%之間，平均為19.89%。E-DP-Split比DP-Split的距離減少ΔDist.%在12.50%和24.23%之間，平均為17.38%。行駛距離的減少將直接降低運(yùn)輸成本。

DP情況下的路徑數(shù)等于點(diǎn)數(shù)，即一條路徑對(duì)應(yīng)一個(gè)點(diǎn)。E-DP-Split情況下的路徑數(shù)比DP下降約41%、比DPSplit下降了約11%；DP-Split比DP下降約34%。路徑數(shù)的下降意味著車(chē)輛使用數(shù)量、車(chē)輛啟動(dòng)費(fèi)用和人力成本的下降，所有這些都將顯著降低運(yùn)輸成本。(說(shuō)明：由于空間限制，無(wú)法在表1中標(biāo)明ΔRt.%；計(jì)算公式類(lèi)似于式(11)、式(12)和式(13))。

三種算法的平均負(fù)載率Load Rate分別為0.96、0.89和0.57。E-DP-Split比DP上升約68.4%，比DP-Split上升約7.9%；DP-Split比DP上升約56.1%。(說(shuō)明：由于空間限制，無(wú)法在表1中標(biāo)明ΔLR.%；計(jì)算公式類(lèi)似于式(11)、式(12)和式(13))。

車(chē)輛行駛產(chǎn)生的路線形狀像圍繞車(chē)場(chǎng)周?chē)幕ò?，客戶點(diǎn)的拆分通常發(fā)生在子域的開(kāi)始或結(jié)束。

E-DP-split情況下，兩個(gè)相鄰路徑之間可能有兩個(gè)分裂點(diǎn)：一個(gè)點(diǎn)是送貨值拆分，另一個(gè)點(diǎn)是集貨值拆分。

4 結(jié)語(yǔ)

本文基于“先聚類(lèi)后路徑”策略開(kāi)發(fā)了求解VRPSPDP的數(shù)學(xué)模型的兩階段構(gòu)造啟發(fā)式方法。第一階段，采用擴(kuò)展的多重啟動(dòng)迭代掃描式算法以及微調(diào)系數(shù) coef將客戶域劃分為若干個(gè)子域，并確定拆分點(diǎn)和拆分值。第二階段，采用改進(jìn)的C-W節(jié)約算法，按照路徑優(yōu)化的原則，檢測(cè)每個(gè)客戶點(diǎn)動(dòng)態(tài)車(chē)載量，確定行駛路徑。在Solomon原始數(shù)據(jù)集的基礎(chǔ)上，通過(guò)重構(gòu)使之適合VRPSPDP的需求，驗(yàn)證所提出方法的可行性和有效性，并與VRPSDP進(jìn)行了分析比較。實(shí)驗(yàn)結(jié)果表明：

1）提出的兩階段算法顯著減少了VRPSPDP的總行駛距離、車(chē)輛使用數(shù)量并提高了平均裝載率。

2）車(chē)輛行駛路徑圍繞著車(chē)場(chǎng)周?chē)螤钕窕ò?，而且客戶拆分?jīng)常發(fā)生在子域的開(kāi)始或結(jié)束處。

3）在重構(gòu)的數(shù)據(jù)集上執(zhí)行E-DP-Split+M-C-W比執(zhí)行DP+M-C-W算法顯示出明顯的優(yōu)勢(shì)：行駛距離平均減少33.91%，使用的車(chē)輛數(shù)量平均下降約41%，平均裝載率上升約68.4%。

4）在執(zhí)行E-DP-Split+M-C-W時(shí)，兩條相鄰路徑之間可能有兩個(gè)分裂點(diǎn)：一個(gè)點(diǎn)是送貨值拆分，另一個(gè)點(diǎn)是集貨值拆分。

本文在集送貨可拆分的車(chē)輛路徑優(yōu)化上作了初步探索嘗試，今后還將在優(yōu)化的算法上進(jìn)一步深入研究，以期獲得更優(yōu)的結(jié)果；擴(kuò)展本文的研究到可分割的 (divisble) 集送貨VRP[22，23]，研究多種拆分案例對(duì)優(yōu)化結(jié)果的影響。