公共自行车调度问题-数学建模论文

s=0; for j=1:1:53 if z(i,j)~=0

s=s+1/z(i,j);%输出概率的K end end s=1/s; K=[K s]; end

3分块距离矩阵计算： ○

distanceMb=zeros(20); for i=1:1:20 k=1; for j=1:1:20 if i~=j

distanceMb(i,k)=abs(x1(Mb(i),1)-x1(Mb(j),1))+abs(x1(Mb(i),2)-x1(Mb(j),2)); end k=k+1; end end

4启发式算法代码： ○

#include #include #include #include

#define ZD 20//定义站点数 ZD = Zhan Dian #define DE 3//搜索深度 using namespace std;

int num[ZD];//各个站点相应的多余、缺少的车辆的数目

- 31 -

int route[10*ZD]; //车行走的路径

bool IsEnd(int num[]){//判断是否所有的车都已经调度完毕 }

int Pathfinding(int first,int vol,int depth){//寻路 找到下一个路径最优的站点

int i;

for(i=0; i

if(num[i]!=0) return false; else return true;}

double distance[ZD][ZD]; //各个站点之间的距离 if(depth <=0)

return -1;

int temp_distance[ZD]; int i,j,k;

for(i=0;i

temp_distance[i] = i;//存储站点号码

for(i=0;i

for(j=i;j

if(distance[first][temp_distance[i]]>distance[first][temp_distance[j]]){ }

k = temp_distance[i];

temp_distance[i] = temp_distance[j]; temp_distance[j] = k;

}//排序 保留的是距离从小到大的站点号码

int bound = DE;//设置边界 int temp_site[DE]; int next_site[DE]; j=0;

for(i=0;i

if(vol + num[temp_distance[i]] >= 0 && num[temp_distance[i]]!=0 &&

- 32 -

temp_distance[i]!=first){

if(vol>=50 && num[temp_distance[i]] >0)

continue;

temp_site[j] = temp_distance[i]; next_site[j]

=

Pathfinding(temp_site[j],vol+num[temp_distance[i]],depth-1);

if(bound<=1)

break;

bound--; j++;

}//从i+1的原因是，第一个点是first点

}//搜索first节点的下一个和下下个节点

int change[ZD];//搬运车的总数 int lenth[ZD];//开车的距离

for(i=0;i

change[i]=0; lenth[i]=0; int voll = vol; if(temp_site[i]<=0)

break;

if(num[temp_site[i]]<0){ }

else if(50-voll > num[temp_site[i]]){ }

- 33 -

change[i] += abs(num[temp_site[i]]); voll += num[temp_site[i]];

change[i] += num[temp_site[i]]; voll += num[temp_site[i]];

else{ }

lenth[i] += distance[first][temp_site[i]];

change[i] += num[temp_site[i]] - 50 + vol; voll = 50;

}

if(next_site[i]>0){ }

else if(50- voll > num[next_site[i]]){ } else{ } }

lenth[i] += distance[first][next_site[i]]; change[i] += num[next_site[i]] - 50 + vol; voll = 50;

change[i] += num[next_site[i]]; voll += num[next_site[i]]; if(num[next_site[i]]<0){

change[i] += abs(num[next_site[i]]); voll += num[next_site[i]];

k=0;

double temp=0; for(i=0;i

- 34 -

if(change[i]>0 && lenth[i]>0 && (double)change[i]/lenth[i]>temp){ }

temp = (double)change[i]/lenth[i]; k = i;

}

return temp_site[k];

int main(){

ifstream fileinput;

fileinput.open(\char v[ZD]; for (i=0;i

{

fileinput>>num[i];

double distance[ZD][ZD]; int first;//初始站点

int time=0;//路径总共走过的站点数 int i,j;

} cout<

fileinput.close();

fileinput.open(\for (i=0;i

fileinput>>distance[i][j];cout<

cout<<\请输入车站起点：\cin>>first; first=first-1;

route[time] = first;//设置出发点 int vol;//注意点 if(num[first]<0) vol=0; else vol=num[first];

while(!IsEnd(num)){//车没搬完，一直搜索

time++;

- 35 -