数据结构关于物流配送路径最优问题的课程设计报告

1、-PAGE . z. / v .数据构造课程设计报告物流配送中的最优路径规划模拟软件学生*：指导教师：所 在 系：电 子 信 息 系所学专业：计 算 机 科 学 与 技 术 年 级：2011级 计算机 2 班2013年6月13日摘要：通过对路径寻优问题的探讨分析，合理选取城市物流配送模式，结合物流配送的一般实际情况，确定较好的解决城市物流配送的路径寻优问题的最为关键一步就是解决末级配送中心的最优配送路线问题；然后深入剖析了影响配送的各种因素，建立基于费用本钱，时间最少，距离最近为一体的最优配送路径的配送系统数学模型。关键词：物流配送 路径最优 数学模型目 录 TOC o 1-3 h z u H

2、YPERLINK l _Toc358971960目录 PAGEREF _Toc358971960 h 2HYPERLINK l _Toc358971961第一章需求分析 PAGEREF _Toc358971961 h 3HYPERLINK l _Toc358971962第二章概要分析 PAGEREF _Toc358971962 h 4HYPERLINK l _Toc3589719631、最短路径分析 PAGEREF _Toc358971963 h 4HYPERLINK l _Toc3589719642、最短时间分析 PAGEREF _Toc358971964 h 5HYPERLINK l _T

3、oc3589719653、最少费用分析 PAGEREF _Toc358971965 h 6HYPERLINK l _Toc358971966第三章系统代码 PAGEREF _Toc358971966 h 7HYPERLINK l _Toc358971967第四章系统调试 PAGEREF _Toc358971967 h 20HYPERLINK l _Toc3589719681、查看城市 PAGEREF _Toc358971968 h 20HYPERLINK l _Toc3589719692、最短路径查询 PAGEREF _Toc358971969 h 20HYPERLINK l _Toc3589

4、719703、最短时间查询 PAGEREF _Toc358971970 h 21HYPERLINK l _Toc3589719714、最少费用查询 PAGEREF _Toc358971971 h 21HYPERLINK l _Toc3589719725、退出系统 PAGEREF _Toc358971972 h 22HYPERLINK l _Toc358971973第五章系统分析与运行环境 PAGEREF _Toc358971973 h 23HYPERLINK l _Toc358971974第六章实验小结 PAGEREF _Toc358971974 h 24HYPERLINK l _Toc358

5、971975参考文献 PAGEREF _Toc358971975 h 25第一章 需求分析随着市场经济的开展和物流技术专业化水平的提高，物流配送业得到了迅猛开展。配送路径的选择是否合理，对加快配送速度、提高效劳质量、降低配送本钱及增加经济效益都有较大影响。配送路径的优化问题是物流配送系统的一个主要问题，物流配送路径的优化就是以最低的运营本钱、最快捷的响应速度、最短的配送运输时间，把货物运至用户手中。第二章 概要分析物流车装载当日需要配送的货品从仓库出发，按照事先规划好的最优配送路径为每一个客户进展配送。IT系统在配送之前需要根据客户的配送地址间线路间距、经历路况做分析计算出一条最优配送路径。此

6、题要求利用c语言设计一套模拟软件，使物流公司可以按照最短路程、最短时间及最少费用的策略生成配送方案，并在软件界面上模拟车辆的行进。1、最短路径分析开场仓库到客户的距离系统分析两地间的路径路 径 是否 最 短输出两地间的最短路径完毕否是图12、最短时间分析否是开场仓库到客户的距离系统分析两地间的路径时 间 是否 最 短输出两地间的最短时间完毕图23、最少费用分析否是开场仓库到客户的费用系统分析两地间的费用费 用 是否 最 少输出两地间的最少费用完毕图3第三章 系统代码/*物流配送路径最优程序模拟*/#includestring.h#includestdio.h#include math.htyp

7、edef struct ArcCellint adj;/相邻接的城市序号ArcCell;/定义边的类型typedef struct verte*typeint number;/城市序号char *city;/城市名称Verte*Type;/定义顶点的类型typedef structVerte*Type ve*12;/图中的顶点，即为城市ArcCell arcs1212;/图中的边，即为城市的距离ArcCell prices1212;/图中的第二边，即为城市的费用ArcCell times1212;/图中的第三边，即为城市的时间int ve*num,arum,pricenum,timenum;

