帶油耗率的車(chē)輛路徑問(wèn)題的改進(jìn)量子遺傳算法研究.pdf

《帶油耗率的車(chē)輛路徑問(wèn)題的改進(jìn)量子遺傳算法研究.pdf》由會(huì)員上傳分享，免費(fèi)在線(xiàn)閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、東莞理工學(xué)院學(xué)報(bào)第22卷第3期JOURNALOFDONGGUANUNIVERSITYOFTECHNOLOGYVo1．22NO．32015年6月Jun．2015帶油耗率的車(chē)輛路徑問(wèn)題的改進(jìn)量子遺傳算法研究汪婷湯雅連。(1．廣東技術(shù)師范學(xué)院天河學(xué)院，廣州510540；2．廣東工業(yè)大學(xué)自動(dòng)化學(xué)院，廣州510006)摘要：針對(duì)實(shí)際生活中車(chē)輛油耗會(huì)隨著運(yùn)載量的變化而變化，建立帶油耗率車(chē)輛路徑問(wèn)題的數(shù)學(xué)模型，以最小化總成本為目標(biāo)函數(shù)。將運(yùn)輸過(guò)程中隨運(yùn)載量變化的油耗率轉(zhuǎn)化成交叉概率，自適應(yīng)地改變交叉概率，提高算法的全局搜索能力；考慮車(chē)輛滿(mǎn)載率，設(shè)計(jì)一種與運(yùn)載量相關(guān)的變異概率

2、，使其逐漸減小并使群體迅速集中，可以抑制早熟?；谝陨戏椒?gòu)造的一種自適應(yīng)遺傳算法，實(shí)例進(jìn)行仿真表明，提出的算法在收斂速度和尋優(yōu)結(jié)果兩方面略?xún)?yōu)于自適應(yīng)遺傳算法和遺傳算法。關(guān)鍵詞：車(chē)輛路徑問(wèn)題；量子進(jìn)化算法；遺傳算法；自適應(yīng)；油耗率；運(yùn)載量中圖分類(lèi)號(hào)：TP301文獻(xiàn)標(biāo)志碼：A文章編號(hào)：：1009—0312(2015)03—0047—09車(chē)輛路徑問(wèn)題(VehicleRoutingProblem，VRP)¨-2]自1959年Dantzig和Ramser首先提出以來(lái)就引起了人們的高度重視，它屬于經(jīng)典的組合優(yōu)化問(wèn)題。VRP的實(shí)用性強(qiáng)，且應(yīng)用廣泛。車(chē)輛路徑問(wèn)題一般定義為：

3、對(duì)一系列送貨點(diǎn)和收貨點(diǎn)，組織適當(dāng)?shù)男熊?chē)路線(xiàn)，使車(chē)輛有序地通過(guò)它們，在滿(mǎn)足一定的約束條件(如貨物需求量、發(fā)送量、送發(fā)貨時(shí)間、車(chē)輛容量限制、行駛里程限制、時(shí)間限制等)下，達(dá)到一定的目標(biāo)(如路程最短、費(fèi)用極小、時(shí)問(wèn)盡量少、使用車(chē)輛數(shù)盡量少等)。量子進(jìn)化算法(QuantumEvolutionaryAlgorithm，QEA)是20世紀(jì)90年代后期新興的一種進(jìn)化算法。由于其良好的性能，已廣泛應(yīng)用于諸多領(lǐng)域，如物流運(yùn)輸調(diào)度、智能交通領(lǐng)域、網(wǎng)格入侵檢測(cè)、網(wǎng)格任務(wù)調(diào)度、非線(xiàn)性規(guī)劃等。MohammedA．M．等人提出了基于量子遺傳的量子交叉算法(Quan．turnCrossov

4、er—basedQuantumGeneticAlgorithm，QXQGA)對(duì)非線(xiàn)性規(guī)劃問(wèn)題求解；蔡延光等人針對(duì)量子進(jìn)化算法計(jì)算量大、收斂速度慢以及容易出現(xiàn)早熟等問(wèn)題，提出混沌混合量子進(jìn)化算法，并證明其可較好地應(yīng)用在智能交通領(lǐng)域。研究車(chē)輛路徑優(yōu)化問(wèn)題(VehicleRoutingProblem，VRP)是研究IVRP的基礎(chǔ)。目前，國(guó)內(nèi)外采用QEA及其改進(jìn)算法對(duì)VRP或其擴(kuò)展問(wèn)題的研究文獻(xiàn)不少，有一定的借鑒意義。CuiL．等人提出了一種帶混合局部搜索的改進(jìn)量子進(jìn)化算法(ImprovedQuantumEvolutionAlgo—rithm，IQEA)對(duì)帶容量約束的

