價格選擇多配送中心車輛調(diào)度問題

1、帶有價格的選擇性多配送中心車輛調(diào)度問題摘要：耐用品行業(yè)的企業(yè)偶爾推出以舊換新或回購活動，通過客戶誘發(fā)更換購買。由于這一結(jié)果，在這期間使用過的產(chǎn)品快速的在經(jīng)銷商處積累。我們研究這樣的公司，其目的是收集其經(jīng)銷商核心的逆向物流問題。在核被檢測到的地方建立了搜集中心，公司的目的是優(yōu)化車輛離開搜集中心的路徑，到達每一個經(jīng)銷商，然后回到同一個中心。我們假設(shè)經(jīng)銷商對于它們的核心不是免費的，而是有一個保留價格。因此，如果由公司宣布的收購價超過了經(jīng)銷商的保留價格，那么積累在經(jīng)銷商的內(nèi)核才能收購回來。但是，公司沒有義務(wù)來訪問所有的經(jīng)銷商;車輛被分派到一個經(jīng)銷商只有當(dāng)它是有利可圖的才這樣做。我們專注的問題成為經(jīng)典的

2、多配送中心車輛調(diào)度問題（ MDVRP ），其中每訪問一個經(jīng)銷商與毛利及收購付出的代價相關(guān)。為解決這個問題我們制定兩個混合整數(shù)線性規(guī)劃（ MILP ）模型，我們把它稱為選擇性MDVRP定價。由于該問題是NP難題，我們提出了一種禁忌搜索啟發(fā)式方法來解決中型和大型的實例。與國家的最先進的商業(yè)求解器解決混合整數(shù)規(guī)劃模型的比較，啟發(fā)式的方法更好一些。關(guān)鍵詞：逆向物流、有選擇的多配送中心車輛路徑、收集、定價、啟發(fā)式搜索1. 引言環(huán)保意識的制造業(yè)，廢物減量和產(chǎn)品回收已經(jīng)作為在過去的二十年中環(huán)境可持續(xù)性的替代手段出現(xiàn)。這促使研究人員和從業(yè)者把重點放在其包括正向供應(yīng)鏈和逆向供應(yīng)鏈的閉環(huán)供應(yīng)鏈中。逆向供應(yīng)鏈管理包

3、括了收集，檢驗，分類被消費者使用過的產(chǎn)品并作適當(dāng)?shù)幕謴?fù)。有效地處理這組活動的一個方面是解決網(wǎng)絡(luò)設(shè)計問題，以確定要被打開的設(shè)施的數(shù)量和位置，并發(fā)現(xiàn)這些設(shè)施和需求節(jié)點之間的產(chǎn)品的流動。多數(shù)網(wǎng)絡(luò)設(shè)計模型采用線性或非線性混合整數(shù)規(guī)劃的方式，并采用商業(yè)求解器或啟發(fā)式方法求解。在這種類型的模型中，位置決定只用于設(shè)施的收集，檢查和再制造業(yè)的運作。也有文章專注于以協(xié)調(diào)的方式處理正向和反向的信道分配問題。因此，設(shè)施自己操作的產(chǎn)品，以滿足使用的產(chǎn)品，消費者從收集到的需求和反向流量轉(zhuǎn)發(fā)流量作出決定。最近，Akçal 等人（2009 年） 和Aras 等人（2010 年）對這兩種類型的文件做了全面的闡述。所

4、涉及的產(chǎn)品回收公司的關(guān)鍵問題之一是使用的產(chǎn)品收購所述的指（2003）。這的確是產(chǎn)物回收的第一活動，并觸發(fā)恢復(fù)系統(tǒng)的其它活動?？梢酝ㄟ^使用回購運動和為產(chǎn)品持有人提供它們向金融獎勵增加的數(shù)量和質(zhì)量的回報。接受廢物流中的所有最終用途產(chǎn)品不是大多數(shù)公司的可行戰(zhàn)略，因為這些產(chǎn)品的高百分比將導(dǎo)致質(zhì)量較差，并且因此將無法恢復(fù)。因此,采用積極的方法和實現(xiàn)產(chǎn)品收購戰(zhàn)略,提供相應(yīng)的回購價格是公司從事產(chǎn)品復(fù)蘇的關(guān)鍵。有幾篇論文，其中明確地納入使用的產(chǎn)品采集。第一項關(guān)于在激勵為基礎(chǔ)的集合建模也考慮到了網(wǎng)絡(luò)設(shè)計的操作問題的研究是Boyac等人做出的（2008年）。作者開發(fā)的連續(xù)選址模型用于收集網(wǎng)絡(luò)通過引入一個下車的戰(zhàn)略

5、。該產(chǎn)品的回報率取決于到位，網(wǎng)絡(luò)的可訪問性，以及對所提供的財政補貼的策略。返回的最終用戶決定是一個實用程序基于的選擇模型捕獲的。一個分析框架，提出以確定每個設(shè)施，并提供給最終用戶的最優(yōu)財政獎勵的收集區(qū)域的最佳尺寸，使收集的利潤是根據(jù)落客和卡車收集策略最大化。Aras and Aksen (2008) 分析了為激勵和距離相關(guān)的回報的一個無容量限制的收集中心選址問題（ CCLP ）。該產(chǎn)品持有人決定是否參與回購活動由前往最近的收集中心（ CC）和依賴于所用產(chǎn)品的質(zhì)量狀態(tài)下的財政獎勵的距離影響。兩種混合整數(shù)非線性規(guī)劃模型，擬為CCLP的固定費用和p-中位。同一 CCLP 的 p-中位版本被認(rèn)為是 A

