近年來(lái)，隨著環(huán)境問(wèn)題的日益突出，越來(lái)越多物流配送企業(yè)開始使用節(jié)能環(huán)保的電動(dòng)物流車。 但是由于續(xù)航里程有限及充電設(shè)施布局不完善等問(wèn)題，電動(dòng)車并不能完全代替燃油車，所以大多物流企業(yè)目前主要采用電動(dòng)車與燃油車混合配送的過(guò)渡模式。 與燃油車配送不同，由于電動(dòng)車需途中進(jìn)行充電，改變了原有配送系統(tǒng)的配置參數(shù)，并對(duì)配送時(shí)間窗產(chǎn)生影響；此外，實(shí)際配送過(guò)程中配送中心會(huì)在車輛離開后繼續(xù)接收新的需求，導(dǎo)致配送系統(tǒng)的狀態(tài)不斷發(fā)生變化，需要對(duì)已有配送方案重新進(jìn)行調(diào)整。 如果不能合理快速地規(guī)劃與調(diào)整配送路線，不僅會(huì)大幅增加企業(yè)的運(yùn)營(yíng)成本，還會(huì)降低顧客服務(wù)水平。 因此，研究電動(dòng)車與燃油車混合配送模式下的動(dòng)態(tài)需求車輛路徑問(wèn)題具有重要的現(xiàn)實(shí)意義。車輛路徑優(yōu)化（ｖｅｈｉｃｌｅ ｒｏｕｔｉｎｇ ｐｒｏｂｌｅｍ，ＶＲＰ） 一直都是物流配送領(lǐng)域中的熱點(diǎn)問(wèn)題，從 １９５９ 年 ＶＲＰ 被 Ｄａｎｔｚｉｇ 和 Ｒａｍｓｅｒ提出后就受到了國(guó)內(nèi)外學(xué)者的廣泛關(guān)注，目前已有非常豐碩的研究成果。 結(jié)合各種現(xiàn)實(shí)場(chǎng)景，研究人員開始對(duì)基礎(chǔ)的ＶＲＰ 進(jìn)行擴(kuò)展研究，如有載重約束的 ＶＲＰ（ＣＶＲＰ）［２］、帶時(shí)間窗約束的 ＶＲＰ（ＶＲＰＴＷ）［３］、多車型 ＶＲＰ（ＨＶＲＰ）［４］等。 使用電動(dòng)物流車的 ＶＲＰ 稱為電動(dòng)車車輛路徑問(wèn)題（ＥＶＲＰ），Ｃｏｎｒａｄ等人［５］首次對(duì) ＥＶＲＰ 進(jìn)行研究，在允許車輛途中充電的條件下，建立使用車輛數(shù)目最少以及行駛成本、服務(wù)時(shí)間成本和充電成本最小的多目標(biāo)模型；Ｓｃｈｎｅｉｄｅｒ 等人［６］進(jìn)一步提出了帶時(shí)間窗的 ＥＶＲＰ，建立使用車輛數(shù)最小和總行駛成本最小的優(yōu)化模型，并設(shè)計(jì)了基于變鄰域搜索和禁忌搜索的混合算法；葛顯龍等人［７］考慮到充電時(shí)間對(duì)時(shí)間窗的違反會(huì)存在影響，提出帶軟時(shí)間窗的 ＥＶＲＰ，建立了行駛成本、路徑成本以及車輛使用成本為目標(biāo)函數(shù)的數(shù)學(xué)模型，并設(shè)計(jì)了節(jié)約里程算法加改進(jìn)的禁忌搜索算法進(jìn)行求解；Ｋｅｓｋｉｎ 等人［８］針對(duì)帶時(shí)間窗的電動(dòng)車車輛路徑問(wèn)題，考慮電動(dòng)車在充電站采取部分充電的情況，設(shè)計(jì)了自適應(yīng)大規(guī)模鄰域搜索算法進(jìn)行求解；Ｐｅｌｌｅｔｉｅｒ 等人［９］考慮電動(dòng)車耗電為非線性的情況，研究天氣、道路情況以及司機(jī)行為等不確定因素背景下的電動(dòng)車車輛路徑問(wèn)題，通過(guò)將問(wèn)題定義為魯棒混合整數(shù)線性規(guī)劃模型，并設(shè)計(jì)一種基于大規(guī)模鄰域搜索的兩階段啟發(fā)式算法進(jìn)行求解；Ａｌｅｓｉａｎ 等人［１０］提出了可以多次訪問(wèn)充電站的電動(dòng)車車輛路徑問(wèn)題，并采用一種帶有學(xué)習(xí)策略的進(jìn)化遺傳算法找到最小化成本（與行駛時(shí)間、充電時(shí)間、能源消耗相關(guān)） 的車輛配送路線；Ｙａｎｇ 等人［１１］考慮了分時(shí)電價(jià)的情況，采用可學(xué)習(xí)的遺傳算法實(shí)現(xiàn)對(duì)車輛路徑以及充電時(shí)間的同時(shí)優(yōu)化。 如果在同一配送系統(tǒng)中同時(shí)使用不同類型的車輛進(jìn)行配送，考慮因素更多，問(wèn)題更加復(fù)雜。Ｇｏｅｋｅ 等人［１２］首次對(duì)帶時(shí)間窗的電動(dòng)車與燃油車的混合配送問(wèn)題（ＥＶＲＰＴＷＭＦ）進(jìn)行研究，并設(shè)計(jì)了自適應(yīng)大規(guī)模鄰域搜索算法進(jìn)行求解；Ｈｉｅｒｍａｎｎ 等人［１３］考慮帶時(shí)間窗的同時(shí)使用傳統(tǒng)燃油車、插電式混合動(dòng)力車以及電動(dòng)車三種車型的車輛路徑問(wèn)題，并設(shè)計(jì)基于遺傳算法以及局部和大規(guī)模鄰域搜索算法的混合啟發(fā)式算法進(jìn)行求解。以上研究均屬于靜態(tài) ＶＲＰ，即所有客戶需求可以事先確定。 但在實(shí)際配送過(guò)程中，配送中心會(huì)在車輛運(yùn)行途中繼續(xù)接收新客戶的配送需求，并對(duì)已有車輛路線重新進(jìn)行規(guī)劃，此類問(wèn)題即動(dòng)態(tài)需求的 ＶＲＰ（ＤＤＶＲＰ）。 Ｈｏｎｇ［１４］研究帶硬時(shí)間窗的 ＤＤＶＲＰ，并將動(dòng)態(tài)問(wèn)題分為一系列的靜態(tài)問(wèn)題，設(shè)計(jì)了改進(jìn)的大規(guī)模鄰域搜索算法對(duì)該問(wèn)題進(jìn)行求解；Ｄｅ Ａｒｍａｓ 等人［１５］將車輛工作時(shí)間不同、顧客有多個(gè)時(shí)間窗、顧客之間存在優(yōu)先級(jí)等現(xiàn)實(shí)因素考慮到動(dòng)態(tài)車輛路徑問(wèn)題中，并用變鄰域搜索算法求解；Ｃｈｅｎ 等人［１６］進(jìn)一步采用自適應(yīng)大規(guī)模鄰域搜索算法進(jìn)行 ＤＤＶＲＰ 的求解；張文博等人［１７］針對(duì)帶時(shí)間窗的 ＤＤＶＲＰ 設(shè)計(jì)了遺傳算法以及模擬退火結(jié)合的兩階段算法；李陽(yáng)等人［１８］針對(duì)帶載重約束的動(dòng)態(tài)需求車輛路徑問(wèn)題，提出了一種延遲服務(wù)機(jī)制，且采用混合變鄰域人工蜂群算法進(jìn)行多階段求解。綜上所述，目前 ＤＤＶＲＰ 已有一定的研究成果，但是這些研究都是基于傳統(tǒng)燃油車。 邵賽等人［１９］首次將電動(dòng)車引入動(dòng)態(tài)需求車輛路徑問(wèn)題中，研究了不考慮客戶時(shí)間窗的電動(dòng)車配送的 ＤＤＶＲＰ。 通過(guò)國(guó)內(nèi)外的文獻(xiàn)檢索，目前還沒(méi)有發(fā)現(xiàn)其他針對(duì)電動(dòng)車的 ＤＤＶＲＰ 的研究，此外也未有針對(duì)電動(dòng)車與燃油車混合配送模式下的 ＤＤＶＲＰ 的研究。 不同于單一燃油車或電動(dòng)車 ＤＤＶＲＰ，混合配送模式將電動(dòng)車與燃油車這兩種具有不同配送特點(diǎn)的車輛納入同一配送系統(tǒng)同步考慮，限制因素更多，尤其需同時(shí)考慮動(dòng)態(tài)需求和客戶時(shí)間窗，模型構(gòu)建與求解將更為復(fù)雜。 考慮到該類問(wèn)題在企業(yè)日常運(yùn)營(yíng)中會(huì)越來(lái)越普遍，本文研究了電動(dòng)車與燃油車混合配送模式下帶時(shí)間窗的動(dòng)態(tài)需求車輛路徑問(wèn)題（ｅｌｅｃｔｒｉｃ ｖｅｈｉｃｌｅ ｒｏｕｔｉｎｇ ｐｒｏｂｌｅｍ ｗｉｔｈ ｔｉｍｅｗｉｎｄｏｗｓ ａｎｄ ｍｉｘｅｄ ｆｌｅｅｔ ｃｏｎｓｉｄｅｒｉｎｇ ｄｙｎａｍｉｃ ｄｅｍａｎｄｓ，ＥＶＲＰＴＷＭＦ?ＤＤ）。 此外，考慮到動(dòng)態(tài)需求對(duì)實(shí)時(shí)性要求較高，而本文研究的 ＥＶＲＰＴＷＭＦ?ＤＤ 又屬于 ＮＰ?ｈａｒｄ 問(wèn)題，用精確算法求解較為困難且時(shí)間成本高。 因此，本文根據(jù)所建模型的特點(diǎn)設(shè)計(jì)了改進(jìn)的自適應(yīng)大規(guī)模鄰域搜索算法，以期在較短的時(shí)間內(nèi)獲得較優(yōu)的配送方案。１　 問(wèn)題描述ＥＶＲＰＴＷＭＦ?ＤＤ 可描述為某物流企業(yè)使用電動(dòng)車和燃油車為 Ｎ 個(gè)有時(shí)間窗要求的顧客提供配送服務(wù)。 首先，對(duì)上一工作日的預(yù)約靜態(tài)客戶制定配送路線并進(jìn)行送貨，在配送過(guò)程中，若出現(xiàn)新的客戶需求，需要對(duì)正在配送的車輛路徑進(jìn)行重新規(guī)劃或派出新車進(jìn)行服務(wù)。 此外，電動(dòng)車由于續(xù)航里程有限，在配送過(guò)程中需要到公共充電站充電才能繼續(xù)進(jìn)行配送任務(wù)。 該問(wèn)題的求解目標(biāo)是尋找車輛行駛總成本最小化的最優(yōu)路徑。 模型的假設(shè)條件如下：ａ） 每個(gè)客戶點(diǎn)只能被一輛車服務(wù)，每輛車可以服務(wù)多個(gè)客戶點(diǎn)，車輛在完成配送服務(wù)后要駛回配送中心；ｂ）電動(dòng)車從配送中心出發(fā)時(shí)電池為滿電，并且允許在行駛過(guò)程中采用滿充的方式進(jìn)行多次充電，充電站可以被多次訪問(wèn)。 為了更好地描述問(wèn)題，給出如圖 １ 所示的簡(jiǎn)單示例。 本文建立了 ＥＶＲＰＴＷＭＦ?ＤＤ 的兩階段 ０? １ 整數(shù)規(guī)劃模型，包括初始階段優(yōu)化模型和動(dòng)態(tài)階段優(yōu)化模型。２　 模型構(gòu)建２􀆰 １　 初始階段優(yōu)化模型初始階段主要對(duì)已經(jīng)預(yù)約的靜態(tài)客戶點(diǎn)進(jìn)行路線設(shè)計(jì)，得到初始的配送路徑優(yōu)化方案。 模型所用參數(shù)與變量如表 １ 所示。 初始階段優(yōu)化模型構(gòu)建如下：

