本文關(guān)鍵詞：基于淘汰機(jī)制的果蠅優(yōu)化算法求解車輛路徑問題

  更多相關(guān)文章： 車輛路徑問題 群智能 果蠅優(yōu)化算法 旅行商問題 淘汰機(jī)制 算子

【摘要】：近些年來,隨著社會(huì)節(jié)奏的加速、電子商務(wù)的蓬勃發(fā)展以及各大O2O平臺(tái)的異軍突起,越來越多的人開始選擇網(wǎng)上購物、網(wǎng)上訂餐,作為這些活動(dòng)中的重要環(huán)節(jié),物流開始在現(xiàn)實(shí)社會(huì)中扮演越來越重要的角色,但與之而來的則是物流代價(jià)的不斷增加,因此,如何有效的減少物流代價(jià),越來越成為人們關(guān)注的熱點(diǎn)問題。在現(xiàn)實(shí)生活中,整個(gè)物流活動(dòng)包括運(yùn)輸、儲(chǔ)存、裝卸、包裝、流通加工、配送、信息處理等基本過程。根據(jù)相關(guān)統(tǒng)計(jì),在整個(gè)物流成本中,配送成本所占比例約為53%,占比超過一半,因此,減少物流代價(jià)的關(guān)鍵在于減少配送代價(jià)。車輛路徑問題(VRP)正是對(duì)物流配送活動(dòng)的抽象,該問題是一個(gè)組合優(yōu)化問題,也是一個(gè)典型的NP難問題,由Dantzing和Ramser兩位科學(xué)家于1959年首次提出。目前求解VRP問題主要有兩類方法:一類是可以求得確切解的精確算法,例如動(dòng)態(tài)規(guī)劃法、分支限定法、線性規(guī)劃法等;另一類是可以在較短時(shí)間內(nèi)求得近似最優(yōu)解的啟發(fā)式算法,例如禁忌搜索算法、遺傳算法、蟻群算法等。果蠅優(yōu)化算法是臺(tái)灣學(xué)者潘文超根據(jù)果蠅覓食行為于2011年提出的一種新的群智能算法,該算法易于理解、實(shí)現(xiàn)簡單,而且果蠅的嗅覺搜索過程對(duì)于解空間具有很好的擴(kuò)展能力,但是果蠅的視覺搜索過程很容易使算法陷入局部最優(yōu)。在充分研究了果蠅算法的優(yōu)缺點(diǎn)之后,本文提出了一種改進(jìn)的果蠅優(yōu)化算法,并將其用于求解旅行商問題(TSP)和VRP問題,最后在相關(guān)數(shù)據(jù)集上進(jìn)行了仿真實(shí)驗(yàn),證明了算法的可行性和有效性。本文的主要工作有以下幾點(diǎn):(1)介紹了VRP問題的研究背景與意義,VRP問題的描述、數(shù)學(xué)模型及其分類,以及該問題的國內(nèi)外研究現(xiàn)狀。(2)充分研究了果蠅優(yōu)化算法的基本原理,并基于該算法提出了一種改進(jìn)的果蠅優(yōu)化算法。改進(jìn)后的算法加強(qiáng)了果蠅的視覺搜索能力,在其他果蠅向最優(yōu)果蠅靠近的過程中,是緩慢的向最優(yōu)果蠅靠近,而不是立刻到達(dá)最優(yōu)果蠅所在的位置,這樣就有效的減小了算法陷入局部最優(yōu)的可能性。同時(shí),改進(jìn)后的算法還引入了淘汰機(jī)制,在算法的每次迭代過程中,會(huì)淘汰掉一部分表現(xiàn)較差的個(gè)體,并隨機(jī)的加入相同數(shù)量的新的個(gè)體,這樣就有效的增加了種群的多樣性,增強(qiáng)了算法對(duì)于解空間的擴(kuò)展能力。(3)利用改進(jìn)的果蠅優(yōu)化算法求解TSP問題。在求解過程中,定義了兩個(gè)算子:逆序算子和乘法算子,分別用于模擬果蠅在嗅覺搜索過程中對(duì)于解空間的拓展和在視覺定位過程中向最優(yōu)解的靠近。并且用TSPLIB中的10個(gè)基準(zhǔn)數(shù)據(jù)集對(duì)于改進(jìn)后的果蠅優(yōu)化算法進(jìn)行了仿真實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果證明了算法的可行性和有效性。(4)利用改進(jìn)后的果蠅優(yōu)化算法求解VRP問題。詳細(xì)介紹了求解過程中的種群初始化、嗅覺搜索以及視覺搜索過程,并且在兩組標(biāo)準(zhǔn)數(shù)據(jù)集上進(jìn)行了仿真實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果證明了算法的可行性和有效性。
【學(xué)位授予單位】：吉林大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：F724.6;TP18

【相似文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前10條

1 任慶生,葉中行,曾進(jìn);進(jìn)化算法的收斂速度[J];上海交通大學(xué)學(xué)報(bào);1999年06期

2 唐浩;;蟻群算法的研究與展望[J];牡丹江教育學(xué)院學(xué)報(bào);2009年06期

3 鄧小波;曹聰聰;龍倫海;康耀紅;;蟻群算法搜索熵研究[J];海南大學(xué)學(xué)報(bào)(自然科學(xué)版);2007年04期

4 張康;顧幸生;;全局組搜索優(yōu)化算法及其應(yīng)用研究[J];青島科技大學(xué)學(xué)報(bào)(自然科學(xué)版);2012年05期

5 李東曉;蔣珉;柴干;;蟻群算法優(yōu)化及其在高速公路緊急救援中的應(yīng)用[J];計(jì)算機(jī)技術(shù)與發(fā)展;2010年11期

6 _5文龍 ,黃，

本文編號(hào)：1280497