6、ksen等人（2009）研究的，根據(jù)拾取集合政策在其中車輛偏離收集中心、訪問客戶區(qū)，和把收集使用產(chǎn)品帶回來。其目的是確定收集中心的位置，金融激勵水平以及負(fù)載組合車輛的數(shù)量。這兩篇論文，作者利用基于禁忌搜索解決方案程序。最近Aksen等人（ 2009）提出了一個雙層配方的框架，描述了政府（領(lǐng)導(dǎo)者），從事收集和回收業(yè)務(wù)公司之間（跟隨者）的補貼協(xié)議。該文研究兩種可供選擇的政策。在扶持政策方面，政府用金錢獎勵（補貼）的方式促使該公司實現(xiàn)一個目標(biāo)收集率。在立法政策方面，另一方面，政府強制要求公司的部分收集目標(biāo)利率。作為回報，公司保證閾值經(jīng)濟效益。在這兩種情況下，政府的目標(biāo)是盡量減少每收集到的項目應(yīng)支付的

7、補貼，而該公司的目標(biāo)是利潤最大化。它們表明，在相同的盈利能力和收集的水平，在立法政策下，政府支付較低的補貼。在本文中，我們著重研究在收集網(wǎng)絡(luò)中的車輛調(diào)度問題。一個收集和逆向物流的車輛路徑問題的極好來源是 Beullens 等人研究的（2004 年）。他們詳細描述了各種版本的經(jīng)典車輛路徑問題（ VRP ）的特性。我們認(rèn)為所面臨的涉及二手產(chǎn)品收購的公司出現(xiàn)的情況如下。該公司已經(jīng)開設(shè)了多家合作中心與無限的存儲容量。它采用回升的政策，收集使用過的產(chǎn)品，被稱為內(nèi)核，在經(jīng)銷商處積累作為以舊換新宣傳活動的結(jié)果。在這些運動中，消費者用他們自己的舊產(chǎn)品購買新產(chǎn)品時會獲得優(yōu)惠的價格。這個折扣也被稱為貿(mào)易中的回扣和

8、經(jīng)銷商通常通過對新客戶提供以舊換新退稅，應(yīng)用價格歧視政策加快他們的購買決策（ Ray等人，2005 ）。由于誘導(dǎo)以舊換新回扣有通過再制造業(yè)務(wù)產(chǎn)生的收入或成本節(jié)約的潛力用于產(chǎn)品的逆向流動，該公司希望通過軸承全部收集相關(guān)的成本從經(jīng)銷商處收集它們，也就是說，運營成本車輛和運輸核從經(jīng)銷商到社區(qū)中心。由該公司提供的收購價使得經(jīng)銷商愿意讓舊產(chǎn)品回流。經(jīng)銷商有不同的保留價格，并且他們同意只有當(dāng)企業(yè)的收購價超過了他們的保留價格才出售他們的核心。對核心較高的收購價格降低了單位收益，但在同一時間增加了交易商愿意出售的核心的意愿。需要注意的是由該公司提供的收購價對所有經(jīng)銷商是相同的，因為定價歧視對于經(jīng)銷商而言被認(rèn)為

9、是一個不公正的態(tài)度。此外，交易商可以很容易地在彼此之間分享企業(yè)的定價信息。該集合是通過為每個車輛分配給CC的一個相同容量限制車輛組成的車隊。關(guān)于可被分配給一個CC車輛的數(shù)目沒有限制。車輛必須背離，來訪多家經(jīng)銷商后回到同一CC。該公司的目標(biāo)是使集合操作盡可能獲利。，由于從芯收集得到的零件和部件的再制造，節(jié)約的生產(chǎn)成本是公司收入的一個來源。公司的成本是核心的收購和經(jīng)營車輛產(chǎn)生的成本。公司不得不決定分配給每個顧客的車輛數(shù)和分配給經(jīng)銷商的車輛的任務(wù)，車輛的路線，以及采購每個核心所花費的價格。車輛路線不必包含所有的經(jīng)銷商。如果從一個經(jīng)銷商處收集核心不賺錢，公司不會往該供銷商發(fā)送任何車輛直到當(dāng)所提供的收購

10、價大于或等于他的保留價格時他準(zhǔn)備賣掉他的核心。我們將此問題作為''選擇性多配送中心的車輛路徑問題定價“ ，并記為SMDVRPP 。最相似的問題，在研究中我們是通過超等人引入了團隊定向問題（ TOP）（ 1996），多個旅游最大集合問題 （Butt and Cavalier, 1994年） 是引進異構(gòu)車輛頂部的變體，和Gueguen （ 1999）提出的有時間窗的選擇性的VRP（ SVRPTW ）提出的集成了額外的容量和時間窗約束。這將在下一節(jié)中提到，這兩個問題都屬于更廣泛的帶利潤（ VRPP ）的車輛路徑問題。然而，只存在一個倉庫服務(wù)選定的客戶。盡我們所知，VRPP的多配送中心

11、問題尚未在研究之內(nèi)。事實上，古典MDVRP （不含利潤）推廣了VRP使用超過1倉庫或中心節(jié)點。各配送中心經(jīng)營著自己的車輛提供服務(wù)的一組客戶。MDVRP的目標(biāo)是為每個配送中心設(shè)計的車輛路線，使訪問所有的客戶的車隊行駛的總距離最小。各配送中心的車輛不能共享，每一輛車必須回到各自的出發(fā)點。我們本文中的SMDVRPP涉及到一組當(dāng)作配送中心，一組作為客戶節(jié)點經(jīng)銷商的社區(qū)中心，以及固定經(jīng)營成本的不限數(shù)量的車輛。有與每個客戶拜訪（拜訪經(jīng)銷商在我們的情況下）相關(guān)的利潤。因此，我們的論文的主要貢獻是引進SMDVRPP的，可以被看作是一個多配送中心的VRPP問題。此外，定價也考慮在內(nèi)，這樣的收購價至少不亞于走訪經(jīng)

