车辆路径识别算法

❶ 请问金溢科技提出的ETC自由流路径识别系统解决方案

该系统方案采用5.8GHz DSRC技术，当车辆经过ETC标识站点时，将路径识别信息写入双片式OBU内。在出口时，依据入口信息、路径标识信息，系统自动辨识车辆实际行驶路径，从而实现按实际行驶路径收取通行费用，并进行精确拆分。

❷ 急求车辆路径问题遗传算法的matlab代码！！！！

python">function[path,lmin]=ga(data,d)%data为点集,d为距离矩阵，即赋权图
tic
%======================
sj0=data;%开环最短路线
%=================================
%sj0=[data;data(1,:)];%闭环最短路线
%=========================
x=sj0(:,1);y=sj0(:,2);
N=length(x);
%=========================
%d(N,:)=d(1,:);%闭环最短路线
%d(:,N)=d(:,1);%距离矩阵d
%======================
L=N;%sj0的长度
w=800;dai=1000;
%通过改良圈算法选取优良父代A
fork=1:w
c=randperm(L-2);
c1=[1,c+1,L];
flag=1;
whileflag>0
flag=0;
form=1:L-3
forn=m+2:L-1
ifd(c1(m),c1(n))+d(c1(m+1),c1(n+1))<d(c1(m),c1(m+1))+d(c1(n),c1(n+1))
flag=1;
c1(m+1:n)=c1(n:-1:m+1);
end
end
end
end
J(k,c1)=1:L;
end
J=J/L;
J(:,1)=0;J(:,L)=1;
rand('state',sum(clock));
%遗传算法实现过程
A=J;
fork=1:dai%产生0～1间随机数列进行编码
B=A;
c=randperm(w);
%交配产生子代B
fori=1:2:w
F=2+floor(100*rand(1));
temp=B(c(i),F:L);
B(c(i),F:L)=B(c(i+1),F:L);
B(c(i+1),F:L)=temp;
end;
%变异产生子代C
by=find(rand(1,w)<0.1);
iflength(by)==0
by=floor(w*rand(1))+1;
end
C=A(by,:);
L3=length(by);
forj=1:L3
bw=floor(1+fix(rand(1,3)*N));%产生1-N的3个随机数
bw=sort(bw);
C(j,:)=C(j,[1:bw(1)-1,bw(2)+1:bw(3),bw(1):bw(2),bw(3)+1:L]);
end
G=[A;B;C];
TL=size(G,1);
%在父代和子代中选择优良品种作为新的父代
[dd,IX]=sort(G,2);
temp=[];
temp(1:TL)=0;
forj=1:TL
fori=1:L-1
temp(j)=temp(j)+d(IX(j,i),IX(j,i+1));
end
end
[DZ,IZ]=sort(temp);
A=G(IZ(1:w),:);
end
path=IX(IZ(1),:)
%fori=1:length(path)
%path(i)=path(i)-1;
%end
%path=path(2:end-1);
lmin=0;l=0;
forj=1:(length(path)-1)
t1=path(j);t2=path(j+1);
l=d(t1,t2);
lmin=lmin+l;
end
xx=sj0(path,1);yy=sj0(path,2);
plot(xx,yy,'r-o');
axisequal
toc

代码亲自前几天还用来着，绝对可用

❸ 蚁群算法车辆路径优化问题信息素如何选择

