自动驾驶路径非绕行共享程序

1、functionsharingautonomoustaxi% 这是分析自动驾驶出租车非绕行共享系统的程序（this is the program toautonomous taxi system)% 下面是出租车数量的初始值设置（Following is the initial setting of taxi distribution) taxinumber=zeros(2000,24); %需设置多于1440（一小时为1440分钟）行，24个节点（we need to set theyze the non-detour sharedinitial number of taxis for mo

2、re taxinumber(1,:)=8; % 初始值设置（initial setting)n 1440 rows, 24 nodes)for i=1:24%如果初始时节点间的值不一样,需用此循环（ if the initial setting among nodes are different, weneed to use this loop) if round(i/4)=i/4taxinumber(901,i)=7;elsetaxinumber(901,i)=8;endend% 以上是出租车数量的初始值设置（Above is the initial setting of taxi dist

3、ribution)% 以下是生成路段时间（Following generates link travel time) rho=xlsread(correlation.xlsx,Sheet1);n=1000;variance=xlsread(link.xlsx,variance); initialmu=xlsread(link.xlsx,initialmu); traveltime=zeros(1440,76);for i=1:1440%generate correlation time sigma=variance(i,:); mu=initialmu(i,:);sigmadep=bsxfun

4、(times,sigma.2,eye(76); SigmaNew=sigmadep*rho*sigmadep; zdep=mvnrnd(mu,SigmaNew,n); xdep=exp(zdep);traveltime(i,:)=mean(xdep);end xlswrite(link.xlsx,traveltime,traveltime);linkmatrix=xlsread(link.xlsx,link); %路网数据B=zeros(24,24)+inf; %24*24节点间的出行时间+INFdistance=(rand(1,76)+5)/5; %生成路段长度 （generates len

5、gth of links) speed=zeros(24,24);for i=1:76x=linkmatrix(i,1);% y=linkmatrix(i,2);%make x equals to value of theelement of every rowmake y equals to value of the sencond element of every rowB(x,y)=3*traveltime(421,i);%make A(x,y) equals to value of the fourth element of every rowspeed(x,y)=distance(1

6、,i)/traveltime(421,i); end% 以上是生成路段时间（Above generates link travel time)% 以下程序用于计算所有OD对之间的最短路径（following codes are used to calculate the shortest distance among every node）nodesshortestdistance=zeros(24,24); %用于OD对之间的最短路径长度 to save the length of shortestroute betn every OD pairsnodesshortestroute=cel

7、l(24,24); %用于OD pairsOD对之间的最短路径 to save the shortest route betn everynodesshortestroutenodenumber=zeros(24,24); %用于OD对最短路径上的节点数 to save number ofnodes in every shortest routefor i=1:24for j=1:24nodesshortestroutei,j=zeros(2,24);endendfor i=1:24%用最短路算法求最短路 search the shortest paths bet n=size(B,1);D=

8、B(i,:);visit=ones(1,n); visit(i)=0; parent=zeros(1,n); for k=1:n-1temproute=zeros(1,n); counteroute=0;for l=1:nif visit(l)temproute=temproute(1:counteroute) D(l); elsetemproute=temproute(1:counteroute) inf;end counteroute=counteroute+1;endn every OD pairvalue,index=m l=index; visit(l)=0;for m=1:nemp

9、route);if D(m)D(l)+B(l,m)D(m)=D(l)+B(l,m);parent(m)=l;endendendnodesshortestdistance(i,:)=D; for route=1:24shortestroute=zeros(1,n); t=route; shortestroute(1)=t; count=1;while t=i & t0p=parent(t);shortestroute=p shortestroute(1:23); t=p;count=count+1;end shortestroute(1)=i;nodesshortestroutei,route(

10、1,:)=shortestroute; nodesshortestroutenodenumber(i,route)=count; for input=1:countif input=1nodesshortestroutei,route(2,input)=0;elsenodesshortestroutei,route(2,input)=nodesshortestroutei,route(2,input-1)+B(nodess hortestroutei,route(1,input-1),nodesshortestroutei,route(1,input);end endendendnodessh

11、ortestdistance=nodesshortestdistance+diag(-diag(nodesshortestdistance);% 以上程序用于计算所有OD对之间的最短路径（above codes are used to search the shortest pa every OD pair% 下面生成出行需求（Following generates trip generation) tripdistribution=xlsread(tripdistribution,Sheet1);for i=1:24%24 hoursfor j=1:60%60 minutesmongx=po

12、issrnd(1/2)*tripdistribution(j,i),1); %生成一个随机数据（generates one random number) O=zeros(x,1); % 代表x个起点（represents x origins)D=zeros(x,1); % 代表x个终点（represents x destinations)latestarrivaltime=zeros(x,1); % 代表x个最晚到达时间（represents x latest arrival time) for k=1:xfor t=1:100G=ceil(rand(1,2)*24); %生成两个介于124的

