diaodu.h

传统的Dijkstra 算法无疑是解决一般最短路径问题的最优算法

#include"graph.h"
//下面是调度函数
int B[6];//Bi,时间段Ti内发出的车辆数
float b[6];//时间段i的平均发车时间间隔为
float PL[6][90][20];//PL（i，k，j）时间段i内第k辆车离开第j个站点时,站点j上的人数
float PW[6][90][20];//PW（i，k，j）时间段Ti内第k辆车到达站点j时，站点j的等待上车人数
float C[6][90][20];//时间段i第k辆车离开站点j时的超载人数
float K[6][20];//时间段i内单位时间平均到站j的人数
float L[6][20];//时间段i内单位时间平均在站j下车的人数
float T[6];//时间段i的长度
int start[6];//5个时段的开始时刻
float t[14];//起点到各个站点的时间
float D[6][90][20];//D(i,k,j)，时间段Ti内第k辆车到达站点j时，下车的人数
float On[6][90][20];//On(i,k,j)，时间段Ti内第k辆车到达站点j时，乘客下车后，车能容纳上车的最大人数
float PLB[6][90][20];//PLB（i，k，j）时间段i内第k辆车离开第j个站点时,车上的人数
float W[6][90][20];//时间段Ti内第k辆车到达站点j时，等待时间过长的乘客
float w[6],c[6],z[6];//记录各个目标函数的数值。
int b1;//全局变量，要调度的线路的站点数
//读取文件时要初始化K[i][j],L[i][j],t[j]。。对K[i][j],L[i][j]也就是要计算各个时间段i某个站点上下车的总人数，
//除与时间段的长度T[i]，即可得到K[i][j],L[i][j],至于t[j]则距离除与速度
//T[i]一是直接初始化，用方法1初始化，用方法2初始化......要不采用输入法自己决定。


//第几时段是从0算起!!!!!!
void initiate1()
{//划分各个时段

	start[0]=5;
	start[1]=6;
    start[2]=9;
    start[3]=16;
    start[4]=18;
	start[5]=23;
	int i,j;
	//初始化K[5][14],L[5][14]
	for(i=0;i<5;i++)
       for(j=0;j<b1;j++)///////////
	     K[i][j]=L[i][j]=0;
	for(i=0;i<5;i++)
		T[i]=(start[i+1]-start[i])*60;

}

void initiate2()
{//划分各个时段

	start[0]=5;
	start[1]=7;
    start[2]=10;
    start[3]=16;
    start[4]=19;
	start[5]=23;
	int i,j;
	//初始化K[5][14],L[5][14]
	for(i=0;i<5;i++)
       for(j=0;j<b1;j++)///////////
	     K[i][j]=L[i][j]=0;
	for(i=0;i<5;i++)
		T[i]=(start[i+1]-start[i])*60;

}

int change(int n)//看开始时间n是第几时段
{
	int i;
	for(i=0;i<5;i++)
		if(start[i]<=n&&n<start[i+1])return i;
	return i;
}

int larger(int a,int b)//看谁大
{
	if(a>b)return a;
	else return b;
}

int less(int a,int b)//看谁小
{
	if(a<b)return a;
	else return b;
}



int getdata1(char *filename)//初始化T[],K[][],L[][]
{
	int time,r,i,j,n;
    char ch;
	ifstream fin1(filename,ios::in);
	if(!fin1)
	{
		cout<<"输入有误，没有该文件!"<<endl;
		return 0;
	}
    
    while(fin1.get(ch)){if(ch==':')break;}
    fin1>>b1;//读入站点数

	initiate1();
    fin1.get(ch);//读入换行符，使文件指针指向下一行
    while(fin1.get(ch))if(ch=='\n')break;//跳过第一行
	while(fin1.get(ch))if(ch=='\t')break;
    //准备开始读战间距离
	for(j=0;j<b1;j++)//先读入距离/////////////////
		fin1>>t[j];
	fin1.get(ch);//'\n'

    for(i=1;i<=36;i++)//再读入人数，单数行上车人数，双数行下车人数
	{	
		if(i%2)//单数行，读入上车人数
		{
			while(fin1.get(ch)){if(ch=='\t'||ch==' ')break;}
			time=(i-1)/2+5;//看开始时间t是
			r=change(time);//看是第几时段
			for(j=0;j<b1;j++)/////////////b1
            {
				fin1>>n;
			    K[r][j]+=n;
			}
			fin1.get(ch);//'\n'
		}
		else//双数行，读入下车人数
		{
			while(fin1.get(ch)){if(ch=='\t')break;}
            while(fin1.get(ch)){if(ch=='\t')break;}
			time=i/2-1+5;//看开始时间t是
			r=change(time);//看是第几时段
			for(j=0;j<b1;j++)////////////b1
            {
				fin1>>n;
			    L[r][j]+=n;
			}
			fin1.get(ch);//'\n'
		}
	}//for(i=1;i<=36;i++)//再读入人数，单数行上车人数，双数行下车人数

		for(i=0;i<5;i++)
			for(j=0;j<b1;j++)//////////
			{
				K[i][j]/=T[i];
				L[i][j]/=T[i];
			}
			
        for(i=b1-1;i>=0;i--)///////
		{
			for(j=i-1;j>=0;j--)
				t[i]+=t[j];
			t[i]=t[i]*3;
		}
		fin1.close();
	return 1;
}

