两点间距离算法.doc

文档介绍：1）最近邻点法（Nearest Neighbor Procedure）：一开始以寻找离场站最近的需求点为起始路线的第一个顾客，此后寻找离最后加入路线的顾客最近的需求点，直到最后。
　　2）节省法（Clark and Wright Sav1）最近邻点法（Nearest Neighbor Procedure）：一开始以寻找离场站最近的需求点为起始路线的第一个顾客，此后寻找离最后加入路线的顾客最近的需求点，直到最后。
　　2）节省法（Clark and Wright Saving）：以服务每一个节点为起始解，根据三角不等式两边之和大于第三边之性质，其起始状况为每服务一个顾客后便回场站，而后计算路线间合并节省量，将节省量以降序排序而依次合并路线，直到最后。
Y=[500 560 570 670 995 1435 2280 2525 2680 3050 3545 4185 5200 5325 5975 7045 7385 8075 8165 8355 8560 8835 9055 9330 9525 9635 10500 9765 9865 9955 10100 10365 10900 11065 11375 11415 11510 11610 12050 12300 13650 14145 14215 15060 14235 14500 14550 14880 15160 15325 8250
] X=[9185 1445 7270 3735 2620 10080 10025 7160 13845 11935 7850 6585 7630 13405 2125 15365 14165 8825 5855 780 12770 2200 14765 7790 4435 10860 10385 565 2580 1565 9395 14835 1250 7280 15305 12390 6410 13915 9510 8345 4930 13265 14180 3030 10915 2330 7735 885 11575 8010 11000
]
scatter(X,Y)
function [d,DD]=dijkstra_aiwa(D,s)
[m,n]=size(D);
d=inf.*ones(1,m);
d(1,s)=0;
dd=zeros(1,m);
dd(1,s)=1;
y=s;
DD=zeros(m,m);
DD(y,y)=1;
counter=1;
while length(find(dd==1))<m
for i=1:m
if dd(i)==0
d(i)=min(d(i),d(y)+D(y,i));
end
end
ddd=inf;
for i=1:m
if dd(i)==0&&d(i)<ddd
ddd=d(i);
end
end
yy=find(d==ddd);
counter=counter+1;
DD(y,yy(1,1))=counter;
DD(yy(1,1),y)=counter;