第二章文獻(xiàn)回顧

1、第二章文獻(xiàn)回顧2.1 車輛路線相關(guān)問(wèn)題之特性分析制，是多路線節(jié)點(diǎn)服務(wù)組合的問(wèn)題。圖2.1 顯示TSP 與VRP 兩種問(wèn)題解出的路線型態(tài)。 路線1 路線2 路線3 ：場(chǎng)站：顧客點(diǎn)(a) TSP (b) VRP 圖2.1 TSP 與VRP 之路線型態(tài)VRRPs 考慮網(wǎng)路特性、顧客需求、設(shè)施資源及配送條件等實(shí)務(wù)限制，在追求一般化成本（Generlized Cost）總和最小之目標(biāo)下，決定出最佳的車輛配送路線方案。上述的決策問(wèn)題具有明確的目標(biāo)與限制條件，可以應(yīng)用數(shù)學(xué)規(guī)劃模式（Mathematical Programming Formulation）來(lái)描述與求解。對(duì)VRRPs 而言，其目標(biāo)函數(shù)（Obje

2、ctive Function）通常為一般化成本之極小化。所謂一般化成本係將車輛配送過(guò)程中可能發(fā)生的各種負(fù)面效果予以數(shù)量化及幣值化。最常見(jiàn)的負(fù)面效果是運(yùn)輸成本，又可分為固定成本與變動(dòng)成本：固定成本係指車輛使用成本（例如，購(gòu)買成本、折舊）及司機(jī)薪資；變動(dòng)成本則與配送路線之排程有關(guān)（例如，路線行駛距離或時(shí)間、油耗、輪胎磨損、裝卸貨時(shí)間）。此外，若有無(wú)法滿足顧客需求或延誤等情形發(fā)生時(shí)，則會(huì)產(chǎn)生無(wú)形的懲罰成本（Penalty Cost ）。除此之外，也有考慮：車隊(duì)規(guī)模極小化、配送公平性（例如，車輛負(fù)載或路線距離），以及收益或服務(wù)水準(zhǔn)之極大化等目標(biāo)。在限制式（Constraints）方面，VRRPs 所面

3、臨的限制條件甚多，共可摡分成以下五種類型：(1) 網(wǎng)路結(jié)構(gòu)：描述節(jié)點(diǎn)與節(jié)線之空間位向關(guān)係，例如1. 1.方向性（Directed）網(wǎng)路：節(jié)線具有方向性（單向相連），反之即為無(wú)方向性（Undirected）網(wǎng)路。2. 2.完全性（Complete）網(wǎng)路：所有點(diǎn)對(duì)（Nodes Pair）之間皆有無(wú)方向性節(jié)線相連，反之即為不完全性（Incomplete）網(wǎng)路。3. 3.對(duì)稱性（Symmetric）網(wǎng)路：無(wú)方向性節(jié)線之成本為對(duì)稱（雙向之成本相同），反之即為非對(duì)稱性（Asymmetric）網(wǎng)路。4. 4.連結(jié)性（Connective）網(wǎng)路：所有點(diǎn)對(duì)（Nodes Pair）之間皆有路徑（Path）相連，反

4、之即為孤立性（Isolated）網(wǎng)路。5. 5.歐氏（Euclidian）網(wǎng)路：節(jié)線成本滿足三角不等式（兩邊和大於第三邊），反之即為非歐氏（Non-Euclidian ）網(wǎng)路。6. 6.節(jié)線成本通常為一固定值，某些特定情形下會(huì)考慮變動(dòng)的節(jié)線成本（例如：尖峰與離峰時(shí)段）。嚴(yán)格來(lái)說(shuō)，網(wǎng)路結(jié)構(gòu)並不會(huì)以限制式的形態(tài)出現(xiàn)在數(shù)學(xué)規(guī)劃模式中，但是會(huì)影響目標(biāo)函數(shù)之變動(dòng)成本參數(shù)。(2) 節(jié)點(diǎn)服務(wù)：規(guī)範(fàn)車輛服務(wù)顧客之方式，會(huì)影響解的基本結(jié)構(gòu)，包括1. 1.流量守恆（Flow Conservation ）：每個(gè)節(jié)點(diǎn)之流入量與流出量必須相等，此處之流量係指車輛服務(wù)次數(shù)（流入為車輛到達(dá)，流出為車輛離開(kāi)）；流量守恆也要求

5、到達(dá)與離開(kāi)的車輛必須為同一輛車。此外，各車輛必須自某場(chǎng)站出發(fā)，最後並回到該場(chǎng)站；特殊情形下，可以不回場(chǎng)站或回到其他場(chǎng)站。1. 2.避免子迴圈（Sub-tour Breaking ）：只有流量守恆限制可能會(huì)產(chǎn)生子迴圈的情形，亦即車輛未從場(chǎng)站出發(fā)/返回，因此需要避免子迴圈之限制式。1. 3.配送方式：依據(jù)收件（Pick-up ）與送件（Delivery）之不同，車輛服務(wù)可分為只收或只送、同時(shí)收送（Pick-up & Delivery ）、先送後收（Backhauls）、優(yōu)先順序（Precedence ）等形式；不同的配送方式不僅影響問(wèn)題的複雜度，也會(huì)影響求解方法的設(shè)計(jì)。(3) 顧客需求：指

