基于遺傳算法的配送路徑優(yōu)化研究開題報告

1、北京師范大學(xué)珠海分校 本科生畢業(yè)論文（設(shè)計）開題報告 學(xué)生姓名 邱俊杰 學(xué) 號0411010209所在院系 物流學(xué)院 專業(yè)物流管理指導(dǎo)教師姓名 鄧小瑜指導(dǎo)教師職稱 講 師指導(dǎo)教師單位物流學(xué)院畢業(yè)論文題目基于遺傳算法 的配送路徑優(yōu)化研究 開題報告內(nèi)容選題依據(jù)（選題 經(jīng)過，國內(nèi)、 國外研究現(xiàn) 狀，初步設(shè) 想及創(chuàng) 新點 等）選題經(jīng)過：通過在大學(xué)四年里對物流知識的學(xué)習(xí)， 讓我對物流企業(yè)的運作和管理有了一定程度的了解和認識。目前，我國很大一部分運輸企業(yè)和物流企業(yè)是采用人工操作方式來對配送車輛進行調(diào)度安排和行車線路的規(guī)劃。 這種依賴人工經(jīng)驗來調(diào)度車輛的方式，不僅會導(dǎo)致企業(yè)運 輸資源浪費運輸成本提高，而且也

2、難以滿足客戶越來越多樣性和不規(guī)則性的需求。在北師大珠海分校學(xué)習(xí)的這四年里，我還輔修了信息技術(shù)學(xué)院的軟件工程”學(xué)位課程，因此，希望在我 畢業(yè)論文設(shè)計中，能結(jié)合自己在程序設(shè)計方面所 學(xué)到的知識，應(yīng)用現(xiàn)代數(shù)學(xué)方法及計算機技術(shù)來求解物流配送路徑優(yōu)化問題。國內(nèi)外研究現(xiàn)狀：配送路徑優(yōu)化問題屬于強NP難題。國外對配送路徑優(yōu)化問題的研究始于50年代末，目前在理論研究和實際應(yīng)用兩方面都已取得了比較 顯著的成果。隨著研究的深入發(fā)展，如何使研究的理論模型 更貼近現(xiàn)實中的運 輸規(guī)劃問題開始成為研究者們關(guān)注的焦 點。而國內(nèi)相關(guān)研究人員對旅行商問題的理論研究較多，對配送路徑優(yōu)化問題 的研究在90年代以后才逐漸起步，比國外

3、相對落后。這幾年來我國已有越來越多的研究人員開始關(guān)注車輛路徑問題題的解決方法，也己取得了一定的成果 但總體來說，我國目前對車輛路徑問題的理論研究仍相對匾 乏，有待進一步發(fā) 展。初步設(shè)想：配送路徑優(yōu)化問題又叫 做車輛調(diào)度問題 VPR(Vehicle Routing Problem)，包含了配 送車輛安排和每輛車行駛線路規(guī)劃兩個方面。本論文首先 將對一定條件下的配送路徑優(yōu)化問題建立數(shù)學(xué)模型，然后用 經(jīng)過改良的遺傳算 法對該模型進行求解。整個算法會用JAVA語言編寫一個桌面應(yīng)用程序來實現(xiàn)。論文中會詳細闡述數(shù)學(xué)模型建立思路以及算法求解該模型的整個流程，并簡要 介紹一下程序設(shè)計、實現(xiàn)的思路與步驟。還會對

4、用語言實現(xiàn)的遺傳算法 在求解不同規(guī)模的 VPR問題時的性能進行分析。論文的最后會總結(jié)一下算法的局限性并對未 來的研究方向做個展望。 理論和實踐的意義及可行性 論 述(包括文獻 綜述) 理論和實踐的意義：當(dāng)前，現(xiàn)代物流是企業(yè)繼續(xù)降低物資消耗、提高勞動生產(chǎn)率后的第三利潤源泉。但我國物流企業(yè)的運輸成本普遍偏高。其中很重 要一個 原因就是對配送車輛運輸路線規(guī)劃不科學(xué)。要想降 低運輸成本，離不開對配送路線的優(yōu)化和配送車輛的合理安排。對物流配送車輛行駛路徑進行優(yōu)化，可以降低物流成本，節(jié)約運輸時間，是提高物流經(jīng)濟效益的有效手段。 可行性論述：配送路徑優(yōu)化問題是典型的優(yōu)化組合問題，具有 很高的計算復(fù)雜 性。但

