王科峰， 葉春明

（1.上海理工大學(xué)管理學(xué)院，上海 200093；2.河南理工大學(xué)能源科學(xué)與工程學(xué)院，焦作 454000）

節(jié)點具有雙重需求車輛路徑問題及其解的性質(zhì)分析

王科峰1，2， 葉春明1

（1.上海理工大學(xué)管理學(xué)院，上海 200093；2.河南理工大學(xué)能源科學(xué)與工程學(xué)院，焦作 454000）

概括介紹了逆向物流領(lǐng)域中的各類車輛路徑問題，將問題按照節(jié)點的需求類型分為節(jié)點單需求以及具有雙重需求兩個大類.按照節(jié)點的需求類型，將同時送取貨（VRPSDP）、集送貨需求可拆分車輛路徑問題（SVRPPD）統(tǒng)稱為節(jié)點具有雙重需求車輛路徑問題（VRPNDD）.文中首先給出了它們的定義及數(shù)學(xué)模型.接著，作為設(shè)計求解問題啟發(fā)式算法的前期工作，對VRPNDD問題解的結(jié)構(gòu)方面的一些性質(zhì)進(jìn)行了分析證明.最后，舉例說明了SVRPPD與送貨需求可拆分車輛路徑問題最優(yōu)解性質(zhì)方面的差異，并通過定理證明說明了SVRPPD，VRPSDP啟發(fā)式算法的改良對于SVRPPD相對VRPSDP節(jié)省成本百分比研究的意義.

同時送取貨；集送貨需求可拆分；弱可行解；強可行解；Hamilton回路；子回路

Key words：simultaneous delivery and pickup；split deliveries and pickups；weakly feasibility solution；strong feasibility solution；Hamilton circuit；subloop

隨著人們對環(huán)境問題越來越多的關(guān)注以及廢物利用帶來的附加經(jīng)濟(jì)效益逐漸被認(rèn)識，使用過的商品在它們生命周期結(jié)束時會被部分或全部回收、拆卸、組裝得以重新使用.此外，包裝和裝載設(shè)備也可以再循環(huán)使用.許多國家已經(jīng)就原材料的再循環(huán)率、產(chǎn)品包裝的回收，甚至產(chǎn)品全部生命周期包括義務(wù)進(jìn)行產(chǎn)品使用期結(jié)束后的回收，對工業(yè)界提出一系列強制性的要求.所有這些活動導(dǎo)致了原材料從終端客戶回溯到上游供應(yīng)鏈的流動.

在存在逆向物流的環(huán)境中，一部分任務(wù)點需要送貨，另一部分任務(wù)點需要集貨，于是產(chǎn)生了帶回程的車輛路徑問題VRPB（vehicle routing problem with backhauls）、混合裝載車輛路徑問題VRPBM（VRP with backhaul and mixed load）、同時送取貨車輛路徑問題VRPSDP（VRP with simultaneous delivery and pickup）、集送貨需求可拆分車輛路徑問題SVRPPD（vehicle routing problem with split deliveries and pickups）和收發(fā)問題PDP（pickup and delivery）.

1 逆向物流領(lǐng)域VRP問題概述

1.1 帶回程車輛路徑問題［1－2］

不同于經(jīng)典的VRP問題［3］，VRPB是在原來車輛只能進(jìn)行后尾裝載（rear-loaded）的時候，如果在發(fā)送完貨物之前進(jìn)行貨物的接收，這樣會影響下一次貨物的發(fā)送這種特定的歷史條件下產(chǎn)生的. VRPB問題中客戶被分為兩個子集，一個子集中的每個客戶只具有接收需求，另一個子集的客戶只具有發(fā)送需求.車輛負(fù)載貨物從車場出發(fā)，先服務(wù)所有的具有發(fā)送需求的客戶，然后服務(wù)具有接收需求的客戶，最后車輛返回車場，車輛的負(fù)載在整個配送過程中是單調(diào)減少的.VRPB的示意圖見圖1（a）.

1.2 混合裝載帶回程車輛路徑問題［4－5］

隨著物流技術(shù)的進(jìn)步，車輛不僅可以進(jìn)行后尾裝載，還可以進(jìn)行側(cè)面裝載（side-loaded），對發(fā)送和接收的順序沒有了限制，因此就產(chǎn)生了VRPBM問題.VRPBM與VRPB不同的是，對于車輛先進(jìn)行發(fā)送還是先進(jìn)行接收沒有限制，車輛負(fù)載在配送過程中不是單調(diào)變化的，因此對于這種問題的車輛容量可行性控制成為算法設(shè)計需要注意的關(guān)鍵.VRPBM示意圖見圖1（b）.