12、銷商的預(yù)訂價能夠帶回來經(jīng)銷商的舊產(chǎn)品。盡我們所知，以前定價問題不在VRPP的考慮范圍內(nèi)。對于這個問題，我們提出了兩種混合整數(shù)非線性規(guī)劃（MINLP ）的方法，這是線性化，以產(chǎn)生它們的混合整數(shù)線性規(guī)劃（ MILP ）版本。如果從核心單位節(jié)約成本足夠高，如果經(jīng)銷商的保留價格都等于零，這個問題顯然降低到經(jīng)典多車輛途程問題（ MDVRP ），它被證明是NP問題（ Lenstra和Rinnooy kan,1981）。這意味著SMDVRPP也是NP-hard問題。大量實例證明，通過求解MILP與商業(yè)求解器不能有效地解決SMDVRPP。因此，我們采用了基于禁忌搜索原理的啟發(fā)式求解方法。本文的其余部分安排如下

13、。選擇性車輛路徑問題的簡要文獻回顧在第2節(jié)規(guī)定。問題定義和兩個數(shù)學(xué)編程在第3節(jié)給出。所提出的啟發(fā)式求解過程的詳細說明第4節(jié)。第5節(jié)報告其結(jié)果和運算測試。最后，第6節(jié)提供了一些結(jié)論。2. 文獻綜述在本文中，我們專注于一個集合問題，叫SMDVRPP ，這是面對參與產(chǎn)品回收的公司提出的。一些收集中心（CCS ）已經(jīng)已經(jīng)打開，包括所使用的產(chǎn)品檢驗和分離，以確定他們的下一個目的地，如再制造工廠，回收中心，或處置場。該公司主要從事用容量限制車輛從經(jīng)銷商到收集中心的核心運輸。除了額外的要求，即要為每個核心支付收購的費用， SMDVRPP屬于它不需要訪問所有客戶（經(jīng)銷商在我們的問題）的MDVRP類。因此，我們

14、的文獻綜述，主要包括對VRP符合利潤的研究，這是最適合我們的工作。關(guān)于參觀所有客戶的路由問題的論文很多，而與利潤相關(guān)的路由問題的論文卻很少。在后者中，客戶送達和車輛路線被確定，以便優(yōu)化給定目標(biāo)函數(shù)。雖然來訪的所有客戶提高了收集到的總收入，訪問某些客戶（邊際收益減去邊際成本）的邊際利潤可能低于零取決于手頭的路由規(guī)劃。在這種情況下，總利潤可以改善，如果這些客戶被排除在外。Feillet等人（ 2005）闡述帶利潤的旅行商問題（TSPP)。TSPP就是沒有必要訪問所有客戶的一般的旅行商問題（TSP ）。關(guān)聯(lián)的每個客戶那里是已知的先驗利潤。TSPP 可以作為離散求解雙準(zhǔn)則優(yōu)化問題，其中的兩個目標(biāo)是最大

15、化利潤和盡量降低旅游成本。另外，也可以以限定的目標(biāo)的目標(biāo)函數(shù)和其他作為約束之一。在一個版本中，這被稱為在文獻中的定向問題（OP），有選擇性的TSP（ STSP ），或最大集合問題（MCP），其目的是所收集的利潤的最大化，使得總行駛成本（距離）不超過上限。命名為獎品收集TSP （ PCTSP ）另一個版本是關(guān)于確定巡演的最低總行駛成本，其中收集損益獎金大于下限。存在TSPP的第三個版本叫賺錢之旅問題（ PTP） ，其目標(biāo)是最大化的收集總利潤和總行駛距離的成本之間的差額。Feillet等人（ 2005）提供現(xiàn)有TSPP文學(xué)的一個很好的調(diào)查。他們的調(diào)查列出了各種建模方法，精確啟發(fā)式求解方法。TSPP

16、的多個車輛的擴展是VRPP。多車版的OP ，這里的車輛被假定為無容量限制，而且對每一個參觀時間限制，就是所謂的團隊定向問題（ TOP）。Chao等人對TOP問題做了較早的研究。作者提出了一個五步啟發(fā)式類似于確定性退火來解決這個問題。Butt和Cavalier (1994)從高中招收足球運動員的多個旅游最大的收集問題（ MTMCP ）來定義TOP問題的。他們提出了一個貪婪的旅游建設(shè)啟發(fā)式算法。Butt和Ryan (1999)在價格分支的基礎(chǔ)上為MTMCP問題制定了一個確切的算法。Tang和Miller-Hooks (2005)用禁忌搜索啟發(fā)式嵌入自適應(yīng)存儲過程解決了TOP問題。ARCHETTI等

17、人（ 2007）提出了一個廣義的兩個變種的禁忌搜索算法和變鄰域搜索算法。Boussier等人（2007年）用新分支策略和幾個加速技術(shù)制定了另一個價格分支的算法。Ke等人（ 2008）用蟻群優(yōu)化（ ACO ）的方式闡述了TOP問題。ARCHETTI等在（2007）提出了兩個可變算法，一個是廣義的禁忌搜索算法和一個是變鄰域搜索算法。Boussier等（2007年）制定的是另一個基于新分支的戰(zhàn)略和加速技術(shù)的分支和價格算法?？碌热耍?008）在top中闡述了蟻群優(yōu)化（ACO）的方式。最近的兩部作品之一是在top由ARCHETTI等人完成的，作者研究的TOP的容量版本和提出確切的和啟發(fā)式的程序，他們還研