5、遺傳算法解決作為一種有效的全局 搜索方法具有隱并行性和較強的魯棒性，在解決非線性的大規(guī)模復(fù)雜問題上具有很好的適應(yīng)性，適合于對VPR問 題進行優(yōu)化求解。標準遺傳算法雖然未必每次都能找到最優(yōu) 解，但通過對標準 遺傳算法進行改進，完全可以在有限時 間內(nèi)對較復(fù)雜的 VPR問題計算出次優(yōu) 解或可行解。因此， 用遺傳算法來解決物流車輛調(diào)度問題還是完全可行的。文獻綜述：1朱劍英.非經(jīng)典數(shù)學(xué)方法M.武昌：華中科技大 學(xué)出版社，2001 2李敏強，寇紀淞，林丹，李書全 遺傳算 法的基本理論與應(yīng)用M.北京：科 學(xué)技術(shù)出版社，2002 3 孫麗麗.物流配送中車輛路徑算法分析與研究D.上海：上海海事大學(xué)，2007 4

6、蓋杉.基于遺傳算法的物流配送調(diào)度系 統(tǒng)D.長春：長春理工大學(xué)，2007 5高運良，基于免疫遺傳算法的物流配送 VRP求解D.武漢：武漢科技大學(xué)，2007 閻慶，邰蕾蕾.用混合遺傳算法解決有時間窗的車輛路徑 規(guī)劃問題J.安徽 大學(xué)學(xué)報，2007(2) 7張海剛，顧幸生. 基于混合免疫遺傳算法的車輛調(diào)度問題J.微電子學(xué)與計算機，2007(1)論文撰寫過 程中擬采取 的方法和手 段 本論 文主要采用遺傳算法作為解決物流配送路徑優(yōu)化問題的主 要算法。但 由于標準遺傳算法具有早熟收斂”的缺陷，有可能使算法陷入局部最優(yōu)解。論文還將嘗試通過把其他算法和遺傳算法相結(jié)合，來有效控制早熟現(xiàn)象的發(fā)生。為了快速得到任

7、意兩個配送點之間的最優(yōu)路線。本論文還擬采用佛 洛依德 算法構(gòu)造配送路線的地理數(shù)據(jù)庫的方式來對路線網(wǎng) 絡(luò)進行預(yù)處理。從而減少整個算法的時間復(fù)雜度和空間復(fù)雜度。論文撰寫 提 綱一、緒論1.研究的背景和意義 2. 問題描述3.國內(nèi)外相關(guān)研究狀況二、遺傳算法基礎(chǔ)1. 標準遺傳算法的基本原理2.標準遺傳算法的早熟現(xiàn)象3.遺傳算法的改進 三、配送路徑問題數(shù)學(xué)模型的設(shè)計和求解 1.配送路徑優(yōu)化問題數(shù)學(xué)模型的設(shè)計2.求解該數(shù)學(xué)模型的遺傳算法設(shè)計四、基于遺傳算法的車輛調(diào)度問題實現(xiàn)1.需求分析2.程序設(shè)計3.程序?qū)崿F(xiàn) 五、程序運行結(jié)果分 析1.實驗數(shù)據(jù)來源 2.實驗結(jié)果分析 3.程序性能評估 六、結(jié)束語1.算法和程序的局限性2.結(jié)論及展望 計劃進度 2009 年11月01日2009 年11月30日：查找 及收集資料 2009年12月01日 2010年12月31 日：研究算法和建立數(shù)學(xué)模型2010年01月01 日2010年1月31日：編寫程序?qū)崿F(xiàn)，運行實驗數(shù)據(jù)2010年02月01日 2010年02月25 日 :撰寫畢業(yè) 論文 2010 年02月26日 2010 年02月26日：提交 初稿2010年02月27日2010年04月11日：和導(dǎo) 師討論，并修改論文2010年04月12日