1.3 同時送取貨車輛路徑問題［6－9］

VRPB和VRPBM中客戶處只具有單一需求，但是如果一個客戶同時具有接收和發(fā)送兩種需求的話，車輛如果仍然一次對其進(jìn)行一種服務(wù)，那么該客戶必然要被進(jìn)行第二次服務(wù)，這樣會產(chǎn)生不必要的車輛被使用，而且考慮到操作的復(fù)雜程度，客戶也可能不會接受兩種需求被分開服務(wù)，于是就有VRPSDP問題的提出.如果一個客戶同時具有收發(fā)需求，且車輛對其只能服務(wù)一次，這種VRP問題就是VRPSDP問題.VRPBM是VRPSDP問題當(dāng)客戶節(jié)點處接收或發(fā)送需求其中一個為0時的特例. VRPSDP的示意圖見圖1（c）.

1.4 集送貨需求可拆分車輛路徑問題［10－13］

VRPB，VRPBM，VRPSDP都有一個前提假設(shè)就是客戶需求不超過車輛容量，問題中所有客戶只能接受一次服務(wù)，客戶點需求不可拆分，車輛大多數(shù)情況下處于非滿載狀態(tài).但物流服務(wù)中可能出現(xiàn)下面的情況：部分或全部任務(wù)點發(fā)送，接收需求量可能很大，車輛容量卻很小，在一次訪問中車輛無法完成任務(wù)；在時間非常緊的情況下，為了在規(guī)定的時間窗內(nèi)完成任務(wù)，對客戶的訪問次數(shù)的限制可以沒有那么高的要求.諸如以上問題，如何解決值得進(jìn)一步研究.

20世紀(jì)90年代Dror和Trudeau［14-15］提出了發(fā)送需求可拆分的車輛路徑問題（split delivery VRP，SDVRP）的概念，因為允許需求拆分導(dǎo)致客戶被訪問一次的限制被取消了，而且車輛的利用率提高了，這樣可以節(jié)省運輸服務(wù)距離，同時可以節(jié)省服務(wù)車輛的數(shù)目.單一發(fā)送需求可拆分的車輛路徑問題所帶來成本上的節(jié)省也使人們聯(lián)想到節(jié)點具有接收和發(fā)送雙重需求的車輛路徑問題，對于這種問題的需求可拆分情形是否也具有同樣良好的性質(zhì)，近年來人們開始了對集送貨需求可拆分車輛路徑問題（SVRPPD）的研究.SVRPPD可以看成是對SDVRP的擴(kuò)展，而后者可看成前者當(dāng)兩種需求其一為0時的特例.SVRPPD的示意圖見圖1（d）.

1.5 收發(fā)問題［16］

PDP問題與前面3種問題不同的是，車輛在具有接收需求的客戶處收貨，將這些貨物發(fā)送給具有發(fā)送需求的客戶，收貨點和送貨點成對出現(xiàn).PDP不僅可以應(yīng)用于逆向物流，同樣在其它領(lǐng)域也有所應(yīng)用，如最常見的校車路徑問題（dial-a-ride problem）.PDP示意圖見圖1（e）.

根據(jù)客戶節(jié)點需求的特點，本文將VRP問題劃分為單一需求的VRP問題以及具有雙重需求的VRP問題.那么VRP，VRPB，VRPBM，PDP，SDVRP以及添加各種約束的變種問題都是節(jié)點單需求的VRP問題，而只有VRPSDP和SVRPPD及其變種問題為節(jié)點具有雙重需求的VRP問題（vehicle routing problem with node having double demands），記作VRPNDD.因為涉及到容量可行性控制，節(jié)點需求的雙重性使得VRPNDD問題求解起來相對于其它幾種問題難度更大，而且這一結(jié)構(gòu)上的復(fù)雜性可能帶給該問題其它尚未發(fā)現(xiàn)的一些性質(zhì).文獻(xiàn)［17］研究了離散情形下，允許節(jié)點需求大于車輛容量、車輛容量取特定值時的VRPNDD問題，給出了問題的計算復(fù)雜性及可簡化性.VRPNDD問題在一般情況下是NP難問題，因此尋找求解問題有效的啟發(fā)式算法是必然選擇.然而，設(shè)計好的啟發(fā)式算法離不開對問題本身固有性質(zhì)的把握，基于這種想法本文將討論該類問題解的一些結(jié)構(gòu)性質(zhì)，為后續(xù)算法研究作準(zhǔn)備.