8、MGraph;/定义图的类型MGraph G;/把图定义为全局变量int P1212;long int D12;void CreateUDN1(v,p)/造图函数int v,p;int m,n;G.ve*num=v;G.pricenum=p;for(m=0;mG.ve*num;+m)G.ve*m.number=m;/下边是城市名G.ve*0.city=;G.ve*1.city=;G.ve*2.city=;G.ve*3.city=;G.ve*4.city=;G.ve*5.city=;G.ve*6.city=亳州;G.ve*7.city=;G.ve*8.city=;G.ve*9.city=;G.v

9、e*10.city=;G.ve*11.city=池州;/这里把所有的边假定为20000，含义是城市间不可到达for(m=0;mG.ve*num;+m)for(n=0;nG.ve*num;+n)G.pricesmn.adj=20000;/下边是可直接到达的城市间的费用，由于两个城市间的费用是相互的，所以要对图中对称的边同时赋值G.prices01.adj=G.prices10.adj=13;G.prices02.adj=G.prices20.adj=54;G.prices03.adj=G.prices30.adj=24;G.prices04.adj=G.prices40.adj=7;G.pric

10、es05.adj=G.prices50.adj=36;G.prices06.adj=G.prices60.adj=62;G.prices07.adj=G.prices70.adj=47;G.prices08.adj=G.prices80.adj=29;G.prices09.adj=G.prices90.adj=38;G.prices010.adj=G.prices100.adj=54;G.prices011.adj=G.prices110.adj=23;G.prices12.adj=G.prices21.adj=44;G.prices13.adj=G.prices31.adj=13;G.pri

11、ces14.adj=G.prices41.adj=14;G.prices15.adj=G.prices51.adj=29;G.prices16.adj=G.prices61.adj=55;G.prices17.adj=G.prices71.adj=30;G.prices18.adj=G.prices81.adj=42;G.prices19.adj=G.prices91.adj=24;G.prices110.adj=G.prices101.adj=44;G.prices111.adj=G.prices111.adj=19;G.prices23.adj=G.prices32.adj=38;G.pr

12、ices24.adj=G.prices42.adj=42;G.prices25.adj=G.prices52.adj=12;G.prices26.adj=G.prices62.adj=26;G.prices27.adj=G.prices72.adj=15;G.prices28.adj=G.prices82.adj=33;G.prices29.adj=G.prices92.adj=30;G.prices210.adj=G.prices102.adj=15;G.prices211.adj=G.prices112.adj=50;G.prices34.adj=G.prices43.adj=19;G.p

13、rices35.adj=G.prices53.adj=42;G.prices36.adj=G.prices63.adj=25;G.prices37.adj=G.prices73.adj=22;G.prices38.adj=G.prices83.adj=64;G.prices39.adj=G.prices93.adj=16;G.prices310.adj=G.prices103.adj=38;G.prices311.adj=G.prices113.adj=24;G.prices45.adj=G.prices54.adj=50;G.prices46.adj=G.prices64.adj=74;G.

14、prices47.adj=G.prices74.adj=22;G.prices48.adj=G.prices84.adj=55;G.prices49.adj=G.prices94.adj=22;G.prices410.adj=G.prices104.adj=37;G.prices411.adj=G.prices114.adj=6;G.prices56.adj=G.prices65.adj=15;G.prices57.adj=G.prices75.adj=22;G.prices58.adj=G.prices85.adj=42;G.prices59.adj=G.prices95.adj=44;G.

15、prices510.adj=G.prices105.adj=25;G.prices511.adj=G.prices115.adj=36;G.prices67.adj=G.prices76.adj=47;G.prices68.adj=G.prices86.adj=65;G.prices69.adj=G.prices96.adj=38;G.prices610.adj=G.prices106.adj=17;G.prices611.adj=G.prices116.adj=42;G.prices78.adj=G.prices87.adj=20;G.prices79.adj=G.prices97.adj=

16、15;G.prices710.adj=G.prices107.adj=33;G.prices711.adj=G.prices117.adj=42;G.prices89.adj=G.prices98.adj=33;G.prices810.adj=G.prices108.adj=47;G.prices811.adj=G.prices118.adj=89;G.prices910.adj=G.prices109.adj=10;G.prices911.adj=G.prices119.adj=54;G.prices1011.adj=G.prices1110.adj=72;void CreateUDN2(v

17、,t)/造图函数int v,t;int m,n;G.ve*num=v;G.pricenum=t;for(m=0;mG.ve*num;+m)G.ve*m.number=m;/下边是城市名G.ve*0.city=;G.ve*1.city=;G.ve*2.city=;G.ve*3.city=;G.ve*4.city=;G.ve*5.city=;G.ve*6.city=亳州;G.ve*7.city=;G.ve*8.city=;G.ve*9.city=;G.ve*10.city=;G.ve*11.city=池州;/这里把所有的边假定为20000，含义是城市间不可到达for(m=0;mG.ve*num;+

18、m)for(n=0;nG.ve*num;+n)G.timesmn.adj=20000;/下边是可直接到达的城市间的时间，由于两个城市间的时间是相互的，所以要对图中对称的边同时赋值G.times01.adj=G.times10.adj=54;G.times02.adj=G.times20.adj=314;G.times03.adj=G.times30.adj=114;G.times04.adj=G.times40.adj=81;G.times05.adj=G.times50.adj=494;G.times06.adj=G.times60.adj=391;G.times07.adj=G.times

