自動駕駛路徑非繞行共享程序

1、functionsharingautonomoustaxi% 這是分析自動駕駛出租車非繞行共享系統(tǒng)的程序（this is the program toautonomous taxi system)% 下面是出租車數(shù)量的初始值設置（Following is the initial setting of taxi distribution) taxinumber=zeros(2000,24); %需設置多于1440（一小時為1440分鐘）行，24個節(jié)點（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%如果初始時節(jié)點間的值不一樣,需用此循環(huán)（ 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% 以上是出租車數(shù)量的初始值設置（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); %路網(wǎng)數(shù)據(jù)B=zeros(24,24)+inf; %24*24節(jié)點間的出行時間+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對最短路徑上的節(jié)點數(shù) 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); %生成一個隨機數(shù)據(jù)（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、整數(shù) （generates two24)egers betn 1 andif G(1,1)=G(1,2) %用于判斷此2數(shù)是否相同，若相同，則重新生成 （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; %總出行數(shù) total trip numbercellnumber=zeros(60,24

15、); %每分鐘的出行數(shù)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); %路徑經(jīng)過的節(jié)點和到達時間to save nodes and arrival timeend assignednodenum=zeros(totaltripnumber,1); %路徑經(jīng)過的節(jié)點數(shù)nodes of every routerow=0; %已經(jīng)分配的出行數(shù)number of trips which were assigned win occupied taxidatabase=0; %已經(jīng)采用空車的出行數(shù)number of trips in assigneddatabase residual=1

17、; %waiting list中的出行數(shù)，初始值設為1iteration=0; %用于實時顯示迭代次數(shù)% 以下程序已經(jīng)共享的出行和數(shù)量following codes are used to save the already reassigned tripsand its number alreadyassigned=zeros(totaltripnumber,1); already=0;% 以上程序已經(jīng)共享的出行its number r sharedistance=0;和數(shù)量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; %本次循環(huán)的總出行數(shù) the total tripnumberhis iterationunserved=residual-1; %循環(huán)中不能被服務的出行者數(shù) the number of customerst cannt beservedhis iterationresidual=1;OD=zeros(iterat

19、iontripnumber,4); %每次循環(huán)的OD數(shù)據(jù)for travel=1:iterationtripnumberif travel=(hh-1)*60+min%如果到達yy處的時間正好大于現(xiàn)在的時刻，說明yy是下一個即將到達的節(jié)點break%終止 else%否則continue%繼續(xù)endendif yy=assignednodenum(y,1) %如果yy正好是該出租車路徑的最后一個節(jié)點continue%不可行，判斷下一個出租車（出行） elseif yy=inf %yy為初始化值，說明該出租車行程已結束continue%不可行else endif con=1%如果本次出行已共享 c

20、ontinue%不可行，判斷下一次else%否則可行for share=1:assignednodenum(ss,1) %對于ss路徑上的每一個節(jié)點if s=assigneddatabasess,1(1,share) %如果s正好是其中一個節(jié)點 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; %可以共享，共享備選方案數(shù)加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%經(jīng)過檢驗，如果存在共享車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%搜索有空車的節(jié)點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; %等車時間為循環(huán)次數(shù) 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; %重車多久后變?yōu)榭哲?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; %出租車數(shù)量更新ODroute=zeros(1,n);ODroute=nodesshortestroutes,e(1,:); %從s到e的最短路徑 sizeODroute=nodesshortestroutenodenumber(s,e); %最短路徑的節(jié)點 database=database+1; %database的數(shù)量加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); %保留比節(jié)點數(shù)多一列，用于最晚到達時間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; %到達各個節(jié)點的時間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); % 最晚到達時間，以供后續(xù)共享判斷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; %出租車數(shù)量更新 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