圖1 逆向物流VRP問題Fig.1 VRP problems in reverse logistics

2 VRPNDD問題定義及模型

定義1 一組容量相同的車輛從一個車場出發(fā)，對一些客戶進(jìn)行服務(wù)最后返回車場.每個客戶具有集貨和送貨雙重需求，且需求不大于車輛容量，車輛在服務(wù)客戶的時候同時執(zhí)行發(fā)送、接收兩種操作，從而保證每個客戶只被服務(wù)一次.目標(biāo)是找到一套車輛路徑使得在保證每條路徑上的裝載量不超過車輛容量的前提下，使得總的行駛距離最小.這種問題稱為同時送取貨車輛路徑問題（VRPSDP）.

定義2 一組容量相同的車輛從一個車場出發(fā)，對一些客戶進(jìn)行服務(wù)最后返回車場.每個客戶具有集貨和送貨雙重需求，且允許這兩種需求大于車輛容量，車輛在服務(wù)客戶的時候集貨、送貨的數(shù)量沒有限制，每個客戶可以被同一個車輛或不同的車輛服務(wù)多次，目標(biāo)是找到一套車輛路徑使得在保證每條路徑上的裝載量不超過車輛容量的前提下，使得總的行駛距離最小.這種問題稱為集送貨需求可拆分車輛路徑問題（SVRPPD）.

2.1 VRPSDP問題數(shù)學(xué)模型

符號說明：

N為車場和客戶節(jié)點的集合，它包括車場（用i=0，n+1來表示車場，其中，i=0表示起點，i= n+1表示終點，它們之間的距離為0），以及客戶節(jié)點集合（i=1，2，…，n）；

C為客戶節(jié)點集（i=1，2，…，n）；

Q為車輛容量；

ci為客戶i處的收貨需求；

di為客戶i處的送貨需求；

wij為從客戶i到客戶j的旅行費用.

決策變量：

xijk為二項變量，如果車輛k直接從客戶i行駛到客戶j，取值為1，否則取值為0；

yijk表示車輛k從客戶i到客戶j這段路徑上的接收貨物裝載量；

zijk表示車輛k從客戶i到客戶j這段路徑上的發(fā)送貨物裝載量.

VRPSDP的數(shù)學(xué)模型為

其中，目標(biāo)函數(shù)是最小化全部的行駛費用；約束（1）說明每輛車從車場出發(fā)不超過一次；約束（2）說明每個客戶只被服務(wù)一次；約束（3）說明一輛車進(jìn)出客戶節(jié)點的次數(shù)相等；約束（4）～（5）保證客戶處的集貨、送貨需求得到滿足；約束（6）表示一條路徑上的車輛裝載量不能超過車輛容量；約束（7）～（8）保證車輛從車場出發(fā)時車輛上沒有已收集的貨物，返回車場時車輛上沒有尚未發(fā)送的貨物；約束（9）～（10）是整數(shù)變量聲明.

2.2 SVRPPD模型

將上述VRPSDP模型中約束（2）去掉即可得SVRPPD問題的數(shù)學(xué)模型.

3 VRPNDD路徑的容量可行性

VRP，SDVRP分別是VRPSDP，SVRPPD當(dāng)節(jié)點需求其中一個為0時的特例.因為節(jié)點需求的雙重性帶來的問題結(jié)構(gòu)方面的改變使得VRPSDP，SVRPPD比只有單一需求的VRP，SDVRP在固有性質(zhì)方面的研究更為困難，在求解算法方面體現(xiàn)在容量可行性控制更為復(fù)雜.所以為了方便對VRPNDD的研究，需要對該問題解中路徑結(jié)構(gòu)特點進(jìn)一步明確.首先引進(jìn)路徑弱可行、強可行的定義.

定義3 如果一條路徑上所有節(jié)點的發(fā)送需求之和以及所有節(jié)點接收需求之和都不大于車輛的容量，則稱該路徑是弱可行的.

定義4 如果一條路徑上所有邊上的車輛裝載量都不超過車輛容量，則稱該路徑是強可行的.

那么顯然有下面結(jié)論成立：

定理1 如果一條路徑是強可行的則這條路徑必是弱可行的，反之不然.

那么在一條弱可行的路徑中所有客戶節(jié)點間，是否存在一條強可行的路徑將它們串聯(lián)起來，下面將研究這個問題.

圖2 裝載函數(shù)Fig.2 Load function