述了。
目前蚁群算法主要用在组合优化方面，基本蚁群算法的思路是这样的：
1. 在初始状态下，一群蚂蚁外出，此时没有信息素，那么各自会随机的选择一条路径。
2. 在下一个状态，每只蚂蚁到达了不同的点，从初始点到这些点之间留下了信息素，蚂蚁继续走，已经到达目标的蚂蚁开始返回，与此同时，下一批蚂蚁出动，它们都会按照各条路径上信息素的多少选择路线(selection)，更倾向于选择信息素多的路径走（当然也有随机性）。
3. 又到了再下一个状态，刚刚没有蚂蚁经过的路线上的信息素不同程度的挥发掉了(evaporation)，而刚刚经过了蚂蚁的路线信息素增强(reinforcement)。然后又出动一批蚂蚁，重复第2个步骤。
每个状态到下一个状态的变化称为一次迭代，在迭代多次过后，就会有某一条路径上的信息素明显多于其它路径，这通常就是一条最优路径。
关键的部分在于步骤2和3：
步骤2中，每只蚂蚁都要作出选择，怎样选择呢？
selection过程用一个简单的函数实现：
蚂蚁选择某条路线的概率＝该路线上的信息素÷所有可选择路线的信息素之和
假设蚂蚁在i点，p(i,j)表示下一次到达j点的概率，而τ(i,j)表示ij两点间的信息素，则：
p(i,j)＝τ(i,j)/∑τ(i)
（如果所有可选路线的信息素之和∑τ(i)＝0，即前面还没有蚂蚁来过，概率就是一个[0,1]上的随机值，即随机选择一条路线）
步骤3中，挥发和增强是算法的关键所在（也就是如何数学定义信息素的）
evaporation过程和reinforcement过程定义了一个挥发因子，是迭代次数k的一个函数
ρ(k)＝1－lnk/ln(k+1)
最初设定每条路径的信息素τ(i,j,0)为相同的值
然后，第k+1次迭代时，信息素的多少
对于没有蚂蚁经过的路线：τ(i,j,k+1)＝(1－ρ(k))τ(i,j,k)，显然信息素减少了
有蚂蚁经过的路线：τ(i,j,k+1)＝(1－ρ(k))τ(i,j,k)＋ρ(k)/|W|，W为所有点的集合
为什么各个函数要如此定义，这个问题很难解释清楚，这也是算法的精妙所在。如此定义信息素的挥发和增强，以及路径选择，根据马尔可夫过程（随机过程之一）能够推导出，在迭代了足够多次以后，算法能够收敛到最佳路径。
组合优化很有意思的，像禁忌搜索、模拟退火、蚁群算法、遗传算法、神经网络这些算法能够解决很多生活中的实际问题，楼主有空可以招本书看看。

❹ 车牌识别算法主要有哪些方法呢

从火眼臻睛车牌识别网站上了解到的，车牌识别算法主要有（1）启发式车牌定位；（2）大规模神经网络识别；（3）易混淆字符处理；三个方面的处理方法。车牌识别算法相对于车牌识别系统来说还是很重要的，这个决定着车牌识别系统的识别率的高低。

❺ 什么是带时间窗口的车辆路径问题