6、顧客的需求量或配送條件，會(huì)影響車隊(duì)規(guī)模及路線組成。1.固定（Fixed）需求與隨機(jī)（Stochastic）需求：前者假設(shè)各顧客節(jié)點(diǎn)之需求量為固定值，後者則假設(shè)需求量符合某一機(jī)率分配。1. 2.不可分割（Indivisible）：各顧客點(diǎn)的需求必須完全由某輛車一次服務(wù)，不可分成多次或由多輛車來(lái)服務(wù)。特殊情形必須分割需求量時(shí)，可假設(shè)同一位置上有多個(gè)不同顧客（實(shí)為同一顧客）。1. 3.時(shí)間窗（Time Windows）：顧客希望在某段時(shí)間內(nèi)被服務(wù)，不可早到或晚到（硬時(shí)窗限制）；或者，晚到會(huì)有懲罰成本（軟時(shí)窗限制）。1. 4.配送頻率（Frequency）：在某一段時(shí)間內(nèi)，各顧客需要被服務(wù)的次數(shù)不盡相

7、同；甚者，顧客會(huì)要求在某種服務(wù)日期組合下進(jìn)行配送。(4) 設(shè)施資源：指場(chǎng)站、車輛及人員等配送資源之特性或限制。1. 1.場(chǎng)站（Depot）：依場(chǎng)站數(shù)之多寡，可分為單一場(chǎng)站（Single Depot）與多場(chǎng)站（Multi-Depots ）兩種類型。1. 2.車隊(duì)（Fleet）：指配送車輛之組成（種類與數(shù)量）。車種方面，可分為單一車種（Homogeneous）與多車種（Heterogeneous）兩種類型；各車輛之負(fù)載量（服務(wù)顧客之需求量總和）不得超過(guò)其容量。數(shù)量方面，假設(shè)車輛數(shù)為無(wú)限，以避免無(wú)解之情形；若求解結(jié)果之車輛數(shù)超過(guò)實(shí)際可用車輛數(shù)時(shí)，可考慮租用外車或多趟使用。1. 3.人員（Crew）：

8、通常假設(shè)人車合一，並將人員（司機(jī)或運(yùn)送員）的薪資反映在車輛之使用成本上；由於人員有每日工時(shí)的限制，因此會(huì)設(shè)定有每條路線之最大距離或時(shí)間的限制式。2. (5) 變數(shù)型態(tài)：指定數(shù)學(xué)規(guī)劃模式中各變數(shù)之型態(tài)，包括，實(shí)數(shù)（Real ）、整數(shù)（Integer）及雙元整數(shù)（Binary Integer）。隨著實(shí)務(wù)狀況與上述限制條件之不同，VRRPs 自TSP 與VRP 衍生出許多種更複雜的問(wèn)題類型，例如：時(shí)間窗車輛路線問(wèn)題（VRP with Time Windows, VRPTW）、多車種車輛路線問(wèn)題（Heterogeneous Fleet VRP, HVRP ）、週期性車輛路線問(wèn)題（Periodic VR

9、P, PVRP），等等。表2.1 顯示部分VRRPs 問(wèn)題類型與目標(biāo)函數(shù)及限制條件之關(guān)係；對(duì)所有的VRRPs 而言，若無(wú)特別指定，皆假設(shè)為完全性、無(wú)方向性、對(duì)稱性之網(wǎng)路結(jié)構(gòu)。由表2.1 可知，各種類型VRRPs 問(wèn)題之間的差異並不大，往往只改變一或二個(gè)限制條件而已。儘管如此，不同類型問(wèn)題的求解方法卻可能有南轅北轍之設(shè)計(jì)理念；限制條件的改變也可能使問(wèn)題求解更加困難。此外，表2.1 所列之部份VRRPs 問(wèn)題特性，僅為該典型問(wèn)題基本之目標(biāo)與限制條件，實(shí)務(wù)應(yīng)用時(shí)可視需要而做修正或調(diào)整。由於VRRPs 屬於解題複雜度很高的NP-Hard 問(wèn)題，亦即當(dāng)問(wèn)題規(guī)模很大時(shí)，幾乎無(wú)法在有效的時(shí)間內(nèi)求得真確最佳解

10、（Exact Solution ）；加以大多數(shù)的實(shí)務(wù)應(yīng)用都屬於大規(guī)模的問(wèn)題，因此不得不採(cǎi)用能迅速求得較佳近似解的啟發(fā)式方法來(lái)進(jìn)行求解。在以下的2. 節(jié)與2.3 節(jié)中，將分別針對(duì)VRRPs 問(wèn)題（主要為T(mén)SP 與VRP）之傳統(tǒng)啟發(fā)式解法與巨集啟發(fā)式解法進(jìn)行回顧。表2.1 部分 VRRPs 問(wèn)題類型之特性問(wèn)題類型目標(biāo)函數(shù)節(jié)點(diǎn)服務(wù)顧客需求設(shè)施資源旅行推銷員問(wèn)題（Traveling Salesman Problem, TSP） 。路線成本最小。流量守恆。避免子迴路。顧客皆需服務(wù)一次，但無(wú)需求。單一場(chǎng)站。無(wú)容量限制車輛路線問(wèn)題（Vehicle Routing Problem, VRP） 。路線成本總和最

11、小。流量守恆。避免子迴路。只收或只送。固定需求。不可分割。單一場(chǎng)站。單一車種。有容量限制。最大距離/時(shí)間多車種車輛路線問(wèn)題（Heterogeneous Fleet VRP, HVRP） 。車輛成本與路線成本之總和最小。流量守恆。避免子迴路。只收或只送。固定需求。不可分割。單一場(chǎng)站。多車種。有容量限制。最大距離/時(shí)間週期性車輛路線問(wèn)題（Periodic VRP, PVRP） 。多日之路線成本總和最小。流量守恆。避免子迴路。只收或只送。固定需求。不可分割。配送頻率。單一場(chǎng)站。單一車種。有容量限制。車輛數(shù)限制。最大距離/時(shí)間時(shí)間窗車輛路線問(wèn)題（VRP with Time Windows, VRPTW