13、整数 （generates two24)egers betn 1 andif G(1,1)=G(1,2) %用于判断此2数是否相同，若相同，则重新生成 （to judge whether thetwo number are the same, if so, generates once again)break elsecontinueend endO(k,1)=G(1,1); %一个为起点 （one the two numbers is origin) D(k,1)=G(1,2); %另一个为终点（another one is destination)latestarrivaltime(k,1

14、)=(i-1)*60+j)+nodesshortestdistance(G(1,1),G(1,2)+10; %最晚到达时间 latest arrival time of every tripendtrip=O,D,latestarrivaltime; %出行需求 （trip demand)A(j,i)=trip;%出行需求 （save the trip demand)endend% 以上是生成出行需求（Above generates trip generation) totaltripnumber=0; %总出行数 total trip numbercellnumber=zeros(60,24

15、); %每分钟的出行数to calculate trip numbers of every minute for hh=1:24for min=1:60cellnumber(min,hh)=size(Amin,hh,1);totaltripnumber=totaltripnumber+cellnumber(min,hh);endendoutput=zeros(totaltripnumber,8); % to save the output of all trips in database assigneddatabase=cell(totaltripnumber,1);for i=1:tota

16、ltripnumberassigneddatabasei,1=zeros(2,24); %路径经过的节点和到达时间to save nodes and arrival timeend assignednodenum=zeros(totaltripnumber,1); %路径经过的节点数nodes of every routerow=0; %已经分配的出行数number of trips which were assigned win occupied taxidatabase=0; %已经采用空车的出行数number of trips in assigneddatabase residual=1

17、; %waiting list中的出行数，初始值设为1iteration=0; %用于实时显示迭代次数% 以下程序已经共享的出行和数量following codes are used to save the already reassigned tripsand its number alreadyassigned=zeros(totaltripnumber,1); already=0;% 以上程序已经共享的出行its number r sharedistance=0;和数量above codes are used to save the already reassigned trips an

18、d%以下是具体的车辆分配过程 （FOLLOWING IS THE PRODETAILED)for hh=1:24S OF VEHICLE ASSIGNMENT INfor min=1:60iterationtripnumber=size(Amin,hh,1)+residual-1; %本次循环的总出行数 the total tripnumberhis iterationunserved=residual-1; %循环中不能被服务的出行者数 the number of customerst cannt beservedhis iterationresidual=1;OD=zeros(iterat

19、iontripnumber,4); %每次循环的OD数据for travel=1:iterationtripnumberif travel=(hh-1)*60+min%如果到达yy处的时间正好大于现在的时刻，说明yy是下一个即将到达的节点break%终止 else%否则continue%继续endendif yy=assignednodenum(y,1) %如果yy正好是该出租车路径的最后一个节点continue%不可行，判断下一个出租车（出行） elseif yy=inf %yy为初始化值，说明该出租车行程已结束continue%不可行else endif con=1%如果本次出行已共享 c

20、ontinue%不可行，判断下一次else%否则可行for share=1:assignednodenum(ss,1) %对于ss路径上的每一个节点if s=assigneddatabasess,1(1,share) %如果s正好是其中一个节点 if share=assignednodenum(ss,1) %并且s不是ss路径的终点for shares=(share+1):assignednodenum(ss,1) %对于从s到ss路径终点之间if e=assigneddatabasess,1(1,shares) %恰好有一个点是eif assigneddatabasess,1(2,share

21、s)=OD(travel,3); %到达 e是时间不晚于s出行的最晚到达时间 potentialchoice=potentialchoice+1; %可以共享，共享备选方案数加1 potentialpotentialchoice,1=assigneddatabasess,1; %把ss加入备选方案集中 potentialrownum(potentialchoice,1)=ss; %ss potentialorigin(potentialchoice,1)=share; %s在ss路径中的位置potentialorigin(potentialchoice,2)=assigneddatabases

22、s,1(2,share); %ss路径到达s点的时间 potentialdestination(potentialchoice,1)=shares; %e在ss路径中的位置 potentialdestination(potentialchoice,2)=assigneddatabas ess,1(2,shares); %ss路径到达e的时间elseendendendendendendendendpotentialrow=0; %选中的共享出行在database中的choicenum=0; %选中的共享出行在potential库的starttime=inf; %真正的共享车到达s点的时间if p