车辆路线问题（VRP）最早是由Dantzig和Ramser于1959年首次提出，它是指一定数量的客户 ，各自有不同数量的货物需求，配送中心向客户提供货物，由一个车队负责分送货物，组织适当的行车路线，目标是使得客户的需求得到满足，并能在一定的约束下，达到诸如路程最短、成本最小、耗费时间最少等目的Paolo Toth，Daniele Vigo。THE VEHICLE ROUTING PROBLEM[M]。Society for Instrial and Applied Mathematics philadephia.2002。 在VRPTW中，车辆除了要满足VRP问题的限制之外，还必须要满足需求点的时窗限制，而需求点的时窗限制可以分为两种，一种是硬时窗（Hard Time Window），硬时窗要求车辆必须要在时窗内到达，早到必须等待，而迟到则拒收；另一种是软时窗（Soft Time Window），不一定要在时窗内到达，但是在时窗之外到达必须要处罚，以处罚替代等待与拒收是软时窗与硬时窗最大的不同[2]。 Bodin[4]和Solomon[5]分别对VRP及其变形问题和VRPTW问题作了较详细的综述。生产实际中许多问题都可以归结为VRPTW来处理, 如钢铁厂编制热轧带钢轧制计划问题实际上就是一个VRPTW问题。一些服务性行业中也普遍存在这样的问题, 如邮政投递，飞机、火车及公共汽车的调度等。自从Savelsbergh[6]证明了VRPTW是一个NP难问题之后, 对其算法的研究就主要集中到各种启发式算法上。遗传算法、禁忌搜索法和模拟退火法等智能化启发式算法的出现为求解VRPTW问题提供了新的工具。Thangiah[7]和Joe[8]都曾应用遗传算法求解VRPTW问题, 前者的目标是使总的服务成本最小, 而后者的目标有两个, 首先是使用最少的车辆, 其次是在使用最少车辆的前提下使总成本最小[3]。 时间窗车辆路径问题的求解方法[2] 含时窗限制之车辆途程问题（VRPTW）相对于车辆途程问题（VRP），必须额外考虑到运送时间与时间窗口，其主要的原因来自顾客有服务时间的最后期限和最早开始服务时间的限制。故在此限制条件之下，原本VRP问题除了空间方面的路径（Routing）考虑之外，还必须要加上时间上的排程（Scheling）考虑，同时由于场站也有时间窗的限制，也间接造成路径长度的限制，由此可知VRPTW的总巡行成本不仅包含运送成本，还需要考虑时间成本，以及未在时间窗限制内送达的处罚成本。因此，若要得到一个好的解答，时间和空间（Temporal andSpatial）问题的探讨是非常重要的。 由于VRPTW比VRP问题多考虑了一样时窗的因素，因此在解法上较VRP问题更为复杂，而根据Taillard（1997）等人的分类，求解VRPTW的方法可以分为六种，分述如下。 1、以分枝界限法求算之精确解法（Exact Algorithm Based on Branch-and-BoundTechniques）： Kolen（1987）利用这种方式可以求得精确解，但是只能解决六至十五个节点的问题，因此求解的范围过小，仅适用于小型问题。 2、途程建构启发式算法（Route Construction Heuristics）： 在一问题中，以某节点选择原则或是路线安排原则，将需求点一一纳入途程路线的解法。如Soloman（1987）的循序建构法（Sequential Insertion Heuristics）。 3、途程改善启发式算法（Route Improvement Heuristics）： 先决定一个可行途程，也就是一个起始解，之后对这个起始解一直做改善，直到不能改善为止。而常见的是节线交换法（Edge Exchange Procere），如Lin（1965）所提出的K-Optimal，以及Potvin与Rousseau（1993）提出一考虑旅行方向的交换算法。 4、合成启发式算法（Composite Heuristics）： 此种解法混合了途程建构启发式算法与途程改善启发式算法，如Russell（1995）所提出的Hybrid Heuristics便是混合了Potvin与Rousseau（1993）所提出的平行插入法，并在之中加入路线改善法的合成启发式算法；Roberto(2000)也提出的属于平行插入法与内部交换改善法的合成启发式解法来求解VRPTW的问题。 5、依据最佳化之启发式算法（Optimization-Based Heuristics）：如Koskosidis（1992）等人利用混合整数规划模块，再透过启发式算法，将原始问题分解成指派/分群的子问题的一系列的巡行以及排程问题。 6、通用启发式算法（Metaheuristics）： 传统区域搜寻方法的最佳解常因起始解的特性或搜寻方法的限制，而只能获得局部最佳解，为了改善此一缺点，近年来在此领域有重大发展，是新一代的启发式解法，包含禁忌法（Tabu Search）、模拟退火法（Simulated Annealing）、遗传算法（Genetic Algorithm）和门坎接受法（Threshold Accepting）等，可以有效解决局部最佳化的困扰。

❻ 车辆路径问题的车辆路径问题的发展

