参考文献

[1] 姜启元，《数学模型》第四版，北京：高等教育出版社，2011年

附录

Solution.m clc;

clear all;

A=xlsread('cumcm2011B附件2_全市六区交通网路和平台设置的数据表.xls','全市交通路口节点数据','b2:c583');

X=A(:,1); Y=A(:,2);

serve_plat=xlsread('cumcm2011B附件2_全市六区交通网路和平台设置的数据表.xls','全市交巡警平台','b2:b81');

city_out=xlsread('cumcm2011B附件2_全市六区交通网路和平台设置的数据表.xls','全市区出入口的位置','b2:b18');

road_start=xlsread('cumcm2011B附件2_全市六区交通网路和平台设置的数据表.xls','全市交通路口的路线','a2:a929');

road_end=xlsread('cumcm2011B附件2_全市六区交通网路和平台设置的数据表.xls','全市交通路口的路线','b2:b929');

name=xlsread('cumcm2011B附件2_全市六区交通网路和平台设置的数据表.xls','全市交巡警平台','a2:a81');

plat_location=A(serve_plat,:); city_out_location=A(city_out,:);

plot(city_out_location(:,1),city_out_location(:,2),'*',plat_location(:,1),plat_location(:,2),'r+');

legend('全市出口位置','全市平台位置'); hold on

for i=1:length(road_start)%%%%%%plot this city's routine

plot([X(road_start(i)),X(road_end(i))],[Y(road_start(i)),Y(road_end(i))]);

end

plot(362,443,'o');

%%%%%%%%%%%%%%%%%next transform the graph into matrix%%%%%%%%%%%%%% D=ones(582);

8

for i=1:582%%%%i 表示路口的节点编号%%%%%%%%%%%% m=find(road_start==i); N=road_end(m);

D(i,N)=sqrt(abs(X(i)^2+Y(i)^2-X(N).^2-Y(N).^2)); end

D(D==1)=inf;%%%%%%%%至此矩阵生成完毕

D(logical(eye(size(D))))=0;%将对角矩阵变为0

%%%%%%%%%%look for the shortest road to the city_out for every serve_plat————useing Floyd%%%%%%%%%%%%%%%%%

m=length(serve_plat); n=length(city_out);

distance=ones(m,n);%%%%%%initial the distance Path=cell(m,n);

[Dis,path]=floyd(D); for i=1:size(Dis,1)-1 for j=i+1:size(Dis,1)

if eq(Dis(i,j),Dis(j,i))==0

Dis(i,j)=min(Dis(i,j),Dis(j,i)); Dis(j,i)=Dis(i,j); end end end

[Dis,path]=floyd(Dis); for i=1:size(Dis,1)-1 for j=i+1:size(Dis,1)

if eq(Dis(i,j),Dis(j,i))==0

Dis(i,j)=min(Dis(i,j),Dis(j,i)); Dis(j,i)=Dis(i,j); end end end

for i=1:m for j=1:n

[distance1

path1]=router(Dis,path,serve_plat(i),city_out(j));

distance(i,j)=distance1; Path(i,j)= {path1}; end end

[Matching,Cost] = Edmonds(distance); [m n]=find(Matching==1); re=[];

9

for i=1:length(m)

re=[re distance(m(i),n(i))]; end

long=max(re);

time=long*1e5/(1e6)/60; bihao=serve_plat(m); Time=re/600;

function [Matching,Cost] = Edmonds(a) Matching = zeros(size(a)); num_y = sum(~isinf(a),1); num_x = sum(~isinf(a),2); x_con = find(num_x~=0); y_con = find(num_y~=0);

P_size = max(length(x_con),length(y_con)); P_cond = zeros(P_size);

P_cond(1:length(x_con),1:length(y_con)) = a(x_con,y_con); if isempty(P_cond) Cost = 0; return end

Edge = P_cond;

Edge(P_cond~=Inf) = 0;

cnum = min_line_cover(Edge);

Pmax = max(max(P_cond(P_cond~=Inf))); P_size = length(P_cond)+cnum; P_cond = ones(P_size)*Pmax;

P_cond(1:length(x_con),1:length(y_con)) = a(x_con,y_con); exit_flag = 1; stepnum = 1; while exit_flag switch stepnum case 1

[P_cond,stepnum] = step1(P_cond); case 2

[r_cov,c_cov,M,stepnum] = step2(P_cond); case 3

[c_cov,stepnum] = step3(M,P_size); case 4

[M,r_cov,c_cov,Z_r,Z_c,stepnum] step4(P_cond,r_cov,c_cov,M);

case 5

[M,r_cov,c_cov,stepnum] = step5(M,Z_r,Z_c,r_cov,c_cov);

10

=

case 6

[P_cond,stepnum] = step6(P_cond,r_cov,c_cov); case 7

exit_flag = 0; end end

Matching(x_con,y_con) = M(1:length(x_con),1:length(y_con)); Cost = sum(sum(a(Matching==1))); function [D,path]=floyd(a)

%floyd算法通用程序，输入a为赋权邻接矩阵 %输出为距离矩阵D,和最短路径矩阵path n=size(a,1); D=a;

path=zeros(n,n); for i=1:n for j=1:n

if D(i,j)~=inf path(i,j)=j; end end end

for k=1:n for i=1:n for j=1:n

if D(i,k)+D(k,j)

function [P_cond,stepnum] = step1(P_cond) P_size = length(P_cond); for ii = 1:P_size

rmin = min(P_cond(ii,:));

P_cond(ii,:) = P_cond(ii,:)-rmin; end

stepnum = 2;

function [r_cov,c_cov,M,stepnum] = step2(P_cond) P_size = length(P_cond); r_cov = zeros(P_size,1); c_cov = zeros(P_size,1);

11