12、） 。路線成本（時(shí)間）總和最小。流量守恆。只收或只送。固定需求。不可分割。時(shí)間窗限制。單一場(chǎng)站。單一車種。有容量限制。最大時(shí)間回頭車車輛路線問(wèn)題（VRP with Backhauls, VRPB） 。路線成本總和最小。流量守恆。避免子迴路。先送後收。固定需求。不可分割。單一場(chǎng)站。單一車種。有容量限制。最大距離/時(shí)間多場(chǎng)站車輛路線問(wèn)題（Multi-Depot VRP, MDVRP） 。路線成本總和最小。流量守恆。避免子迴路。只收或只送。固定需求。不可分割。多場(chǎng)站。單一車種。有容量限制。最大距離/時(shí)間動(dòng)態(tài)車輛路線問(wèn)題（Dynamic VRP, DVRP） 。路線成本總和最小（動(dòng)態(tài)路線成本）。流量守

13、恆。避免子迴路。只收或只送。隨機(jī)需求。不可分割。單一場(chǎng)站。單一車種。有容量限制。最大距離/時(shí)間2.2 傳統(tǒng)啟發(fā)式方法回顧網(wǎng)路組合最佳化問(wèn)題的求解方法大致可分成兩大類：精確解法（Exact Solution Methods）與近似解法（Approximation Methods）。精確解法大多是以數(shù)學(xué)規(guī)劃為基礎(chǔ)（ MP-Based ）的方法，例如：分枝定限法（Branch-and-Bound ）、拉氏鬆弛法（ Lagrangean Relaxation ）、切割平面法（Cutting Plane ）及變數(shù)產(chǎn)生法（Column Generation）等。雖然精確解法可以保證找到最佳解，但由於VRR

14、Ps 問(wèn)題複雜度屬於NP-Hard，在求解大規(guī)模的問(wèn)題時(shí)，精確解法幾乎無(wú)法在有效率的時(shí)間內(nèi)求得最佳解。在近似解法方面，演算法（Algorithms）或啟發(fā)式方法（Heuristics）經(jīng)常被用來(lái)求解VRRPs 這類困難的組合最佳化問(wèn)題。根據(jù)Golden et al.1984與Fisher 1995等學(xué)者對(duì)TSP 與VRP 各種求解方法之分類，吾人可將其中主要的啟發(fā)式方法概分為：構(gòu)建法（Construction Methods）與改善法（Improvement Methods）兩大類。(一) 構(gòu)建法構(gòu)建法係依循特定的規(guī)則逐步的建構(gòu)出一個(gè)可行解。在各種構(gòu)建法當(dāng)中，最常使用的方法應(yīng)屬節(jié)省法（Savi

15、ngs Methods ）與插入法（Insertion Methods ），兩者之基本求解概念如圖2.2 所示，其中Cik 表示節(jié)線(i, k)之行駛成本。Ci0 C0k Sik = Ci0 + C0k - Cik i Cik k 0 0 (a) 節(jié)省法Ii0k = Cik + Ck0- Ci0 i Cik k Ci0 Ck000 (b) 插入法圖2.2 節(jié)省法與插入法之求解概念節(jié)省法係由Clark & Wright 1964所提出：假設(shè)每個(gè)顧客皆有一條路線直接服務(wù)，然後藉由逐步合併路線的方式來(lái)構(gòu)建可行解；路線合併的依據(jù)在於合併後所能產(chǎn)生之路線成本節(jié)省值（如圖2.2(a)之Sik），節(jié)

16、省值愈大者將優(yōu)先考慮合併，但仍不得違反車輛之容量限制。節(jié)省法首先被Clark & Wright 應(yīng)用在VRP 之求解上，隨後更陸續(xù)衍生出多種修改或變形版本以求解其他的VRRP 問(wèn)題。例如，在多車種車輛路線問(wèn)題（HVRP）方面，Golden et al 1984提出組合節(jié)省法（Combined Savings ），同時(shí)考慮路線成本與車輛使用成本之節(jié)省值；而Soloman 1984也曾提出一個(gè)修正的節(jié)省法來(lái)求解時(shí)間窗車輛路線問(wèn)題（VRPTW）。插入法係由Rosenkrantz et al.1960所提出：從一條簡(jiǎn)單的路線開(kāi)始，逐步加入新的顧客點(diǎn)以產(chǎn)生可行解；插入的準(zhǔn)則在於插入顧客點(diǎn)後所增加

17、的路線成本（如圖2.2(b) 之Ii0k）愈小愈好，且須滿足車輛容量限制。評(píng)估插入成本有許多不同的準(zhǔn)則，例如：最近插入（Nearest Insertion）、最遠(yuǎn)插入（Farthest Insertion ）、最省插入（Cheapest Insertion）、最快插入（Quick Insertion）、任意插入（Random Insertion）等。表2.2 列舉節(jié)省法與插入法之基本公式與優(yōu)點(diǎn)比較。由表可知節(jié)省法與插入法無(wú)論在基本公式或優(yōu)點(diǎn)方面都相當(dāng)類似；容易執(zhí)行、速度快、有彈性等優(yōu)點(diǎn)，使得節(jié)省法與插入法成為最普遍使用的起始解構(gòu)建方法。表2.2 節(jié)省法與插入法之優(yōu)點(diǎn)比較節(jié)省法插入法基本公式路線