5、VRP(CapacitatedVehicleRoutingProblem，CVRP)求解；WangL．等人提出了一種改進(jìn)量子進(jìn)化算法(Quantum—InspiredEvolutionaryAlgorithm，IQEA)對(duì)帶時(shí)間窗的VRP(VehicleRoutingProblemwithTimeWindows，VRPTW)求解；葛顯龍等人根據(jù)隨機(jī)需求信息把動(dòng)態(tài)配送問(wèn)題轉(zhuǎn)換成一系列靜態(tài)配送問(wèn)題，設(shè)計(jì)基于并行節(jié)約算法動(dòng)態(tài)插入隨機(jī)需求信息的混合量子遺傳算法，對(duì)動(dòng)態(tài)模型實(shí)時(shí)再優(yōu)化；之后，葛顯龍等人又采用量子比特位設(shè)計(jì)染色體結(jié)構(gòu)，改進(jìn)遺傳算法中交叉與變異算子，避免優(yōu)秀

6、基因被破壞，設(shè)計(jì)快速尋優(yōu)機(jī)制與最優(yōu)保留機(jī)制，增強(qiáng)求解效率對(duì)以配送總費(fèi)用最小為優(yōu)化目標(biāo)的數(shù)學(xué)模型求解；ZhangJ．等人提出了一種自適應(yīng)網(wǎng)格多目標(biāo)量子進(jìn)化算法(Multi—objectiveQuantumEvolutionaryAgorithm，MOQEA)對(duì)帶客戶(hù)滿(mǎn)意度的多目標(biāo)VRP(Multiob-ectiveVehicleRoutingProblemConsideringCustomerSatisfaction，MVRPCS)求解；MichalletJ．等人研究了非常嚴(yán)格的帶時(shí)問(wèn)窗的周期性VRP，并提出了混合整數(shù)線(xiàn)性模型和多起點(diǎn)迭代局部搜索算法；Cris—

7、pinA．等人提出了一種量子模擬算法對(duì)帶容量約束的VRP求解；ZhengT．等人l提出了量子差分進(jìn)化算法對(duì)調(diào)度問(wèn)題求解；ZhouL．等人針對(duì)傳統(tǒng)的遺傳算法不能保證收斂到最優(yōu)解的最大概率，提出了對(duì)小規(guī)模求解具有快速收斂和良好搜索能力的量子遺傳算法，對(duì)VRP求解；NingT．等人¨結(jié)合量收稿日期：2014—07—13作者簡(jiǎn)介：汪婷(1988一)，女，江西鷹潭人，講師，碩士，主要從事物流信息技術(shù)及組合優(yōu)化研究。東莞理工學(xué)院學(xué)報(bào)2015往子粒子群優(yōu)化算法和模擬退火算法，提出了混合量子粒子群優(yōu)化算法對(duì)帶時(shí)間窗的VRP求解；彭典軍在其碩士論文中，主要研究了一種量子進(jìn)化算法

8、在車(chē)輛路徑問(wèn)題中的應(yīng)用，具體求解了有能