當(dāng)車輛行駛到點m時，車輛裝載量為

4 SVRPPD與SDVRP路徑結(jié)構(gòu)差異

定理2說明了VRPNDD問題的解中每條弱可行路徑必存在強可行路徑與之對應(yīng).下面討論SVRPPD由于節(jié)點需求的雙重性，導(dǎo)致其解的路徑結(jié)構(gòu)性質(zhì)與SDVRP結(jié)構(gòu)性質(zhì)方面的差異.

例1 假設(shè)共有4個客戶節(jié)點，如圖3所示，節(jié)點編號及客戶需求分別為1（3，1），2（1，2），3（0，1），4（1，1），0代表車場，車輛容量Q=5.設(shè)距離對稱，邊長c01=1.2，c02=1.5，c04=0.8，c12=0.5，c13= 0.5，c14=0.5，c23=0.5，c34=0.8.顯然，這些距離滿足三角不等式.假設(shè)車輛裝載剩余空箱數(shù)為rd，已裝載實箱數(shù)為rc.

圖3 SVRPPD問題的解中可能含有子回路Fig.3 Subloop possibly contained in the solution of SVRPPD

如圖3（a）所示，車輛訪問節(jié)點的次序及在各節(jié)點的裝卸情況如下：車輛從車場出發(fā)裝載5單位待發(fā)送貨物，此時rd=5且rc=0；到達(dá)節(jié)點2卸載2個單位貨物，同時裝載1個單位貨物，則rd=3且rc=1；到達(dá)節(jié)點3卸載1個單位貨物，則rd=2且rc=1；到達(dá)節(jié)點4卸載1單位貨物，同時裝載1單位貨物，則rd=1且rc=2；到達(dá)節(jié)點1卸載1單位貨物，同時裝載3單位貨物，則rd=0且rc=5；最終車輛滿載5單位收集的貨物返回車場.整條路徑滿足強可行性，并且是一條Hamilton回路，記為l1.將l1的總長度記為s1，則s1=c02+c23+c34+ c41+c10=1.5+0.5+0.8+0.5+1.2=4.5.

如圖3（b）所示，車輛訪問節(jié)點的次序及在各節(jié)點的裝卸情況如下：車輛從車場出發(fā)裝載5單位待發(fā)送貨物，此時rd=5且rc=0；到達(dá)節(jié)點1卸載1單位貨物，則rd=4且rc=0；到達(dá)節(jié)點2卸載2單位的貨物，同時裝載1單位的貨物，則rd=2且rc=1；到達(dá)節(jié)點3卸載1單位的貨物，則rd=1且rc=1；到達(dá)節(jié)點1裝載3單位的貨物，則rd=1且rc=4；到達(dá)節(jié)點4卸載1單位的貨物，同時裝載1單位貨物，則rd=0且rc=5；最終車輛滿載5單位收集的貨物返回車場.整條路徑滿足強可行性，但是含有子回路，記為l2.將l2的總長度記為s2，則s2=c01+c12+c23+c31+c14+c40=1.2+0.5+ 0.5+0.5+0.5+0.8=4.

由于s2＜s1，這說明在SVRPPD問題的解的一條路徑中含有子回路的路徑相對于不含子回路的路徑可能會使行駛距離更短，而對距離滿足三角不等式的SDVRP問題卻不存在這種情況.所以在SDVRP的定義中，節(jié)點需求允許被不同的車輛拆分運輸而不允許被同一輛車分多次拆分運輸，而在SVRPPD問題的定義中，節(jié)點需求可以被同一輛車或不同車輛分多次拆分運輸.

在明確了SVRPPD解中路徑結(jié)構(gòu)以后，很容易得到如下結(jié)論：

定理3 VRPSDP問題的可行解一定是SVRPPD問題的可行解，反之不然.

定理4 記“z（ ）”為問題最優(yōu)值，則有z（SVRPPD）≤z（VRPSDP）.

5 SVRPPD最優(yōu)解性質(zhì)

Dror和Trudeau［15］證明了如果距離滿足三角不等式，那么在SDVRP問題的最優(yōu)解中，任何兩條路徑的公共點的數(shù)目都不會超過1；進(jìn)而證明了SDVRP問題的最優(yōu)解中，不存在k-split cycle.這兩個性質(zhì)是關(guān)于SDVRP問題的很重要的結(jié)論，SDVRP的一些性質(zhì)證明很多基于它們［18］.由于SVRPPD是SDVRP問題當(dāng)節(jié)點需求變?yōu)殡p重需求時的更為一般的情形，所以很容易想到，SVRPPD問題的最優(yōu)解是否也存在同樣的性質(zhì).作者已經(jīng)通過實例說明了SVRPPD問題的最優(yōu)解中兩條路徑間可能有兩個公共點［17］，這是SVRPPD與SDVRP問題的最優(yōu)解性質(zhì)的重要差異.