18、成本節(jié)省值：Sik = Ci0 + C0k - Cik 路線成本增加值：Ii0 k = Cik + Ck0 Ci0 優(yōu)點(diǎn)。執(zhí)行容易且速度快。可依問(wèn)題特性修改基本公式。有循序(Sequential) 與平行(Parallel) 兩種路線構(gòu)建法則。執(zhí)行容易且速度快?？梢绬?wèn)題特性修改基本公式?？衫貌煌牟迦氤杀驹u(píng)估準(zhǔn)則來(lái)構(gòu)建路線(二) 改善法改善法是以任意的可行解（起始解）為基礎(chǔ)，使用特定程序自現(xiàn)有解（Current Solution/ Incumbent ）產(chǎn)生出其他的可行解，並逐步改善其目標(biāo)函數(shù)。改善法大多藉由交換現(xiàn)有解的部分組成元素或順序來(lái)產(chǎn)生新的可行解。此種交換型改善法也被稱為鄰域搜尋（N

19、eighborhood Search ）法或局部搜尋（Local Search ）法，其執(zhí)行過(guò)程必須從現(xiàn)有解之鄰域當(dāng)中找尋得以改善目標(biāo)值的鄰解（Neighbors ），然後將該鄰解設(shè)為新的現(xiàn)有解並重複此鄰域搜尋的動(dòng)作；若找不到可改善的鄰解，即停止搜尋。從現(xiàn)有解轉(zhuǎn)換成鄰解的動(dòng)作，稱之為移動(dòng)（Move ）；鄰域搜尋法可說(shuō)是一連串的移動(dòng)過(guò)程，且移動(dòng)會(huì)造成目標(biāo)值的改變。一般而言，鄰域搜尋法具有以下幾點(diǎn)特質(zhì)： (1) 須有一個(gè)產(chǎn)生鄰解的機(jī)制。所謂鄰解係指經(jīng)由特定程序改變現(xiàn)有解S 的部分組成結(jié)構(gòu)（l個(gè)元素）所產(chǎn)生的一個(gè)新的可行解S'。由於僅改變部分元素，S 與S之間具有很大的相似性，因此解S 的l

20、-鄰解（l-Neighbor ）可定義為：至多改變S 的l個(gè)元素所得到的可行解。鄰解並非為唯一的解；某現(xiàn)有解的所有鄰解形成之集合即稱為鄰域，記做Nl(S)?？尚薪馀c其鄰域聯(lián)集形成的解空間，稱為搜尋空間（Search Space ）；對(duì)相同的現(xiàn)有解而言，採(cǎi)用不同的鄰域搜尋機(jī)制有可能會(huì)產(chǎn)生不同的搜尋空間。(2) 須有一個(gè)接受法則（Acceptance Rule ）。因?yàn)猷徲蛑械目尚薪夂芏?，所以要透過(guò)接受法則來(lái)篩選好的可行解；符合接受法則的鄰解即稱之為候選解（Candidate ），所有候選解形成之集合即為候選清單（Candidate List）。傳統(tǒng)的鄰域搜尋法只接受比現(xiàn)有解更佳的鄰解進(jìn)入候選清單

21、，屬於嚴(yán)格的（Strict ）接受法則；某些巨集啟發(fā)式方法採(cǎi)用的是包容性（Generic）接受法則，允許接受劣於現(xiàn)解的鄰解。(3) 須有一個(gè)選擇策略（Selection Strategy ）。當(dāng)候選清單中含有兩個(gè)以上的候選解時(shí)，必須透過(guò)選擇策略決定該移動(dòng)至那一個(gè)鄰解上。最常見(jiàn)的選擇策略有兩種：最佳改善（Best Improvement ）與首先改善（First Improvement ）。最佳改善係選擇候選清單中改善效果最大的鄰解，而首先改善則是選擇搜尋過(guò)程中遇到的第一個(gè)候選解。對(duì)同一種鄰域搜尋法而言，採(cǎi)用不同的選擇策略可能會(huì)得到不同的搜尋結(jié)果。茲以極小化問(wèn)題為例，說(shuō)明鄰域搜尋法的基本執(zhí)行架構(gòu)

22、與虛擬碼如表2.3。其中，X 代表現(xiàn)有解，C(·) 為目標(biāo)函數(shù)，A 為候選清單集合，N(·) 為鄰域集合，X代表候選鄰解，X* 代表被選擇的候選鄰解。由表2.3 可知，此鄰域搜尋法使用的是嚴(yán)格的接受法則（C(X) C(X) < 0），以及最佳改善的選擇策略（C(X*) := MinC(X) ）。表2.3 鄰域搜尋法之虛擬碼BEGIN /* Initialization */Get a initial solution: X;/* Search */REPEAT Generate neighborhood: N(X);A:= S| C(X) C(X) < 0, X

23、 N(X) ;IF A f THEN C(X*) := MinC(X)| X Aand X := X*;UNTIL stop; END 對(duì)VRRPs 而言，交換型的鄰域搜尋法大致可分為：節(jié)線交換（Arc Exchange）與節(jié)點(diǎn)交換（Node Exchange）兩類；以下簡(jiǎn)要介紹數(shù)種常見(jiàn)的交換型鄰域搜尋法。最有名的鄰域搜尋法要算是k-Opt 節(jié)線交換法（Cores 1958, Bock 1958, Lin 1965）：以任一起始解為現(xiàn)解，交換同路線中k 條不相鄰節(jié)線之銜接方式以產(chǎn)生可行的鄰解（鄰域搜尋），若其中存在有優(yōu)於現(xiàn)解之鄰解，則移動(dòng)至該鄰解（新的現(xiàn)解），重複上述鄰域搜尋的動(dòng)作，直到所有鄰