18、究了PTP的延伸，其中一隊可用容量限制的車輛。其它工作是由于Vansteenwegen等（2009年）完成。作者提出的一種算法結(jié)合了一個引導(dǎo)本地搜索方法但不同于本地搜索的啟發(fā)式和多樣化的過程，這有助于開拓更廣泛的解空間。3.模型公式在我們提出基于SMDVRPP的兩個MILP模型之前 ，我們列出了描述問題的中所做的假設(shè)，在節(jié)點之間的行進距離d ij i和j是已知的，其中節(jié)點是CC和經(jīng)銷商的位置。核心的數(shù)量由經(jīng)銷商i所擁有，而且這個企業(yè)熟知它的預(yù)定價格。當(dāng)統(tǒng)一收購價格W采用一個大于或等于pi的單元核心來提供給經(jīng)銷商時，那么他會擁有經(jīng)銷商銷售的所有核心。每個所收集核心產(chǎn)生的收益R，代表了使用產(chǎn)品的剩

19、余價值，這種產(chǎn)品可以通過再制造或回收而獲得。該公司可能還沒有決定從經(jīng)銷商i甚至wpi中收集核心，也就是說，即使該經(jīng)銷商愿意給內(nèi)核。是這種情況時，經(jīng)銷商獲得的總收益并不能夠賠償拜訪他的額外成本。用同類有著容量Q的車隊來進行共同的收集，每單位的距離對操作車輛進行收費，有一個可變成本C2和一個固定的成本C1。每個經(jīng)銷商可以通過最多一輛車被訪問，也就是說拆分收集是不允許的，此外，在車輛必須收集它訪問經(jīng)銷商的所有核心。對于最后一個必要假設(shè)的條件就是 q P 最大值ai.。如果q < 最大值ai，這些有（AI> Q）核心數(shù)量的經(jīng)銷商不會訪問，哪怕是有利可圖。每輛車必須啟動并在到其指定的CC完成

20、其運行。它不能在另一個CC卸載和重新調(diào)度。每個CC可以運行無限數(shù)量的車輛。該公司的目標(biāo)是從收集的核心中獲得的最大化利潤總額中減去回購成本，經(jīng)營成本和差旅費所組成的車輛的集合總成本。對于SMDVRPP我們建立第一個模型稱為SMDVRPP-1，其利用米勒 - 塔克 - 澤林（MTZ）的子路消除約束（卡拉等人，2004），以及在這些約束中使用的ui變量緊界限,第二模型SMDVRPP-2是基于連續(xù)流動的變量和Gavish - 格雷夫斯單個商品流約束（Gavish與Graves，1978）。在這兩種配方，IC表示一組CC位置，ID表示集合經(jīng)銷商位置，在¼ICID中，由于參數(shù)是常見的兩種配方，我

21、們總結(jié)它們的定義表1中。3.1.SMDVRPP-1在此模型中的變量定義如下：請注意， Ui為只需要編寫解除米勒 - 塔克 - 澤林（ MTZ ）子路消除制約。根據(jù)這些變量和參數(shù)提出如下數(shù)學(xué)規(guī)劃問題：表1.在模型中使用的參數(shù)（1）（19） Subject to ; ;；目標(biāo)函數(shù) （1） 是被計算作為總收入減去總采購成本和營運車輛的成本生成的最大化的利潤。約束 (2) 及 (3) 確保經(jīng)銷商可以被訪問至少一次。約束 (4) 保證進入和離開一個經(jīng)銷商位置或收集中心車輛的數(shù)量（零個或一個）必須是相同的。約束 (5)可確保在兩個收集中心間沒有車輛約束（ 6 ）中指定的用于汽車的總?cè)萘勘仨氉阋赃\送收集芯。

22、約束（7）滿足該經(jīng)銷商被分配到最多一個收集中心。如該交易商分配給收集中心約束條件（ 8 ）和（ 9 ）確保經(jīng)銷商必須由車輛被訪問。約束（10）和（11）一起意味著，如果兩個經(jīng)銷商由車輛連續(xù)訪問的，那么這些經(jīng)銷商必須被分配到相同的收集中心。約束（12）確保所提供的購買價格為每個核心必須大于或等于所訪問的商的最大的保留價格?；叵胍幌?，公司的政策是不使經(jīng)銷商之間的存在價格歧視。約束（13）是解除MTZ子路消除約束，這連同Ui變量的下界和上界一起使用。約束（ 14 ）為Ui確定了一個下界簡單的說就是車輛從經(jīng)銷商i離開之后的負(fù)荷必須至少等于從經(jīng)銷商i加上訪問經(jīng)銷商i之前從經(jīng)銷商j收集的數(shù)量之和。如果車輛

23、來自收集中心和經(jīng)銷商i之間，然后第二個約束在此消失。約束（15） - （17）都在規(guī)定Ui的上界。約束（ 15 ）表示，如果車輛行駛經(jīng)銷商從i到經(jīng)銷商j ，那么車輛的剩余容量（q-Ui）從經(jīng)銷商i離開后必須足以收集經(jīng)銷商j，即q-Uiaj。如果車輛在經(jīng)銷商i后到達收集中心，那么Ui就有上限約束，即Uiq。約束（ 16 ）保證，如果經(jīng)銷商i在收集中心之后被訪問，那么，離開經(jīng)銷商i之后的載重量Ui不能超過ai。如果經(jīng)銷商i不是第一個被訪問的經(jīng)銷商，那么可獲得上界。約束（ 17 ）在性質(zhì)上（ 15 ）相似，但它們納入Desrochers 和Laporte (1991)提出的升降系數(shù)（q-maxjaj

24、-ai）。因為目標(biāo)函數(shù)中的雙線性YikW的問題，所以該公式是一個MINLP或特定的混合整數(shù)雙線性模型。雙線性既不凹陷，也不凸，因此涉及他們的問題時商業(yè)解算器不能保證全局最優(yōu)。雙線性YikW可以如下進行線性化。首先，我們觀察到，Yik 0,1和W0 ， maxjD Pj。接下來，我們定義一個輔助變量Vik= YikW并引入以下幾組約束：;用Vik來替換目標(biāo)函數(shù)（1）中的YikW并添加了（20）（21）約束條件使得MILP與目標(biāo)函數(shù)等效。；需要注意的是的Vik最小和最大可能值分別為零和maxjD Pj。Yik=0，意味著Vik= 0，因為Yik=VikW。這確保了約束條件（ 21 ），因為Yik=