然而，以上只是對SVRPPD問題最優(yōu)解性質(zhì)的一些觀察，關(guān)于該問題最優(yōu)解的性質(zhì)可能還存在尚未發(fā)現(xiàn)的結(jié)論.目前對于“SVRPPD與SDVRP最優(yōu)解性質(zhì)差異”直接研究存在困難，可以采取先進(jìn)行節(jié)省成本分析，看成本節(jié)省最大值如何，通過這些研究有助于發(fā)掘問題最優(yōu)解的性質(zhì).就像有關(guān)SDVRP相對于VRP節(jié)省成本百分比分析那樣［18］，當(dāng)客戶的平均需求略大于車輛容量的一半且需求方差較小時SDVRP最優(yōu)值相對于VRP最優(yōu)值節(jié)省成本百分比達(dá)到最大.作為對SVRPPD問題最優(yōu)解性質(zhì)的進(jìn)一步探索，SVRPPD相對于VRPSDP節(jié)省成本百分比×100%的研究也是關(guān)于VRPNDD問題研究的一項重要工作.目前，關(guān)于VRPSDP問題的求解算法比較多，求解精度也比較高，而關(guān)于SVRPPD問題的求解算法相對比較少，只有為數(shù)不多的幾篇文章［10-13］.

定理5 設(shè)VRPSDP，SVRPPD問題的最優(yōu)值分別為z1，z2＞0，啟發(fā)式算法求解VRPSDP，SVRPPD問題的計算結(jié)果分別為H1，H2＞0，而且存在ε1，ε2＞0，使得H1-ε1=z1，H2-ε2=z2，則

從式（11）可以看出，求解算法的精度越高，即ε1，ε2越接近0，則使用啟發(fā)式算法進(jìn)行節(jié)省成本分析的研究所得結(jié)果越準(zhǔn)確，所以今后對SVRPPD及VRPSDP求解精度的改良是進(jìn)行成本節(jié)省分析的關(guān)鍵.

6 總 結(jié)

由于VRPNDD問題節(jié)點需求的雙重性，使得該類問題也變得相對于節(jié)點單一需求的VRP問題更加難以求解.VRPNDD問題一般情況下是NP難的，因此尋找能夠有效快速求解的啟發(fā)式算法是問題求解必需選擇的正確研究方向.為設(shè)計更好的啟發(fā)式算法作準(zhǔn)備，本文致力于進(jìn)一步明確VRPNDD解的結(jié)構(gòu)特點，給出了幾個重要的關(guān)于解的結(jié)構(gòu)性質(zhì)的定理，并對之進(jìn)行了證明.最后，本文說明了SVRPPD的最優(yōu)解性質(zhì)與SDVRP問題最優(yōu)解性質(zhì)的顯著差異，并闡述了SVRPPD，VRPSDP啟發(fā)式算法的改良對于SVRPPD問題最優(yōu)解性質(zhì)研究及SVRPPD相對VRPSDP節(jié)省成本百分比研究的意義.通過本文的研究，明確了今后有效啟發(fā)式算法的設(shè)計與改良、最優(yōu)解性質(zhì)及節(jié)省成本分析研究的方向，所以具有重要的理論意義.

［1］ Mingozzi A，Giorgi S，Baldacci R.An exact method for the vehicle routing problem with backhauls［J］. Transportation Science，1999，33（3）：315-329.

［2］ Brandao J.A new tabu search algorithm for the vehicle routing problem with backhauls［J］.European Journal Operational Research，2006，173（2）：540-555.

［3］ 馬慧民，吳勇，葉春明.車輛路徑問題的并行粒子群算法研究［J］.上海理工大學(xué)學(xué)報，2007，29（5）：435 -444.

［4］ Salhi S，Nagy G.A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling［J］.Journal of the Operational Research Society，1999，50（10）：1034-1042.

［5］ Wade A C，Salhi S.An investigation into a new class of vehicle routing problem with backhauls［J］.Omega，2002，30（6）：479-487.

［6］ Subramanian A，Uchoa E，Pessoa A A，et al.Branchand-cut with lazy separation for the vehicle routing problem with simultaneous pickup and delivery［J］. Operations Research Letters，2011，39（5）：338-341.

