【正文】 留有經(jīng)常儲(chǔ)備，這就可以實(shí)現(xiàn)生產(chǎn)企業(yè)多年追求的“零庫(kù)存” ，將企業(yè)從庫(kù)存的包袱中解脫出來(lái)，同時(shí)解放出大量?jī)?chǔ)備資金，從而改善企業(yè)的財(cái)務(wù)狀況。同時(shí)增加了調(diào)節(jié)能力，也提高了社會(huì)經(jīng)濟(jì)效益。5）簡(jiǎn)化事務(wù)，方便用戶(hù) 采用配送方式，用戶(hù)只需向一處訂購(gòu)，或向一個(gè)進(jìn)貨單位聯(lián)系就可訂購(gòu)到以往需去許多地方才能訂到的貨物，只需組織對(duì)一個(gè)配送單位的接貨便可代替現(xiàn)有的高頻率接貨，因而大大減輕了用戶(hù)工作量和負(fù)擔(dān)，也節(jié)省了費(fèi)用開(kāi)支。采取配送方式，配送中心可以比任何單位企業(yè)的儲(chǔ)備量更大，因而對(duì)每個(gè)企業(yè)而言，中斷供應(yīng)、影響生產(chǎn)的風(fēng)險(xiǎn)便相對(duì)縮小，使用戶(hù)免去短缺之憂(yōu)。目前普遍采用的對(duì)配送服務(wù)進(jìn)行評(píng)估的指標(biāo)主要有以下內(nèi)容。配送是上游物流活動(dòng)的末端活動(dòng)，同時(shí)又是下游物流活動(dòng)的開(kāi)端。影響配送時(shí)效性的因素，除了送貨司機(jī)的個(gè)人因素以外，還有選帶有時(shí)間窗的車(chē)輛路徑問(wèn)題的優(yōu)化研究12擇的配送路線(xiàn)不恰當(dāng)，客戶(hù)點(diǎn)卸貨不方便，客戶(hù)不配合等。因此配送路線(xiàn)的選擇是配送中心工作的一個(gè)重點(diǎn)，也是眾多專(zhuān)家進(jìn)行研究的重點(diǎn)和熱點(diǎn)。2）可靠性 能否將貨物按照客戶(hù)的要求，保質(zhì)保量、完好無(wú)缺地送達(dá)目的地是衡量配送系統(tǒng)的另外一個(gè)重要的要素。 可靠性完整地體現(xiàn)整個(gè)配送系統(tǒng)的設(shè)施能力和服務(wù)水平。包括員工裝卸貨時(shí)的細(xì)心程度，運(yùn)送過(guò)程對(duì)貨品的保護(hù)，對(duì)客戶(hù)地點(diǎn)及作業(yè)環(huán)境的了解，配送人員的素質(zhì)等。對(duì)于送貨方式、送貨計(jì)劃的安排，應(yīng)該采取具有較大彈性的柔性系統(tǒng)，能夠?yàn)楦鞣N客戶(hù)和要求及時(shí)提供便利的服務(wù)，滿(mǎn)足客戶(hù)緊急送貨、信息傳送、順道退貨、輔助資源回收等獨(dú)特要求。4）經(jīng)濟(jì)性在一個(gè)公正的市場(chǎng)經(jīng)濟(jì)環(huán)境中，配送中心提供服務(wù)的價(jià)格，在正常狀態(tài)下，主要依賴(lài)于配送系統(tǒng)運(yùn)作的成本。也就是說(shuō)，要在保證配帶有時(shí)間窗的車(chē)輛路徑問(wèn)題的優(yōu)化研究13送滿(mǎn)足客戶(hù)要求、提升客戶(hù)滿(mǎn)意度的同時(shí)，通過(guò)各種技術(shù)和管理手段，降低運(yùn)作成本。這就是本文下面需要研究的帶有時(shí)間窗的車(chē)輛路徑問(wèn)題。 從二十世紀(jì)六十年代以來(lái)，許多學(xué)者對(duì)車(chē)輛路徑問(wèn)題進(jìn)行了廣泛的研究。經(jīng)過(guò)幾十年來(lái)許多學(xué)者的不斷努力，VRP包含的類(lèi)型和相關(guān)的解法已經(jīng)相當(dāng)豐富，按不同的劃分標(biāo)準(zhǔn)可以分成不同的種類(lèi)，如按照任務(wù)特征可以劃分為集貨問(wèn)題或者送貨問(wèn)題和集送貨一體化問(wèn)題；按車(chē)輛滿(mǎn)載狀況可以劃分為滿(mǎn)載問(wèn)題和非滿(mǎn)載問(wèn)題；按車(chē)場(chǎng)數(shù)目可劃分為單車(chē)場(chǎng)問(wèn)題和多車(chē)場(chǎng)問(wèn)題；按優(yōu)化目標(biāo)數(shù)可以劃分為單目標(biāo)優(yōu)化和多目標(biāo)優(yōu)化等等。主要的附加條件有：帶有時(shí)間窗的車(chē)輛路徑問(wèn)題的優(yōu)化研究151) VRPLC(帶有運(yùn)行時(shí)間約束的VRP ):每輛汽車(chē)運(yùn)行的時(shí)間不能超過(guò)預(yù)先給定的界L。2) MVRP(多處發(fā)點(diǎn)的VRP):允許從多個(gè)不同的出發(fā)點(diǎn)出發(fā)給客戶(hù)供貨。該模型下求得的解至少都和正常的VRP一樣好，因而可以充分利用汽車(chē)的資源，從而節(jié)省汽車(chē)。某些值，如客戶(hù)的數(shù)目、客戶(hù)的需求、客戶(hù)的服務(wù)時(shí)間不是事先確定的，而是隨機(jī)變化的。所謂帶有時(shí)間窗的車(chē)輛路徑問(wèn)題是指假設(shè)有n個(gè)等待服務(wù)的客戶(hù)，一個(gè)出發(fā)點(diǎn)，K輛有一定載重量的汽車(chē)，己知:每個(gè)客戶(hù)的位置坐標(biāo)、貨物需求量、出發(fā)點(diǎn)的位置坐標(biāo)、每輛汽車(chē)的最大載重量，允許服務(wù)的時(shí)間窗口(時(shí)間窗口是指配送車(chē)輛或顧客希望服務(wù)或被服務(wù)的時(shí)間范圍。另一方面，汽車(chē)也必須在出發(fā)點(diǎn)開(kāi)門(mén)后才可以離開(kāi)，ib在關(guān)門(mén)前返回出發(fā)點(diǎn))。由于JIT理論和實(shí)踐的成熟，現(xiàn)代產(chǎn)業(yè)對(duì)物流配送提出了更高的要求——將合適的零件以合適的數(shù)量在合適的時(shí)間送到生產(chǎn)線(xiàn)，并且只將所需要的零件、只以所需要的數(shù)量、只在正好需要的時(shí)間送到生產(chǎn)。消費(fèi)者需求趨于多樣化，對(duì)送貨時(shí)間的要求日趨嚴(yán)格，除了因缺貨造成的機(jī)會(huì)成本的損失外，由于配送不及時(shí)也會(huì)造成貨物價(jià)值的大大降低。帶有時(shí)間窗的車(chē)輛路徑問(wèn)題的優(yōu)化研究16帶有時(shí)間窗的車(chē)輛路徑優(yōu)化問(wèn)題根據(jù)其時(shí)間約束的嚴(yán)格與否，可分為軟時(shí)間窗和硬時(shí)間窗。它一般把最小的車(chē)輛數(shù)作為一個(gè)目標(biāo),而最低的行駛成本作為另一目標(biāo)；時(shí)間窗是雙向的,即顧客應(yīng)當(dāng)在最早時(shí)間之后或最晚時(shí)間之前得到服務(wù),否則就會(huì)發(fā)生車(chē)輛早到等待或服務(wù)延誤。精確算法是指可以確定求得最優(yōu)解的算法。該方法最初由Kolen (1987)等人提出，可被看作Christofides (1981)對(duì)VRPTW的狀態(tài)空間分解方法的擴(kuò)展，該方法對(duì)小規(guī)模問(wèn)題有效。Fisher(1985),Jomstern(1986),Madsen(1990)和Halse(1992)等人用不同的拉格朗日分解方法求解VRP問(wèn)題，目的是產(chǎn)生一個(gè)接近最優(yōu)解的下界。3) 列生成方法。4) K一樹(shù)方法。5)整數(shù)線(xiàn)性規(guī)劃方法。7)網(wǎng)絡(luò)流算法。直到1985年Savelsbergh證明了車(chē)輛路徑問(wèn)題是NP完全問(wèn)題以后，研究的重點(diǎn)才轉(zhuǎn)向?qū)で髥?wèn)題的近似最優(yōu)解上，這時(shí)所采用的是啟發(fā)式方法。這個(gè)算法解決CVRP(容量車(chē)輛路徑問(wèn)題)，在這里車(chē)輛數(shù)目不限。這個(gè)算法的復(fù)雜性是(n 2logn)。節(jié)約法是構(gòu)造啟發(fā)式算法的一種。確定了這樣一條路線(xiàn)的各點(diǎn)以后再對(duì)這條路線(xiàn)通過(guò)解一個(gè)相應(yīng)的TSP問(wèn)題進(jìn)行優(yōu)化。一般在第一階段用構(gòu)造方法，第二階段用一些改進(jìn)方法對(duì)初始解進(jìn)行改進(jìn)，如掃描法。在兩階段法求解過(guò)程中，常常采用交互式優(yōu)化技術(shù)，把人的主觀能動(dòng)作用結(jié)合到問(wèn)題的求解過(guò)程中，其主要思想是:有經(jīng)驗(yàn)的決策者具有對(duì)結(jié)果和參數(shù)的某種判斷能力，并且根據(jù)知識(shí)直感，把主觀的估計(jì)加到優(yōu)化模型帶有時(shí)間窗的車(chē)輛路徑問(wèn)題的優(yōu)化研究18中去。兩階段法是目前成果最豐富、應(yīng)用最多的一類(lèi)方法。4）插入法該法是通過(guò)每次將一個(gè)請(qǐng)求插入到某條路徑而構(gòu)造一組路徑的過(guò)程。重復(fù)第二步驟直到L為空。首先根據(jù)問(wèn)題的初始解，按照某種鄰域生成機(jī)制先生成當(dāng)前解的鄰域解，根據(jù)目標(biāo)函數(shù)對(duì)鄰域解進(jìn)行評(píng)價(jià)，然后采用某種接受準(zhǔn)則(確定性、概率性、混沌性等)來(lái)決定接受哪個(gè)鄰域解，取代當(dāng)前解繼續(xù)搜索，直至滿(mǎn)足算法停止準(zhǔn)則。改進(jìn)方法根據(jù)對(duì)鄰域解進(jìn)行搜索的策略不同可以分為局部?jī)?yōu)化和全局優(yōu)化方法兩類(lèi)。當(dāng)搜索無(wú)法使目標(biāo)函數(shù)進(jìn)一步改進(jìn)時(shí)，得到一個(gè)局部最優(yōu)解。一旦目標(biāo)函數(shù)值無(wú)法有進(jìn)一步地改進(jìn)，搜索就會(huì)中斷，因此很容易陷入局部極值中。根據(jù)改進(jìn)方法中鄰域生成機(jī)制涉及到的路徑數(shù)目，可將局部改進(jìn)方法分為兩類(lèi):路徑內(nèi)和路徑間改進(jìn)方法。常用的路徑內(nèi)優(yōu)化方法有2opt, 3opt方法。2)全局優(yōu)化方法全局優(yōu)化方法也稱(chēng)為“元啟發(fā)式方法”，許多資料上又稱(chēng)亞啟發(fā)式方法，其由當(dāng)前解生成新解的過(guò)程是嵌入在決定搜索策略的啟發(fā)式方法之中的。在解集中搜索最優(yōu)解的同時(shí)，保持候選解的群體多樣性，更廣泛、更深入地對(duì)解空間進(jìn)行搜索，能避免搜索陷入局部極值，找到全局最優(yōu)解的可能性相對(duì)較大 [14]。?模擬退火算法（Simulated Annealing)模擬退火算法(簡(jiǎn)稱(chēng)SA)，是一種基于熱力學(xué)退火原理的隨機(jī)搜索算法，源于20世紀(jì)50年代，到80年代開(kāi)始應(yīng)用于組合優(yōu)化領(lǐng)域。該算法在求解優(yōu)化問(wèn)題時(shí)，不但接受對(duì)目標(biāo)函數(shù)(能量函數(shù))有改進(jìn)的狀態(tài)，還以某種概率接受使目標(biāo)函數(shù)惡化的狀態(tài)，從而可使之避免過(guò)早收斂到某個(gè)局部極值點(diǎn)。模擬退火算法的特點(diǎn)是:對(duì)目標(biāo)函數(shù)無(wú)特殊要求，從理論上可以找到全局最優(yōu)解，且在一般情況下，解的質(zhì)量都相當(dāng)好；方法靈活，可以考慮多種約束，易于并行處理；在實(shí)用過(guò)程中，發(fā)現(xiàn)迭代初值好壞對(duì)其搜索質(zhì)量影響不大，能較好跳出局部最優(yōu)，因此易于與其他算法構(gòu)高效的組合算法。在實(shí)際應(yīng)用中，一般只能求得近似解，其計(jì)算rt量相當(dāng)大，十分耗時(shí)，影響了其實(shí)用性 [15]。禁忌(tabu或者taboo)表示禁止的意思。禁忌搜索也是人工智能的一種體現(xiàn)，其最重要的思想是標(biāo)記對(duì)應(yīng)已搜索到的局部最優(yōu)解的一些對(duì)象，并在進(jìn)一步的迭代搜索中盡量避開(kāi)這些對(duì)象，而不是絕對(duì)禁止循環(huán)，從而保證對(duì)解空間中的不同區(qū)域進(jìn)行有效的搜索。Tabu搜索法的特點(diǎn)是:對(duì)目標(biāo)函數(shù)要求較少，理論上可以找到全局最優(yōu)解；搜索速度快，能找到非常好的次優(yōu)解；局部搜索能力強(qiáng)，不易陷入局部最優(yōu)，適于與其他算法組成高效組合算法。?蟻群算法(Ants Colony Algorithm)蟻群算法（簡(jiǎn)稱(chēng)AC）, , 受到對(duì)真實(shí)蟻群行為研究的啟發(fā)而首先提出的。該方法的主要特點(diǎn)是:正反饋、分布式計(jì)算、易于與其他啟發(fā)式算法相結(jié)合。?神經(jīng)網(wǎng)絡(luò)算法(Artificial Neural Networks)神經(jīng)網(wǎng)絡(luò)優(yōu)化算法（簡(jiǎn)稱(chēng)AN）是利用神經(jīng)網(wǎng)絡(luò)中神經(jīng)元的協(xié)同并行運(yùn)算能力來(lái)構(gòu)造的優(yōu)化算法，它將實(shí)際問(wèn)題的優(yōu)化解與神經(jīng)網(wǎng)絡(luò)的穩(wěn)定狀態(tài)相對(duì)應(yīng)，把對(duì)實(shí)際問(wèn)題的優(yōu)化過(guò)程映射為神經(jīng)網(wǎng)絡(luò)系統(tǒng)的演化過(guò)程。但卻易于陷入學(xué)習(xí)停滯和局部最優(yōu)；對(duì)于一些費(fèi)用和約束的時(shí)變性不易處理；在構(gòu)造能量函數(shù)時(shí)，有關(guān)系數(shù)的選取尚未有理論指導(dǎo) [16]。遺傳算法是基于生物進(jìn)化和隨機(jī)選擇的全局性搜索算法，它模擬生物進(jìn)化的基本過(guò)程，用數(shù)碼串來(lái)類(lèi)比生物中的染色個(gè)體，通過(guò)選擇，交叉，變異等遺傳算子來(lái)仿真生物的基本進(jìn)化過(guò)程，利用適應(yīng)度函數(shù)來(lái)表示染色個(gè)體所蘊(yùn)涵的問(wèn)題解質(zhì)量的優(yōu)良，通過(guò)種群的不斷“更新?lián)Q代”，從而提高每代種群的平均適應(yīng)度，并在此基礎(chǔ)上，使得最優(yōu)異個(gè)體所代表的問(wèn)題解逼近問(wèn)題的全局最優(yōu)解。遺傳算法被證明為很適合用來(lái)優(yōu)化多目標(biāo)，其機(jī)理在于大量個(gè)體可并行搜尋多個(gè)準(zhǔn)則，最終找到問(wèn)題的最佳有效解。在生物自然環(huán)境中，生物種群的自然繁衍，生存，發(fā)展，最終取決于它對(duì)自然環(huán)境的適應(yīng)能力。所以，一個(gè)種群的優(yōu)異的適應(yīng)能力是該種群得以繁衍發(fā)展的根本。 遺傳算法的基本概念遺傳算法是基于生物進(jìn)化和隨機(jī)選擇的全局性搜索算法，它模擬生物進(jìn)化的基本過(guò)程，用數(shù)碼串來(lái)類(lèi)比生物中的染色個(gè)體，通過(guò)選擇，交叉，變異等遺傳算子來(lái)仿真生物的基本進(jìn)化過(guò)程，利用適應(yīng)度函數(shù)來(lái)表示染色個(gè)體所蘊(yùn)涵的問(wèn)題解的質(zhì)量的優(yōu)良，通過(guò)種群的不斷“更新?lián)Q代”，從而提高每代種群的平均適應(yīng)度，并在此基礎(chǔ)上，使得最優(yōu)異個(gè)體所代表的問(wèn)題解逼近問(wèn)題的全局最優(yōu)解 [17]。其遺傳進(jìn)化操作過(guò)程簡(jiǎn)單，容易理解，帶有時(shí)間窗的車(chē)輛路徑問(wèn)題的優(yōu)化研究24是其他一些遺傳算法的基礎(chǔ)。選擇、交叉和變異是遺傳算法的 3 個(gè)主要操作算子，它們構(gòu)成了遺傳操作，使遺傳算法具有了其他傳統(tǒng)方法沒(méi)有的特點(diǎn)。具體體現(xiàn)在：1)遺傳算法運(yùn)算的是解集的編碼，而非解集本身；2)遺傳算法的搜索始于一個(gè)種群，而非單個(gè)解；3)遺傳算法只使用報(bào)酬信息即適應(yīng)值函數(shù)，而非導(dǎo)數(shù)或其他輔助知識(shí)；4)遺傳算法采用概率的，而非確定的狀態(tài)轉(zhuǎn)移規(guī)則。遺傳算法對(duì)問(wèn)題的依賴(lài)性小，對(duì)其求解函數(shù)要求簡(jiǎn)單，魯棒性強(qiáng)，實(shí)現(xiàn)簡(jiǎn)單高效，因而，遺傳算法從它被提出以來(lái)，一直受到研究者的普遍關(guān)注，并且在函數(shù)優(yōu)化、機(jī)器學(xué)習(xí)、組合優(yōu)化、人工神經(jīng)元網(wǎng)絡(luò)訓(xùn)練、自動(dòng)程序設(shè)計(jì)、專(zhuān)家知識(shí)系統(tǒng)等領(lǐng)域都取得了廣泛的應(yīng)用。此編碼操作使得遺傳算法可以直接對(duì)結(jié)構(gòu)對(duì)象進(jìn)行操作。這一特點(diǎn)使得遺傳算法具有廣泛的應(yīng)用領(lǐng)域。相反，遺傳算法采用的是同時(shí)處理群體中多個(gè)個(gè)體的方法，即同時(shí)對(duì)搜索空間中的多個(gè)解進(jìn)行評(píng)估。3)不需要輔助信息遺傳算法對(duì)所求解的優(yōu)化問(wèn)題沒(méi)有太多的數(shù)學(xué)要求，魯棒性強(qiáng)。更重要的是，遺傳算法帶有時(shí)間窗的車(chē)輛路徑問(wèn)題的優(yōu)化研究25的適應(yīng)度函數(shù)不僅不受連續(xù)可微的約束，而且其定義域可以任意設(shè)定。由于限制條件的縮小，使得遺傳算法的應(yīng)用范圍大大擴(kuò)展。概率僅僅是作為一種工具來(lái)引導(dǎo)其搜索過(guò)程朝著搜索空間的更優(yōu)化的解區(qū)域移動(dòng)的。5)遺傳算法的各態(tài)遍歷性使得其能夠非常有效地進(jìn)行概率意義下的全局搜索，在問(wèn)題不具有凸性時(shí)也能找到全局最優(yōu)解(或近似最優(yōu)解)。? 遺傳算法的缺陷遺傳算法的進(jìn)化機(jī)制的不完善之處主要表現(xiàn)在以下兩個(gè)方面:1)對(duì)于遺傳算法的收斂性缺少完整的理論。對(duì)于不同的問(wèn)題存在多種不同的編碼方式。遺傳算法的收斂判據(jù)不充分，使得算法的終止準(zhǔn)則過(guò)分依賴(lài)研究者的主觀意識(shí)。盡管Holland等學(xué)者給出了Shema理論，但該理論不能解釋遺傳算法在實(shí)現(xiàn)過(guò)程中出現(xiàn)的過(guò)早收斂現(xiàn)象即“早熟”現(xiàn)象。 遺傳算法過(guò)程描述遺傳算法模擬了自然選擇和遺傳中發(fā)生的復(fù)制、交叉和變異等現(xiàn)象，從任一初始種群出發(fā)，通過(guò)隨機(jī)選擇、交叉和變異操作，產(chǎn)生一群更適應(yīng)環(huán)境的個(gè)體，使群體進(jìn)化到搜索空間中越來(lái)越好的區(qū)城，這樣一代一代地不斷繁衍進(jìn)化，最后收斂到一群最適應(yīng)環(huán)境的個(gè)體，求得問(wèn)題的最優(yōu)解。在遺傳算法中，染色體的表現(xiàn)形式通過(guò)編碼機(jī)制來(lái)實(shí)現(xiàn)的。對(duì)于具體問(wèn)題的編碼，目前還沒(méi)有統(tǒng)一的方法。在編碼時(shí)主要的編碼原則有以下兩點(diǎn)：編碼原則一 ——有意義的積木塊編碼原則。這個(gè)原則事實(shí)上是符合Holland所提出的模式定理的。應(yīng)使用能使問(wèn)題得到自然表示或者描述的具有最小編碼字符集的編碼方案。? 二進(jìn)制編碼二進(jìn)制編碼機(jī)制是遺傳算法中最為常見(jiàn)的編碼機(jī)制。二進(jìn)制編碼機(jī)制有著操作簡(jiǎn)單，便于交叉操作和變異操作，符合最小字符集編碼原則等優(yōu)點(diǎn)，但是也有不可彌補(bǔ)的缺陷:海明懸崖(Hamming Clifs)問(wèn)題。 ??iliibabHamp。在二iai進(jìn)制編碼表示中，即使是相鄰的兩個(gè)數(shù)之間的海明距離可能很大，例如7和8之間，以四位的二進(jìn)制表示，海明距離達(dá)到了4。海明懸崖問(wèn)題不利于遺傳算法獲得全局最優(yōu)解，因?yàn)?，在算法后期過(guò)程中逼近最優(yōu)解時(shí)，近似最優(yōu)解和全局最優(yōu)解之間由于存在著海明懸崖問(wèn)題，從而會(huì)導(dǎo)致從近似最優(yōu)解到最優(yōu)解之間的逼近過(guò)程緩慢，甚至找不到最優(yōu)解，所以提出了后面的Gray編碼。它有這么一個(gè)特點(diǎn):即任意兩個(gè)整數(shù)之間的差正好是這兩個(gè)整數(shù)所對(duì)應(yīng)的Gray碼之間的海明距離。設(shè)有二進(jìn)制串( )，n?,21??對(duì)應(yīng)的Gray串( )，則從二進(jìn)制編碼到Gray編碼的變換為:n?,21????????kk??1由于Gray編碼的鄰近兩個(gè)數(shù)之間的海明距離短的特點(diǎn)，所以使得算法從近似最優(yōu)解逼近全局最優(yōu)解的代價(jià)減少，有利于提高遺傳算法朝全局最優(yōu)解的逼近能力，便于對(duì)連續(xù)的函數(shù)進(jìn)行局部空間的搜索。? 實(shí)數(shù)編碼對(duì)于一些問(wèn)題的表現(xiàn)形式是實(shí)向量的情形，如果使用二進(jìn)制編碼機(jī)制，會(huì)存在效率低下，無(wú)法控制算