24、解皆無(wú)法優(yōu)於現(xiàn)解為止。k-Opt 在每次移動(dòng)後，必須重新檢查現(xiàn)解之所有可行交換型態(tài)，以確定是否有更佳的鄰解存在；k 值愈大，可行的交換型態(tài)愈多，因此 k 值通常取 2 或3。如圖2.3 所示：2-Opt 在拿掉(1, 2)與(3, 4)兩條節(jié)線後，將可產(chǎn)生兩種不同的交換型態(tài)，但其中僅有一種為可行的交換型態(tài)，即連接 (1, 3)與(2, 4)兩條節(jié)線；至於3-Opt 在拿掉 (1, 2)、(3, 4)與(5, 6) (3, 4) 三條節(jié)線後，雖可產(chǎn)生14 種不同的交換型態(tài)，其中四種為真正可行的3-Opt 交換型態(tài)（如圖2.3(b)），三種為可行的3-Opt 交換型態(tài)，其餘七種則是不可行的交換型態(tài)

25、。(a) 2-Opt: (b) 3-Opt: 2 圖2.3 2-Opt 與3-Opt 之節(jié)線交換型態(tài)示意圖Lin & Kernighan 1973曾提出稱之為變動(dòng)深度（Variable Depth ）的節(jié)線交換法，其產(chǎn)生鄰解的機(jī)制更形複雜，每次移動(dòng)時(shí)所交換的節(jié)線數(shù)並非為固定的值。Reinelt 1993曾指出，Lin & Kernighan 節(jié)線交換法的解題精確度明顯優(yōu)於k-Opt 節(jié)線交換法及大多數(shù)當(dāng)時(shí)期的啟發(fā)式解法，例如：節(jié)省法、插入法、掃描（Sweep）法、最小擴(kuò)張樹(shù)（Minimal Spanning Tree）法、一般化指派（Generalized Assignment

26、）法。Or 1978在其博士論文中曾提出一種簡(jiǎn)化的3-Opt 節(jié)線交換法，稱為Or-Opt 交換法。該方法在每次執(zhí)行鄰域搜尋的迴圈當(dāng)中，係陸續(xù)將某二段節(jié)線（p=3）、一段節(jié)線（p=2）及一個(gè)節(jié)點(diǎn)（p=1）自路線中抽出，然後將其插入該路線的其他節(jié)線之間，檢查插入後的結(jié)果是否能維持可行並獲得改善，再?zèng)Q定接受改善效果最好的位置進(jìn)行插入。Reinelt 1993曾提及一個(gè)類似的方法，稱為節(jié)點(diǎn)節(jié)線插入（Node/ Edge Insertion）法，如圖2.4 所示，節(jié)點(diǎn)節(jié)線插入法即為Or-Opt 的特例（p=1 或2）。值得注意的是，Or-Opt 法在進(jìn)行節(jié)線交換時(shí)，並不需要反轉(zhuǎn)路線中任何節(jié)線之銜接順序

27、。(a) Or-Opt (p=3): (b) Or-Opt (p=2): (節(jié)線插入) (c) Or-Opt (p=1): (節(jié)點(diǎn)插入)圖2.4 Or-Opt 節(jié)線交換與節(jié)點(diǎn)/節(jié)線插入型態(tài)示意圖此外，Gendreau et al.1992 提出的一般化插入解繫法（Generalized Insertion/ Unstringing and Stringing, GENIUS），可視為是節(jié)點(diǎn)插入法與節(jié)線交換法的結(jié)合。其中，一般化插入（GENI）屬於路線構(gòu)建部分，而解繫（US）則為路線改善部分。GENI 與US 的基本型態(tài)是相同的，共有Type I 與Type II 兩種；節(jié)點(diǎn)的插入位置不一定限於

28、相鄰的兩點(diǎn)之間，但是插入後該兩點(diǎn)將與插入點(diǎn)相鄰。圖2.5 顯示GENIUS 兩種插入型態(tài)的示意圖，當(dāng)某節(jié)點(diǎn)被連繫（String ）或被解開(kāi)（Unstring ）後，部分節(jié)線也會(huì)被更換（Type I 為3-Opt 節(jié)線交換，Type II 為4-Opt 節(jié)線交換）。以解繫部分為例：首先從路線中選擇某個(gè)節(jié)點(diǎn)（例如圖2.5(a) 中之點(diǎn)6）予以解開(kāi)，然後重新選擇任意兩點(diǎn)（點(diǎn)4 與點(diǎn)7），配合相關(guān)節(jié)線之3-Opt 交換將該節(jié)點(diǎn)插入此兩點(diǎn)之間。(a) Type I: String Unstring (b) Type II: String Unstring 圖2.5 GENIUS之插入型態(tài)示意圖當(dāng)解的型態(tài)

