帶后進(jìn)先出限制的配送收集旅行商問題的樹形表示.pdf

1、配送收集旅行商問題(TSPPD)是一個(gè)非常經(jīng)典的組合優(yōu)化問題，已有相當(dāng)多的文獻(xiàn)對(duì)此問題進(jìn)行了研究。在現(xiàn)存的大部分文獻(xiàn)中，TSPPD的合法解都是使用線性序列來表示，并且需要執(zhí)行一些特殊操作來確保解的合法性。
　　 本文研究的問題是TSPPD的變種，名為帶后進(jìn)先出限制的配送收集旅行商問題(TSPPDL)。TSPPDL是在TSPPD的基礎(chǔ)上增加了配送收集過程必須滿足后進(jìn)先出的限制。TSPPDL被認(rèn)為是一個(gè)比TSPPD更為復(fù)雜的問題，原

2、因是在判斷表示為線性序列的解的合法性的時(shí)候，不僅要檢查配送點(diǎn)和對(duì)應(yīng)收集點(diǎn)的先后順序，還要檢查解是否滿足后進(jìn)先出的約束。本文證明了TSPPDL的合法解與TSPPDL解的樹形表示之間存在一一映射關(guān)系。該樹形數(shù)據(jù)結(jié)構(gòu)從本質(zhì)上揭示了TSPPDL的特性，并且使得基于線性表示方式的操作更容易被理解和實(shí)現(xiàn)。
　　 本文基于樹形表示方式，提出了一個(gè)有效的變鄰域搜索(VNS)算法。該算法運(yùn)用了多個(gè)新穎可行的操作，而這些操作都是利用了樹形表示方式的