//运行下列前要先初始化数组T[i]、、、、、、、、、
void findbestBi(int i,int b1)//求时段i最佳发车数B[i]，b1为站点数
{
	int k,j,wtime,bestbi;
	float m=-1;
	float zi,ci,wi,pi;
	if(b1==1||b1==3)wtime=5;//根据繁忙时段取等待时间，现在时段2，时段4是高峰期
	else wtime=10;
	for(B[i]=1;B[i]<90;B[i]++)//测试时段i各种发车数
	{
		b[i]=T[i]/B[i];//时间段i的平均发车时间间隔
        //k=1时，即第一趟车到达站点j时，站点j的乘客数
		//使用前要初始化t[j],K[i][j]，L[i][j]、、、、、、、、、
	    t[0]=0;
		//对起点站的数据处理
		PLB[i][1][0]=K[i][0];
		W[i][1][0]=K[i][0]*b[i]/2;
        for(k=2;k<=B[i];k++)
		{
			PLB[i][k][0]=b[i]*K[i][0];
            if(2*b[i]>wtime)W[i][k][0]=K[i][0]*(2*b[i]-wtime);
			else W[i][k][0]=0;
		}
		for(k=1;k<=B[i];k++)
		{
		if(b[i]>wtime)W[i][k][0]=K[i][0];
		PW[i][k][0]=K[i][0];
        D[i][k][0]=0;
		C[i][k][0]=larger(PLB[i][k][0]-100,0);
		On[i][k][0]=120;
		PL[i][k][0]=0;
		}
        

		for(j=1;j<b1;j++)//第一趟车的数据处理
		{
			PW[i][1][j]=t[j]*K[i][j];
            D[i][1][j]=(t[j]-t[j-1])*L[i][j];
			On[i][1][j]=120-(PLB[i][1][j-1]-D[i][1][j]);//车上乘客下车后,车上的最大容量
            PLB[i][1][j]=larger(PLB[i][1][j-1]-D[i][1][j]+less(On[i][1][j],PW[i][1][j]),0);	
			C[i][1][j]=larger(PLB[i][1][j]-100,0);
			PL[i][1][j]=larger(PW[i][1][j]-On[i][1][j],0);
            if(2*b[i]>wtime)W[i][1][j]=K[i][j]*(2*b[i]-wtime);
            else W[i][1][j]=0;
		}
		
		for(k=2;k<=B[i];k++)//逐次推导时间段i的第k趟车
			for(j=1;j<b1;j++)//逐次推导每个站
			{
				PW[i][k][j]=PL[i][k-1][j]+b[i]*K[i][j];
                D[i][k][j]=b[i]*L[i][j];
				On[i][k][j]=larger(120-(PLB[i][k][j-1]-D[i][k][j]),0);
				PLB[i][k][j]=larger(PLB[i][k][j-1]-D[i][k][j]+less(On[i][k][j],PW[i][k][j]),0);
				C[i][k][j]=larger(PLB[i][k][j]-100,0);
				PL[i][k][j]=larger(PW[i][k][j]-On[i][k][j],0);
				//If（T（i，k，j）-10>T（i,k-2,j））W（i，k，j）=max{ Kij*（T（i，k，j）-10- T（i,k-2,j）），PL(i,k-1,j)}
                if(2*b[i]>wtime)W[i][k][j]=larger(K[i][j]*(2*b[i]-wtime),PL[i][k-1][j]);
				else W[i][k][j]=0;
			}//for(j=1;j<b1;j++)//逐次推导每个站

		//求时间段i车上总人数
        zi=ci=wi=pi=0;
		for(k=1;k<=B[i];k++)
			for(j=0;j<b1;j++)
			{
				pi+=PLB[i][k][j];
				wi+=W[i][k][j];
				ci+=C[i][k][j];
			
			}
			wi/=pi;//（超时的乘客在时间段i所占的比例）
			ci/=pi;//（超载的乘客在时间段ｉ所占的比例）
			zi=pi/(100*B[i]*b1);//（满载率）
			if(zi>0.5&&zi<1.2)
			if(zi/3-wi/3-ci/3>m)
			{
				m=zi/3-wi/3-ci/3;
				z[i]=zi;
				w[i]=wi;
				c[i]=ci;
				bestbi=B[i];
			} 

	}//	for(B[i]=1;B[i]<90;B[i]++
 cout<<"时间段"<<i+1<<":"<<start[i]<<":00-"<<start[i+1]<<":00,最佳调度为:每间隔"<<T[i]/bestbi<<"分钟发一班车"<<endl;
 cout<<"对该时间段的相关预测如下："<<endl;
 cout<<"车辆的满载率为"<<z[i]<<",等待超时乘客比例为"<<w[i]<<",超载的乘客比例为"<<c[i]<<endl<<endl;
}//函数结束