　 　本；式（２）表示每個(gè)客戶只能被訪問(wèn)一次；式（３） 為流守恒約束；式（４）表示每輛車最多服務(wù)一條路徑且從配送中心出發(fā)；式（５）表示電動(dòng)車配送的任務(wù)總量不能超過(guò)其最大載重；式（６）表示燃油車的配送任務(wù)總量不能超過(guò)其最大載重量；式（７）表示要滿足客戶點(diǎn)ｉ 的服務(wù)時(shí)間窗要求；式（８）表示從點(diǎn)ｉ到 ｊ 的行駛時(shí)間為兩點(diǎn)之間距離與速度的比值；式（９）表示電動(dòng)車在充電站充電時(shí)間的計(jì)算；式（１０）表示車輛在到達(dá)和離開點(diǎn) ｉ 的時(shí)間關(guān)系；式（１１）表示車輛到達(dá)點(diǎn)ｊ 的時(shí)間為前邊行駛時(shí)間的累計(jì)；式（１２）表示電動(dòng)車到達(dá)和離開客戶點(diǎn)的電量不發(fā)生改變；式（１３）表示電動(dòng)車在充電站滿充；式（１４）表示電動(dòng)車從點(diǎn) ｉ 行駛到點(diǎn) ｊ 的電量消耗關(guān)系；式（１５）表示電動(dòng)車到達(dá)每一個(gè)點(diǎn)的電量都要大于 ０；式（１６）為 ０?１ 變量約束條件式（１）為目標(biāo)函數(shù)，最小化包含電動(dòng)車與燃油車的運(yùn)輸成

