在車輛調(diào)度的精確算

外文21.doc的翻譯數(shù)學(xué)規(guī)劃20（1981）,255。北荷蘭出版公司在車輛調(diào)度的精確算法基于生成樹和問(wèn)題，最短路徑放寬N.赫里斯托菲，英國(guó)帝國(guó)學(xué)院，倫敦SW72BX?A.MINGOZZISOGESTA，意大利烏爾比諾?P.TOTH的博洛尼亞大學(xué)，意大利博洛尼亞?1978年11月17日收到修改稿1980年17March我們認(rèn)為路由駐扎在中央設(shè)施（油庫(kù)）的車輛供應(yīng)問(wèn)題旅游客戶與已知的需求，在這樣一種方式，以最小化總的距離。？該問(wèn)題被稱為車輛路徑問(wèn)題（VRP）是一個(gè)概括的多個(gè)旅行商問(wèn)題有許多實(shí)際應(yīng)用。?我們提出了樹的搜索算法結(jié)合較低的VRP的精確解來(lái)自（i）最短的跨越k次中心樹（K-DCT）計(jì)算的界限，及（ii）Q-路線。最終的算法，還包括問(wèn)題減少和優(yōu)勢(shì)測(cè)試。?來(lái)自文獻(xiàn)的問(wèn)題，提出了一些計(jì)算結(jié)果。結(jié)果表明，是來(lái)自于第q航線的范圍是從k-DCT高達(dá)約25客戶該VRPS可以精確求解。?關(guān)鍵詞：車輛路徑，拉氏松弛，最短生成樹動(dòng)態(tài)規(guī)劃松弛。?介紹我們正在考慮的一個(gè)問(wèn)題，其中一組在地理上分散的已知的需求“客戶”與“車輛的車隊(duì)，必須送達(dá)”駐扎在中央工廠或倉(cāng)庫(kù)，這樣的方式，以盡量減少一些分布目標(biāo)。？據(jù)推測(cè)，所有車輛路線必須開始和結(jié)束車廠。車輛路徑問(wèn)題（VRP）是一整類的通用名稱?涉及的“客戶”參觀“車輛”的問(wèn)題。?VRP（也在文獻(xiàn)中被稱為“車輛調(diào)度”［8,9,10］，“車輛調(diào)度ing“的［4,11，20］，或者干脆”交貨“的問(wèn)題［1，14,21］）顯得非常在實(shí)際情況中經(jīng)常不直接重新|ATED的實(shí)物交付貨。？例如，收集從郵件箱中的兒童，拾取器?255256N.赫里斯托菲，A.Mingozzi和P.托特/精確算法車輛路徑?校車，房子通話旅游由醫(yī)生，預(yù)防性維護(hù)檢查旅游服務(wù)，洗衣交付等都是的VRPS在“交貨”操作可能是一個(gè)收集，收集和/或交付，或者兩者都不是，而這甚至可能不是一個(gè)物理性質(zhì)。?這里考慮的基本VRP如下所示。圖G=（X，A）被定義為它的頂點(diǎn)集合X和設(shè)定其甲弧線。設(shè)X'={XI］I=1 ?N}的一組N個(gè)顧客，并讓X0是用于倉(cāng)庫(kù)。？X=X,U{X0}的。一位顧客XI有以下要求：?（a） 在數(shù)量q?交付由車輛的一些產(chǎn)品，（b） 在“成本”UI車輛所需的卸載數(shù)量補(bǔ)氣，在x?。我們假設(shè)m個(gè)相同車輛容量Q的駐扎在油庫(kù)，總“成本”（如“距離”或“時(shí)間”）的車輛路線必須小于或等于給定數(shù)量T.?車輛的數(shù)目被假定為足夠大的一個(gè)可行的解決辦法存在。?我們進(jìn)一步假設(shè)，“成本”的最低成本路徑從每個(gè)頂點(diǎn)XI每個(gè)頂點(diǎn)XI為c~~J。？這是要求的總的數(shù)量在每個(gè)車輛路由是小于或等于到Q，每條路由的總的“成本”（計(jì)算成本的總和C?j的弧（XJ）形成的路線，再加上為這些客戶的路線上的xi的總和的U?）小于或等于T。?這里被認(rèn)為是VRP的目標(biāo)是設(shè)計(jì)出可行的路線-為每輛車之一-以提供所有客戶最小化總“成本”的所有路由。？對(duì)于本文的目的，“成本”C~~J上述可以是行程或旅游客戶之間的時(shí)間。？上面定義的VRP是一個(gè)概括的旅行商問(wèn)題（TSP）。？然而，雖然這后一個(gè)問(wèn)題的解決方案的確切方法有已經(jīng)開發(fā)了可以解決的問(wèn)題中的一個(gè)或兩個(gè)百元客戶［5］的VRP沒有這樣的算法存在。？事實(shí)上，最大尺寸一般VRPS報(bào)道解決在文獻(xiàn)中涉及的問(wèn)題有10或12個(gè)客戶？［9］雖然已經(jīng)解決了對(duì)于較大規(guī)模的非常特定的VRPS的［4］。在本文中，我們開發(fā)了一個(gè)確切的分支定界算法一般VRP的定義同上。？這些算法都是基于邊界派生：（一）固定程度的最短生成樹在一個(gè)指定的頂點(diǎn)，及（ii）最小Q-航線，Q=1.....?Q.在這些航線上的總負(fù)載正是Q，通過(guò)客戶的一個(gè)子集的軟件倉(cāng)庫(kù)通過(guò)從返回車廠。處罰Langrangean程序是用來(lái)計(jì)算這些界限。？我們也考慮和計(jì)算評(píng)估兩個(gè)不同的分支樹的計(jì)劃，搜索和介紹一些顯性的測(cè)試。？計(jì)算導(dǎo)致了一些問(wèn)題。N.赫里斯托菲，A.Mingozzi和P.Tothl精確算法車輛路徑問(wèn)題制定下面我們給一個(gè)整數(shù)規(guī)劃制定的VRP。？這制劑是一種簡(jiǎn)化，12［6］中給出的那些。？讓SK=1，如果車輛k后立即訪問(wèn)客戶訪問(wèn)第十一顧客兮，IJK-?，否則為0。VRP是：？最小化，L，？我：O?=OK=升NM？受???：ISK=1，J=1 ?N，（2）？我=0K=?NN/：0X!?IPK-J?=0?PSK=0'=K：L,...,M,P：0 ?N,(3)??(補(bǔ)氣?？I,K)<-Q,K：L ?M,(4)=1：O?CIJ~~IJK+EUI?IJK-<T,K=1 ?M,(5)?I=0J?愛?J=0??0/K：1,K=1 ?M,（6）?J二升中號(hào)?Y~~-YJ+N??：0K-<NL，我#j的=....?N（7）?K=升??我?KE{0,1}對(duì)所有的i,J,K,（8）???武斷。?表達(dá)式（2）的狀態(tài)，客戶必須訪問(wèn)一次。？表達(dá)?（3）指出，如果車輛訪問(wèn)客戶，它也必須離開它。表達(dá)式（4）和（5）的容量和每條路徑上的“成本”的限制。式（6）規(guī)定的車輛必須只能使用一次。？表達(dá)式（7）是子路消除條件來(lái)自旅行商問(wèn)題米勒，Tucker和Zemlin說(shuō)［19］，這也迫使各條路線穿過(guò)倉(cāng)庫(kù)內(nèi)；（8）的完整性條件。上述公式太復(fù)雜，是有用的，這是很清楚解決大小非平凡VRPS。?下界的計(jì)算在任何分支定界程序計(jì)算的值范圍到其它的問(wèn)題的解決方案（在某些節(jié)點(diǎn)的樹）是最重要的算法的效率。？在本節(jié)中，我們描述了兩個(gè)不同的VRP的下界。？這些邊界嵌入到樹搜索258N.赫里斯托菲，A.Mingozzi和P.托特/車輛路徑的精確算法在下面的部分中描述的程序和所產(chǎn)生的算法。？在為了簡(jiǎn)化演示，從今往后，我們將承擔(dān)對(duì)稱［C?J］。矩陣，并使用兩個(gè)CIJ和c282表示?。╥，1）的成本或電弧升分別?3.1。????勢(shì)必從最小k度中心樹（K-DCT）這是很明顯的，該溶液的值對(duì)M-TSP是低級(jí)綁定到的值的VRP的解決方案，采用M的車輛，由于VRP的是M-TSP額外約束。？因此，我們將在本節(jié)得出一個(gè)必然的M-TSP，然后專門為VRP。?考慮的解決方案示于圖的M-TSP。？升，其中車廠編號(hào)為X0，其中M=4的多條航線。？移除弧（X0，A），（X0，B），（X0，C）和（D，E），從各條路線之一-從這一解決方案-產(chǎn)生一個(gè)樹X0度為k=5。？我們將調(diào)用一個(gè)樹X0程度KAk次中心樹（K-DCT）。？一般來(lái)說(shuō)，如果任何一組，所以Y-<M弧相鄰x0和任何設(shè)置S1我的弧不相鄰X0刪除-從各條路線-一條弧產(chǎn)生的圖形將是一個(gè)k-DCTK=2M-Y。？的圓弧形成的M-TSP解決，因此，顯示tinguished分為三組：那些弧線形成一個(gè)K-DCT（與相關(guān)變量?升電弧升二1，如果在第k-DCT和?t二，否則為0）;這些弧因此，形成了集（與?：O=1，所以如果我是弧集??=0）;弧線形成一個(gè)集S?（?=1，如果l是集$1=0）。?對(duì)M-TSP現(xiàn)在可以歸結(jié)為如下：?米?最大限度地減少Z=?CT（T+?O+?I），（9）?受？？T->1，VSTCX#O，S，（10）/CTST，ST)?T=2M-Y，(11)圖?1。N.Christolfdes,A.Mingozzi和P,托特/車輛路徑的精確算法2?T=N（12/?/=1?,?0?0=Y,（13）??L=我（14）?國(guó)際能源署（IEA）AO?（?+?+?：?）=2，=L ?N，（15）?IU-AI??TE｛0，1｝，（16A）??OE｛0，1｝，（16B）??IE｛0，1｝。?（16C）??武斷。?其中m=IA｛弧的總數(shù)；（ST，ST）編寫的所有的弧集一個(gè)終端的頂點(diǎn)在?頂點(diǎn)集St和的補(bǔ)集?頂點(diǎn)的另一端；?AI是第十一集所有弧事件。?約束（10）對(duì)K-DCT的連通性，約束（11）IM構(gòu)成的程度上頂點(diǎn)X0，約束條件（12），（13）和（14）指定的數(shù)量弧和約束（15）施加的程度每個(gè)頂點(diǎn)（除X0）中的M-TSP溶液是2。？在上述公式中，Y被認(rèn)為是一種可變的，雖然它可能已固定先驗(yàn)恒定值M?或者，如果它是已知的（通過(guò)任何其他手段）的最大數(shù)目M-TSP解決方案單頂點(diǎn)游（即旅游類型X0-XI-X0）M，則y可以固定范圍內(nèi)的任意整數(shù)M1-<Y-M的先驗(yàn)然后，由式（9）?（16）所定義的問(wèn)題的解決方案將保持任何這樣的固定的y的最佳。？這是因?yàn)橹辽贋閥=M1弧相鄰X0（所以）必須從M-TSP（連同最佳的解決方案另一個(gè)M-Y不相鄰的弧X0，即獲得K-DCT。對(duì)于M-TSP，與N->M+1,我們必須有M,-<M-1,所以y可以選擇M-1-<Y<M.在上述公式中，我們還沒有取代的常數(shù)（M或M-1）為y，因?yàn)樵贛-TSP放松的，如下最佳的解決方案不是固定不變的，我們希望用y選擇y值（M?-Y-<M），最大限度地結(jié)合。?讓艾，I=1……？N，約束（15）非負(fù)相關(guān)的處罰。這些約束條件的拉格朗日松弛產(chǎn)生三個(gè)分解問(wèn)題P，P0和P，對(duì)于一個(gè)給定的y值，與一般的目標(biāo)：?MN?V（A）=?6，WT-2?_?喜（17）?I二升?赫里斯托菲A.Mingozzi的和P.托特/車輛路徑的精確算法其中PI=克拉+在，+AJ噸，它和JT是兩個(gè)終端的頂點(diǎn)的圓弧升，A0=0，并WL是寫？，?0?我的三個(gè)問(wèn)題，分別為。?對(duì)于一個(gè)給定的y值，設(shè)V（A，y）是最佳的解決方案的價(jià)值定義的問(wèn)題（P）（17），（10），（11），（12）和（16A），設(shè)V，A（A，Y）的最佳P0的問(wèn)題的解決方案的價(jià)值所定義的（17），（13）和（16b）中，讓V?（A）是定義最優(yōu)解的值的問(wèn)題P?（17），（14）和（16c的）。？較低綁定到M-TSP因此：?H=最大｛最大[V（A，Y）+V“A（A，Y）+V1（A，Y）]｝。？（18）?MI-Y-MA>0?上述約束也顯然是有效的VRP。？此外，額外的在VRP的約束可以被用來(lái)獲得一個(gè)更好的MI值大于該值M-1到M-TSP，從而增加了結(jié)合的進(jìn)一步。？M1值VRP的，可以得到如下所示。？讓客戶訂購(gòu)QL的遞減順序。？的M?單個(gè)客戶的路由，最多可以提供數(shù)量~~Q補(bǔ)氣其余車輛必須的，因此，能夠提供的剩余量，即(M-MOQ->?(19A)氣。I=I?L+1同樣，每一個(gè)客戶X?貢獻(xiàn)金額至少t?=UI+（CLI?+ciiz）的路線，其中x?“成本”，是“最近”和x?2第二次“最近”顧客到顧客X?。？因此，如果客戶訂購(gòu)降序的t?我們得到一個(gè)表達(dá)類似（19A）：（MM）T>-?TI。?（19B）I=MI+I?我們現(xiàn)在可以選擇M?作為最大的價(jià)值，同時(shí)滿足不等式（19A）（19B）。?3.1.1。????計(jì)算的V（A，Y）對(duì)于一個(gè)給定的問(wèn)題（P）A和Y，是一個(gè)K-DCT（K=2M-Y）;問(wèn)題解決方案是T?值V（A，Y）。???可以很容易計(jì)算計(jì)算最短生成樹（SST）的G［3］，并注意到度D頂點(diǎn)X0。？如果？-K樹T?導(dǎo)出，如果d<KA積極的罰款??/?放在頂點(diǎn)x0??和被替換的成本COJc0j-/Z，如果。>嘉負(fù)處罰P?被放置在x0和頂點(diǎn)的成本COJc0j/X的取代。？在過(guò)去的兩年情況下，SST是重新計(jì)算的過(guò)程反復(fù)進(jìn)行，直至D=K。?這是很容易證明，上述程序是有限的。？讓我們假設(shè)最初D<K。？對(duì)于每一個(gè)?。╔0，喜）?T~~計(jì)算艾：?AI=?愛-最大［T］（20）?李i?赫里斯托菲A.Mingozzi的和P.托特/車輛路徑的精確算法其中，E?是從x0到x路徑組的圓弧的T??，c0和GT在最后一節(jié)所定義的拉格朗日處罰修改弧費(fèi)用。讓升（一）是產(chǎn)生上述最大電弧。？如果/X，然后選擇?為：?/X=最小值［愛我（XO，西安）F???］（21）?我上述每個(gè)迭代將引入一個(gè)額外的弧，即?。╔0,X）并刪除弧I（我），其中i*i值，最大限度地減少（21）。當(dāng)d>K可以給出一個(gè)類似的證明有限性。?3.1.2。?????計(jì)算了VA（A，Y）P0問(wèn)題的解決涉及到選擇的y弧最小成本C0I的，I=1……?n要獲取的價(jià)值特搜A（A，Y）。然而，一個(gè)更好的選擇，所以設(shè)定的y弧可以得到如下：讓我們與每個(gè)路線rM-TSP解決方案成本？？？，這些成本加入路由rX0的兩個(gè)圓弧。？我們將承擔(dān)？->?注意，對(duì)于一個(gè)客戶的路由-6?因?yàn)檫@兩個(gè)成本是指相同的弧。？此外，我們訂購(gòu)的路線以升序字典順序的載體（0F0F）和重新編排他們的路線r指的是這個(gè)順序RTH路線。？因?yàn)閷?duì)于每個(gè)第一y的航線，我們可以選擇元素，所以最長(zhǎng)的兩個(gè)圓弧連接各條路線貯藏庫(kù)，它是明確的，所以費(fèi)用的集的弧可以高達(dá)：？?？。?現(xiàn)在，讓我們所有費(fèi)用60i的弧線毗鄰車廠下令在上升重復(fù)一次，為了與前M?有序列表中的成本，使它們看起來(lái)有序列表中的兩次。？令h（對(duì)）中的第p位置相對(duì)應(yīng)的成本此列表中。？它是那么很清楚，到M-TSP任何可行的解決方案，我們有?->小時(shí)（2），6-小時(shí)（4），63-小時(shí)（6）等，一般在6?-小時(shí)（2R）為任意的r=1 ?M,因此：??A（LY）=小時(shí)（2R）-<???（22）?R=LR=?是一個(gè)下界弧的成本因此，在套。??度皿，y）的計(jì)算，從（22）可以用來(lái)代替特搜A（A，y）的COMputation從方程（18）的約束。？這是因?yàn)榧s束：?EL??A_>L，A（A，Y）?LEA??可能已被添加到由方程（9）-（16）給出M-TSP的制劑。M-TSP這個(gè)約束是多余的，但不再冗余在P0問(wèn)題產(chǎn)生的M-TSP拉格朗日松弛。？（事實(shí)上，一個(gè)N.Christoiides,A.Mingozzi和P.托特/車輛路徑的精確算法數(shù)為M-TSP冗余的其他方面的限制，但并非如此之一的由此產(chǎn)生的問(wèn)題P，P0或P?可能已被添加到改善的最優(yōu)值V，V，A和第六這些問(wèn)題。）?3.1.3。????計(jì)算VI（A，Y）用“6”？［0］是在客戶處的最短電弧事件的成本乂？不含弧從倉(cāng)庫(kù)。？讓數(shù)量［1］遞增的順序排序，讓客戶重新編號(hào)，所以該客戶X?是指客戶在第i個(gè)有序列表。？然后，我們有：?我的?V,（H，Y）=Y?E，［1］。i=1時(shí)?3.1.4。????計(jì)算綁定（LB0）在本節(jié)中，我們給出了一個(gè)下界的計(jì)算程序從第k-DCT---LB0以下稱作。?步驟0（初始化）。？設(shè)置下界Z*=0。？讓Z*的價(jià)值到目前為止，最好的解決方案。？設(shè)置Y=ML。?步驟1（初始化）。？設(shè)置KOUNT=1，=0，=0 ?n和k=：2M-Y。?第2步（最短K-DCT）。？計(jì)算最短跨越的K-DCTT*上面提到的。第3步（附加的?。?。？計(jì)算?A（H，Y）和V?（H，Y），所以讓美元和1套弧產(chǎn)生的L值，A（A，y）和VL（H，Y）。?第4步（圖G）。？形成圖G=（X，T?u所以USOT*是用來(lái)意味著在樹T*的弧的集合。？讓ZL=G.ZL中所有弧的成本總和解決VRP的值的一個(gè)下界。？如果Z*〈爰集合Z?-ZL。如果Z?-Z?停止（主要算法的跟蹤步驟），否則如果Z*Z*去步驟5。？如果z*---ZL和KOUNT的=最大迭代次數(shù)允許去第7步。？否則KOUNT=KOUNT+1，轉(zhuǎn)到第5步。?第5步（處罰）。？如果就圖G頂點(diǎn)十一度DL2（I=1，...，N）=2M，停止。？（ZL*是最好的下限，可以通過(guò)以下方式獲得此步驟。），否則計(jì)算處罰：?（訾？-ZL）（二?我），我=0 ??喜喜+?F?21/2?-?=（DJ-/3j）］?where/3i=2,如果是0and/3i=2M-0,a為常數(shù)。第6步（成本矩陣［C?］）。？修改成本矩陣［C?D］為：?C?J=CO+）Q+喜。?轉(zhuǎn)到步驟2。步驟（更新Y）。？如果y=M停止，否則Y=Y+1，請(qǐng)轉(zhuǎn)至步驟1。?赫里斯托菲A.Mingozzi的和P.托特/車輛路徑的精確算法3.2。????最小Q-路線霍克等人。？［17］N-TSP路徑：這是特殊情況動(dòng)態(tài)規(guī)劃松弛，獲得邊界COM程序binatorial問(wèn)題和［7］中所述。？在這里，我們使用這樣的程序開發(fā)界的VRP。?讓W(xué)是集所有可能的負(fù)載（數(shù)量），可以存在于任何車輛的路線，即?W=Q~~補(bǔ)氣?我=Q~~問(wèn)，對(duì)于一些??我？｛0，1｝。?I=!?讓w元素的升序排列，并讓寫---［威斯康星。？我們將表示由q（升）的第l個(gè)元素的W的值，7R（十七），升*，使Q（升）=Q。?路徑上的總負(fù)荷Q~~-（XO，西安，XI2……x?K）被定義為Y~~，倉(cāng)??x0/qi-（注的Q?不一定是簡(jiǎn)單的路徑。）?讓英尺（？）的最低成本路徑的成本與總負(fù)荷從X0到西安的?6XOq（下升）。？圖？圖2顯示了一個(gè)可能的這樣的路徑，被稱為的q路徑。?AQ路徑額外的?。╔I，XO）被稱為終端Q-路線和具有成本F?（^一）=FL（?）+C?O。?讓VRP的溶液組成的M航線：?R1=（XO，可可西里“，”?，Xipl，XO載荷q（1/10）;?R2=（XO，XI2 兮，2，XO）與負(fù)載Q（12）;RU=(XO,秀 xipM,XO)負(fù)載Q(IM)。?，如果路由RK成本C(RK),然后表示?JF~~K(XI?K)=-FLK(XI?)+CI~~K,0<-C(RK)，K=1 ?M,?該路徑對(duì)應(yīng)于英尺(十一)不一定是簡(jiǎn)單的，但它是不容易施加的條件，沒有頂點(diǎn)被訪問(wèn)的路徑多于一次。？在另一方面，它是很容易施加限制的路徑不應(yīng)該包含連續(xù)三個(gè)頂點(diǎn)所形成的循環(huán)。？(例如，中的路徑圖？2包含環(huán)路XK，XK，X)，有了這個(gè)限制，更好的低綁定可以計(jì)算出來(lái)。\“阿憶ore2?_?RC43CO?圖?2。?赫里斯托菲A.Mingozzi的和P.托特/車輛路徑的精確算法3.2.1。?????Q-無(wú)循環(huán)的路徑設(shè)角(X?)的頂點(diǎn)之前，為了乂？到f(11)相對(duì)應(yīng)的路徑上。讓簡(jiǎn)(X?)的最低成本路徑從車廠到x?載荷q(l)及?RT(^一)PT(X?)?,L(XL)是頂點(diǎn)之前，對(duì)x?路徑上的對(duì)應(yīng)荷蘭，EKT(XL)。?圖？圖3顯示了兩種可能的路徑，對(duì)應(yīng)到f?(十一)?BL(?)。?對(duì)于一個(gè)給定的值的I，令g(?中，x?)從x0到的最低成本路徑的成本?X?喜之前為x?沒有循環(huán)。然后：我FR(XJ)+Q，I，如果PR(XJ)?XI(23)，克（XJ,西安）?為l?（XJ）+Q,?，否則?1'Q（L'）=Q（L）奇。由于函數(shù)g計(jì)算從（23），函數(shù)f和?b的現(xiàn)在升計(jì)算如下：?佛羅里達(dá)州（十一）二最小值［克（XJ，西安）］］?XJ我24a中?PT（-一）=??其中，x?xi的對(duì)應(yīng)于上述最低值；?QBL=最小值［克（XK，西安），（^一）XK?P?（??噸（24B）?E，（，）=！?其中，x?XK的值對(duì)應(yīng)于上述最小。從上面的表達(dá)式中的路徑對(duì)應(yīng)到f?（11）很明顯，有沒有結(jié)束循環(huán)。的函數(shù)f，?，p和?初始化，如下所示：?FL（-一）=&T（11）=?L使得Q（I）#QL?//??噸（次）?:CO?圖？3。N.克里斯托?DES，A.Mingozzi和P.托特/精確算法車輛路徑佛羅里達(dá)州（十一）=“合作，我PL（西安）=XO］QBL（XI）=?/1，Q（L）=補(bǔ)氣。3.2.2。????通過(guò)Q航線設(shè)q,T(X)的最低成本路由的價(jià)值，沒有循環(huán)，從車廠，傳遞到x?整理回車廠總載荷q(L)。這樣的路線將被稱為要么必須由一個(gè)通過(guò)Q-QJL路線，(十一)最好的兩個(gè)Q-十一的路徑添加到q'(升)的總負(fù)荷-q時(shí)(升)+Q?，或最好路徑和次佳的路徑為x?添加到q'(升)的總負(fù)荷。?的QJT(十一)然后，可以計(jì)算如下：?F?TQ)(-一)+F?QV)-Q)(X)如果P，Q)(X?)“如?QV)_q)(?)?BL(XI)二風(fēng)采補(bǔ)氣<-Q<-?Q'(L)QEW最小[F<Q)(^一)+4，#"UET)-Q)(11)?B#"EQ)(^—)+/?！?“6)_q)(^一)]IFP?TQ)(-一)=PT，ECT)-Q)(-一)。我們?cè)谶@里指出，計(jì)算工作量計(jì)算的q路徑呈線性關(guān)系為w。？因此，如果w是大，此操作可能會(huì)相當(dāng)時(shí)間耗時(shí)。?3.3。????的q-航線的境界，從計(jì)算設(shè)在VRP可能可行的單航線的總數(shù)被索引R-1.....??讓客戶路線r指標(biāo)集先生，成本的路線博士和路線的總負(fù)荷KR=?我?M，補(bǔ)氣。？讓倪指標(biāo)集航線來(lái)訪客戶X?。?如果路線r是在最佳VRP溶液，否則。?VRP是：?閔？DRYR，(25)?ST?ff'u。?YR=1，=1 ?N，(26)年=M,(27)?年E{0,1}。？(28)路由?赫里斯托菲A.Mingozzi的和P.托特］精確算法［或車輛3.3.1。????束縛LB1讓我們重新編號(hào)路線r=1的組，...，？，通過(guò)集分割成N個(gè)塊，阻塞I（I=1.....N）是與最后一名顧客索引ix?塊中的航線上。？在一個(gè)塊的路線索引S二升 ？?。?讓?=｛的10otherwise.ifof塊i是在溶液中，?路線?上述配方（方程（25）-（28））變成：?最小“？?二？（25'）?I?LS=?圣?_?=1，J=1....?，N（26'）（I，S）?NJ?I=1秒?升??，S，E｛0，1｝。?（28'）?的有序?qū)Γ╥，）是用于在標(biāo)簽的路由的塊i和/QRJ有序?qū)Γ↖，S）是一套識(shí)別含有客戶XJ的路線。??~~是路線的成本（一）。?所定義的問(wèn)題（25'）（28'）可以通過(guò)更換約束條件放寬（26'）與弱約束下面的一組：???<1，=1 ?N，（26'a）S=L???文？，F(xiàn)I?=(26'b)I=1秒=?其中KIS是路由的負(fù)載（I,S）和QR=?-1氣。?（25'）所定義的問(wèn)題，（26'a）,（26'b）,（27'）和（28'）,現(xiàn)在可以減少通過(guò)觀察對(duì)于一個(gè)給定的路線上的，路線（I，S*i和一個(gè)給定的載荷q）所有其他航線占主導(dǎo)地位（I，S），S=1.....??，S?*，如果?DLS，二和KIS=KI?*=Q。?因此，對(duì)于每個(gè)i和各qEW只有一個(gè)路由需要加以考慮。？讓我們撥打這條路線（I，L），與我-?-（Q）。？現(xiàn)在有瓦特航線考慮對(duì)每個(gè)i。松弛問(wèn)題就變成了：?閔??！?IL，（29）?i=1時(shí)?赫里斯托菲A.Mingozzi的和P.托特/車輛路徑的精確算法瓦特?ST?FLT-L，I=L ?N，（30）NW?NW?=M，I，(32)I-1?適合?{0，1}。?（33）?一個(gè)下界值二？（即成本最低成本路由總載荷q（l）及X;作為最后的客戶訪問(wèn)）的成本是麻省理工學(xué)院---F?（十一）最少的成本Q-Q=Q（L）路由。？因此，可以得到作為一個(gè)綁定LB1值的目標(biāo)函數(shù)所定義的B1問(wèn)題的解決方案：?I=1=1受約束（30）-（33）。B題1動(dòng)態(tài)編程方便，可以解決如下。讓喜（B,A）是最佳的解決問(wèn)題右側(cè)的B1用b替換（31）和（32）的右手側(cè)，取而代之的是，與適合=0J>I，L=1 ?瓦特?喜（二）可以計(jì)算遞歸喜（B，A）=最小值［喜（B，A），最小｛喜升（B-Q，-1）+公里。？？）｝］（34）??QEW我?:A=2，...，M;= ?N-M+A;QR-（MA）。Q<B〈分鐘［QR］a'Q。功能被初始化為：?喜（黑l）=｛M?我'#（B）ififbCW'b?W。?下界VRP?LB1=HN（Q，M）。（35）?3.3.2。????界LB2我們?cè)俅慰紤]的VRP制定方程（25）-（28）。讓我們代替Y，通過(guò)：1?年='KR2?irqi。（36）?I?MR?現(xiàn)在變成制定VRP的方程（25）-（28）I?MRN.赫里斯托菲，A.Mingozzi和P.Tothl精確算法車輛路徑ST?北京時(shí)間，R=L，=L...?N，（38）任我?=1"？M上？jrqj'IEMR，R= ?（39）?IRKR-RJEE（40）?R=李?MR??IR?{0,1}。?（41）?約束（39）確保二1當(dāng)且僅當(dāng)?J,=VJ1EMR,因此?二1。因此，約束（38）對(duì)應(yīng)的限制（26）。?讓上述的問(wèn)題（i）除去約束（39）和（ii）在放寬更換一套先生由一整套路線rI={1……？N}。？將所得通過(guò)添加約束松弛問(wèn)題可以在一定程度上加強(qiáng)??EE補(bǔ)氣？IR=QT,（42）R=LI=1?由方程（37）給出的配方是多余的-（41）,但不再是多余的，對(duì)于新的松弛問(wèn)題。?在松弛的問(wèn)題所定義的式（37）,（38）,（40）,（41）和（42）（與我先生取代），只有一個(gè)路線需要考慮為每一個(gè)客戶X?和路線上的每個(gè)可能值載荷q（QEW）。？這是明確的事實(shí)上，如果兩條航線RL和rz都包含客戶X和負(fù)載KRL=2=K,Q,那么DQ<-DR2，航班RL主導(dǎo)路線R2松弛問(wèn)題。讓我們調(diào)用undominated路線（I,L）L=7R（Q）。？我們將表示成本這條路線用d~~J。？現(xiàn)在有瓦特航線考慮對(duì)每個(gè)i。？輕松的現(xiàn)在的問(wèn)題變成?NW?閔：牛乳?我，（43）?瓦特?ST__?為l?'IL=1,=1 ?N,（44）/?RW?/?RW（46）?我?？{0,1},（47）?哪里的DIS-ditqi/Q（L）。?需要注意的是，如果沒有路由，然后通過(guò)我與載荷q（L）存在DIJ=00。二?/Q（L）代表的邊際成本提供客戶，路由負(fù)載Q（L），單位數(shù)量，因此二?顧客i的是“成本貢獻(xiàn)”。N.克里斯托］新娘，A.MingozziP.托特/車輛路徑的精確算法這是很明顯的成本?bt的（/）通過(guò)Q-的航班的最小成本通過(guò)X/并具有載荷q（L）是一個(gè)下界DTT的客戶。？因此，解決問(wèn)題的B2定義的目標(biāo)函數(shù)?NW?閔？?一下？（48）?和約束條件（44）-（47），其中位=@T（XT）"，QL/Q（L），是一個(gè)下界VRP。位是一個(gè)下界D/T是通過(guò)放寬限制，在一個(gè)可行的解決方案，每個(gè)頂點(diǎn)的度為2。?在3.2節(jié)中，我們給了一個(gè)程序，用于計(jì)算T，英國(guó)電信（BT）（十一）對(duì)每個(gè)i=1.....??每1=1 ?瓦特?3.3.3。????計(jì)算結(jié)合LB2一個(gè)簡(jiǎn)單的綁定LB2可以計(jì)算通過(guò)忽略約束（45）和（46）并盡量減少只（44）和（47）（48）。？的結(jié)果必然是：LB2=最小值［位］。?（49）?T=LI=L，...，W?拉格朗日松馳考慮，可以得出一個(gè)更好的綁定LB2約束（45）和（46）以通常的方式。?3.3.4。????處罰程序［或改善的范圍結(jié)合LB1對(duì)應(yīng)的解決方案，可以通過(guò)以下方式獲得回溯使用遞歸（34），（部24a）和（24b）的。？此解決方案代表的曲線圖，如在圖中示出一個(gè)。？4，它顯示了三個(gè)Q-航線，因?yàn)檫@些航線都不是簡(jiǎn)單的路由不一定成對(duì)頂點(diǎn)相交造成圖圖G。?4包含頂點(diǎn)度（客戶）尊重0度到G大于2,有的客戶。現(xiàn)在，讓我們放置罰則艾（I-1.....N）上的頂點(diǎn)XI計(jì)算機(jī)從類似的表達(dá)式，以對(duì)M-DCT結(jié)合的，即用于?/?我=愛+或“1-N字?我-ZL11/2（DI-2）（50）?修改成本矩陣［CJ：CTJ=CTJ+AT+AJ。?的功能，對(duì)，?b和#現(xiàn)在可以計(jì)算新的矩陣［cJ的等?在第t次迭代的結(jié)束：LB1=HS（QT，M）-2?艾（51）?i-1的?其中，HN（QT，M），計(jì)算從遞歸（34）相對(duì)于改性矩陣CTJ，是一個(gè)綁定的VRP。對(duì)于結(jié)合LB2的情況下，我們可以找到-回溯-Q-路線GIN.赫里斯托菲，A.Mingozzi和P.Tothl精確算法車輛路徑\“？一。？？。？問(wèn)degree6?..“W/河-??“？，，-?“??0??????? 度0?圖?4。?QJL，（xi），二是1的值中的最小值對(duì)應(yīng)的表達(dá)?最?。跿PL（，）］升二, ?l問(wèn)-3-廣的?讓8?XKGI程度。？計(jì)算DK=??],補(bǔ)氣/Q(LI)。度DK都應(yīng)該等于2VRP在任何可行的解決方案。?現(xiàn)在的上升過(guò)程中涉及的迭代計(jì)算的h?詞我表達(dá)（50），修改的成本，重新計(jì)算，P，B，？?和tk等。第t次迭代結(jié)束時(shí)的LB2=?分鐘問(wèn)？-2（52）?I=LT=L ?LQ（L）JI?升?是綁定的VRP。?3.4。????結(jié)合的計(jì)算的計(jì)算方面從最小DCT結(jié)合的LB0的值作為一個(gè)函數(shù)的圖中給出罰款的上升過(guò)程中的迭代的數(shù)量。？5。？也如圖所示。？圖5是綁定的LB2從第q航線。？圖？5。？指的是一個(gè)21客戶VRP曾在文獻(xiàn)中出現(xiàn)的測(cè)試問(wèn)題3在參考文獻(xiàn)［9］中，但沒有最大路徑距離的限制，并與客戶的交貨時(shí)間假定為零。？的值的最佳解決方案對(duì)這個(gè)問(wèn)題的長(zhǎng)度為374.3個(gè)單位，涉及4輛。?作為比較的手段，解決無(wú)約束的4-TSP值?315。在分支定界過(guò)程很清楚，回溯可以發(fā)生?N.基督=的潮汐，A.Mingozzi和P.托特/精確算法車輛路徑271400-374-R369LB2=---325=。?LB0300-?200-100,468101214161820迭代圖？5。?一旦被綁定在某些迭代?*（超過(guò)的值的最佳解決方案迄今為止發(fā)現(xiàn)的）。？為了避免不必要的計(jì)算，在迭代過(guò)程中我們使用了擬合的多項(xiàng)式描述作為一個(gè)函數(shù)的值的約束迭代次數(shù)，來(lái)預(yù)測(cè)預(yù)期的迭代次數(shù)所需的勢(shì)必將超過(guò)Z札？如果這個(gè)數(shù)字是非常高的，或者如果最終預(yù)期值綁定低于Z*，上升迭代終止分支是采取的地方。?設(shè)T是允許的最大數(shù)量的迭代，讓：?LB（T）7/=LB（1）'?LB（t）是值的綁定在迭代（T）之后。？讓?/計(jì)算初始節(jié)點(diǎn)分支定界樹。？如果在任意節(jié)點(diǎn)v<Z*分支和綁定的樹rlLBV（1）的（如LBV（1）后的第一個(gè)約束迭代節(jié)點(diǎn)v）則沒有作出進(jìn)一步的迭代設(shè)法改善約束。？如果?LB?（1）->祖噸?迭代塊（固定先驗(yàn)），多項(xiàng)式272N.赫里斯托菲，A.Mingozzi和P.托特/車輛路徑的精確算法?嵌合的值LBV（噸），t=1時(shí)....？，TZ和LBV該值T*（T*）=Z*的計(jì)算方法。？如果t*->T的上升是被遺棄。？如果t<T另一個(gè)塊的t?迭代被執(zhí)行時(shí)，被裝配到一個(gè)新的多項(xiàng)式LB'（t）的，噸=1……？噸?等？分支策略第7節(jié)中所示的計(jì)算結(jié)果，推導(dǎo)出通過(guò)使用兩個(gè)可能的分支策略如下。?5.1。 ????分公司上一個(gè)弧形（BB1條）支化，電?。?？11）與此不同的是選擇了在一個(gè)節(jié)點(diǎn)的分支搜索樹，以延長(zhǎng)部分完成的路線（X0，XK……x?）。替代分支作為一個(gè)可能的延伸，是拒絕?。╔I，XJ）路線。?5.2。 ????分公司路由（BB2規(guī)則）與此不同的搜索樹的一個(gè)節(jié)點(diǎn)的分支對(duì)應(yīng)于一個(gè)一個(gè)可行的路線SJ。在這個(gè)節(jié)點(diǎn)的狀態(tài)（比如在舞臺(tái)h）為代表的有序列表：?SJ，L=｛（X），SJ2（2） ?SJH（X'h）｝?SJ（X?），是一個(gè)可行的單一路由（jrth），其中包括指定顧客XLR和其他客戶是不是已經(jīng)包含在前面路線SJL（可可西里）……？？爵士（Xir_l）"在本節(jié)中，我們將使用的字路線暗示無(wú)序客戶形成路徑。組7R（X?R），也就是說(shuō)，所有可行的路線SJ（X?，）通過(guò)一個(gè)客戶X-R，形成所產(chǎn)生的所有可能的套客戶（包括客戶x?R）范圍內(nèi)的客戶，使總需求集少于或等于問(wèn)：路由開銷通過(guò)的第j個(gè)這樣的集合SJ（西安）然后計(jì)算解決相應(yīng)的TSP。由表L表示的狀態(tài)是在圖示意性地示出。6中FH=X-Y（X0?S#?R二升?是用于集“免費(fèi)”的（即尚未布線）客戶階段?。一旦達(dá)到樹底部的說(shuō)，級(jí)M時(shí)，F(xiàn)M=0，列表L包含的溶液組成的M航線VRP的。?從某個(gè)階段正向分支?涉及客戶的選擇十^一，+??FH一代列表ZR（XIH+?）所有可行的單一路線，通過(guò)通過(guò)這個(gè)客戶。這是很明顯的小的數(shù)目分支的可能性的任何階段?樹搜索的效率就越高，并且它是因此，很顯然，使x?H+'應(yīng)選擇從FHSO列表7R路由?赫里斯托菲A.Mingozzi的和P.托特/精確算法［或車輛階段I?\\\\?SJ（?）?/..?///II?\\\?2?的分期////“L”“?所有的列表的E（xiz）?/?/J?'。我“?可行的單一路線通過(guò)XI2傳遞和othercustomers?/IX“-從FI?H??n的NH級(jí)LI?,/??），HSJ（-一）?SJH（XIH）?代表的國(guó)家由表L圖？6。?（十一）盡可能短。這往往是的情況下，如果x?H??選擇是一個(gè)“孤立的”從倉(cāng)庫(kù)的遠(yuǎn)客，或者如果它哈哈?的大量需求qih的，“?它是昂貴的計(jì)算僅僅是為了通過(guò)產(chǎn)生的所有路由X??不可行的，然后直接消除通過(guò)征收各種測(cè)試。它是。因此，希望將這些減少測(cè)試進(jìn)入在早期階段路由路由產(chǎn)生過(guò)程，從而消除否則在以后的時(shí)間被認(rèn)為是不可行的。其中的一些測(cè)試被考慮在下一節(jié)促進(jìn)。減少和優(yōu)勢(shì)測(cè)試考慮矩陣B=〔b］的計(jì)算過(guò)程中引入結(jié)合的LB2。讓L*l的值?B，T=最小值［B］。?升?減少R1。如果對(duì)某個(gè)i和1：?LB2-BITT+B，-Z*(53)274N.赫里斯托菲，A.Mingozzi和P.托特/車輛路徑的精確算法?然后元素b?j的矩陣B可設(shè)定為0%,LB2是由公式(52)。?減少R2。讓我們假設(shè)，在一些解決方案，客戶XK提供載荷q(L)的路線。S值的下界是：?其中V是最大貢獻(xiàn)?一組客戶綁定LB2其總需求為q(L)-QK,即?:VMYcxMax{XK}［XI?CY位，xiGY?-J=(54)?QLq(下升)-QK］。?上限I7忽略的完整性限制，可以計(jì)算出在V在上述表達(dá)式(24)完全相同的方式綁定丹計(jì)算背包問(wèn)題。？如果?Z雙向，？+Q，(XK)，Q-2?我喜＞-Z*?我#K?則可以設(shè)置為oo與矩陣B的元素BKL。?6.1。????顧客對(duì)納入和排除II排除現(xiàn)在，我們將假定乙已減少了施加削減R1和R2所示。讓我們考慮兩個(gè)客戶XK和XI。如果這兩個(gè)客戶在相同的路由(R)的最優(yōu)解，那么成本C(R)的路線是?C（R）-COGQ-CKJ"的Cjo?和路徑R上的最大負(fù)載必須-〈問(wèn)：因此，如果XK和xi上?同樣的路線？?=B"T+（庫(kù)克群島+CKJ+CJO）（補(bǔ)氣+QK）LQ-2E?是最佳的解決方案的一個(gè)下界。因此，如果V->Z*如下x?和xj不能在同一路線。我們將調(diào)用［XK，X?］禁止對(duì)客戶集合元素（K，J）的矩陣P=［PKJ］-我。?5.1.2?包容讓我們?cè)賮?lái)考慮兩個(gè)客戶X?和x?2和形成減少VRP沒有這兩個(gè)客戶。下界減少VRP至少?#?，?2億，*-2?我??2&，因?yàn)槿绻麑?duì)應(yīng)路由QJT，*（X~~）包含N.赫里斯托菲，A.Mingozzi和托特/精確算法車輛路徑?？蛻羲觯騲?：或兩者兼而有之，那么路線不包含這些客戶必須有大于或等于價(jià)值。此外客戶X?和x?2的減少VRPVRP的解決方案會(huì)增加成本（至少）?V=?分鐘［C?，?，+C，V，-C??］問(wèn)？+Q?+QV<-Q］。?I=1,2?I，易?如果?。ㄉ?，x?2）被排除在該溶液中，然后加入的乂，而x?2中減少的VRP系統(tǒng)軟件的成本會(huì)增加一個(gè)量V'由下式給出的解決方案相同的表達(dá)式，但與X~~，XR，?，:和x?：XV??x?。?因此，一個(gè)下界VRP?。╔?，X?2）排除雙向？-?，?I+V'，?I?2ICTL，CT-1如果這個(gè)界是大于或等于z?：如下，電?。╔?，?2）必須只有在這種情況下，我們?cè)O(shè)置元件P??2=1的溶液。未設(shè)置為矩陣P的所有元素-+1的排除和納入測(cè)試假定被設(shè)置為0。?矩陣P可以被用來(lái)減少分支的多少則在樹中搜索兩個(gè)不同的支化的基礎(chǔ)上的?。˙B1）和算法分支的基礎(chǔ)上的路由（BB2）。?7.1。????可行性和優(yōu)勢(shì)我們現(xiàn)在將描述一些簡(jiǎn)單的可行性和優(yōu)勢(shì)測(cè)試可以用來(lái)消除分支定界樹的節(jié)點(diǎn)。?（一） 當(dāng)使用分支計(jì)劃的BB1國(guó)家的陳述包括部分完成的路線。如果這條線路可以提高由3局部最優(yōu)優(yōu)化的程序［18］相對(duì)應(yīng)的節(jié)點(diǎn)可以被拒絕。（二） 當(dāng)使用分支計(jì)劃BB2讓時(shí)SJ?（?h）和S?（XIH）的兩個(gè)節(jié)點(diǎn)（航線）所產(chǎn)生的同一個(gè)頂點(diǎn)級(jí)（小時(shí)-1）。讓瑞銀（F?）是一個(gè)上限和LB（F?）總成本的一個(gè)下界需要提供客戶在F???［SI?（?小時(shí)）］+UB（FH）-<C［SJ?（XIH）］+LB（F-），?其中C（S）是一個(gè)可行的路線S的成本，然后節(jié)點(diǎn)S~~的（XL）主導(dǎo)節(jié)點(diǎn)SI?（XIH），而后者則可以從列表中7R（X，H）中刪除。這兩個(gè)分支計(jì)劃BB1（當(dāng)路由目前正在一步形成完成）和計(jì)劃BB2：?（三） 如果能夠證明，其余的車輛不能夠（例如因?yàn)槟芰Σ蛔悖┨峁┪床季€的客戶，該節(jié)點(diǎn)可以拒絕。（4）如果兩個(gè)節(jié)點(diǎn)a和/3,表示為一個(gè)路?？由的成本?路由?赫里斯托菲A.Mingozzi的和P.托特/精確算法［或車輛大于或等于/3所表示的路由的成本和剩余的VRP在一個(gè)節(jié)點(diǎn)是同樣的問(wèn)題或節(jié)點(diǎn)/3留在VRP的一個(gè)子問(wèn)題，/3主要是由節(jié)點(diǎn)/3可以拒絕。?例子我們將說(shuō)明前面幾節(jié)中所描述的程序，通過(guò)一個(gè)例子涉及N=10的客戶和M=4的車輛。距離矩陣［C0］和客戶需求；0是指車廠。？該車輛的通行能力是24個(gè)單位。0123456789100-24.127.617.223.311.116.07.020.29.822.024.1-26.033.046.227.621.2-15.535.320.240.432.728.037.245.8-20.017.026.124.028.826.939.023.316.135.320.0-31.317.029.242.728.142.4距離C~~?矩陣11.126.020.217.031.3-27.113.412.018.625.616.028.140.426.117.027.1-18.035.514.427.67.031.232.724.029.213.418.0-18.05.315.020.238.028.028.842.712.035.518.0-23.022.69.833.037.226.928.118.614.45.323.0-14.322.046.245.839.042.425.627.615.022.614.3-I=12345678910?需求?補(bǔ)氣=156789121313345678921?（一）首先，我們將使用一棵樹搜索程序使用分支規(guī)則BB1勢(shì)必LB0。以啟發(fā)式取得了初步的可行的解決方案給出了一個(gè)上限為225.0。分支定界樹的根節(jié)點(diǎn)計(jì)算下界LB0為211.0，后30罰迭代計(jì)算。完整的樹示于圖中。??????????????旁邊的數(shù)字到一個(gè)節(jié)點(diǎn)是綁定LB0對(duì)應(yīng)到該節(jié)點(diǎn);?N.Christolfdes，A.Mingozzi和P.托特/車輛路徑的精確算法在每個(gè)節(jié)點(diǎn)的數(shù)目是要訪問(wèn)的客戶的數(shù)量上的下一個(gè)新興路線。以上的客戶數(shù)表示否定（即酒吧客戶是不是下一個(gè)要訪問(wèn)的）。？圖?7代表深度優(yōu)先“分支左”每當(dāng)產(chǎn)生的程序和樹可能。？因此，在搜索期間找到的第一個(gè)解決方案是產(chǎn)生在第23屆節(jié)點(diǎn)（標(biāo)有星號(hào)），另外26個(gè)節(jié)點(diǎn)生成證明該解決方案是最佳的。最佳的解決方案是：?路線1：0-9-7-0路線2：0-5-8-0路線3：0-4-1-3-2-0路線4：0-6-10-0?的最優(yōu)值是222.7。（B） 現(xiàn)在，我們將說(shuō)明使用的相同示例的結(jié)合LB2。？在試圖計(jì)算路由節(jié)點(diǎn)的分支和一個(gè)下界界樹，使用表達(dá)式（22），根據(jù)表達(dá)式計(jì)算與懲罰西昂（20），以及允許的最大的20罰迭代，222.7綁定來(lái)自上面的第七迭代的。路線1（XL）產(chǎn)生這種綁定從等式（22）表示的一個(gè)可行的解決方案的VRP，即?BL，（9）和TPL，（7）符合上述路線1;$L，（5）和$1，（8）符合以上航線2;?BL，（6）和$1，（10）符合上述路線3;?1，（4），$升，（1），$1，（3）?千升，（2）對(duì)應(yīng)于上述路線4。?已獲得了最佳的解決方案，因此，該過(guò)程終止沒有分支的分支定界樹是必要的。?（C） 現(xiàn)在，我們將說(shuō)明使用LB0結(jié)合分支規(guī)則4.2節(jié)。示于圖的完整的樹搜索。？8。？在第一級(jí)三生成節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)代表一個(gè)可行的路線通過(guò)挑選顧客（客戶91級(jí)）。（上限再次假設(shè)225.0）經(jīng)過(guò)其中的分支是從與該節(jié)點(diǎn)的搜索計(jì)算最低的區(qū)域在每一個(gè)階段，在圖所示的樹。8產(chǎn)生。？在這個(gè)數(shù)字顯示綁定節(jié)點(diǎn)和客戶形成相應(yīng)的路由節(jié)點(diǎn)內(nèi)。顯然，隨著四條航線有只有四個(gè)水平總共具有22個(gè)節(jié)點(diǎn)的樹。?????????????計(jì)算結(jié)果在本節(jié)中，我們調(diào)查的計(jì)算性能三個(gè)在實(shí)施例中示出的算法，也包括顯性測(cè)試第5節(jié)。？10個(gè)問(wèn)題用于測(cè)試范圍從N=10，N=25278?N.Christolfdes，A.Mingozzi和P.托特/車輛路徑的精確算法211[O?UB=225。198[9升223我21010213.2121816}[6我199/7?223.2225.2226(7)210.9(17)213。?不可行217.7[3}225.113}212.7?我213.318我224223。?(1)225(I)222.4(0)223(0)213.2(2)222.2??，…L,?(1?2231?225[0I(0?223[2]223?不可行??216.613升221.21222.7?*?218SolutiOnUB.222.7found不可行//不可行0-9-7-0224I?0-5-8-0??0-4-1-3-2-0不可行??v??0-6-10-O??圖？7。？例如使用綁定的LBO和分支規(guī)則BB1的分支定界樹。??0?R??C?，問(wèn)BJQC?C?，問(wèn)?了？N.克里斯托］新娘，A.MingozziP.托特/車輛路徑的精確算法客戶。這些問(wèn)題有些是從文學(xué)，其他均來(lái)自直接從這些。示于表1的10個(gè)測(cè)試問(wèn)題。?問(wèn)題6至10日在表1中的車廠車廠在相同的位置在［9］的50個(gè)客戶的問(wèn)題。在所有的問(wèn)題中，沒有時(shí)間的限制是con-考慮它們?表2和表3給出了三種算法的計(jì)算性能，樹搜索算法1分支規(guī)則BB1LB0和約束；算法圖2是相同的作為與結(jié)合LB2的算法1，算法3是樹搜索分支規(guī)則BB2結(jié)合LB0。?表2示出的值的最優(yōu)解的問(wèn)題，以及的值界LB0和LB2根節(jié)點(diǎn)。還示出車輛路徑啟發(fā)式算法的使用，即通過(guò)以下方式獲得的值的解決方案最好的“2階段”和“樹”啟發(fā)式［6］。?表3顯示了計(jì)算時(shí)間和分支中的節(jié)點(diǎn)總數(shù)界樹算法的1，2,和3。還示出了計(jì)算時(shí)間需要運(yùn)行的上述兩個(gè)啟發(fā)式。所有的計(jì)算時(shí)間如表3所示，CDC7600秒FTN編譯器。？所有代碼是在FORTRAN4。?雖然使用的啟發(fā)式始終獲得最佳的解決方案，為每問(wèn)題，應(yīng)當(dāng)指出，這主要是由于這樣的事實(shí)，存在的問(wèn)題是小尺寸和相對(duì)自由的限制。還應(yīng)當(dāng)指出，從表2綁定LB2的最佳解決方案值的2.4%以內(nèi)，平均在任何場(chǎng)合是綁定遜于6.9%。這表明，對(duì)可能許多實(shí)用場(chǎng)合，目前可用的解決方案的VRP?表1測(cè)試問(wèn)題?問(wèn)題NMQ詳情10424,例如由于1246000[9]問(wèn)題21236500其他資料2146000[9]問(wèn)題42164000其他資料15555是第15條50客戶問(wèn)題19]問(wèn)題615390其他資料20658客戶是指那些編號(hào)為11到第30的50客戶的概率LEM[9]問(wèn)題820485其他資料25848的客戶是指那些編號(hào)16到30中的50顧客的概率LEM[9]?赫里斯托菲A.Mingozzi的和P.托特/車輛路徑的精確算法（使用綁定）保證足夠接近到最佳不保證?一種改進(jìn)的解決方案繼續(xù)搜索。?表2計(jì)算結(jié)果：值問(wèn)題解決方案的初始值下限?啟發(fā)式優(yōu)化LB0LB2?TOC\o"1-5"\h\z222.7 222.7 211.0 222.7290.0 290.0 228.6 269.8244.0 244.0 225.1 240.3374.3 374.3 325.4 369.1494.7 494.7 400.0 474.0334.1 334.1 298.1 321.4277:9 277.9 252.1 265.5429.9 429.9 381.2 429.7357.6 357.6 260.0 346,4606.3606.3488.9602,9?表3計(jì)算結(jié)果：時(shí)間（以秒的CDC7600上使用FTN編譯）和節(jié)點(diǎn)總數(shù)?問(wèn)題算法1算法2算法3啟發(fā)式時(shí)間節(jié)點(diǎn)時(shí)間節(jié)點(diǎn)時(shí)間節(jié)點(diǎn)時(shí)間?0.2490.110.1220.140.0338928.212080.9730.17.2703.3300.770.1*28.1158*0.4*244.04026*0.554.0333611.61944.02270.333.7214860.949826.616510.2*8.175.846280.4139.2*886*0.4*118,600,0001718*0.6?*????時(shí)間上限250秒。承認(rèn)?筆者想感謝SOGESTA,烏爾比諾（意大利）支持?工作。？他們也想感謝兩位匿名審稿人對(duì)他們的SUGgestions已導(dǎo)致了一些改進(jìn)和約翰?比斯利博士進(jìn)行一些計(jì)算測(cè)試。N.克里斯托]新娘，A.MingozziP.托特/車輛路徑的精確算法參考文獻(xiàn)?MLBalinskiRE匡特“，在整數(shù)規(guī)劃交付問(wèn)題”，操作研究12（1964）300。R.貝爾曼，“在一個(gè)路由的問(wèn)題,”應(yīng)用數(shù)??學(xué)季刊（1958年）87。N.赫里斯托菲，圖論，算法的方法（學(xué)術(shù)出版社，倫敦，1975年）。N.赫里斯托菲，“車輛路徑問(wèn)題”，歌劇Franqaise自動(dòng)化，信息等RECHERCHEOP?rationnelle10（1976）55。N.赫里斯托菲，“旅行商問(wèn)題”，N.赫里斯托菲A.Mingozzi，P.托特C.三弟合編，組合優(yōu)化（JohnWiley和Sons，倫敦，1979年）。N.赫里斯托菲，A.Mingozzi和P.托特，“車輛路徑問(wèn)題”，在：A.N.赫里斯托菲Mingozzi，P.Toth和C.三地合編，組合優(yōu)化（JohnWiley和Sons，倫敦，1979）。N.赫里斯托菲A.Mingozzi和P.托特，“國(guó)家空間放寬組合問(wèn)題”，國(guó)子監(jiān)內(nèi)部報(bào)告IC，79，09，1979年7月C.克拉克和JQ懷特，“從一個(gè)中心倉(cāng)庫(kù)，一些車輛調(diào)度交付點(diǎn)“，運(yùn)籌學(xué)12（1964）568。S.埃隆C.沃森-甘迪和N的赫里斯托菲，分銷管理，數(shù)學(xué)建模和實(shí)證分析（格里芬，倫敦，1971年）。TJ蓋斯凱爾，“基地”車輛調(diào)度，運(yùn)營(yíng)研究季刊18（.967）281。?BE吉萊和LR米勒，“一種啟發(fā)式algorqthm的車輛調(diào)度問(wèn)題”，運(yùn)籌學(xué)22（1974）340。BL金，“車輛路徑問(wèn)題”的配方和啟發(fā)式的解決方案，技術(shù)，ORC技術(shù)報(bào)告113，麻省理工學(xué)院（1975年）。BL金，“最近的事態(tài)發(fā)展在車輛路徑”，在二百年數(shù)學(xué)規(guī)劃會(huì)議（1976年11月）。R.海斯“交貨問(wèn)題”，卡內(nèi)基科技管理科學(xué)研究所研究報(bào)告106（1967）。M.舉行R.卡普，“TSP和最小生成樹”運(yùn)籌學(xué)18（1970）1138。M.持有R.卡普，“TSP和最小生成樹II”數(shù)學(xué)規(guī)劃（1971）6-25。D.霍克，JC皮卡德，M.凱拉納，RRVemuganti的的“旅行商問(wèn)題和最短的N-路徑“，馬里蘭大學(xué)（1977年）。;林和BWKernighan的，“一個(gè)有效的啟發(fā)式算法的TSP”，運(yùn)營(yíng)研究21（1973）498。C.米勒，AW塔克和RAZemlin說(shuō)，“整數(shù)規(guī)劃制定的旅行推銷員問(wèn)題“，期刊協(xié)會(huì)[或計(jì)算機(jī)械（1960）。JF皮爾斯，“兩階段的方法來(lái)解決車輛調(diào)度問(wèn)題”，提出在17TIMS倫敦國(guó)際會(huì)議（1970）。FA蒂爾曼和H.科克倫，“解決交付問(wèn)題的啟發(fā)式算法”，期刊工業(yè)工程19（1969）354。??MathematicalProgramming20（1981）255-282.North-HollandPublishingCompanyEXACTALGORITHMSFORTHEVEHICLEROUTINGPROBLEM,BASEDONSPANNINGTREEANDSHORTESTPATHRELAXATIONSN.CHRISTOFIDESImperialCollege,LondonSW72BX,EnglandA.MINGOZZISOGESTA,Urbino,ItalyP.TOTHUniversityofBologna,Bologna,ItalyReceived17November1978Revisedmanuscriptreceived17March1980Weconsidertheproblemofroutingvehiclesstationedatacentralfacility(depot)tosupplycustomerswithknowndemands,insuchawayastominimizethetotaldistancetravelled.Theproblemisreferredtoasthevehicleroutingproblem(VRP)andisageneralizationofthemultipletravellingsalesmanproblemthathasmanypracticalapplications.WepresenttreesearchalgorithmsfortheexactsolutionoftheVRPincorporatinglowerboundscomputedfrom(i)shortestspanningk-degreecentretree(k-DCT),and(ii)q-routes.Thefinalalgorithmsalsoincludeproblemreductionanddominancetests.Computationalresultsarepresentedforanumberofproblemsderivedfromtheliterature.Theresultsshowthattheboundsderivedfromtheq-routesaresuperiortothosefromk-DCTandthatVRPsofuptoabout25customerscanbesolvedexactly.Keywords:VehicleRouting,LagrangeanRelaxation,ShortestSpanningTrees,DynamicProgrammingRelaxation.1.IntroductionWeareconsideringaprobleminwhichasetofgeographicallydispersed"customers"withknownrequirementsmustbeservedwithafleetof"vehicles"stationedatacentralfacilityordepotinsuchawayastominimizesomedistributionobjective.Itisassumedthatallvehicleroutesmuststartandfinishatthedepot.Thevehicleroutingproblem(VRP)isagenericnamegiventoawholeclassofproblemsinvolvingthevisitingof"customers"by"vehicles".TheVRP(alsoknownintheliteratureasthe"vehiclescheduling"[8,9,10],"vehicledispatching"[4,11,20]orsimplyasthe"delivery"problem[1,14,21])appearsveryfrequentlyinpracticalsituationsnotdirectlyre|atedtothephysicaldeliveryofgoods.Forexample,thecollectionfrommail-boxes,thepickupofchildrenby255256N.Christofides,A.MingozziandP.Toth/Exactalgorithmsforvehicleroutingschoolbuses,house-calltoursbyadoctor,preventivemaintenanceinspectiontours,thedeliveryoflaundry,etc.areallVRPsinwhichthe"delivery"operationmaybeacollection,collectionand/ordelivery,orneither,andwhichmaynotevenbeofaphysicalnature.ThebasicVRPconsideredhereisasfollows.AgraphG=(X,A)isdefinedbythesetXofitsverticesandthesetAofitsarcs.LetX'={xi]i=1 N}beusedforthesetofNcustomersandletx0bethedepot.X=X'U{x0}.Acustomerxihasthefollowingrequirements:aquantityq~ofsomeproducttobedeliveredbyavehicle,a"cost"uirequiredbyavehicletounloadthequantityqi,atx~.WeassumethatMidenticalvehicleseachofcapacityQarestationedatthedepotandthatthetotal"cost"(e.g."distance"or"time")ofavehicleroutemustbelessthanorequaltoagivennumberT.Thenumberofvehiclesisassumedtobelargeenoughforafeasiblesolutiontoexist.Wefurtherassumethatthe"cost"oftheleastcostpathfromeveryvertexxitoeveryvertexxiisgivenasc~j.ItisrequiredthatthetotalquantityoneachvehiclerouteislessthanorequaltoQ,andthatthetotal"cost"ofeachroute(computedasthesumofthecostsc~jofthearcs(x~,xj)formingtheroute,plusthesumoftheu~forthosecustomersxiontheroute)islessthanorequaltoT.TheobjectiveintheVRPthatisconsideredhereistodesignfeasibleroutes--oneforeachvehicle--inordertosupplyallofthecustomersandminimizethetotal"cost"ofalltheroutes.Forthepurposeofthispaper,the"cost"c~jmentionedabovecanbetakentobeeithertraveldistancesortraveltimesbetweenthecustomers.TheVRPdefinedaboveisageneralizationofthetravellingsalesmanproblem(TSP).However,althoughforthislatterproblemexactmethodsofsolutionhavebeendevelopedwhichcansolveproblemsofoneortwohundredcustomers[5],fortheVRPnosuchalgorithmsexist.InfactthelargestsizeofgeneralVRPsreportedsolvedintheliteratureinvolveproblemswithtenortwelvecustomers[9]althoughveryspecialtypesofVRPshavebeensolvedforlargersizes[4].InthispaperwedevelopanumberofexactbranchandboundalgorithmsforthegeneralVRPdefinedabove.Thesealgorithmsarebasedonboundsderivedfrom:(i)theshortestspanningtreewithafixeddegreeatonespecifiedvertex,and(ii)minimumq-routes,q=1 Q. Theseareroutes,onwhichthetotalloadisexactlyq,startingfromthedepotpassingthroughasubsetofthecustomersandreturningbacktothedepot.Langrangeanpenaltyproceduresareusedtocomputethesebounds.Wealsoconsiderandcomputationallyevaluatetwodifferentbranchingschemesforthetreesearchandintroducesomedominancetests.Computationalresultsonanumberofproblemsarepresented.N.Christofides,A.MingozziandP.TothlExactalgorithmsforvehicleroutingProblemformulationWegivebelowaformulationoftheVRPasanintegerprogram.Thisformulationisasimplificationoftheonesgivenin[6,12].Let~sk=1ifvehiclekvisitscustomerxiimmediatelyaftervisitingcustomerXi,~ijk-~0otherwise.TheVRPis:minimize,l,i:Oj=Ok=lNMsubjectto~~~:iSk=1,j=1 N,(2)i=0k=l/:0X!~ipk--j~=0~PSk=0'=k:l,...,虬p:0 N,(3)~(qi~!~i,k)<--Q,k:l 虬(4)i=11:oCij~ijk+Eui~ijk-<T,k=1 M, (5)i=0j~oi~j=0NE~0./k:1,k=1 M,(6)j=lMy~-yj+N~'~:0k-<N-l,i#j=l....N(7)k=l~i~kE{0,1}foralli,j,k,(8)y~arbitrary.Expression(2)statesthatacustomermustbevisitedexactlyonce.Expression(3)statesthatifavehiclevisitsacustomer,itmustalsodepartfromit.Expressions(4)and(5)arethecapacityand"cost"limitationsoneachroute.Expression(6)statesthatavehiclemustbeusedexactlyonce.Expression(7)isthesubtour-eliminationconditionderivedforthetravellingsalesmanproblembyMiller,TuckerandZemlin[19],andwhichalsoforceseachroutetopassthroughthedepot;(8)aretheintegralitycon