19、70.adj=246;G.times08.adj=G.times80.adj=159;G.times09.adj=G.times90.adj=205;G.times010.adj=G.times100.adj=309;G.times011.adj=G.times110.adj=120;G.times12.adj=G.times21.adj=285;G.times13.adj=G.times31.adj=88;G.times14.adj=G.times41.adj=176;G.times15.adj=G.times51.adj=349;G.times16.adj=G.times61.adj=33

20、2;G.times17.adj=G.times71.adj=187;G.times18.adj=G.times81.adj=273;G.times19.adj=G.times91.adj=171;G.times110.adj=G.times101.adj=288;G.times111.adj=G.times111.adj=228;G.times23.adj=G.times32.adj=224;G.times24.adj=G.times42.adj=298;G.times25.adj=G.times52.adj=50;G.times26.adj=G.times62.adj=255;G.times

21、27.adj=G.times72.adj=60;G.times28.adj=G.times82.adj=152;G.times29.adj=G.times92.adj=182;G.times210.adj=G.times102.adj=173;G.times211.adj=G.times112.adj=350;G.times34.adj=G.times43.adj=229;G.times35.adj=G.times53.adj=283;G.times36.adj=G.times63.adj=240;G.times37.adj=G.times73.adj=109;G.times38.adj=G.

22、times83.adj=73;G.times39.adj=G.times93.adj=71;G.times310.adj=G.times103.adj=165;G.times311.adj=G.times113.adj=251;G.times45.adj=G.times54.adj=416;G.times46.adj=G.times64.adj=453;G.times47.adj=G.times74.adj=380;G.times48.adj=G.times84.adj=240;G.times49.adj=G.times94.adj=331;G.times410.adj=G.times104.

23、adj=424;G.times411.adj=G.times114.adj=56;G.times56.adj=G.times65.adj=205;G.times57.adj=G.times75.adj=125;G.times58.adj=G.times85.adj=231;G.times59.adj=G.times95.adj=245;G.times510.adj=G.times105.adj=145;G.times511.adj=G.times115.adj=515;G.times67.adj=G.times76.adj=271;G.times68.adj=G.times86.adj=369

24、;G.times69.adj=G.times96.adj=174;G.times610.adj=G.times106.adj=68;G.times611.adj=G.times116.adj=515;G.times78.adj=G.times87.adj=33;G.times79.adj=G.times97.adj=99;G.times710.adj=G.times107.adj=192;G.times711.adj=G.times117.adj=331;G.times89.adj=G.times98.adj=201;G.times810.adj=G.times108.adj=321;G.ti

25、mes811.adj=G.times118.adj=265;G.times910.adj=G.times109.adj=89;G.times911.adj=G.times119.adj=382;G.times1011.adj=G.times1110.adj=485;void CreateUDN(v,a)/造图函数int v,a;int i,j;G.ve*num=v;G.arum=a;for(i=0;iG.ve*num;+i)G.ve*i.number=i;/下边是城市名G.ve*0.city=;G.ve*1.city=;G.ve*2.city=;G.ve*3.city=;G.ve*4.city

26、=;G.ve*5.city=;G.ve*6.city=亳州;G.ve*7.city=;G.ve*8.city=;G.ve*9.city=;G.ve*10.city=;G.ve*11.city=池州;/这里把所有的边假定为20000，含义是城市间不可到达for(i=0;iG.ve*num;+i)for(j=0;jG.ve*num;+j)G.arcsij.adj=20000;/下边是可直接到达的城市间的距离，由于两个城市间的距离是相互的，所以要对图中对称的边同时赋值G.arcs01.adj=G.arcs10.adj=77;G.arcs02.adj=G.arcs20.adj=399;G.arcs03

