1 簡介
在給定有限的候選公交站點、有限的連接,已知各OD對乘客的出行需求的情況下,進(jìn)行定制公交的路線設(shè)計,尋找最優(yōu)的運(yùn)行路線,確定每輛車運(yùn)送的乘客數(shù)量。車輛從場站出發(fā),最終返回場站。每個站點有規(guī)定的時間間隔,車輛超出該時間間隔外到達(dá)站點將有乘客放棄使用該服務(wù)。? ? 假設(shè):(1)已知各OD對的出行需求;(2)預(yù)先設(shè)定每個站點的規(guī)定時間間隔和停站時間;(3)已知站點間的運(yùn)行時間和距離;(4)車輛的容量和平均車速是給定的常數(shù);(5) 定制公交運(yùn)行線路是雙向的物理網(wǎng)絡(luò)。
2 部分代碼
%
%
clear
clc
close all
tic
%% 用importdata這個函數(shù)來讀取文件
c101=importdata('.datac101.txt');
cap=50; %車輛最大裝客量
%% 提取數(shù)據(jù)信息
E=c101(1,5); %發(fā)車中心時間窗開始時間
L=c101(1,6); %發(fā)車中心時間窗結(jié)束時間
vertexs=c101(:,2:3); %所有點的坐標(biāo)x和y
customer=vertexs(2:end,:); %站點坐標(biāo)
cusnum=size(customer,1); %站點數(shù)
v_num=21; %車輛最多使用數(shù)目
demands=c101(2:end,4)./2; %每個站點乘客量
a=c101(2:end,5); %站點時間窗開始時間[a[i],b[i]]
b=c101(2:end,6); %站點時間窗結(jié)束時間[a[i],b[i]]
s=c101(2:end,7); %站點的服務(wù)時間
h=pdist(vertexs);
dist=squareform(h); %距離矩陣,滿足三角關(guān)系,暫用距離表示花費c[i][j]=dist[i][j]
alpha=10; %違反的容量約束的懲罰函數(shù)系數(shù)
belta=100; %違反時間窗約束的懲罰函數(shù)系數(shù)
MAXGEN=100; %迭代次數(shù)
%% 遺傳算法
NIND=100; %種群大小
Pc=0.9; %交叉概率
Pm=0.05; %變異概率
GGAP=0.9; %代溝(Generation gap)
N=cusnum+v_num-1; %染色體長度=站點數(shù)目+車輛最多使用數(shù)目-1
addpath('.GA')
[FF_GA,bestVC_GA]=ga(cusnum,a,b,L,s,dist,demands,cap,NIND,N,alpha,belta,GGAP,Pm,Pc,MAXGEN);
rmpath('.GA')
%%
%% 禁忌搜索設(shè)置參數(shù)
lamda=0.015;
delta=0.5;
vehicles_customer=cell(cusnum,1); %每輛車所經(jīng)過的站點
TbLength=20; %禁忌長度
addpath('.TW')
[FF_TW,bestVC_TW]=TW(cusnum,a,b,L,s,dist,demands,cap,alpha,belta,MAXGEN,TbLength,delta,lamda);
rmpath('.TW')
disp('遺傳算法最優(yōu)解:')
draw_Best(bestVC_GA,vertexs);
title('遺傳算法最優(yōu)派車方案路線圖')
disp('禁忌搜索算法最優(yōu)解:')
draw_Best(bestVC_TW,vertexs);
title('禁忌搜索算法最優(yōu)派車方案路線圖')
figure(3);
hold on;box on
xlim([0,MAXGEN])
title('迭代曲線')
xlabel('代數(shù)')
ylabel('最優(yōu)值')
plot(1:MAXGEN,FF_GA,'b-',1:MAXGEN,[FF_TW,FF_TW(end)],'r-')
legend('遺傳算法','禁忌搜索算法')
toc
3 仿真結(jié)果
4 參考文獻(xiàn)
[1]閻慶, and 邰蕾蕾. "用混合遺傳算法解決有時間窗的車輛路徑規(guī)劃問題." 安徽大學(xué)學(xué)報(自科版) 032.002(2007):41-44.
?
本文摘自 :https://blog.51cto.com/u