（１）為目標(biāo)函數(shù)，最小化包含電動(dòng)車與燃油車的運(yùn)輸成

主程序

tic clear clc %% 輸入數(shù)據(jù) dataset=importdata('input.txt'); %數(shù)據(jù)中，每一列的含義分別為[序號(hào)，x坐標(biāo)，y坐標(biāo)] x=dataset(:,2); %x坐標(biāo) y=dataset(:,3); %y坐標(biāo) vertexes=dataset(:,2:3); %提取各個(gè)城市的xy坐標(biāo) h=pdist(vertexes); dist=squareform(h); %距離矩陣 %% 參數(shù)初始化 MAXGEN=300; %最大迭代次數(shù) %% 構(gòu)造初始解 [Sinit,init_len]=construct_route(dist); %貪婪構(gòu)造初始解 init_length=route_length(Sinit,dist); str1=['初始總路線長(zhǎng)度 = ' num2str(init_length)]; disp(str1) %% 初始化當(dāng)前解和全局最優(yōu)解 Scurr=Sinit; curr_length=init_length; Sbest=Sinit; best_length=init_length; %% 主循環(huán) gen=1; BestL=zeros(MAXGEN,1); %記錄每次迭代過(guò)程中全局最優(yōu)個(gè)體的總距離 while gen<=MAXGEN%% “破壞”解[Sdestroy,removed]=destroy(Scurr);%% “修復(fù)”解[Srepair,repair_length]=repair(removed,Sdestroy,dist);if repair_length<curr_lengthScurr=Srepair;curr_length=repair_length;endif curr_length<best_lengthSbest=Scurr;best_length=curr_length; end%% 打印當(dāng)前代全局最優(yōu)解disp(['第',num2str(gen),'代最優(yōu)路線總長(zhǎng)度 = ' num2str(best_length)])BestL(gen,1)=best_length;%% 計(jì)數(shù)器加1gen=gen+1; end str2=['搜索完成！ 最優(yōu)路線總長(zhǎng)度 = ' num2str(best_length)]; disp(str2) %% 畫出優(yōu)化過(guò)程圖 figure; plot(BestL,'LineWidth',1); title('優(yōu)化過(guò)程') xlabel('迭代次數(shù)'); ylabel('總距離'); %% 畫出全局最優(yōu)路線圖 plot_route(Sbest,x,y); toc