27、.adj=G.arcs30.adj=141;G.arcs04.adj=G.arcs40.adj=78;G.arcs05.adj=G.arcs50.adj=523;G.arcs06.adj=G.arcs60.adj=466;G.arcs07.adj=G.arcs70.adj=309;G.arcs08.adj=G.arcs80.adj=182;G.arcs09.adj=G.arcs90.adj=236;G.arcs010.adj=G.arcs100.adj=362;G.arcs011.adj=G.arcs110.adj=135;G.arcs12.adj=G.arcs21.adj=285;G.arc

28、s13.adj=G.arcs31.adj=64;G.arcs14.adj=G.arcs41.adj=155;G.arcs15.adj=G.arcs51.adj=446;G.arcs16.adj=G.arcs61.adj=389;G.arcs17.adj=G.arcs71.adj=195;G.arcs18.adj=G.arcs81.adj=258;G.arcs19.adj=G.arcs91.adj=159;G.arcs110.adj=G.arcs101.adj=285;G.arcs111.adj=G.arcs111.adj=212;G.arcs23.adj=G.arcs32.adj=221;G.

29、arcs24.adj=G.arcs42.adj=440;G.arcs25.adj=G.arcs52.adj=52;G.arcs26.adj=G.arcs62.adj=289;G.arcs27.adj=G.arcs72.adj=90;G.arcs28.adj=G.arcs82.adj=217;G.arcs29.adj=G.arcs92.adj=176;G.arcs210.adj=G.arcs102.adj=185;G.arcs211.adj=G.arcs112.adj=497;G.arcs34.adj=G.arcs43.adj=219;G.arcs35.adj=G.arcs53.adj=382;

30、G.arcs36.adj=G.arcs63.adj=325;G.arcs37.adj=G.arcs73.adj=131;G.arcs38.adj=G.arcs83.adj=213;G.arcs39.adj=G.arcs93.adj=95;G.arcs310.adj=G.arcs103.adj=221;G.arcs311.adj=G.arcs113.adj=276;G.arcs45.adj=G.arcs54.adj=492;G.arcs46.adj=G.arcs64.adj=544;G.arcs47.adj=G.arcs74.adj=350;G.arcs48.adj=G.arcs84.adj=2

31、34;G.arcs49.adj=G.arcs94.adj=314;G.arcs410.adj=G.arcs104.adj=440;G.arcs411.adj=G.arcs114.adj=57;G.arcs56.adj=G.arcs65.adj=265;G.arcs57.adj=G.arcs75.adj=142;G.arcs58.adj=G.arcs85.adj=269;G.arcs59.adj=G.arcs95.adj=287;G.arcs510.adj=G.arcs105.adj=161;G.arcs511.adj=G.arcs115.adj=549;G.arcs67.adj=G.arcs7

32、6.adj=316;G.arcs68.adj=G.arcs86.adj=443;G.arcs69.adj=G.arcs96.adj=230;G.arcs610.adj=G.arcs106.adj=104;G.arcs611.adj=G.arcs116.adj=601;G.arcs78.adj=G.arcs87.adj=127;G.arcs79.adj=G.arcs97.adj=86;G.arcs710.adj=G.arcs107.adj=212;G.arcs711.adj=G.arcs117.adj=407;G.arcs89.adj=G.arcs98.adj=737;G.arcs810.adj

33、=G.arcs108.adj=399;G.arcs811.adj=G.arcs118.adj=281;G.arcs910.adj=G.arcs109.adj=126;G.arcs911.adj=G.arcs119.adj=299;G.arcs1011.adj=G.arcs1110.adj=497;void narrate()/说明函数int i,k=0;/printf(n*欢送使用最优路径程序！*n);printf(n城市列表如下:nn);for(i=0;i12;i+)printf(%2d)%-10s,i,G.ve*i.city);/输出城市列表k=k+1;if(k%4=0)printf(n)

34、;void ShortestPrice(Num)/最少费用函数int Num;int v,w,i,t;int final12;int min;for(v=0;v12;+v)finalv=0;Dv=G.pricesNumv.adj;for(w=0;w12;+w)Pvw=0;if(Dv20000)PvNum=1;Pvv=1;DNum=0;finalNum=1;for(i=0;i12;+i)min=20000;for(w=0;w12;+w)if(!finalw)if(Dwmin)v=w;min=Dw;finalv=1;for(w=0;w12;+w)if(!finalw&(min+G.pricesvw

35、.adj)Dw)Dw=min+G.pricesvw.adj;for(t=0;t12;t+)Pwt=Pvt;Pww=1;void output1(city1,city2)/输出函数int city1;int city2;int a,b,c,d,q=0;a=city2;if(a!=city1)printf(n 从%s到%s的最少费用路径是,G.ve*city1.city,G.ve*city2.city);printf(最少费用为 %dRMB.)nt,Da);printf(%s,G.ve*city1.city);d=city1;for(c=0;c12;+c)gate:;/*标号，可以作为goto语句

36、跳转的位置*/Pacity1=0;for(b=0;b12;b+)if(G.pricesdb.adj%s,G.ve*b.city);q=q+1;Pab=0;d=b;if(q%8=0)printf(n);goto gate;void ShortestTime(Number)/最短时间函数int Number;int v,w,i,t;int final12;int min;for(v=0;v12;+v)finalv=0;Dv=G.timesNumberv.adj;for(w=0;w12;+w)Pvw=0;if(Dv20000)PvNumber=1;Pvv=1;DNumber=0;finalNumbe