25、 0 使這種約束的右側(cè)W-maxjD Pj0 ，這意味著約束（ 21 ）是多余的。因此，由約束（20）和目標(biāo)函數(shù)（22），可得Vik= 0。當(dāng)Yik=1時，約束（21）變成VikW。由于優(yōu)化的取值是最大化，Vik=W是一個最佳值。這是由Vik的定義獲得的，即Vik= YikW當(dāng)Yik=1。應(yīng)用線性化過程是由Al-Khayyal和Falk （ 1983）證明的，用來為在給定的矩形區(qū)域提供下估計最緊密的凸的雙線性函數(shù)。因此，該MILP問題可以通過國家的最先進的商業(yè)MILP求解器如CPLEX解決。3.2.SMDVRPP-2另一種MILP方法可以通過定義連續(xù)流變量FIJ那些以書面Gavish - 格雷

26、夫斯單一商品流動的限制（ Gavish與Graves ， 1978）用于解決我們的問題。這些流動變量代表由經(jīng)銷商i運到經(jīng)銷商j的量。保持其他變量和參數(shù)是相同的，新的SMDVRPP -2的線性化給出如下：；限制條件（2）（3）（4）（5）（6）（7）（8）（9）（10）（11）（12）（21）；約束條件（ 24）是對每個經(jīng)銷商iD 寫入的流量平衡約束。約束（ 25 ）保證，如果車輛從經(jīng)銷商或收集中心i到另一個位置j處，從i到j(luò)的運輸量Fij不能大于（q-aj）。換句話說，離開i處后的裝載能力必須能夠滿足j處的裝載能力。當(dāng)j為收集中心時，對于jC由于aj=0,這些約束簡化為Fijq。約束（26）簡

27、單地說，i和j之間的車輛負(fù)載應(yīng)至少等于從i中收集的核心數(shù)量。當(dāng)i時收集中心時，就得到一個非負(fù)性約束（Fij0）。約束集（ 24 ）-（ 26 ）消除了子集就像在SMDVRPP- 1中增加MTZ約束一樣。4. 解決方法由于SMDVRPP是和MDVRP一樣困難的NP-hard問題，非常難以用商業(yè)混合整數(shù)線性規(guī)劃求解器來獲得合理的解決方案。因此，啟發(fā)式算法的發(fā)展是有益的。在MDVRP的啟發(fā)式算法中，禁忌搜索（TS）已經(jīng)被（Renaud 等人，1996 ；Cordeau等人，1997）證明是非常有效的。通過這一事實的啟發(fā)，基于TS原則我們也設(shè)計一個啟發(fā)式程序。禁忌搜索算法是通過在一個解決方案到另一個解

28、決方案之間的迭代進行解空間的探索。當(dāng)st+1不比st優(yōu)化時禁忌機制到位，以防止程序在解之間循環(huán)。一個防止循環(huán)的簡單的方法是回到以前遇到過解決方案，但這樣做禁止的過程通常需要過多的記錄。相反，過去的解決方案或移動過去的某些屬性被認(rèn)為是禁止的，這些解決方案或移動擁有這些屬性不可能考慮到以后的k次迭代。這種機制通常把短期記憶的數(shù)目k稱為禁忌的持續(xù)時間或禁忌列表的大小。其他功能，如多樣化和集約化也往往被利用。多樣化的目的是為了確保在搜索過程中解空間不會被限制在有限部分。它可以跟蹤過去的解決方案和經(jīng)常進行移動的懲罰。這通常被稱為長期記憶。在最好的解決方案周圍進行貪婪局部搜索。我們提出了一個富人區(qū)的TS

29、（ TS- RN）啟發(fā)式的SMDVRPP模型。TS- RN是加上戰(zhàn)略波動，也就是說，我們也承認(rèn)這些解決方案，其中一個或多個旅行團違反車輛容量約束。我們稱這些為容量不可行的解決方案。在這種解決方案的目標(biāo)價值計算，我們乘的總的產(chǎn)能過剩（總結(jié)超出車輛的通行能力而進行的內(nèi)核數(shù)量在所有不可行之旅）與動態(tài)變化的處罰，并添加所產(chǎn)生的不可行性成本總的旅行距離。在每次迭代中，在TS -RN算法探討了一些當(dāng)前解決方案的周邊解決方案，包括那些不可行的，并選擇其中最好的為最高目標(biāo)，價值計算作為新的當(dāng)前解。該算法的關(guān)鍵步驟如下：初始解生成方法鄰里結(jié)構(gòu)和相關(guān)禁忌條件新的當(dāng)前解決方案的選擇分配并更新懲罰值的戰(zhàn)略性振蕩的過程

30、終止條件4.1.產(chǎn)生一個初始解最初的解決方案是把所有經(jīng)銷商都放入單個旅游經(jīng)銷商序列中按其指數(shù)的排序位置形成的。也就是說，在這次巡演中，第一個經(jīng)銷商首先到來，第二個經(jīng)銷商第二個到來。這次巡演連接到具有最小索引的收集中心。請注意此最初的解決方案是幾乎可以肯定是不可行的 ；因此，其客觀的價值將為產(chǎn)能過剩承擔(dān)各個懲罰成本。4.2.鄰域結(jié)構(gòu)及禁忌條件附近的結(jié)構(gòu)或所謂的TS -RN的移動而影響迭代過程，被指定為當(dāng)前解決方案的軌跡。在我們的執(zhí)行中存在兩種類型：路徑的移動和經(jīng)銷商選擇的移動。有7種具體的移動方式是1-0移動， 1-1交換， 2-2交換， 2 - 選件，鏈互換， 1 - 分裂，以及跨巡演交流。經(jīng)