23、otentialchoice=0%经过检验，如果存在共享车for choice=1:potentialchoice%对于所有可以进行共享的出行if potentialorigin(choice,2)=(hh-1)*60+min %如果本共享车尚未到达s点，且到达s点比之前判断的共享车到达s点早starttime=potentialorigin(choice,2); %把该到达时间赋值给starttime choicenum=choice; %本共享出行在potential库的 potentialrow=potentialrownum(choice,1); %本共享出行在database中的en

24、dendendif starttime=inf%starttime不等于INF，说明存在共享车occupieddritime=starttime-(hh-1)*60-min; %本次出行需等待共享车的时间sharewaittime=OD(travel,4)*1+(starttime-(hh-1)*60-min); %乘客的等待时间sharetraveltime=potentialdestination(choicenum,2)-potentialorigin(choicenum,2); %乘客的出行时间else end%以下开始搜索空车 temp=zeros(1,24); count=0;fo

25、r i=1:24%搜索有空车的节点if taxinumber(hh-1)*60+min,i)0 temp=temp(1:count) i; count=count+1;elsecontinueendendif count=0%如果都没有空车 if there is no unoccupied taxi at all nodes unoccupiedwaittime=inf; %空车到达乘客所需时间elseif isempty(find(temp=s)=1%如果乘客起点恰好有空车 if there is an unoccupied taxiat the origin of the custome

26、rindex1=s; %从s点取车unoccupiedwaittime=OD(travel,4)*1; %等车时间为循环次数 waiting time is the times of iterationempdritime=0; %车辆接客的空驶时间 the unoccupied driving time to pick up the customerelse %如果别的点有车distance=zeros(1,count); %有车点到s的最短路径 for j=1:count%最短路算法temps=temp(j); tempe=s; n=size(B,1);D=B(temps,:); taxi

27、searchroute=; visit=ones(1,n); visit(temps)=0; parent=zeros(1,n); for k=1:n-1temproute=zeros(1,n); counteroute=0;for l=1 nif visit(l)temproute=temproute(1:counteroute) D(l);elsetemproute=temproute(1:counteroute) inf;end counteroute=counteroute+1;endvalue,index=memproute);l=index; visit(l)=0; for m=1

28、:nif D(m)D(l)+B(l,m)D(m)=D(l)+B(l,m);parent(m)=l;endendenddistance(1,j)=D(tempe);endvalue1,index1=min(distance); %最近的点在temp中的 index1=temp(index1); %最近的点在24个点中的 empdritime=value1; %空驶时间和长度unoccupiedwaittime=value1+OD(travel,4)*1; %乘客等车时间 taxisearchroute=zeros(1,2*n); %以下是空车行驶路径 t=index1;taxisearchrou

29、te(1)=t; count=1;while t=temps & t0 p=parent(t);taxisearchroute=p taxisearchroute(1:count); t=p;count=count+1;end taxisearchroute(1)=temps;taxisearchroute=taxisearchroute(1:count);endtemoccupiedtime=inf; %选中的重车到达乘客的时间 temoccupiedwaittime=inf; %乘客等待时间 temoccupiedrr=0; %重车多久后变为空车 temoccupiedll=0; %重车变

30、为空车时所在的点for rr=1:1for ll=1:24if taxinumber(hh-1)*60+min+rr,ll)0%如果rr分钟后，ll点有空车if rr+nodesshortestdistance(ll,s)=10%如果车辆空驶时间小于10分钟if rr+nodesshortestdistance(ll,s)empdritime%如果等待空车的时间更短if temoccupiedtime=inf & temoccupiedtimeempdritime%如果重车的等车时间更短taxinumber(hh-)*60+memoccupiedrr,temoccupiedll)=taxinu

31、mber(hh-1)*60+memoccupiedrr,temoccupiedll)-1; %出租车数量更新ODroute=zeros(1,n);ODroute=nodesshortestroutes,e(1,:); %从s到e的最短路径 sizeODroute=nodesshortestroutenodenumber(s,e); %最短路径的节点 database=database+1; %database的数量加1number of taxis with singlecustomerfor h=1:sizeODrouteassigneddatabasedatabase,1(1,h)=ODr

32、oute(1,h); %把乘客路径信息加入assigneddatabase，以供后面共享分析save nodes of route of this customer endassigneddatabasedatabase,1=assigneddatabasedatabase,1(:,1:(sizeODroute)+1); %保留比节点数多一列，用于最晚到达时间assignednodenum(database,1)=sizeODroute; %save number of nodes of this customers routett=0; %出行时间 travel time for h=1:s