［7］ Dethloff J.Vehicle routing and reverse logistics：the vehicle routing problem with simultaneous delivery and pick-up［J］.OR Spektrum，2001，23（1）：79-96.

［8］ Catay B.A new saving-based ant algorithm for the vehicle routing problem with simultaneous pickup and delivery［J］.Expert Systems with Applications，2010，37（10）：6809-6817.

［9］ Subramanian A，Drummond L M A，Bentes C，et al.A parallel heuristic for the vehicle routing problem with simultaneous pickup and delivery［J］.Computers& Operations Research，2010，37（11）：1899-1911.

［10］ Mitra S.An algorithm for the generalized vehicle routing problem with backhauling［J］.Asia-Pacific Journal of Operational Research，2005，22（2）：153 -169.

［11］ Mitra S.A parallel clustering technique for the vehicle routing problem with split deliveries and pickups［J］. Journal of the Operational Research Society，2008，59（11）：1532-1546.

［12］ Tang G C，Ning A B，Wang K F，et al.A practical split vehicle routing problem with simultaneous pickup and delivery［C］∥Proceeding IEEE 16th International Conference on Industrial Engineering and Engineering Management.Beijing，2009.

［13］ Wang K F，Ye C M，Ning A B.Competitive decision algorithm for the split vehicle routing problem with simultaneous pickup and delivery and time windows［C］∥International Conference on Future Information Technology and Management Engineering，Changzhou，2010.

［14］ Dror M，Trudeau P.Savings by split delivery routing［J］.Transportation Science，1989，23（2）：141-145.

［15］ Dror M，Trudeau P.Split delivery routing［J］.Naval Research Logistics，1990，37（3）：383-402.

［16］ Savelsbergh M，Sol M.The general pickup and delivery problem［J］.Transportation Science，1995，29（1）：17-29.

［17］ 王科峰，葉春明，唐國春.節(jié)點具有雙重需求的車輛路徑問題及其性質(zhì)［J］.系統(tǒng)科學(xué)與數(shù)學(xué)，2011，31（10）：1185-1196.

［18］ Archetti C，Savelsbergh M W P，Grazia M.Worst-case analysis for split delivery vehicle routing problems［J］.Transportation Science，2006，40（2）：226-234.

［19］ Archetti C，Savelsbergh M W P，Speranza M G.To split or not to split：that is the question［J］. Transportation Research Part E，2008，44（1）：114 -123.

［20］ 唐國春.新的車輛路徑問題［C］∥中國運籌學(xué)會第九屆學(xué)術(shù)交流會論文集.香港，2008. （編輯：丁紅藝）

Vehicle Routing Problem with Nodes of Double Demands and the Property of Its Solution

WANGKe-feng1，2， YEChun-ming1
（1.Bussiness School，University of Shanghai for Science and Technology，Shanghai 200093，China；2.School of Energy Science and Engineering，Henan Polytechnic University，Jiaozuo 454000，China）

A general outline of various types of vehicle routing problems in the field of reverse logistics was given.The vehicle routing problems were divided into two classes，i.e.the problem of single demand and double demands，according to the demand characteristic of the customer node. The vehicle routing problem with simultaneous delivery and pickup（VRPSDP）and the vehicle routing problem with split deliveries and pickups（SVRPPD）were called as the vehicle routing problem with nodes of double demands（VRPNDD）.Their definitions and mathematic models were given.Then as the preliminary work for designing the heuristics，some constitutive properties of the solution for the VRPNDD were investigated.The difference in properties of optimal solutions between SVRPPDand SDVRP（the vehicle routing problem with split delivery）was illustrated，and a theorem was proved to show the significance of the heuristics’improving on cost saving analysis of SVRPPD relative to VRPSDP.

O 221；U 116.2

A

1007-6735（2013）04-0329-07

2012-10-28

國家自然科學(xué)基金資助項目（71271138）；教育部人文社會科學(xué)規(guī)劃基金資助項目（10YJA630187）；上海市教育委員會科研創(chuàng)新資助項目（12ZS133）；高等學(xué)校博士點基金資助項目（20093120110008）

王科峰（1980-），女，博士研究生.研究方向：車輛路徑優(yōu)化、物流系統(tǒng)優(yōu)化.E-mail：kfhere＠126.com

葉春明（1964-），男，教授.研究方向：工業(yè)工程、供應(yīng)鏈管理.E-mail：yechm6464＠163.com