29、具有多條路線時(shí)（例如：VRP、VRPTW 等），可應(yīng)用路線間的節(jié)點(diǎn)交換法來(lái)進(jìn)行成本改善。節(jié)點(diǎn)交換法最早係由Christofides & Eilon 1969所提出，對(duì)於任兩條路線相互交換其部分節(jié)點(diǎn)，檢查交換後的結(jié)果是否能維持可行並獲得改善，然後決定接受某種交換以獲得較佳的路線。節(jié)點(diǎn)交換的形式很多，例如：1 點(diǎn)對(duì)0 點(diǎn)、1 點(diǎn)對(duì)1 點(diǎn)、1 點(diǎn)對(duì)2 點(diǎn)等等，圖2.6 顯示上述三種節(jié)點(diǎn)交換型態(tài)之示意圖。(a) 1-0: depotdepot(b) 1-1: depotdepot(c) 1-2: depot depot 圖2.6 路線間節(jié)點(diǎn)交換型態(tài)示意圖由於鄰域搜尋法在移動(dòng)時(shí)採(cǎi)用嚴(yán)格的接受法則

30、，因此最後會(huì)陷入局部最佳解而無(wú)法自拔。2.3 節(jié)所要介紹的數(shù)種巨集啟發(fā)式方法，即是針對(duì)此現(xiàn)象加以改進(jìn)，設(shè)計(jì)出可以跳離局部最佳解的機(jī)制。2.3 巨集啟發(fā)式方法回顧本節(jié)概略介紹數(shù)種著名的及新發(fā)展的巨集啟發(fā)式方法，包括：禁制搜尋法（Tabu Search, TS ）、模擬鍛鍊法（Simulated Annealing, SA ）、門(mén)檻接受法（Threshold Accepting, TA）、大洪水法（Great Deluge Algorithm, GDA）、紀(jì)錄更新法（Record-to-Record Travel, RRT ）、噪音擾動(dòng)法（Noising Method, NM）、兩極跳躍法（Fli

31、p-Flop, FF）、搜尋空間平滑法（Search Space Smoothing, SSS），以及變動(dòng)鄰域搜尋法（Variable Neighborhood Search, VNS）。(一) 禁制搜尋法禁制搜尋法（TS）的觀念架構(gòu)最早是由Glover 1986及Hansen 1986所提出，經(jīng)過(guò)多年來(lái)的發(fā)展與演進(jìn)，TS 法已經(jīng)成為當(dāng)代最著名的巨集啟發(fā)式方法之一。TS 法的理念是想構(gòu)建一個(gè)智慧型的問(wèn)題求解程序：在現(xiàn)有解的鄰域進(jìn)行搜尋，並應(yīng)用人工智慧的記憶機(jī)制，將已經(jīng)搜尋過(guò)的解及其特徵記錄在禁制列（Tabu List），以避免重複性或毫無(wú)目標(biāo)的搜尋；等到整個(gè)鄰域都搜尋完畢後，再選擇一個(gè)最佳的方

32、向進(jìn)行移動(dòng)，以逐漸逼近最佳解。TS 法發(fā)展至今已形成相當(dāng)複雜的執(zhí)行架構(gòu)（Glover & Laguna 1997 ），其所應(yīng)用的高階策略主要包含了以下四個(gè)概念。1. (1)記憶結(jié)構(gòu)（Memory Structures）管理：記憶結(jié)構(gòu)乃是TS 法之特色與核心，又分成短期記憶（Short Term/ Recency-Based Memory ）與長(zhǎng)期記憶（Long Term/ Frequency-Based Memory ）兩種結(jié)構(gòu)。短期記憶以禁制列為基礎(chǔ)，將最近搜尋過(guò)的解或移動(dòng)之屬性（Attributes ）記錄在禁制列，以避免後續(xù)搜尋的解重複先前的搜尋途徑。然而，經(jīng)過(guò)一段禁制期間（Ta

33、bu Tenure ）之後，禁制的屬性即可恢復(fù)自由。此外，短期記憶亦可利用渴望水準(zhǔn)（Aspiration Levels ）的機(jī)制來(lái)打破禁制列的限制；亦即當(dāng)搜尋的新解優(yōu)於目前最佳解時(shí)，雖然其屬性在禁制列之中，仍允許移動(dòng)至該解。至於長(zhǎng)期記憶結(jié)構(gòu)則以記錄屬性出現(xiàn)的次數(shù)為主，再配合深度或廣度搜尋策略，以擴(kuò)大TS 法的搜尋範(fàn)圍。2. (2)深度搜尋與廣度搜尋（Intensification/ Diversification Search ）：深度搜尋策略係在搜尋過(guò)程中將較佳的數(shù)個(gè)解記錄在精英列（Elite List ）內(nèi)，當(dāng)短期記憶搜尋無(wú)法改善時(shí)，再?gòu)木⒘兄羞x擇一個(gè)解做為下階段搜尋的起點(diǎn)，重新開(kāi)始。精

34、英列不一定要記錄一個(gè)完整的解，也可以只記錄經(jīng)常出現(xiàn)的部份解（Parts of Solution ）。廣度搜尋策略則需要配合長(zhǎng)期記憶結(jié)構(gòu)記錄搜尋過(guò)程中解或?qū)傩猿霈F(xiàn)的次數(shù)，當(dāng)短期記憶搜尋無(wú)法改善時(shí)，選擇次數(shù)較少之屬性方向重新進(jìn)行短期記憶搜尋。計(jì)算出現(xiàn)次數(shù)時(shí)，需乘以一懲罰值（Penalty ），以控制其搜尋方向。3. (3)策略交替運(yùn)用（Strategic Oscillation）：是一個(gè)調(diào)和深度搜尋與廣度搜尋的機(jī)制，藉由臨界水準(zhǔn)（Critical Level ）來(lái)控制深度搜尋與廣度搜尋的切換時(shí)機(jī)。4. (4)搜尋路徑連結(jié)（Path Relinking）：先設(shè)定一個(gè)目標(biāo)解（Guiding Solut