33、izeODroute-1assigneddatabasedatabase,1(2,h)=(hh-)*60+memoccupiedtime+tt+empdritime; %到达各个节点的时间save arrival time of every node ofthe customer tt=tt+B(ODroute(h),ODroute(h+1); %出行时间endassigneddatabasedatabase,1(2,h+1)=(hh-)*60+memoccupiedtime+tt+empdritime; %到达终点的时间save arrival time of destination of

34、the customer assigneddatabasedatabase,1(2,h+2)=OD(travel,3); % 最晚到达时间，以供后续共享判断save latest arrival time of the customeroutput(row,1)=(hh-1)*60+m output(row,2)=s; output(row,3)=e;in;output(row,6)=nodesshortestdistance(temoccupiedll,s); %空驶时间 output(row,7)=temoccupiedwaittime; %乘客等车时间output(row,8)=node

35、sshortestdistan row=row+1;,e); %乘客出行时间taxinumber(hh-)*60+memoccupiedrr+floor(output(row-,6)+output(row-,8)+1,e)=taxinumber(hh-)*60+memoccupiedrr+floor(output(row-1,6)+output(row-1,8)+1,e)+1; %出租车数量更新 continueelse%采用空车 waittime=unoccupiedwaittime;taxinumber(hh-1)*60+m endin,index1)=taxinumber(hh-1)*6

36、0+min,index1)-1;else%如果共享车的等车时间更短 already=already+1; alreadyassigned(already,1)=potentialrow;waittime=sharewaittime; traveltime=sharetraveltime; row=row+1; output(row,1)=(hh-1)*60+m output(row,2)=s; output(row,3)=e;output(row,4)=occupieddritime; output(row,5)=empdritime; output(row,6)=0; output(row,

37、7)=waittime; output(row,8)=traveltime;in;sharedistan continueharedistance+traveltime;endelseif starttime=inf & unoccupiedwaittime=inf%如果只有共享车 already=already+1;alreadyassigned(already,1)=potentialrow; waittime=sharewaittime; traveltime=sharetraveltime;row=row+1;output(row,1)=(hh-1)*60+m output(row,2

38、)=s; output(row,3)=e; output(row,4)=occupieddritime; output(row,5)=empdritime; output(row,6)=0; output(row,7)=waittime; output(row,8)=traveltime;in;sharedistan continueharedistance+traveltime;elseif starttime=inf & unoccupiedwaittime=inf%如果只有空车if temoccupiedtime=inf & temoccupiedtimeDa(j)+B(j,k)%Da(

39、k)=Da(j)+B(j,k); parenta(k)=j;endendenddistancea=Da(e); ODroute=zeros(1,2*n); ta=e;ODroute(1)=ta;counta=1;while ta=s & ta0p=parena);ODroute=p ODroute(1:counta); ta=p;counta=counta+1;endODroute(1)=s; ODroute=ODroute(1:counta); sizeODroute=size(ODroute,2); database=database+1;for h=1:sizeODroute assig

40、neddatabasedatabase,1(1,h)=ODroute(1,h);end assigneddatabasedatabase,1=assigneddatabasedatabase,1(:,1:sizeODroute); assignednodenum(database,1)=sizeODroute;tt=0;for h=1:sizeODroute-1assigneddatabasedatabase,1(2,h)=(hh-1)*60+m tt=tt+B(ODroute(h),ODroute(h+1);t+empdritime;endassigneddatabasedatabase,1

41、(2,h+1)=(hh-1)*60+mt+empdritime;taxinumber(hh-1)*60+min+floor(tt+empdritime)+1,e)=taxinumber(hh-1)*60+min+floor(tt+empdritime)+1,e)+1; %?X?Vnode空? row=row+1;output(row,1)=(hh-1)*60+m output(row,2)=s; output(row,3)=e; output(row,4)=occupieddritime; output(row,5)=empdritime; output(row,6)=empdritime;

42、output(row,7)=waittime; output(row,8)=tt;in;endtripresidual=tripresidual(1:residual-1,:); %未分配的出行 tripsve not been servedtaxinumber(hh-1)*60+min+1,:)=taxinumber(hh-1)*60+min+1,:)+taxinumber(hh-1)*60+min,:);iteration=iteration+1endendoutput=output(1:row,:);totalempdritime=0; %车辆总空驶时间 totalwaittime=0; %乘客总等车时间 totaltraveltime=0; %总载客行程时间 waitdistribution=zeros(1,21); %等待时间分布矩阵 for i=1 rowtotalempdritime=totalempdritime+output(i,6); %空驶时间 totalwaitt