31、銷商選擇的動作是加1，加2，減1，減2。下面我們講解以及一個可視化表示的路由移動，其中經(jīng)銷商和收集中心分別由圓形和方形表示。1-0移動：給定兩個經(jīng)銷商，第一個是從當(dāng)前位置移除，并在第二個之后（圖1和2 ）被插入1-1交換：給定兩個經(jīng)銷商，交換他們的位置（圖3和4 ）2-2交換：給定兩個經(jīng)銷商，第一個和它的后繼者換用第二個（圖5和圖6 ） 。2 - 選擇：由于在相同的巡演二級經(jīng)銷商，這兩個圓弧與他們的繼任連接它們被刪除后，經(jīng)銷商連接，其繼任人接，終于第一次經(jīng)銷商的繼任者，第二經(jīng)銷商之間的鏈被逆轉(zhuǎn)（圖7）鏈交換：由于在不同的旅游二級經(jīng)銷商，從每個經(jīng)銷商各自的鏈上的行的最后，交易商互換（圖8）。1

32、- 分裂：給定一個交易商在現(xiàn)有的巡演，從收集中心直至包括經(jīng)銷商保留鏈條，而巡演的其余部分作為一個新的巡演。新的路線可以啟動在同一收集中心（圖9），或者它可以被分配到另一個收集中心（圖10）。1 - 跨線總是會增加線上的總數(shù)目。請注意，根據(jù)三角不等式，1 - 分裂不能降低總行進距離，如果新的游被分配到相同的收集中心作為現(xiàn)有游，它可能減輕由于產(chǎn)能過剩導(dǎo)致的不可行性。圖1. 1-0移動圖2.1-0不同旅行線上移動圖3.1-1相同線上交換圖4.1-1不同線上交換圖5.2-2相同線上交換圖 6.2-2不同線上交換圖7.2-O相同線上選擇圖8.2-O不同線上鏈交換混合交換（ITE）：該鄰域結(jié)構(gòu)有三種情況案

33、例一.A鏈的經(jīng)銷商是從一個給定的線中提取并插入一個新的線上擁有相同的或其他的收集中心如圖11 。像1-分裂，在ITE移動這種情況下，增加了線上的參與數(shù)量。案列二.A鏈的經(jīng)銷商在給定的線上從當(dāng)前位置移動到屬于相同或不同的收集中心做另一次游覽。這種情況示于圖12 。案例三.任意大小分屬兩個不同鏈上的經(jīng)銷商交換。如圖13圖9.1-相同收集中心分裂圖10.1-不同收集中心分裂圖11.ITE案例一圖12.ITE案例二圖13.ITE案例三添加- 1 ：對不包括在線上的經(jīng)銷商所有可能的插入位置進行檢查，經(jīng)銷商插在最佳位置。最佳位置，要么是一個有希望使當(dāng)前解決方案的目標(biāo)價值最高增幅（利潤總額） ，或者如果沒有

34、這樣的位置存在，那么它使其中一個下降的客觀價值最少。此舉實際上相當(dāng)于旅行商問題的最廉價的插入規(guī)則。添加- 2 ：對不包括在線上的經(jīng)銷商所有可能的插入位置進行檢查并給予經(jīng)銷商都插在繼承對方的最佳位置上，它被定義為中的添加- 1移動的解釋。此舉相當(dāng)于應(yīng)用于對經(jīng)銷商最便宜的插入規(guī)則。刪除1 ：線上的經(jīng)銷商從線上被刪除，它的前和后繼續(xù)連接。刪除2 ：將線上的給定經(jīng)銷商和他的繼任者是從線上刪除，他的前身和繼任者后面的繼續(xù)連接。TS- RN算法利用禁忌的條件來執(zhí)行解空間不同區(qū)域的探索。為此，每當(dāng)解按一定的鄰域結(jié)構(gòu)更新時禁忌狀態(tài)與該結(jié)構(gòu)相關(guān)聯(lián)。嚴(yán)禁覆蓋禁忌條件，除非在最好的可行的目標(biāo)函數(shù)值Zbest立即改善

35、得以實現(xiàn)。禁忌狀態(tài)被解除的禁忌持續(xù)時間j的結(jié)束。在我們的算法中，我們使用禁忌持續(xù)時間在區(qū)間 7,24 獨立問題規(guī)模的隨機決定。與所有11個鄰域結(jié)構(gòu)相關(guān)的禁忌條件列于表2。表2.采用鄰域結(jié)構(gòu)相關(guān)的禁忌條件列表 雖然我們提出了大量的不同的移動，可能的情況是，并非所有的移動都能產(chǎn)生高品質(zhì)的解決方案。只有其中的一些可以實現(xiàn)，特別是表2中的，如1-0移動， 1-1交換和2-2交換。出于這個原因，我們產(chǎn)生了一些舉措組合，并在本文探討測試情況下它們的表現(xiàn)。4.3.選擇一個近似的方案作為下一步的初始方案在每次的TS-RN迭代時，當(dāng)我們依靠使用的調(diào)度方案我們搜索當(dāng)前方案的領(lǐng)域N ðSt Þ，