1959年Dantzig和Ramse首次对闭合式VRP进行了研究，描述的是将汽油送往各个加油站的实际问题，并首次提出了相应的数学规划模型以及求解算法。
1964年，Clark和Wright[4]一种对Dantzig-Ramse方法改进的有效的启发式算法Clark-Wright节约算法。
正是由于以上两篇开创性论文的发表，使得VRP成为运筹学以及组合优化领域的前沿和研究热点课题。
1969年，Christofides和Eilon应用2-opt[5]和3-opt[6]处理车辆路径问题。
1970年，提出了两阶段方法求解车辆路径问题，包括先分组后定路线（clusterfirst-route second）和先定路线后分组（routefirst-cluster second）两种启发式策略。
1981年，Fisher和Jaikumar提出以数学规划为主的最优化方法来处理包含大约50个顾客点的问题,同样其运算效率是一个亟待解决的问题。同年，Gullen，Jarvis和Ratliff建立了人机互动的启发式方法。
1981年，Bodin and Golden将众多的VRP求解方法进行了归纳。分为以下七种：数学解析法（Exact Procere）；人机互动法（Interactive Optimization）；先分群再排路线（Cluster First–Route Second）；先排路线再分群（Route First–Cluster Second）；节省法或插入法（Saving or Insertion）；改善或交换法（Improvement or Exchanges）；数学规划近似法（Mathematical programming）。
1990年以来，人工智能方法在解决组合优化问题上显示出强大功能，在各个领域得到充分应用，很多学者也将人工智能引入车辆路线问题的求解中，并构造了大量的基于人工智能的启发式算法。 禁忌搜索法（TS）基本上是属于一种人工智能型（AI）的局部搜寻方法，Willard首先将此算法用来求解VRP 。袁庆达[7]等设计了考虑时间窗和不同车辆类型的禁忌算法，这种算法主要采用GA方法产生初始解，然后禁忌算法对初始解优化。模拟退火方法具有收敛速度快，全局搜索的特点，Osman[8]对VRP的模拟退火算法进行了研究。遗传算法具有求解组合优化问题的良好特性，Holland首先采用遗传算法（GA）编码解决VRPTW 问题。现在多数学者采用混合策略，分别采用两种人工智能方法进行路线分组和路线优化。Ombuki[9]提出了用GA进行路线分组，然后用TS方法进行路线优化的混合算法。Bent和Van Hentenryck[10]则首先用模拟退火算法将车辆路线的数量最小化，然后用大邻域搜索法（largneighborhood search）将运输费用降到最低。
综合过去有关VRP的求解方法，可以将其分为精确算法（exact algorithm）与启发式算法（heuristics），其中精确算法有分支界限法、分支切割法、集合涵盖法等；启发式算法有节约法、模拟退火法、确定性退火法、禁忌搜寻法、基因算法、神经网络、蚂蚁殖民算法等。

❼ 我在做一个车辆路径问题,用遗传算法的,不会MATLAB编程,有人能帮我一下吗

% Optimizing a function using Simple Genetic Algorithm with elitist preserved
%Max f(x1,x2)=10-x1*x1-x2*x2+x1*x2; -2.0480<=x1,x2<=2.0480
clc;clear all;
format long;%Set the data format(设定数据显示格式)
%parameters Initialization (初始化参数)
T=100;% Generation( 仿真代数)
N=80;% Population size ( 群体规模)
pm=0.05;pc=0.8;%Crossover and mutation probability(交叉变异概率)
umax=2.048;umin=-2.048;%Parameter range(参数取值范围)
L=10;%Single parameter string length, the total coding length is 2L(单个参数字串长度，总编码长度2L)
bval=round(rand(N,2*L));%Population Initialization(初始种群)
bestv=-inf;%Optimal fitness Initialization(最优适应度初值)
%Iteration stsar(迭代开始)
for ii=1:T
%Decoding, and the fitness calculation(解码，计算适应度)
for i=1:N
y1=0;y2=0;
for j=1:1:L
y1=y1+bval(i,L-j+1)*2^(j-1);
end
x1=(umax-umin)*y1/(2^L-1)+umin;
for j=1:1:L
y2=y2+bval(i,2*L-j+1)*2^(j-1);
end
x2=(umax-umin)*y2/(2^L-1)+umin;
obj(i)=10-x1*x1-x2*x2+x1*x2; %The objective function(目标函数)
xx(i,:)=[x1,x2];
end
func=obj;%Objective function into the fitness function(目标函数转换为适应度函数)
p=func./sum(func);
q=cumsum(p);%Cumulative(累加)
[fmax,indmax]=max(func);%seeking the best in this generation(求当代最佳个体)
if fmax>=bestv
bestv=fmax;%So far, the best fitness value(到目前为止最优适应度值)
bvalxx=bval(indmax,:);%So far the best bit string(到目前为止最佳位串)
optxx=xx(indmax,:);%So far the optimal parameters(到目前为止最优参数)
end
Bfit1(ii)=bestv; % So far the optimal parameters(存储每代的最优适应度)
%%%%Genetic operation starts(遗传操作开始)
%Roulette wheel selection(轮盘赌选择)
for i=1:(N-1)
r=rand;
tmp=find(r<=q);
newbval(i,:)=bval(tmp(1),:);
end
newbval(N,:)=bvalxx;%Optimal retention(最优保留)
bval=newbval;
%Single-point crossover(单点交叉)
for i=1:2:(N-1)
cc=rand;
if cc<pc
point=ceil(rand*(2*L-1));%To obtain one integer from 1 to 2L-1(取得一个1到2L-1的整数)
ch=bval(i,:);
bval(i,point+1:2*L)=bval(i+1,point+1:2*L);
bval(i+1,point+1:2*L)=ch(1,point+1:2*L);
end
end
bval(N,:)=bvalxx;%Optimal retention(最优保留)
%Locus mutation(位点变异)
mm=rand(N,2*L)<pm;%N lines(N行)
mm(N,:)=zeros(1,2*L);%Variation of the last line not change set to 0(最后一行不变异，强制赋0)
bval(mm)=1-bval(mm);
end

