【正文】 ”算法，從解空間的某個(gè)解出發(fā)搜索當(dāng)前解的鄰域，如果某個(gè)鄰近解比當(dāng)前解更優(yōu)，則用此鄰近解取代當(dāng)前解，然后繼續(xù)搜索直至滿足搜索停止條件。(二)改進(jìn)啟發(fā)式算法所有的改進(jìn)啟發(fā)式方法的優(yōu)化流程都采用“鄰域搜索”的方式。每一種方法討論的情況不盡一致，適用范圍也不完全相同。一些基于數(shù)學(xué)規(guī)劃的算法也屬于兩階段法，把問題直接描述成一個(gè)數(shù)學(xué)規(guī)劃問題，根據(jù)其模型的特殊構(gòu)形，應(yīng)用一定的技術(shù)(如分解)進(jìn)行分劃，進(jìn)而求解己被廣泛研究過的子問題。2）掃描算法這個(gè)算法的起源可以追溯到1971年Wren和Wren and Hollieday的論文，它假設(shè)有一個(gè)車庫(kù)或者幾個(gè)車庫(kù)，點(diǎn)(顧客)坐落在歐基里德平面上，由極坐標(biāo)來表示每個(gè)點(diǎn)(顧客)的位置(β i,ρ i)，從β i=0的任意一點(diǎn)i’開始，隨著角度的增加把一些顧客包括進(jìn)一條路線，保持車的容量不被超過。這個(gè)方法開始假設(shè)每條路線包括車庫(kù)和一個(gè)另外的點(diǎn)(顧客)，每一步按照最大節(jié)省費(fèi)用原則合并兩條路線。在過去的較長(zhǎng)時(shí)間內(nèi)，大多數(shù)研究者對(duì)帶有時(shí)間窗的車輛路徑問題的研究集中在用精確算法尋求最優(yōu)解的方向上，不過這種情況沒有持續(xù)多久，在隨后出現(xiàn)的大規(guī)模問題上，這些方法都存在“組合爆炸”的問題，求解時(shí)間隨著問題規(guī)模成指數(shù)級(jí)增長(zhǎng)。Fisher(1994)把解VRP的1樹方法擴(kuò)展為K一樹方法。采用拉格朗日分解和分枝定界的組合方法，能夠有效求解規(guī)模不超過100個(gè)顧客問題。主要的VRPTW問題的精確算法可分為如下幾種:1)動(dòng)態(tài)規(guī)劃法。在實(shí)際情況中，軟時(shí)間窗的車輛路徑問題更加常見，也更加符合實(shí)際，因此本文研究的時(shí)間窗主要是指軟時(shí)間窗。這是為了適應(yīng)消費(fèi)需要變得多樣化、個(gè)性化而建立的一種生產(chǎn)體系及為此生產(chǎn)體系服務(wù)的物流體系。一方面，汽車可以在時(shí)刻 之前到達(dá)該客戶所在地，但它必須等待直到 才可以為該客戶服ia ia務(wù)，并且不允許遲于 到達(dá)。4)隨機(jī)VRP(SVRP)。每輛汽車的運(yùn)行時(shí)間由汽車在客戶間的行駛時(shí)間和汽車為客戶服務(wù)的時(shí)間所構(gòu)成。車輛路徑問題(Vehicle Routing Problem,簡(jiǎn)稱VRP)是指:給定一個(gè)配送中心點(diǎn)(中心車庫(kù)，central depot),一個(gè)車輛集合和一個(gè)顧客集合，車輛和顧客各有自己的屬性，每輛車都有車的容量，所裝載貨物不能超過它的車的容量，起初車輛都在配送中心車庫(kù)，顧客任意分布，車把貨物從配送中心車庫(kù)運(yùn)送到每一個(gè)顧客(或從每個(gè)顧客處把貨物運(yùn)到配送中心車庫(kù))，要求滿足顧客的需求，車輛最后返回車庫(kù)，每個(gè)顧客只能被服務(wù)一次，設(shè)計(jì)車輛旅行路徑使運(yùn)輸總費(fèi)用最小 [10]。第三章 帶有時(shí)間窗的車輛路徑問題的算法回顧 帶有時(shí)間窗的車輛路徑問題的概念和研究現(xiàn)狀為了更好地完成配送，實(shí)現(xiàn)配送中心的目標(biāo)，不僅需要關(guān)注選用合理的運(yùn)輸服務(wù)，而且還需要根據(jù)已知的車輛狀況、客戶送貨時(shí)間需求，選擇一種合適的路線方案。 便利性的實(shí)現(xiàn)更多地體現(xiàn)在對(duì)配送系統(tǒng)的技術(shù)要求上，目前，在配送系統(tǒng)中廣泛采用先進(jìn)的信息處理技術(shù)、通信技術(shù)、定位技術(shù)等輔助手段，幫助操作人員及時(shí)響應(yīng)客戶的要求。在配送之前，快速準(zhǔn)確地驗(yàn)貨，配送前的加工，貨物的包裝，貨物的裝卸，任何一個(gè)環(huán)節(jié)都體現(xiàn)配送系統(tǒng)的技術(shù)水平和管理能力。但是，具體到一個(gè)實(shí)際的配送中心的工作狀況，任何細(xì)小環(huán)節(jié)的失誤都會(huì)在過程中不斷被放大，對(duì)最終的結(jié)果產(chǎn)生很大的影響。為了確保下游物流活動(dòng)的順利進(jìn)行，及時(shí)有效的送貨是極其重要的要求，也是任何一個(gè)配送系統(tǒng)必須承諾的。 配送的評(píng)估指標(biāo)配送是整個(gè)物流過程最末端的環(huán)節(jié)，車輛配送是物流中心作業(yè)最終及最具體的服務(wù)表征。此外，采用集中庫(kù)存可利用規(guī)模經(jīng)濟(jì)的優(yōu)勢(shì)，使單位存貨成本下降。4）通過集中庫(kù)存使企業(yè)實(shí)現(xiàn)低庫(kù)存或零庫(kù)存 實(shí)現(xiàn)了高水平的配送之后，尤其是采取 JIT 配送方式之后，生產(chǎn)企業(yè)可以完全依靠配送中心的準(zhǔn)時(shí)配送而不需保持自己的庫(kù)存。但是，在所有的干線運(yùn)輸之后，往往都要輔以支線運(yùn)輸和小搬運(yùn)，這種支線運(yùn)輸及小搬運(yùn)成了物流過程的一個(gè)薄弱環(huán)節(jié)。但是，配送的主體活動(dòng)與一般物流卻有不同，一般物流是運(yùn)輸及保管，而配送則是運(yùn)輸及分揀配貨，分揀配貨是配送的獨(dú)特要求，也是配送中有特點(diǎn)的活動(dòng)，以送貨為目的的運(yùn)輸則是最后實(shí)現(xiàn)配送的主要手段，從這一主要手段出發(fā)，常常將配送簡(jiǎn)化地看成運(yùn)輸中的一種。但是在配送過程中，也包含著其他的物流功能，如裝卸、儲(chǔ)存、包裝等?？梢?，有效的物流管理有利于社會(huì)商品價(jià)格水平的降低。只有這樣，才能使交換功能得以發(fā)揮。商品生產(chǎn)的目的就是為了交換，是為他人生產(chǎn)的。當(dāng)然，批發(fā)商業(yè)的專業(yè)化服務(wù)使得大批量的買賣成為可能，促使市場(chǎng)的范圍不斷擴(kuò)大，也使消費(fèi)品生產(chǎn)供應(yīng)上的“時(shí)” 、 “空”矛盾得以解決，商品流通速度加快，促使社會(huì)經(jīng)濟(jì)的發(fā)展。同時(shí)，針對(duì)客戶的不同要求優(yōu)化物流管理系統(tǒng)，以適應(yīng)用戶的特殊要求。物流管理已成為當(dāng)今企業(yè)最具挑戰(zhàn)性的領(lǐng)域之一。但由于科學(xué)技術(shù)手段越來越先進(jìn)，使得大多數(shù)產(chǎn)品很容易被仿制。那么，如何通過物流獲得競(jìng)爭(zhēng)優(yōu)勢(shì)呢? 帶有時(shí)間窗的車輛路徑問題的優(yōu)化研究81）成本領(lǐng)先 其優(yōu)勢(shì)直接來源于產(chǎn)品和服務(wù)的低成本。2）空間效用——產(chǎn)品通過在特定地點(diǎn)服務(wù)于消費(fèi)者，給消費(fèi)者帶來的效用。物流與商流的結(jié)合構(gòu)成了整個(gè)流通。根據(jù)實(shí)際需要，將運(yùn)輸、存儲(chǔ)、裝卸、搬運(yùn)、包裝、流通加工、配送、信息處理等基本功能實(shí)現(xiàn)有機(jī)結(jié)合 [4]。 日本后勤系統(tǒng)協(xié)會(huì)將物流改稱后勤，并且該協(xié)會(huì)名稱中的“后勤系統(tǒng)”幾個(gè)字并沒有翻譯成日文漢字，而是直接用注音。第二次世界大戰(zhàn)后，這套后勤補(bǔ)給理論、方法也為企業(yè)和理論界認(rèn)同，并廣泛運(yùn)用起來，他們將其稱為商業(yè)物流或銷售物流(Business Logistics)，以力求合理有效地組織商品的供應(yīng)、保管、運(yùn)輸、配送，而且實(shí)踐證明取得了相當(dāng)大的成效。4）運(yùn)用改進(jìn)的遺傳算子求解模型。利用遺傳算法的原理和其特殊優(yōu)勢(shì)，為帶有時(shí)間窗的車輛路徑問題的求解提供一個(gè)切實(shí)可行的算子設(shè)計(jì)，求得一個(gè)較優(yōu)的可行解，并說明其有效性。 本文研究的內(nèi)容及技術(shù)路線國(guó)內(nèi)外絕大多數(shù)關(guān)于VRPTW的研究都集中在算法創(chuàng)新，目的是獲得更接近最優(yōu)解的近似解，致使物流費(fèi)用降低。有效地解決帶有時(shí)間窗的車輛路徑問題，不僅可以能夠提高物流工作效率，而且能夠?yàn)榧皶r(shí)生產(chǎn)(JIT)模式的企業(yè)提供運(yùn)輸上的保障，從而實(shí)現(xiàn)物流管理科學(xué)化。3）國(guó)內(nèi)外研究中存在的問題? 著重啟發(fā)式算法研究，模型研究成果比較多，但多目標(biāo)模型研究還不夠完善。JORG HOMBERGER AND HERMANN GEHRING 在《TWO EVOLUTIONARY METAHEURISTICS FOR THE VEHICLE ROUTING PROBLEMB WITH TIME WINDOWS 》中運(yùn)用了兩種進(jìn)化策略來解決車輛路徑問題，并充分利用了META啟發(fā)技術(shù)。2）國(guó)外研究現(xiàn)狀國(guó)外關(guān)于車輛路徑問題的研究較早，最初由Dantzig和Ramser于1959年首先提出的，很快引起運(yùn)籌學(xué)、應(yīng)用數(shù)學(xué)、組合數(shù)學(xué)、網(wǎng)絡(luò)分析、圖論、計(jì)算機(jī)應(yīng)用等學(xué)科的專家與運(yùn)輸計(jì)劃制定者和管理者的極大重視，他們進(jìn)行了大量的理論研究及試驗(yàn)分析，取得了很大進(jìn)展。通過中國(guó)期刊數(shù)據(jù)庫(kù)檢索，1994～2022 年12年時(shí)間，在中國(guó)的正式期刊上已經(jīng)發(fā)表該領(lǐng)域的文章僅二十多篇。在這種嚴(yán)峻的形勢(shì)下，大力推進(jìn)現(xiàn)代物流產(chǎn)業(yè)發(fā)展，降低運(yùn)輸成本，增強(qiáng)物流環(huán)節(jié)的服務(wù)質(zhì)量，是提高物流效率的迫切需要。據(jù)統(tǒng)計(jì)，各國(guó)運(yùn)輸成本占國(guó)民生產(chǎn)總值的10%~ 15%左右 [1]。世界各國(guó)都已經(jīng)意識(shí)到物流的重要性，尤其是在工業(yè)發(fā)達(dá)國(guó)家，物流管理與物流技術(shù)己經(jīng)得到了廣泛的應(yīng)用與發(fā)展，包括生產(chǎn)、流通、消費(fèi)等過程諸環(huán)節(jié)的物流系統(tǒng)，已成為適合于市場(chǎng)經(jīng)濟(jì)發(fā)展的基礎(chǔ)產(chǎn)業(yè)之一。在求解的過程中，根據(jù)自然數(shù)編碼的特點(diǎn)，對(duì)遺傳算法的三個(gè)算子——選擇、交叉、變異進(jìn)行了特別設(shè)計(jì)，最終得出了模型的解。在配送運(yùn)輸上，時(shí)間窗口顯得越來越重要。現(xiàn)代物流作為一種先進(jìn)的組織方式和管理技術(shù)，被廣泛認(rèn)為是企業(yè)在降低物資消耗，提高勞動(dòng)生產(chǎn)率以外的重要的利潤(rùn)源泉，在國(guó)民經(jīng)濟(jì)和社會(huì)發(fā)展中發(fā)揮著重要作用。作者簽名： 日期： 年 月 日學(xué)位論文版權(quán)使用授權(quán)書本學(xué)位論文作者完全了解學(xué)校有關(guān)保留、使用學(xué)位論文的規(guī)定，同意學(xué)校保留并向國(guó)家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和電子版，允許論文被查閱和借閱。作者簽名：　　 　 　　 日　 期：　　 　 　　 學(xué)位論文原創(chuàng)性聲明本人鄭重聲明：所呈交的論文是本人在導(dǎo)師的指導(dǎo)下獨(dú)立進(jìn)行研究所取得的研究成果。畢業(yè)設(shè)計(jì)（論文）原創(chuàng)性聲明和使用授權(quán)說明原創(chuàng)性聲明本人鄭重承諾：所呈交的畢業(yè)設(shè)計(jì)（論文） ，是我個(gè)人在指導(dǎo)教師的指導(dǎo)下進(jìn)行的研究工作及取得的成果。作 者 簽 名：　　 　 　　 日　 期：　　 　 　　 指導(dǎo)教師簽名：　　 　 　　 日 　　期：　　 　 　　 使用授權(quán)說明本人完全了解 大學(xué)關(guān)于收集、保存、使用畢業(yè)設(shè)計(jì)（論文）的規(guī)定，即：按照學(xué)校要求提交畢業(yè)設(shè)計(jì)（論文）的印刷本和電子版本；學(xué)校有權(quán)保存畢業(yè)設(shè)計(jì)（論文）的印刷本和電子版，并提供目錄檢索與閱覽服務(wù)；學(xué)校可以采用影印、縮印、數(shù)字化或其它復(fù)制手段保存論文；在不以贏利為目的前提下，學(xué)?？梢怨颊撐牡牟糠只蛉?jī)?nèi)容。本人完全意識(shí)到本聲明的法律后果由本人承擔(dān)。作者簽名： 日期： 年 月 日導(dǎo)師簽名： 日期： 年 月 日指導(dǎo)教師評(píng)閱書指導(dǎo)教師評(píng)價(jià)：一、撰寫（設(shè)計(jì)）過程學(xué)生在論文（設(shè)計(jì)）過程中的治學(xué)態(tài)度、工作精神□ 優(yōu) □ 良 □ 中 □ 及格 □ 不及格學(xué)生掌握專業(yè)知識(shí)、技能的扎實(shí)程度□ 優(yōu) □ 良 □ 中 □ 及格 □ 不及格學(xué)生綜合運(yùn)用所學(xué)知識(shí)和專業(yè)技能分析和解決問題的能力□ 優(yōu) □ 良 □ 中 □ 及格 □ 不及格研究方法的科學(xué)性；技術(shù)線路的可行性；設(shè)計(jì)方案的合理性□ 優(yōu) □ 良 □ 中 □ 及格 □ 不及格完成畢業(yè)論文（設(shè)計(jì)）期間的出勤情況□ 優(yōu) □ 良 □ 中 □ 及格 □ 不及格二、論文（設(shè)計(jì)）質(zhì)量論文（設(shè)計(jì)）的整體結(jié)構(gòu)是否符合撰寫規(guī)范？□ 優(yōu) □ 良 □ 中 □ 及格 □ 不及格是否完成指定的論文（設(shè)計(jì)）任務(wù)（包括裝訂及附件）？□ 優(yōu) □ 良 □ 中 □ 及格 □ 不及格三、論文（設(shè)計(jì)）水平論文（設(shè)計(jì)）的理論意義或?qū)鉀Q實(shí)際問題的指導(dǎo)意義□ 優(yōu) □ 良 □ 中 □ 及格 □ 不及格論文的觀念是否有新意？設(shè)計(jì)是否有創(chuàng)意？□ 優(yōu) □ 良 □ 中 □ 及格 □ 不及格論文（設(shè)計(jì)說明書）所體現(xiàn)的整體水平□ 優(yōu) □ 良 □ 中 □ 及格 □ 不及格建議成績(jī)：□ 優(yōu) □ 良 □ 中 □ 及格 □ 不及格（在所選等級(jí)前的□內(nèi)畫“√”）指導(dǎo)教師： （簽名） 單位： （蓋章）年 月 日評(píng)閱教師評(píng)閱書評(píng)閱教師評(píng)價(jià)：一、論文（設(shè)計(jì)）質(zhì)量論文（設(shè)計(jì)）的整體結(jié)構(gòu)是否符合撰寫規(guī)范？□ 優(yōu) □ 良 □ 中 □ 及格 □ 不及格是否完成指定的論文（設(shè)計(jì)）任務(wù)（包括裝訂及附件）？□ 優(yōu) □ 良 □ 中 □ 及格 □ 不及格二、論文（設(shè)計(jì)）水平論文（設(shè)計(jì)）的理論意義或?qū)鉀Q實(shí)際問題的指導(dǎo)意義□ 優(yōu) □ 良 □ 中 □ 及格 □ 不及格論文的觀念是否有新意？設(shè)計(jì)是否有創(chuàng)意？□ 優(yōu) □ 良 □ 中 □ 及格 □ 不及格論文（設(shè)計(jì)說明書）所體現(xiàn)的整體水平□ 優(yōu) □ 良 □ 中 □ 及格 □ 不及格建議成績(jī)：□ 優(yōu) □ 良 □ 中 □ 及格 □ 不及格（在所選等級(jí)前的□內(nèi)畫“√”）評(píng)閱教師： （簽名） 單位： （蓋章）年 月 日帶有時(shí)間窗的車輛路徑問題的優(yōu)化研究V教研室（或答辯小組）及教學(xué)系意見教研室（或答辯小組）評(píng)價(jià)：一、答辯過程畢業(yè)論文（設(shè)計(jì)）的基本要點(diǎn)和見解的敘述情況□ 優(yōu) □ 良 □ 中 □ 及格 □ 不及格對(duì)答辯問題的反應(yīng)、理解、表達(dá)情況□ 優(yōu) □ 良 □ 中 □ 及格 □ 不及格學(xué)生答辯過程中的精神狀態(tài)□ 優(yōu) □ 良 □ 中 □ 及格 □ 不及格二、論文（設(shè)計(jì)）質(zhì)量論文（設(shè)計(jì)）的整體結(jié)構(gòu)是否符合撰寫規(guī)范？□ 優(yōu) □ 良 □ 中 □ 及格 □ 不及格是否完成指定的論文（設(shè)計(jì)）任務(wù)（包括裝訂及附件）？□ 優(yōu) □ 良 □ 中 □ 及格 □ 不及格三、論文（設(shè)計(jì)）水平論文（設(shè)計(jì)）的理論意義或?qū)鉀Q實(shí)際問題的指導(dǎo)意義□ 優(yōu) □ 良 □ 中 □ 及格 □ 不及格論文的觀念是否有新意？設(shè)計(jì)是否有創(chuàng)意？□ 優(yōu) □ 良 □ 中 □ 及格 □ 不及格論文（設(shè)計(jì)說明書）所體現(xiàn)的整體水平□ 優(yōu) □ 良 □ 中 □ 及格 □ 不及格評(píng)定成績(jī)：□