亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        基于快速排序和遺傳算法的物流路徑優(yōu)化研究

        2016-12-13 06:53:38陳疇鏞鄭冬冬
        生產(chǎn)力研究 2016年11期
        關(guān)鍵詞:物流配送復(fù)雜度適應(yīng)度

        陳疇鏞,鄭冬冬

        (杭州電子科技大學(xué)管理學(xué)院,浙江杭州310018)

        基于快速排序和遺傳算法的物流路徑優(yōu)化研究

        陳疇鏞,鄭冬冬

        (杭州電子科技大學(xué)管理學(xué)院,浙江杭州310018)

        為了使企業(yè)處理物流配送問(wèn)題更加高效、節(jié)約經(jīng)濟(jì)成本和時(shí)間、以及獲得更多的利潤(rùn),則建立物流配送路徑問(wèn)題數(shù)學(xué)模型,在約束條件中增加配送車輛和貨物數(shù)量,在遺傳算法選擇操作中引入快速排序算法降低時(shí)間復(fù)雜度;使用M atlab工具和C語(yǔ)言對(duì)數(shù)學(xué)模型仿真,實(shí)驗(yàn)結(jié)果顯示,引入快速排序算法的遺傳算法,不僅能得到物流路徑問(wèn)題的最優(yōu)解,而且降低了時(shí)間復(fù)雜度,提高了配送效率、節(jié)約了時(shí)間。

        物流配送;路徑優(yōu)化;快速排序;遺傳算法;時(shí)間復(fù)雜度

        一、引言

        從數(shù)學(xué)角度分析,物流配送路徑優(yōu)化是指,貨車從起點(diǎn)(配送中心)出發(fā),向需求點(diǎn)運(yùn)送貨物,其中已明確的條件是任意需求點(diǎn)所要求的數(shù)量、地理位置、車輛最大承重、最長(zhǎng)路程,獲得送貨的最佳路線。

        遺傳算法是在處理面對(duì)眾多送貨路線抉擇出最佳方案的方法當(dāng)中使用更為廣泛。美國(guó)的J.H.Holland教授最早構(gòu)想遺傳算法(Genetic Algorithm,GA)。最近幾年,遺傳算法不斷地發(fā)展,H.C.W.Lau認(rèn)為遺傳算法是解決多個(gè)倉(cāng)庫(kù)、多個(gè)需求點(diǎn)、多個(gè)物品車輛配送路徑優(yōu)化問(wèn)題的較好方法,通過(guò)模糊邏輯指導(dǎo)遺傳算法關(guān)于處理貨車行駛路線獲得最優(yōu)解[1]。姜大立認(rèn)為遺傳算法是解決車輛路徑優(yōu)化問(wèn)題的一個(gè)較好方案,構(gòu)建了經(jīng)典的數(shù)學(xué)模型,利用遺傳算法和染色體,以及針對(duì)向量采取了可行化影射[2]。郎茂祥認(rèn)為遺傳算法是解決復(fù)雜難題較好的方法,構(gòu)造包括對(duì)個(gè)體編碼、個(gè)體適應(yīng)值計(jì)算及選擇、交叉和變異,以此獲得物流配送路徑的滿意解[3]。張迅認(rèn)為遺傳算法使用比較靈活,具有較強(qiáng)的收斂性和穩(wěn)定性,特別是關(guān)于快遞配送問(wèn)題的處理如何分配車輛到各需求點(diǎn)送取貨,是一個(gè)很好的解決方法[4]。郭賽克通過(guò)對(duì)遺傳算法進(jìn)行設(shè)計(jì)、編程和數(shù)據(jù)仿真研究,以及多次測(cè)試,驗(yàn)證了遺傳算法的優(yōu)越性[5]??傮w而言,遺傳算法在物流配送領(lǐng)域使用廣泛,具有隨機(jī)性、全局性的特點(diǎn),可以求得滿意解,能夠解決復(fù)雜問(wèn)題。但是遺傳算法也有明顯的缺陷,它所具有的全局搜索性、迭代性,自由空間大,隨機(jī)選擇,也導(dǎo)致了運(yùn)算次數(shù)和時(shí)間復(fù)雜度高[6]。設(shè)計(jì)計(jì)算簡(jiǎn)便、時(shí)間復(fù)雜度低的遺傳算法,能提高物流處理速度,對(duì)于企業(yè)節(jié)省經(jīng)濟(jì)成本具有重要的意義。

        二、物流配送路徑優(yōu)化的數(shù)學(xué)模型

        物流配送路徑優(yōu)化問(wèn)題是指:以配送中心為起點(diǎn),使用車輛向需求點(diǎn)送貨,當(dāng)車輛將貨物送到目地的時(shí),則返回起點(diǎn),且等待下一次運(yùn)送,需求點(diǎn)的所要求數(shù)量是已知的,需求點(diǎn)的地理位置是確定的,車輛具有最大的承載量和行駛最長(zhǎng)距離。目標(biāo)為總距離最短,總距離指車輛往返的長(zhǎng)度,約束條件為:(1)全部車輛只從僅存在的一個(gè)配送中心點(diǎn)出發(fā);(2)起點(diǎn)具有充沛的貨物和足夠的貨車可以進(jìn)行調(diào)度;(3)每輛車不容許超出最大承載量運(yùn)行;(4)每輛車不允許超出限定的最長(zhǎng)路程;(5)每一送貨點(diǎn)的配送僅指派一輛車;(6)需求點(diǎn)所要求的數(shù)量和地理位置是確定的;(7)起點(diǎn)和需求點(diǎn)間的路程是已知的;(8)配送必須滿足需求點(diǎn)所要求的到貨時(shí)間。

        本文主要參考文獻(xiàn)[3]所創(chuàng)建的車輛路徑問(wèn)題的數(shù)學(xué)模型,根據(jù)實(shí)際情況,對(duì)模型進(jìn)行修改,考慮到在配送過(guò)程的優(yōu)化效果更顯著,增加兩個(gè)變量的約束范圍,即配送車輛和貨物的數(shù)量,使其趨于無(wú)窮,以此建立如下的數(shù)學(xué)模型。

        假設(shè)1:O標(biāo)記成起點(diǎn),K為貨車數(shù)量,G個(gè)貨物,每輛貨車的承載量最多是Qk(k=1,2,…,K),路程最長(zhǎng)是Dh,L個(gè)送貨點(diǎn),需求點(diǎn)i的所要求數(shù)量為qi,配送中心O到需

        求點(diǎn)i的距離為doi,i和j之間的距離為dij(i,j=1,2,…,L)。

        假設(shè)2:nk為第k輛貨車所要送貨的需求點(diǎn)數(shù)量(nk= 0為第k輛貨車未被指派),Rk為第k條的路線,由rki構(gòu)成,指需求點(diǎn)在路線k里排序是i(不含rki=0),令rki=0為起點(diǎn),以此創(chuàng)建此類物流配送問(wèn)題的數(shù)學(xué)模型:

        式(1)表示建立數(shù)學(xué)模型,在約束條件下,最終目的是最小值化z;

        式(2)~(10)為研究問(wèn)題的約束條件;

        式(2)表示每輛車的貨物總重量小于等于最大承載量;

        式(3)表示必須滿足指派出的車輛小于等于最長(zhǎng)路程;

        式(4)表示必須滿足各個(gè)路線上的送貨點(diǎn)沒(méi)有超出總量;

        式(5)表示任一需求點(diǎn)都安排車輛配送;

        式(6)表示表示路徑所需要配送的需求點(diǎn);

        式(7)表示滿足任意一輛車能送多個(gè)點(diǎn),但是每個(gè)客戶僅由某貨車負(fù)責(zé);

        式(8)表示起點(diǎn)具有足夠的貨車;

        式(9)表示配送中心具有足夠的貨物;

        式(10)存在兩類情況,分別是貨車參與送貨,第k輛車運(yùn)送需求點(diǎn)總數(shù)≥1,使sign(nk)=1;貨車沒(méi)有被指派,第k輛車送貨需求點(diǎn)總數(shù)<1時(shí),使sign(nk)=0。

        三、算法

        (一)遺傳算法的思想

        遺傳算法是模仿自然界優(yōu)勝劣汰的進(jìn)化狀況,將可能的解編碼形成向量,而基因是構(gòu)成向量的元素,通過(guò)不斷計(jì)算各染色體的適應(yīng)值,選擇最好染色體,求得滿意解或接近最優(yōu)解。遺傳算法優(yōu)化的是一定數(shù)量個(gè)體構(gòu)成的種群,優(yōu)化的做法分別是選擇、交叉、變異。在遺傳操作過(guò)程中,設(shè)置一些基本參數(shù):包括染色體長(zhǎng)度、種群大小、實(shí)施交叉和變異操作的概率、最終結(jié)束運(yùn)算值T。該算法包含以下6個(gè)元素及遺傳算法流程圖(見(jiàn)圖1)。

        (1)編碼:是指將求解問(wèn)題的每個(gè)可能的解編碼形成向量(染色體),基因是構(gòu)成染色體的元素,使計(jì)算機(jī)能辨別且可處理。

        圖1 遺傳算法處理流程圖

        (2)初始群體生成:初始種群個(gè)體是由隨機(jī)方式產(chǎn)生,種群的規(guī)模大小是由種群個(gè)體數(shù)目所決定,每個(gè)個(gè)體對(duì)應(yīng)所研究問(wèn)題的解。

        (3)適應(yīng)度評(píng)估:是指各自對(duì)周圍的順應(yīng)能力,從而計(jì)算出適應(yīng)度值來(lái)作為評(píng)估好壞的準(zhǔn)則。需要按照問(wèn)題本身需求,構(gòu)建不同適應(yīng)度函數(shù),在遺傳算法中處于重要位置[7]。

        (4)選擇:一般情況下,選擇是基于一定的概率,是使用種群中個(gè)體的適應(yīng)度值大小作為標(biāo)準(zhǔn),當(dāng)個(gè)體的適應(yīng)度值越大,被選取的可能性也更高。

        (5)交叉:一般來(lái)講,交叉操作是以一定概率來(lái)替換重組兩個(gè)父代中個(gè)體的一部分結(jié)構(gòu)而生成新個(gè)體,交叉最終目標(biāo)是為形成新的一代,是孕育出新的良好個(gè)體的方法。通常情況下,一般選取較大的交叉概率值,取值范圍一般為0.4~0.9,交叉率越大,就會(huì)越早達(dá)到最優(yōu)解。

        (6)變異:一般情況下,變異是以一定概率進(jìn)行變異。通常情況下,選取的變異概率值較小,區(qū)間是0.001~0.1,如果過(guò)高,會(huì)引起不穩(wěn)定性。變異操作的思想來(lái)源是模擬人類遺傳基因的突變,根據(jù)人體的遺傳學(xué),遺傳基因是相對(duì)穩(wěn)定的,突變情況是相對(duì)較少,則變異概率應(yīng)選取偏小值。變異操作是為防止過(guò)早收斂,保證種群多樣性,使染色體上基因發(fā)生突變。

        (二)快速排序算法

        通常,在遺傳算法的選擇操作中,個(gè)體的適應(yīng)度值是進(jìn)行從大到小的普通排序,時(shí)間復(fù)雜度大,則引入快速排序算法,降低時(shí)間復(fù)雜度。

        快速排序是由C.A.R.Hoare在1962年提出,是始于分治的戰(zhàn)略,其就像一個(gè)二叉樹,基本思想是將排序的序列分成兩個(gè)獨(dú)立的子序列,前面的子序列中任一數(shù)據(jù)都比后面的子序列中任一數(shù)據(jù)要小,使無(wú)序序列成為有序序列。具

        體可描述為:假設(shè)這是一組無(wú)序序列K[1]、K[2]、…、K[n],首先任取數(shù)據(jù)K[x]作為基準(zhǔn);從序列的兩端向中間按照順序執(zhí)行比較和交換所處的位置,使排在前的子序列中只留下比K[x]小的數(shù)據(jù),排在后的子序列中只留下比K[x]大的數(shù)據(jù),同時(shí)重復(fù)把排在前子序列中大于等于K[x]的數(shù)據(jù)同排在后的子序列小于等于K[x]的數(shù)據(jù)互換位置,全部數(shù)據(jù)遍歷之后,將K[x]放置在前面和后面兩個(gè)子序列的接壤地方i,則排在前的子序列中所有數(shù)據(jù)都小于等于K[x],排在后的而是大于等于K[x],也就是使前面的K[1]~K[i-1]中的每一個(gè)數(shù)據(jù)<K[x],K[i+1]~K[n]中的每一個(gè)數(shù)據(jù)>K[x],K[x]的目前位置是排序后的最終放置的地方;緊接著K[1]~K[i-1]和K[i+1]~K[n]兩組數(shù)據(jù)執(zhí)行快速排序,循環(huán)上面語(yǔ)句,存在任一序列為空或僅包括一個(gè)元素,則中斷并跳出。

        一次劃分PARTITION的算法步驟:

        Step1:首先定義兩個(gè)變量分別是i和j,對(duì)i和j進(jìn)行初始化,令i=a,j=b;

        Step2:使從未排序列中選擇在第一位置的S[a]成為key,將K[x]值給pivot,則命令pivot=S[a];

        Step3:從j由后向前比較(j--),尋找到第一個(gè)小于key的元素S[j],交換S[i]與S[j],同時(shí),i++;

        Step4:從i位置開(kāi)始由前向后比較(i++),找到第一個(gè)大于key(基準(zhǔn))的S[i],S[i]與S[j]交換,同時(shí),j--。

        假設(shè)待排序的序列為{20,26,50,26,15,36,09},通過(guò)表1和表2的運(yùn)算可知,一次劃分之后為{15,09}20{26,50,36,26},序列左進(jìn)行排序得到{09,15}20{26,50,36,26},序列右進(jìn)行排序最終得到{26,26,36,50},最終得到的結(jié)果為{09,15,20,26,26,36,50}。

        表1 i=1的一次劃分過(guò)程

        表2 以第一個(gè)數(shù)據(jù)為基準(zhǔn)的排序結(jié)果

        (三)結(jié)合快速排序的遺傳算法

        在遺傳算法的選擇操作當(dāng)中,第一步是計(jì)算每條染色體的適應(yīng)度值,第二步是算出各自占總和的比例,第三步按照適應(yīng)度值從大到小排序。根據(jù)很多研究理論顯示,計(jì)算機(jī)使用算法處理數(shù)據(jù),排序時(shí)間占總處理時(shí)間的25%,則提高排序時(shí)間能提高算法處理效率。在此,將快速排序引入遺傳算法的選擇操作中是比較合理的,并不會(huì)產(chǎn)生沖突。不僅能夠改善遺傳算法的排序時(shí)間,而且可以提高其整體時(shí)間。由很多的理論基礎(chǔ)、實(shí)驗(yàn)結(jié)果對(duì)比顯示,在復(fù)雜情況下,其他算法略遜于快速排序。

        對(duì)快速排序的效率分析得出,由很多的理論、實(shí)驗(yàn)、對(duì)比表明,快速排序算法仍然是目前最好的和時(shí)間復(fù)雜度最低的方法[8]。當(dāng)記錄較大時(shí),則應(yīng)選擇快速排序,從平均時(shí)間性能的角度,其他3種的排序方法略次于快速排序和歸并排序,這兩種方法當(dāng)輸入規(guī)模龐大時(shí),快速排序就占上風(fēng)[9]??焖倥判虻奶攸c(diǎn)在于排序極其快,數(shù)據(jù)移動(dòng)少,最終使序列從小到大排序??焖倥判蛩惴ㄊ悄壳白顚?shí)用的算法,很適合處理復(fù)雜問(wèn)題,當(dāng)問(wèn)題規(guī)模越大時(shí),運(yùn)用算法的執(zhí)行時(shí)間則更長(zhǎng),相對(duì)于其他算法,使用快速排序的效率更高,效果更顯著。通常用時(shí)間復(fù)雜度(Asymptotic Time Complexity)和空間復(fù)雜度來(lái)衡量算法的效率,對(duì)比算法的時(shí)間復(fù)雜度在保證相同存儲(chǔ)空間下,也就是保證S(n)的前提下,得到算法的運(yùn)行的時(shí)間,快速排序算法的時(shí)間復(fù)雜度和空間復(fù)雜度分別為:

        式(1)中,T(n)為算法執(zhí)行時(shí)間,f(n)為問(wèn)題的函數(shù),其中n為研究問(wèn)題的規(guī)模,T(n)是n的某個(gè)函數(shù),T(n)和f(n)的增長(zhǎng)率相同。

        表3 快速排序算法的性能

        針對(duì)n個(gè)需求點(diǎn)的時(shí)間復(fù)雜度研究顯示,根據(jù)表3可知,當(dāng)需求點(diǎn)越多,快速排序發(fā)揮的作用越大,引入快速排序時(shí),使用遺傳算法對(duì)n個(gè)需求點(diǎn)進(jìn)行物流配送路徑的優(yōu)化,需要計(jì)算n2次;然而,當(dāng)引入以后,僅計(jì)算nlogn次,總的降低了n2-nlogn次,當(dāng)n越大時(shí),在運(yùn)算的時(shí)間上也明顯減少,同時(shí)運(yùn)算的次數(shù)得到很大的減少,最重要的是時(shí)間復(fù)雜度得到很大降低。

        則可知引入后的時(shí)間復(fù)雜度:

        未引入的時(shí)間復(fù)雜度:

        (四)基于快速排序的遺傳算法

        針對(duì)物流配送路徑優(yōu)化問(wèn)題的特點(diǎn),構(gòu)建解決此類現(xiàn)象的遺傳算法,包括選擇設(shè)計(jì)簡(jiǎn)單和最為經(jīng)典的適應(yīng)度函數(shù),在選擇操作中引入快速排序方法,主要是為遺傳算法的復(fù)雜度得到下降。

        1.編碼方法:本文選用自然數(shù)的編碼方式,0為起點(diǎn)(配送中心),其它的每個(gè)整數(shù)為每一個(gè)客戶點(diǎn)。假設(shè)有10個(gè)需求點(diǎn),1到10分別表示10個(gè)不同的需求點(diǎn),配送順序?yàn)?-2-1-3-5-6-4-10-9-8-7-0,這就是一條完整的配送路徑,以0為起始點(diǎn),以0為結(jié)束點(diǎn),代表的含義是車輛配送時(shí)從配送中心出發(fā)最終回到配送中心。

        2.初始群體生成:由各個(gè)需求點(diǎn)隨機(jī)產(chǎn)生K條配送路

        徑,然后由K條配送路徑構(gòu)成初始種群,初始種群的大小也就為K。

        3.適應(yīng)度函數(shù):本文選擇按比例的適應(yīng)度計(jì)算,原理是將該問(wèn)題的可行解代入模型方程計(jì)算,可得目標(biāo)值,假如其值越小,適應(yīng)度更優(yōu),該方法比基于排序的適應(yīng)度計(jì)算更為簡(jiǎn)單,方便。根據(jù)資料顯示,適應(yīng)度函數(shù)可以根據(jù)解決問(wèn)題的需求進(jìn)行設(shè)計(jì),目前存在較多適應(yīng)度函數(shù),適應(yīng)度函數(shù)[8-9](Fitness Function)的選取及設(shè)計(jì)盡可能簡(jiǎn)單,使計(jì)算的時(shí)間復(fù)雜度最小,由于適應(yīng)度函數(shù)會(huì)影響遺傳算法的收斂速度及是否可以找到滿意解,且是否體現(xiàn)遺傳算法“優(yōu)勝劣汰”的特點(diǎn)。

        4.選擇:是根據(jù)適應(yīng)度函數(shù)的計(jì)算方法,第一步運(yùn)算出每條染色體的適應(yīng)度值,第二步所有的適應(yīng)度求和,接著計(jì)算出每條染色體的適應(yīng)度占總和的比例,最后按適應(yīng)度值從大到小快速排序,在此引入快速排序代替普通排序,其原因在于快速排序能降低遺傳算法運(yùn)算的時(shí)間復(fù)雜度。

        5.交叉:本文選擇的是部分匹配交叉法(PartiallyMapped Crossover,PXM),原理是在兩條任意染色體上選取兩個(gè)點(diǎn)X、Y,對(duì)X、Y點(diǎn)之間的基因片段交叉,確定X,Y之間的基因映射關(guān)系,最后將未換部分按映射關(guān)系進(jìn)行映射,以此恢復(fù)合法性。假設(shè)染色體1為:8-7-10-|9-3-1-2|-6-5-4;染色體2為:3-4-5-|2-6-7-9|-10-8-1;對(duì)染色體1和染色體2雙切點(diǎn)之間的中間片段進(jìn)行交換,確定映射關(guān)系,最終按照映射關(guān)系將未換部分進(jìn)行映射得到:染色體1為:8-1-10-|2-6-7-9|-3-5-4;染色體2為:6-4-5-|9-3-1-2|-10-8-7。

        6.變異:本文選擇的變異方法是換位變異,換位變異法是為避免問(wèn)題過(guò)早收斂,能保證多樣性;基本原理是按一定概率選中染色體的換位變異操作,任意選出兩個(gè)需求點(diǎn)交換位置。假設(shè)染色體1為:(13567842),若隨機(jī)選擇3和4兩個(gè)需求點(diǎn)進(jìn)行互換,則換位后的染色體1為(14567832)。

        四、仿真實(shí)驗(yàn)與結(jié)果分析

        本文針對(duì)物流配送路徑優(yōu)化問(wèn)題進(jìn)行仿真實(shí)驗(yàn)分析,目標(biāo)是總距離最短。

        假設(shè)貨車為6輛,車輛的最大承載力為20噸,行駛的最長(zhǎng)距離為65 km,根據(jù)模擬的10個(gè)坐標(biāo),如表4所示,求解各個(gè)距離,使用C語(yǔ)言和Matlab工具,在此使用引入快速排序的遺傳算法對(duì)物流配送路徑問(wèn)題進(jìn)行優(yōu)化,求出配送需求點(diǎn)的順序。

        表4 10個(gè)隨機(jī)點(diǎn)的坐標(biāo)及需求量

        在實(shí)驗(yàn)當(dāng)中采用以下參數(shù)值:遺傳代數(shù):500,種群個(gè)數(shù):100,交叉率:0.8,變異率:0.05,終止代數(shù)T為200。

        經(jīng)計(jì)算,未優(yōu)化前得到最終的線路為:0-7-8-6-9-5-10-2-1-3-4-0,配送的總距離為:147.745 8 km,如圖2所示。

        圖2 優(yōu)化前的配送路徑

        針對(duì)此問(wèn)題,在遺傳算法的選擇操作中引入快速排序算法及對(duì)遺傳算法的設(shè)計(jì)對(duì)此例優(yōu)化,算法運(yùn)算具體步驟如下:

        (1)獲取表4需求點(diǎn)坐標(biāo),利用算法運(yùn)算,求得距離值,具體運(yùn)算過(guò)程如圖3所示。

        圖3 算法通過(guò)獲取坐標(biāo)后的運(yùn)算

        最后還需判斷基因是否在指定的區(qū)間isInArray(int value,int*s,int start,int end)。

        (2)初始化種群:采用自然數(shù)的編碼方法,Num為個(gè)體數(shù),初始種群長(zhǎng)度為len,初始化隨機(jī)操作getOneRandSolution(int*fR,int len),初始化種群的代碼流程如圖4所示。

        圖4 初始化種群的代碼流程圖

        (3)適應(yīng)函數(shù):選取按比例的適應(yīng)度運(yùn)算方式,令適應(yīng)度值為f(x),目標(biāo)值為F(x),如公式(1)所示,當(dāng)目標(biāo)值越小,則適應(yīng)度越好。

        f(x)=1/F(X)(1)

        選擇:在選擇操作中引入快速排序算法QSort(float *R,int**P,int start,int end)排序代替普通排序方法,提高排序速度,代碼如下:

        (4)交叉操作利用部分匹配交叉法Cross(int*f1,int*f2,int*s1,int*s2,int start,int end,int len)進(jìn)行交叉,按照遺傳的交叉率0.8進(jìn)行部分交叉。為防止過(guò)早收斂,引入變異操作,采用換位變異Mutation(int**P,int Num,int len,float Pm)進(jìn)行變異,按照遺傳變異率0.05進(jìn)行變異,最終例子的最優(yōu)解。

        (5)遺傳算法優(yōu)化后的結(jié)果:通過(guò)(1)~(5)的算法優(yōu)化過(guò)程,也就是遺傳算法設(shè)計(jì)及引入快速排序遺傳算法的優(yōu)化過(guò)程,優(yōu)化后配送總距離為:122.017 3 km,最終的配送線路為:0-3-2-1-10-9-8-7-6-5-4-0,某公司的物流配送路徑如圖5所示。

        圖5 優(yōu)化后的配送路徑

        通過(guò)遺傳算法優(yōu)化后與優(yōu)化前的配送總距離比較可得優(yōu)化的距離差值D:

        D=147.7458 km-122.0173 km=25.7277 km(1)

        則通過(guò)算式(1)的計(jì)算得到差值D為25.727 7 km,可知10個(gè)需要的優(yōu)化后的距離明顯減少很多。

        通過(guò)遺傳算法的設(shè)計(jì)得到此例的最優(yōu)解,及引入快速排序可提高遺傳算法的時(shí)間復(fù)雜度,從例子中10個(gè)需求點(diǎn)的時(shí)間復(fù)雜度研究顯示,在實(shí)驗(yàn)中,可知引入快速排序的遺傳算法比未引入快速排序遺傳算法的運(yùn)算時(shí)間復(fù)雜度更低,具體可以描述為:未引入快速排序時(shí),遺傳算法對(duì)10個(gè)需求點(diǎn)優(yōu)化操作需要計(jì)算102次;引入快速排序時(shí),遺傳算法優(yōu)化10個(gè)需求累計(jì)的計(jì)算次數(shù)達(dá)到10log10次,則運(yùn)算次數(shù)減少102~10log10次,大概約為90次,不僅提高計(jì)算的效率,而且減少運(yùn)算次數(shù),降低其時(shí)間復(fù)雜度。

        五、結(jié)語(yǔ)

        處理物流配送路線優(yōu)化問(wèn)題,目前較多使用遺傳算法,這是由于其實(shí)此類現(xiàn)象是NP難題,而且是企業(yè)比較關(guān)注的問(wèn)題,能夠?yàn)槠髽I(yè)帶來(lái)更多的利益,使企業(yè)能快速發(fā)展。為了企業(yè)在處理配送的時(shí)間帶來(lái)客戶滿意度的下降,則需要不斷提高配送的技術(shù)。研究發(fā)現(xiàn)遺傳算法具有可以擴(kuò)大搜索空間,限制性較小,較自由,不受約束的特點(diǎn),但有運(yùn)算次數(shù)高和運(yùn)算效率低的缺陷。所以根據(jù)此問(wèn)題,構(gòu)造引入快速排序的遺傳算法來(lái)降低遺傳算法的時(shí)間復(fù)雜度,以及設(shè)計(jì)包括采用自然數(shù)的編碼、個(gè)體適應(yīng)值的計(jì)算及選擇、基于概率的交叉和變異操作。當(dāng)企業(yè)所需配送的需求點(diǎn)越多,引入快速排序的效果更明顯,效果不僅是配送的處理速度更加快速,當(dāng)企業(yè)配送員碰到交通高峰期的時(shí)候,急需選擇正確的道路,此方法可以為物流路徑問(wèn)題的滿意解。

        [1]Lau H C W,Chan T M,Tsui W T,et al.Application of Genetic Algorithms to Solve the Multidepot Vehicle Routing Problem[J].IEEE Transactions on Automation Science and Engineering,2010,7(2):383-392.

        [2]姜大立,楊西龍,杜文,等.車輛路徑問(wèn)題的遺傳算法研究[J].系統(tǒng)工程理論與實(shí)踐,1999,19(6):40-44.

        [3]郎茂祥,2002.基于遺傳算法的物流配送路徑優(yōu)化問(wèn)題研究[J].中國(guó)公路學(xué)報(bào)(3):78-81.

        [4]張迅,劉海東,李丹,等,2013.基于遺傳算法的快遞配送車輛路徑問(wèn)題研究[J].物流技術(shù)(5):263-267.

        [5]郭賽克,劉成泳,2012.基于遺傳算法的物流配送路徑優(yōu)化問(wèn)題的研究[J].科技信息(10):96-97.

        [6]席裕庚,柴天佑,惲為民,1996.遺傳算法綜述[J].控制理論與應(yīng)用(6):697-708.

        [7]朱鰲鑫,1998.遺傳算法的適應(yīng)度函數(shù)研究[J].系統(tǒng)工程與電子技術(shù)(11):60-64.

        [8]霍紅衛(wèi),許進(jìn),2002.快速排序算法研究[J].微電子學(xué)與計(jì)算機(jī)(6):6-9.

        [9]淦艷,楊有,2010.五種排序算法的性能分析[J].重慶文理學(xué)院學(xué)報(bào)(自然科學(xué)版)(3):45-50.

        (責(zé)任編輯:C校對(duì):R)

        F224.0;F252

        A

        1004-2768(2016)11-0001-05

        2016-08-31

        國(guó)家自然科學(xué)基金項(xiàng)目(71171070,U1509220)

        陳疇鏞(1955-),男,浙江紹興人,杭州電子科技大學(xué)管理學(xué)院教授,研究方向:供應(yīng)鏈與物流管理、信息管理與商務(wù)智能;鄭冬冬(1993-),女,浙江溫州人,杭州電子科技大學(xué)管理學(xué)院碩士研究生,研究方向:供應(yīng)鏈與物流管理。

        猜你喜歡
        物流配送復(fù)雜度適應(yīng)度
        改進(jìn)的自適應(yīng)復(fù)制、交叉和突變遺傳算法
        山西將打造高效農(nóng)村快遞物流配送體系
        基于精益生產(chǎn)的SPS物流配送應(yīng)用研究
        基于Flexsim的飲品物流配送中心仿真優(yōu)化研究
        一種低復(fù)雜度的慣性/GNSS矢量深組合方法
        直企物流配送四步走
        求圖上廣探樹的時(shí)間復(fù)雜度
        基于空調(diào)導(dǎo)風(fēng)板成型工藝的Kriging模型適應(yīng)度研究
        某雷達(dá)導(dǎo)51 頭中心控制軟件圈復(fù)雜度分析與改進(jìn)
        出口技術(shù)復(fù)雜度研究回顧與評(píng)述
        中文字幕人妻被公上司喝醉| 国产亚洲精品视频网站| 国产影片一区二区三区| 综合色就爱涩涩涩综合婷婷| 18无码粉嫩小泬无套在线观看| 精品国产乱码一区二区三区在线| 亚洲av中文字字幕乱码软件 | 97久久精品无码一区二区天美| 午夜性刺激免费视频| av在线网站手机播放| 日本免费在线一区二区三区| 色欲色欲天天天www亚洲伊| 屁屁影院一区二区三区| 亚洲精品中文有码字幕| 开心五月婷婷激情综合网| 久久久国产精品免费a片3d| 四虎精品成人免费观看| 丰满人妻无套内射视频| 亚洲av天堂免费在线观看| 94久久国产乱子伦精品免费| 久久狠色噜噜狠狠狠狠97| 国产在线一区二区三区不卡| 一本久久综合亚洲鲁鲁五月天 | 国产精品日本中文在线| 老熟女富婆激情刺激对白| 久久久久久人妻一区二区三区 | 中文字幕久久人妻av| 国产精品国产三级国产aⅴ下载 | 大伊香蕉在线精品视频75| 亚洲熟妇中文字幕日产无码| 夜夜高潮夜夜爽免费观看| 又色又爽又高潮免费视频观看| 国产成年无码V片在线| 亚洲免费av第一区第二区| 2019nv天堂香蕉在线观看 | 免费看奶头视频的网站| 国产av精品一区二区三区视频| 欧美黑人又粗又大xxxx| 人妻去按摩店被黑人按中出| 亚洲精品视频免费在线| 女优av一区二区三区|