%Output(输出)
plot(Bfit1);% Draw the best fitness evolution curves(绘制最优适应度进化曲线)
bestv %Output the optimal fitness value(输出最优适应度值)
这个遗传的我没试过
下面这个是蚁群的结果
function [R_best,L_best,L_ave,Shortest_Route,Shortest_Length]=ACATSP(C,NC_max,m,Alpha,Beta,Rho,Q)
%%=========================================================================
%% ACATSP.m
%%-------------------------------------------------------------------------
%% 主要符号说明
%% C n个城市的坐标，n×2的矩阵
%% NC_max 最大迭代次数
%% m 蚂蚁个数
%% Alpha 表征信息素重要程度的参数
%% Beta 表征启发式因子重要程度的参数
%% Rho 信息素蒸发系数
%% Q 信息素增加强度系数
%% R_best 各代最佳路线
%% L_best 各代最佳路线的长度
%%=========================================================================

%%第一步：变量初始化
C=[1304,2312;3639,1315;4177,2244;3712,1399;3488,1535;3326,1556]
NC_max=200;
m=31;
Alpha=1;
Beta=5;
Rho=0.1;
Q=100;

n=size(C,1);%n表示问题的规模（城市个数）
D=zeros(n,n);%D表示完全图的赋权邻接矩阵
for i=1:n
for j=1:n
if i~=j
D(i,j)=((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2)^0.5;
else
D(i,j)=eps;
end
D(j,i)=D(i,j);
end
end
Eta=1./D;%Eta为启发因子，这里设为距离的倒数
Tau=ones(n,n);%Tau为信息素矩阵
Tabu=zeros(m,n);%存储并记录路径的生成
NC=1;%迭代计数器
R_best=zeros(NC_max,n);%各代最佳路线
L_best=inf.*ones(NC_max,1);%各代最佳路线的长度
L_ave=zeros(NC_max,1);%各代路线的平均长度

while NC<=NC_max%停止条件之一：达到最大迭代次数
%%第二步：将m只蚂蚁放到n个城市上
Randpos=[];
for i=1:(ceil(m/n))
Randpos=[Randpos,randperm(n)];
end
Tabu(:,1)=(Randpos(1,1:m))';

%%第三步：m只蚂蚁按概率函数选择下一座城市，完成各自的周游
for j=2:n
for i=1:m
visited=Tabu(i,1:(j-1));%已访问的城市
J=zeros(1,(n-j+1));%待访问的城市
P=J;%待访问城市的选择概率分布
Jc=1;
for k=1:n
if length(find(visited==k))==0
J(Jc)=k;
Jc=Jc+1;
end
end
%下面计算待选城市的概率分布
for k=1:length(J)
P(k)=(Tau(visited(end),J(k))^Alpha)*(Eta(visited(end),J(k))^Beta);
end
P=P/(sum(P));
%按概率原则选取下一个城市
Pcum=cumsum(P);
Select=find(Pcum>=rand);
to_visit=J(Select(1));
Tabu(i,j)=to_visit;
end
end
if NC>=2
Tabu(1,:)=R_best(NC-1,:);
end

%%第四步：记录本次迭代最佳路线
L=zeros(m,1);
for i=1:m
R=Tabu(i,:);
for j=1:(n-1)
L(i)=L(i)+D(R(j),R(j+1));
end
L(i)=L(i)+D(R(1),R(n));
end
L_best(NC)=min(L);
pos=find(L==L_best(NC));
R_best(NC,:)=Tabu(pos(1),:);
L_ave(NC)=mean(L);
NC=NC+1

%%第五步：更新信息素
Delta_Tau=zeros(n,n);
for i=1:m
for j=1:(n-1)
Delta_Tau(Tabu(i,j),Tabu(i,j+1))=Delta_Tau(Tabu(i,j),Tabu(i,j+1))+Q/L(i);
end
Delta_Tau(Tabu(i,n),Tabu(i,1))=Delta_Tau(Tabu(i,n),Tabu(i,1))+Q/L(i);
end
Tau=(1-Rho).*Tau+Delta_Tau;

%%第六步：禁忌表清零
Tabu=zeros(m,n);
end

%%第七步：输出结果
Pos=find(L_best==min(L_best));
Shortest_Route=R_best(Pos(1),:)
Shortest_Length=L_best(Pos(1))
subplot(1,2,1)
DrawRoute(C,Shortest_Route)
subplot(1,2,2)
plot(L_best)
hold on
plot(L_ave)

function DrawRoute(C,R)
%%=========================================================================
%% DrawRoute.m
%% 画路线图的子函数
%%-------------------------------------------------------------------------
%% C Coordinate 节点坐标，由一个N×2的矩阵存储
%% R Route 路线
%%=========================================================================

N=length(R);
scatter(C(:,1),C(:,2));
hold on
plot([C(R(1),1),C(R(N),1)],[C(R(1),2),C(R(N),2)])
hold on
for ii=2:N
plot([C(R(ii-1),1),C(R(ii),1)],[C(R(ii-1),2),C(R(ii),2)])
hold on
end

❽ 车辆路径问题代表的是哪一类的问题

车辆路径问题（vehicle routeing problem，VRP）通常指带有容量约束的车辆路径问题（capacitied vehicle routeing problem，CVRP）。这一问题与旅行商问题（travel salesman problem，TSP）具有一定渊源，TSP可以看作是VRP的特殊情况。

先说TSP吧，在一个平整表面，有若干个点，任意两点间均可到达，我们的旅行商现在正在0点处，他想顺次走完所有的点，而且一个点不想走两遍，最后回到0点，求怎么走总路径最短。
CVRP类似，平面内由一系列顾客点（costumer），以及一个车场（depot），一系列车辆想从车场出发不重不漏地访问所有顾客点最后回到车场。与TSP不同的是，每个顾客点都有一个可量化的需求，而每辆车能满足需求的能力有限，比如顾客点是消费者，车场是快递站，快递员从快递站出发为消费者送快递，但是快递员每次能拿的货是有限的，就需要好多快递员同时从快递站点出发，每个快递员访问一系列不同的消费者，最后回到快递站点。求怎么走总路径最短。

❾ 高速收费系统 路径识别

随着高速公路网不断延伸，路网存在二义性路径环的数量越来越多，越来越复杂，根据车辆行驶路径收费变得非常复杂，而经营性路段业务对于按实际路径收费的呼声越来愈高。
路径识别系统采用带权有向图为高速公路的路网建模，将复杂的路网按照一定的规则进行模型化处理；采用分布计算和内存计算等技术，极大地提高系统处理速度；在业务处理逻辑层面，系统采用路径预测和路径分发技术，提前将车辆行驶路径提前分发到对应的收费站，能够满足高速公路快速收费的要求；在数据传输层面，采用类似通信中间件技术，确保路径数据的采集、分发能够快速、准确传输到相应的地方。通过上述技术，最终满足按实际路径收费、实际路径拆帐的联网收费技术要求。

基于路径识别的车辆行驶轨迹分析，为收费稽核提供数据支撑服务，提高偷逃费稽核能力。

❿ 高速收费站是如何知道车子行驶路线以及跑了多少里程的

最早的时候，上高速会拿着一张票证，它的原理是，司机进入高速公路后，按照入口的A计费点到出高速公路B计费点这一段最短的路径，来计算收费，现在很多地方都发一种高速公路二义性路径识别系统复合通行卡，这种卡里内置了电源，电磁线圈等，利用射频技术来记录车辆在高速路上的行车路径，由此计算里程。