改進(jìn)算法構(gòu)造初始解

%% 貪婪算法構(gòu)造TSP的初始解 %輸入dist： 距離矩陣 %輸出init_route： 貪婪算法構(gòu)造的初始路線 %輸出init_len： init_route的總距離 function [init_route,init_len]=construct_route(dist) N=size(dist,1); %城市數(shù)目 %先將距離矩陣主對(duì)角線上的0賦值為無(wú)窮大 for i=1:Nfor j=1:Nif i==jdist(i,j)=inf;endend endunvisited=1:N; %初始未被安排的城市集合 visited=[]; %初始已被安排的城市集合min_dist=min(min(dist)); %找出距離矩陣中的最小值 [row,col]=find(dist==min_dist); %在dist中找出min_dist所對(duì)應(yīng)的行和列 first=row(1); %將min_dist在dist中所對(duì)應(yīng)行序號(hào)作為起點(diǎn)unvisited(unvisited==first)=[]; %將first從unvisit中刪除 visited=[visited,first]; %把first添加到visit中 pre_point=first; %將fisrt賦值給pre_point while ~isempty(unvisited)pre_dist=dist(pre_point,:); %pre_point與其它城市的距離pre_dist(visited)=inf; %將pre_point與已經(jīng)添加進(jìn)來(lái)的城市之間的距離設(shè)位無(wú)窮大[~,pre_point]=min(pre_dist); %找出pre_dist中的最小值unvisited(unvisited==pre_point)=[]; %將pre_point從unvisit中刪除visited=[visited,pre_point]; %把pre_point添加到visit中 end init_route=visited; init_len=route_length(init_route,dist); %計(jì)算init_route的總距離 end

代碼下載連接

總結(jié)

以上是生活随笔為你收集整理的matlab改进大规模邻域搜索算法求解路径优化的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。