35、ion ），然後藉由深度搜尋、廣度搜尋與渴望水準(zhǔn)控制搜尋路徑朝向目標(biāo)解前進(jìn)。TS 法嘗試將人類的思考邏輯轉(zhuǎn)化成各種高階指導(dǎo)策略，配合記憶結(jié)構(gòu)且靈活運(yùn)用深度搜尋與廣度搜尋，是TS 法成功之關(guān)鍵。讀者可參考Glover & Laguna 1997 之大作以了解TS 法的執(zhí)行細(xì)節(jié)。(二) 門(mén)檻型演算法（Threshold Algorithms） 模擬鍛鍊法（SA）、門(mén)檻接受法（TA）、大洪水法（GDA）與紀(jì)錄更新法（RRT）皆屬於門(mén)檻型演算法。此類方法之基本觀念乃是在鄰域搜尋陷入局部最佳解時(shí)，採(cǎi)取較鬆的接受法則（通常為一門(mén)檻值）接受劣於現(xiàn)解之鄰解，以便脫離局部最佳解的束縛而繼續(xù)搜尋下去。SA

36、、TA、GDA 與RRT 等方法的執(zhí)行架構(gòu)與傳統(tǒng)鄰域搜尋法之架構(gòu)相似，差異之處僅在於使用的接受法則不同。傳統(tǒng)的鄰域搜尋法僅接受較佳的鄰解，門(mén)檻型演算法則可接受暫劣之鄰解。模擬鍛鍊法的基本觀念最早是由Metropolis et al.1953所提出，然後由Kirkpatrick et al.1983加以應(yīng)用到組合最佳化問(wèn)題之求解上，因而產(chǎn)生了目前所謂的模擬鍛鍊法。SA 法的執(zhí)行關(guān)鍵在於接受法則與降溫過(guò)程（Cooling Process）的機(jī)制設(shè)計(jì)。SA 法的接受法則為機(jī)率性接受暫劣解：利用一個(gè)隨機(jī)產(chǎn)生的數(shù)值與門(mén)檻值做比較，此門(mén)檻值是鄰解與現(xiàn)有解之目標(biāo)值差額及溫度的函數(shù)；此處所謂溫度對(duì)SA 而言是

37、一個(gè)抽象的觀念，僅做為控制門(mén)檻值高低的參數(shù)；降溫則是為了使SA 能夠逐漸收斂。門(mén)檻接受法（Dueck & Scheuer 1990）、大洪水法（Dueck 1993）與紀(jì)錄更新法（Dueck 1993）的觀念雖源自於SA，但採(cǎi)用確定性的接受法則。茲以圖2.7 的示意圖說(shuō)明TA、GDA 與RRT 等方法之接受法則異同：TA 法事先產(chǎn)生一組固定的門(mén)檻值數(shù)列（通常為遞減），依次使用數(shù)列中的門(mén)檻值，其接受法則為C(Xnew) < C(Xcurrent) + Tk；GDA 法設(shè)定一個(gè)起始水位，只要有改善就降低水位（固定的下降速度），其接受法則為C(Xnew) < L ；至於RRT 法