36、以設(shè)法找到下一個調(diào)度方案St+1時，我們充分地探索領(lǐng)域結(jié)構(gòu)，除了Inter-tour Exchange。換言之，領(lǐng)域N ðSt Þ的候選子集N ðSt Þ被充分地探索，領(lǐng)域N ðSt Þ在五條路徑調(diào)度中是等價的。由于計算的難度，對案例b、c中的國際商貿(mào)交易中的調(diào)度問題的領(lǐng)域只進行了部分探索。另一方面，案例a的領(lǐng)域全部被探索。事實上，當(dāng)其他的領(lǐng)域結(jié)構(gòu)不能提供一個比當(dāng)前方案St更好的Rt的時候，ITE才會被執(zhí)行，兩者優(yōu)劣的比較基礎(chǔ)是包含不可行懲罰函數(shù)的目標(biāo)函數(shù)值。為了更好地理解在關(guān)于ITE的上兩個案例中的部分搜索過程，我們首先給出下面3個

37、定義：（1）節(jié)點與目的地的距離：節(jié)點N1和目的地T的距離表示為N1 R T,是節(jié)點N1與與之相近并包含在節(jié)點T中的節(jié)點N2之間的距離。我們用Dist(N1, T).表示該距離。（2）到節(jié)點最近的距離：到節(jié)點N1的最近距離是不包含N1的其他目的地到N1距離中最小的距離。我們用N1 R TÃ來表示該距離。（3）最近的目的地組：在T中與各單個節(jié)點距離最近的目的地組，我們用T（T）來表示這樣的目的地組。例如，讓目的地T只包含N1，N2，N3三個節(jié)點，讓最近的一個N1為T,另外兩個N2,N3記為T,然后，T(T)將成為T ,T ”.注意，在T(T)中的T并不意味著也在T(T)中。有了上述三個定

38、義，使解釋關(guān)于ITE的兩個案例中的局部搜索過程有了可能。從選擇的鏈中給定目的地T，被檢測的這些目的地只能是最近目的地組T中的對象，被稱為T ðTÞ。也就是說，對于目的地T 2 St來說，足以決定和檢查目的地組T ðTÞ中的路徑。當(dāng)Inter-tour Exchange中的案例b、c的領(lǐng)域調(diào)度在當(dāng)前方案中被詳細的探索時，就沒有必要考慮T ðTÞ中的其他路徑了。 此外，對于T1，T2來說，假如T2 在 T ðT 1 Þ 中， T1在 T ðT 2 Þ中，然后，在案例C中，當(dāng)ITE的另一個目的地領(lǐng)域被

39、探索期間，不論何時，其中一個目的地被考慮時，為了節(jié)省計算時間，沒必要核對T1。 最后需要說明的應(yīng)作出有關(guān)TS -RN算法的多樣化規(guī)則。當(dāng)我們在探索候選領(lǐng)域的最優(yōu)方案時，我們不但記錄了鄰域中最好的方案Rbest，同時也記錄了最壞的結(jié)果Rworst，用最低的利潤減去不可行的懲罰成本。讓Rworst表示鄰域中最壞的方案。現(xiàn)在，如果Rbest是無效的，意味著對于現(xiàn)方案St來說，它的利潤正好和不可行懲罰成本相等，進而下一現(xiàn)行方案St+1是最差方案。然而，如果Rbest并非是無效的，St+1就會轉(zhuǎn)向最優(yōu)。從St到Rworst而不是Rbest的跳躍，在一定意義上，是由分散算法的搜索造成的。通過這個多樣化的方

40、案，我們可能打破關(guān)于在多個局部最優(yōu)解都有相同的目標(biāo)值的循環(huán)。4.4.為了戰(zhàn)略上的調(diào)整來更新懲罰函數(shù)值正如前面提過的，在每次迭代中，TS -RN算法探索了一系列的方案，根據(jù)車輛容量限制的因素，這些方案有的可行，有的不可行。選擇懲罰不可行方案的懲罰參數(shù)值的最主要的基本原理是為了確?？尚蟹桨负筒豢尚蟹桨付季哂邢嗨频目赡苄猿蔀猷徲蛩阉髦械淖顑?yōu)方案，然后成為下一階段當(dāng)前方案的可行方案。這種方法增加了對解空間探索的多樣性。很顯然，太高的懲罰函數(shù)值會使算法無法無法訪問不可行解；而太低的懲罰函數(shù)值則沒有辦法區(qū)分各種可行解。因此，懲罰函數(shù)的值需要進行動態(tài)的改變以盡可能的保證一定數(shù)目的可行解與不可行解都可以作為當(dāng)

41、前方案而被訪問。對于一個被給定的迭代，一個不可行方案變成一個最優(yōu)的鄰域方案，并被選作下一階段當(dāng)前方案所需要的次數(shù)或者這種不可行方案的數(shù)目都被記錄下來了。如果不可行方案的比例高于60%，則懲罰函數(shù)值需要增加。如果比例小于40%，則懲罰函數(shù)值要減小。如果不可行方案的比值保持在40%-60%之間，則懲罰函數(shù)值保持不變。通過增加懲罰函數(shù)的步長來執(zhí)行懲罰函數(shù)的更新。換句話說，如果懲罰函數(shù)值需要增加，則表達式為：=懲罰值 + 懲罰步長；反之，則為：= penaltyValue À penaltyStepSize。懲罰步長的大小不是恒定的，有如下四種情況：1. 如果懲罰值必須增大并在前面的控制就增

42、加，然后懲罰步長加倍并加到懲罰值上。2. 如果懲罰值必須增加并在前面的控制下降，那么懲罰步長減半加到懲罰值上。3. 如果懲罰值必須被減少，在先前的控制被降低，然后懲罰步長加倍，并從懲罰值中減去。4. 如果懲罰值必須降低，并在前面的控制就增加，則刑罰步長減半，并從懲罰值中減去。需要注意的是，每次的懲罰值被更新時 numInfeasible參數(shù)復(fù)位為0。懲罰值更新過程如圖1算法在附錄A中，其中t表示當(dāng)前迭代次數(shù)。4.5終止條件條件1.有兩種類型的終止條件是受TS- RN的影響。我們只要其中任何一個得到滿足便終止算法。非改善迭代的最大數(shù)量限制（最大非限制數(shù)）。這個條件限制了該算法在此期間，最佳可行解