37、r=1;for(i=0;i12;+i)min=20000;for(w=0;w12;+w)if(!finalw)if(Dwmin)v=w;min=Dw;finalv=1;for(w=0;w12;+w)if(!finalw&(min+G.timesvw.adj)Dw)Dw=min+G.timesvw.adj;for(t=0;t12;t+)Pwt=Pvt;Pww=1;void output2(city1,city2)/输出函数int city1;int city2;int a,b,c,d,q=0;a=city2;if(a!=city1)printf(n 从%s到%s的最少时间路径是,G.ve*cit

38、y1.city,G.ve*city2.city);if(Da/60=0)printf(最少时间为 %dminutes.)nt,Da);/if(Da/60!=0)elseprintf(最少时间为 %dh %dmin.)nt,Da/60,Da%60);printf(%s,G.ve*city1.city);d=city1;for(c=0;c12;+c)gate:;/*标号，可以作为goto语句跳转的位置*/Pacity1=0;for(b=0;b12;b+)if(G.timesdb.adj%s,G.ve*b.city);q=q+1;Pab=0;d=b;if(q%8=0)printf(n);goto g

39、ate;void ShortestPath(num)/最短路径函数int num;int v,w,i,t;int final12;int min;for(v=0;v12;+v)finalv=0;Dv=G.arcsnumv.adj;for(w=0;w12;+w)Pvw=0;if(Dv20000)Pvnum=1;Pvv=1;Dnum=0;finalnum=1;for(i=0;i12;+i)min=20000;for(w=0;w12;+w)if(!finalw)if(Dwmin)v=w;min=Dw;finalv=1;for(w=0;w12;+w)if(!finalw&(min+G.arcsvw.a

40、dj)Dw)Dw=min+G.arcsvw.adj;for(t=0;t12;t+)Pwt=Pvt;Pww=1;void output(city1,city2)/输出函数int city1;int city2;int a,b,c,d,q=0;a=city2;if(a!=city1)printf(n 从%s到%s的最短路径是,G.ve*city1.city,G.ve*city2.city);printf(最短路径为 %dkm.)nt,Da);printf(%s,G.ve*city1.city);d=city1;for(c=0;c12;+c)gate:;/*标号，可以作为goto语句跳转的位置*/P

41、acity1=0;for(b=0;b12;b+)if(G.arcsdb.adj%s,G.ve*b.city);q=q+1;Pab=0;d=b;if(q%8=0)printf(n);goto gate;int main()/*主函数*/int v0,v1;int a;int type ; int run = 1;CreateUDN(12,66);CreateUDN1(12,66);CreateUDN2(12,66);printf( 最优路径解决方法:n);printf(*n 1.查看城市n 2.按最短路径查询n 3.按最短时间查询n 4.按最少费用查询n 5.退出系统n *n );doprint

42、f(请输入您需要效劳的工程：); scanf(%d, &type); switch(type) case 1:narrate();break; case 2:printf(nn请选择起点城市(011):);scanf(%d,&v0);printf(n);printf(nn请选择终点城市(011):);scanf(%d,&v1);printf(n);ShortestPath(v0); /*计算两个城市之间的最短路径*/output(v0,v1); /*输出结果*/printf(n); break; case 3:printf(nn请选择起点城市(011):);scanf(%d,&v0);prin

43、tf(n);printf(nn请选择终点城市(011):);scanf(%d,&v1);printf(n);ShortestTime(v0); /*计算两个城市之间的最短时间*/output2(v0,v1); /*输出结果*/printf(n); break; case 4:printf(nn请选择起点城市(011):);scanf(%d,&v0);printf(n);printf(nn请选择终点城市(011):);scanf(%d,&v1);printf(n);ShortestPrice(v0); /*计算两个城市之间的最少费用*/output1(v0,v1); /*输出结果*/printf