38、則是將目前的暫優(yōu)解設(shè)為記錄值，取記錄值之固定百分比率做為門(mén)檻值，其接受法則為C(Xnew) < C(Xcurrent) + R×p。C(Xnew) < L 目目L 目標(biāo)標(biāo)標(biāo)函函函數(shù)數(shù)數(shù)C(X) C(X) C(X) 移動(dòng) 解Xcurrent Xnew 解 解(a) TA(b) GDA (c) RRT 圖2.7 TA、GDA 與RRT 接受法則示意圖16 表2.4 以最小化問(wèn)題之求解來(lái)說(shuō)明SA、TA、GDA 與RRT 等方法之重要執(zhí)行機(jī)制的異同，其中C(X)為現(xiàn)有解X 之目標(biāo)值，C(X')為鄰解X'的目標(biāo)值。此外，表2.4 中的控制參數(shù)係指用以控制演算法執(zhí)行與

39、停止之參數(shù)；接受法則為判斷是否將鄰解X'列為候選解之準(zhǔn)則；收斂法則是為了確定搜尋過(guò)程會(huì)收斂，在現(xiàn)有解移動(dòng)後對(duì)其控制參數(shù)進(jìn)行調(diào)整之方式；停止法則係規(guī)範(fàn)演算法停止搜尋之標(biāo)準(zhǔn)。表2.4 SA、TA、GDA與RRT之比較方法SA TA GDA RRT 控制參數(shù)。溫度(T) 。機(jī)率值(0 < r < 1) 。次數(shù)(K) 。門(mén)檻(Tk) 。次數(shù)(K) 。水位(L) 。速度(S) 。誤差率(p < 1) 。記錄值(R) 。次數(shù)(K) 接受法則機(jī)率性接受： T C XC Xr )()(exp -< 確定性接受：C(X') < C(X) + Tk 確定性接受：C(X

40、') < L 確定性接受：C(X') < C(X) + R*p 收斂法則T遞減Tk遞減L = L S 更新R值停止法則完成K次迴圈完成K次迴圈所有C(X') > L 完成K次迴圈Fisher 1995曾將VRP 求解方法的發(fā)展分為三個(gè)時(shí)期：簡(jiǎn)單啟發(fā)式方法、數(shù)學(xué)規(guī)劃基礎(chǔ)方法、人工智慧方法。其中，第三時(shí)期的人工智慧方法包含了專家系統(tǒng)與包容性搜尋法（Generic Search Methods）兩者。所謂的包容性搜尋法，即是允許搜尋過(guò)程中接受暫劣解的一種方法，門(mén)檻型演算法與前述的禁制搜尋法皆被Fisher 歸類為包容性搜尋法的一種。(三) 擾動(dòng)型演算法（Pe

41、rturbation Algorithms） 擾動(dòng)型演算法屬於改變搜尋空間的觀念，這類方法包括：噪音擾動(dòng)法（NM）、兩極跳躍法（FF）與搜尋空間平滑法（SSS）等?；旧?，這類方法仍以傳統(tǒng)鄰域搜尋法為其移動(dòng)之機(jī)制；當(dāng)鄰域搜尋陷入局部最佳解時(shí)，藉由暫時(shí)性的成本擾動(dòng)改變其原有的搜尋空間，然後藉由傳統(tǒng)鄰域搜尋跳脫出原始成本空間之局部最佳解的束縛。擾動(dòng)型演算法之設(shè)計(jì)重點(diǎn)在於成本擾動(dòng)機(jī)制與執(zhí)行架構(gòu)；NM、FF 與SSS 的執(zhí)行架構(gòu)較傳統(tǒng)鄰域搜尋架構(gòu)複雜，其中，NM 與FF 屬於原始搜尋空間與成本擾動(dòng)空間兩者交替搜尋之雙層架構(gòu)，而SSS 則屬於一連串平滑空間持續(xù)搜尋之單層架構(gòu)。噪音擾動(dòng)法是Charon &

42、amp; Hudry 1993 提出的一種擾動(dòng)型演算法，藉由隨機(jī)性地?cái)_動(dòng)成本函數(shù)來(lái)改變搜尋空間，然後在原始成本空間與擾動(dòng)成本空間之間交替地執(zhí)行鄰域搜尋，以達(dá)到跳脫局部最佳解之目的。近年來(lái)，在Charon & Hudry 1999 的努力下，NM 法也衍生出多種成本擾動(dòng)方式與執(zhí)行架構(gòu)。陳國(guó)清1996 修改NM 法之隨機(jī)性成本擾動(dòng)函數(shù)，提出一個(gè)確定性的成本擾動(dòng)方式，稱之為兩極跳躍法（FF）。FF 的原理非常簡(jiǎn)單，即當(dāng)鄰域搜尋陷入局部最佳解時(shí)，將所有的成本乘上-1 ，然後繼續(xù)鄰域搜尋；如此一來(lái)，原先若為極小化的問(wèn)題就變成了極大化問(wèn)題。此外，為避免搜尋過(guò)程重複先前的搜尋途徑，F(xiàn)F 法在成本擾動(dòng)

43、前後係採(cǎi)用不同的鄰域搜尋方法。Gu & Huang 1994 提出的SSS 法，係以正規(guī)化公式將搜尋空間平滑化，然後逐漸還原至原始成本空間，屬於另一種擾動(dòng)搜尋空間的方式。不同於NM 與FF 的執(zhí)行方式，SSS 法僅於最後一次才在原始成本空間進(jìn)行鄰域搜尋，之前都是在不同的平滑成本空間進(jìn)行鄰域搜尋。NM、FF 與SSS 執(zhí)行機(jī)制之異同說(shuō)明如圖2.8，其中C(·) 表示原始成本空間之目標(biāo)函數(shù)值、P(·) 表示擾動(dòng)成本空間之目標(biāo)函數(shù)值、Sa(·) 表示第a次平滑成本空間之目標(biāo)函數(shù)值。表2.5 則以求解最小化問(wèn)題為例，比較NM、FF 與SSS 等方法重要執(zhí)行機(jī)制之異

44、同，其中cij 為各節(jié)線之實(shí)際成本值，cmax = max(cij)為實(shí)際成本最大項(xiàng)之值，cij'為各節(jié)線之?dāng)_動(dòng)成本值，cij(a)為各節(jié)線之平滑成本值，ncij 為實(shí)際成本之正規(guī)化值（0 < ncij < 1），ac 為ncij 之平均值。此外，擾動(dòng)法則係指改變搜尋空間（擾動(dòng)成本）的方式；控制參數(shù)、接受法則、收斂法則與停止法則之定義同於表2.4。S1(·) X0 原擾原 擾原S2(·)X平始動(dòng)始動(dòng)始1 滑成成成成成X1 成本本本本本 本空空空空空X空間間間間間3 間(c) SSS 2.8 NM、FF 與SSS 執(zhí)行機(jī)制示意圖表2.5 NM 、FF與SS

45、S之比較方法NM FF SSS 控制參數(shù)。擾幅：R Rn, Rx 。次數(shù)：N, K 。機(jī)率值(-1 < r < 1) 。次數(shù)(K) 。平滑因子(a > 1) 。次數(shù)(K) 擾動(dòng)法則機(jī)率性擾動(dòng)：cij' = cij + (r×R×cmax) 確定性擾動(dòng)：cij' = -cij 確定性平滑：c ac acij ij(a) a = + -nc 接受法則C(X')<C(X) 或 P(X')<P(X) C(X')<C(X) 或 P(X')<P(X) Sa(X') < Sa(X) 收斂法則擾幅自Rx遞減至Rn 無(wú)a遞減至1 停止法則完成N&