43、Sbestdoes沒有改善的連續(xù)迭代的次數(shù)。條件2.時間限制（ CPU時間限制）。它決定了所允許的最大CPU運行時間。5. 計算結(jié)果 在這里，我們先介紹我們是如何產(chǎn)生的隨機問題的實例。然后，我們劃定的替代移動的組合，在我們的TS -RN啟發(fā)式實驗中計算包含三種解決方法的性能比較的結(jié)果。由CPLEX 11.2解決SMDVRPP -1和SMDVRPP -2的模型與所選擇的移動組合來實現(xiàn)我們的啟發(fā)式TS- RN。最后，通過TS -RN一些基準(zhǔn)實例的比較來充分研究MDVRP，以評估其性能。通過為收集中心（C=1,2,3,4,5）分配五個不同的價值觀，和為經(jīng)銷商的數(shù)量（D=10,20,30,40,50,

44、60,70,80,90,100）分配十個不同的值，我們得到40個實例其中每個實例被標(biāo)記為（C,D)。注意的是，當(dāng)經(jīng)銷商的數(shù)量較少時，也保持收集中心較少的數(shù)量。例如當(dāng)D=20時，C=1,2。收集中心和經(jīng)銷商的位置坐標(biāo)（ X，Y）是在區(qū)間 0 ，500 上的一個離散均勻分布采樣。位置之間的移動距離DIJ使用歐幾里德距離計算。每個經(jīng)銷商的預(yù)訂價Pi在文獻 5 ，7.5內(nèi)均勻分布的隨機變量抽樣。每個經(jīng)銷商的核的數(shù)量是在區(qū)間 5,15 的離散均勻分布生成的。固定車輛運行成本c1等于100和每行駛距離可變交通工具成本C2被取為1。車輛容量q被設(shè)定為在該經(jīng)銷商的核心數(shù)量的10倍，即q = 10maxi ai

45、 = 150的最大數(shù)目。每單位核心的收入r等于15 。值得一提的是，在隨機情況下，我們要注意不能取得實例的最好的解決方法是訪問所有的經(jīng)銷商和收集所有的內(nèi)核。在這種情況下，SMDVRPP將減少到經(jīng)典MDVRP。TS- RN被編碼在Java和與Java Server虛擬機編譯的有16 GB的RAM和兩個Intel四核至強3.2 GHz處理器的計算機上。對于所有的移動配置， TS -RN的參數(shù)值如下：懲罰控制計數(shù)= 100 ，懲罰值= 0 ，懲罰步長= 1 ，最大非限制數(shù) = 2000 ， CPU時間上限= 15分鐘。5.1選擇最好的組合 我們定義一個組合為C0包括以下移動：添加-1，添加-2，刪除

46、-1，刪除-2,1-分裂，2-O選擇和鏈轉(zhuǎn)換。注意，前四個為經(jīng)銷商的移動選擇，我們正在處理一個選擇性的路徑問題,并不是所有經(jīng)銷商都必須訪問,經(jīng)銷商移動選擇動作是很重要的,因此它們都包含在基本組合。其他組合在表3中給出，C15包含本研究中使用的所有組合。通過運行TS- RN不同的移動組合， C9平均利潤為1116.29是40個實例中被發(fā)現(xiàn)的最好的移動組合。組合C15和C10分別以1049.35和1048.69的平均利潤排第二和第三。我們用MDVRP基準(zhǔn)實例來評估TS- RN的性能，C9是否在上SMDVRPP上有類似的問題由于針對SMDVRPP的TS- RN啟發(fā)式算法不考慮對車輛游覽時間的約束問題

47、，即最大行程時長的限制，我們僅選擇那些沒有這樣的約束條件的MDVRP實例。因此，我們已實施的TS -RN 10 MDVRP測試實例的數(shù)據(jù)文件，可以在VRP網(wǎng)絡(luò)（ http:/neo.lcc.uma.es/radi-aeb/WebVRP ）和加拿大分銷管理研究的網(wǎng)站上（ http:/neumann.hec.ca/chairedistributique/data ）查到。表4 ，包括每個實例得到的最好的目標(biāo)函數(shù)值，由TS- RN和從最好的目標(biāo)函數(shù)值的百分比偏差所獲得的客觀價值的結(jié)果。這樣觀察到的TS- RN的精度是比較滿意的。因此，在我們的進一步研究中我們采用C9組合和令人滿意的TS- RN。表3

48、.TS- RN考慮到的組合表4.驗證TS -RN性能的MDVRP實例5.2該解決方案的對比 在表5中，我們提出的結(jié)果，作為用于解決SMDVRPP實例3的方法的準(zhǔn)確度和效率的基礎(chǔ)?！?LB ”表示對應(yīng)于每一種方法所得到的最好的可行解決方案的利潤。此值表示在實例上的考慮最佳利潤的一個下界?！?UB ”，另一方面，表示SMDVRPP -1和SMDVRPP -2的模型內(nèi)由CPLEX發(fā)現(xiàn)為3小時或等價10800 S中的允許時限內(nèi)的上限?！癗OD”代表拜訪經(jīng)銷商的數(shù)量。 CPLEX只能為三個實例（1,10 ），（ 1,20） ，（2 ，20）獲得的最優(yōu)解。在其他情況下，最佳的利潤在LB和UB的值之內(nèi)。表5中的第一個實例達到零值，為LB和UB無論是解決方法。這表明收集的十個經(jīng)銷商的任何一個核心都是不賺錢的。在SMDVRPP - 2模型下，一些LB值都是零，這意味著CPLE