还剩21页未读，继续阅读
本资源只提供10页预览，全部文档请下载后查看！喜欢就下载吧，查找使用更方便
文本内容:
4.2流程图第五章计算过程
4.1计算各点对间连接的费用节约值s（，,J）—Go+6oj~cij~4o+4”-%例如，连接点1和点2时，有s（l,2）=4（）+d（\7—d\7=40+60—65—35类似的，可得到连接其他各点对时的费用节约值，从大到小的顺序示于表4-3中表4-3点对之间连接的费用节约值5,75,63,55,84,51,56,7i,jsi,j270230225205190190190i,j4,72,52,73,77,84,61,7si,j17516014514514011590i,j2,63,66,81,34,81,62,8si,j85858075706565i,j3,42,3⑵41,21,41,83,8si,j6560503530205由于距离为对称距离，因此有s（i,j）=djo+d-d/Oi故表中所示的,也可以表示为s（/,i）
5.2构造线路根据表4-3所示的s（i,j）的顺序，逐项考察对应的i-j,点对之间的连接过程示于表4-4中表中第一列表示根据表4-3的顺序考察的i-j,若两点均不在线路上，则考察j和j-*i;若一点不在线路上，一点是外点，则考察j（i不在线路上、j是线路的起点，或i是线路的终点、j不在线路上）或者j-i（j不在线路上、i是线路的起点，或j是线路的终点、i不在线路上）；若两点都是线路上的外点,则根据点的位置关系，构造成终点（一条线路）一起点（另一条线路）的顺序；第二列表示考察的两点的位置，若不满足位置关系，显然不能连接，不在考察其他各项，在第6列划义，转其他点对第3列表示连接后线路的总任务量，若大于车辆容量，则在第6列中划X第4列表示点i与点j连接后的七弓第5列为或A,若£为0,则计算A；；若EFj0,则计算与根据（或A；.）,若满足时间约束，则第6列表示线路i-j或j-i,否则划X第7列表示i与j连接后，j后面的各任务的新的开始时间当一个点不在线路上时，认为点i与车场单独构成线路0—i—0由表4-4,得到最终的线路为Of8f5f7foOf6f4foOf3-i2fo显然各任务的开始时间均满足时间窗约束如表4-4中，对5-7,满足所7，有5-7,经检验满足即2即不可能存在7-5,故无时间可行的回路，表中只表示了一种情况表4-4点对之间的连接过程1234567••勺啊两点位连接Q=£gi EFj=2+2+fiJ~Sj Sk=+EFj1-J置否*j5T5-7非线路EF=S+T+A；=LT]—$7=3s:=s+EF=75577147—S7=
2.8上点
7.8=4q6-5非线路0=++gi=8=q EF5=S6+T6+%-=min{LT-%,X5上点，外$5=1,9点LT.-s.}=
0.23-5非线路XQq上点，外点8f5非线路8-5Q=8S+8+EF5=S3+TS+S5=$5+E耳5=min{5-ET,55上点，外g7=7q-7=
3.9‘85-S5=-1点s:=s+EF=775S7—ETj}=
17.74-5一点为X1-5内点7-6外点，XQq7f4非线路上点2-5一点为X内点7-2外点，XQq非线路7-3上点4-6不在线6一4Q=@4+7EF4=S6+T6+,64A4=LT4-£=3%=%+EF4二二路q-$4=267-1外点，XQq非线路2-6上点3f66T两个起X点IT不在线3-1Q=g]+g3=
6.5EF[=S+T+^=LT-s=3S]:=S[+33x1路q EF[=
3.3-4=
2.34f8外点XQq1-62-84-32-3非线路居X0=g2+g3+gi E=S+T+=min{LT3-%,22上点，外=8=9，23-$3=6点LT,-s,}=
0.54f2外点，XQq非线路上点1-2EF=$]++Z|2-3-1s:=s+EF=外点，Q=g3+gl+N—LT—$2=2222g=8=q=
1.6一
25.6非线路上点第六章算法的总结与分析
5.1处理其他的约束算法还可以处理其他约束，如线路的长度约束，则考虑连接点对时，需检查是否违反线路的长度限制总之，约束越多，考虑的因素越多，问题就越复杂，求解起来就越困难
6.2算法的进一步讨论若允许车辆在任务处等待，也允许任务延迟进行，但要计等待损失费用和延迟罚款，即时间窗约束为软时间窗约束，这时可对原费用节约值
5.力进行修正,得至U S（i，j）=j）一Z2-3Z Ek kjkj式中，Q,C3分别为等待时间和延迟时间的相对费用系数，2为连接点，和点J所在线路时，车辆在，•后面任务女处的等待时间，当为任务上开始执行的延迟时间2和项分别由下式得到D=max{ET一（与+EF）,O）k kyEk=max{（s+EF”LT,0）kk显然瓦°时，计算2;“与°时，计算演计算完所有力后，根据s«,/）连接点对需要注意的是，每当连接一项后，各量可能会发生变化，因此需要重新计算，在考虑连接
6.3算法的推广若每项任务都有各自的集货点或送货点与卸货点，即集货与送货一体化车辆优化调度问题，这时，用（表示从任务，的集货点至送货点的时间，％表示从任务i的卸货点到任务，•的装货点间的时间，则算法也可适用于该种情况
6.4结论有时间窗约束的厢由于它的强样特性，使求解起来很困难，本节提出了求解该问题的C-W启发式算法，以的C-W算法为基础，构造了连接点对时对线路上点的最大允许提前时间或最大允许延迟时间的检查约束，以及等待惩罚和延迟惩罚的处理方法,设计了算法的实施程序，并应用实例进行了分析说明该方法应用性好，可在连接点对时，同时考虑其他的约束1234567••两点位连接EFj=s+T+~Sj A或ASk EFj1-Ji i二以+置否*j5T5-7非线路EF=S+T+A；=LTj—5=3Sj:=SQ+EFj7557=4qO=g5+g7上点g—S]=
2.8=
7.86一5非线路0=+十gi=8=E月=1+4+=min{LT-s.X55上点，外q=L9点LT-s}=
0.2113-5非线路XQq上点，外点8-5非线路8一5居Q=gs+g+E=%+4+‘85-§5=S5+EF55上点，外S=7q$5=—0,1一7=
3.9A=min{%-ET,5点S7S7+E%==
7.7s-ET}=l114-5一点为X1T内点7一6外点，XQq7-4非线路上点2-5一点为X内点7-2外点，XQq非线路7-3上点4-6不在线6一4=心+=£=1++=3S4:=S4+EF47q路，64-§4=2=67-1外点，XQq非线路2-6上点3-66-8两个起X点1T不在线3-l££=*+1+s:=J+EF93==Z7]—S]=3[]=+路=
3.
36.5q%-N=
2.34f8外点XQq1-62-84-32-3非线路XQ=+g3+gi=8EF=S+T+min{LT322△；=3一*,上点，外=q，23-§3=6点LT S]}=
0.5[一4一2外点，XQq非线路上点1-2外点，EF=S]++Zp—3一1Q=g3+gl+2A；=LT—$2=2s=$2+EF22非线路s=
1.6一24=8=4—
5.6上占附录一代码设计#includestdio.h#includemath.h#includestdlib.hint mainfloat minfloat,float;intij,s
[9]
[9]={0},n=8,L
[9]={0},Q=8,Ln=0,M
[4]={0},jb=0,ib=0,a=0,b=0,N
[5]={0},x=0,y=0;float t
[9]
[9]={0},DERTAa1,DERTAa2,DERTAb l,DERTAb2,k
[9],EF
[100],qq=0,q
[8]={0};float g
[9]={0,2,L5,
4.5,3/54,
2.5,3};float T
[9]={0,1,2,1,3,2,
2.5,3,
0.8;float ET
[9]={0,1,4,1,4,3,2,5,
1.5};；float LT
[9]={0,4,62,7,
5.5,5,8,4}int d
[9]
[9]={0,40,60,75,90,200,100,160,80,40,0,65,40,100,50,75,110,100,60,65,0,75,100,100,75,75,75,75,40,75,0,100,50,90,90,150,90,100,100,100,0,100,75,75,100,200,50,100,50,100,0,70,90,75,100,75,75,90,75,70,0,70,100,160,110,75,90,75,90,70,0,100,80,100,75,150,100,75,100,100,0;printf各任务的货运量g[i]如下\nn;for i=l;i=n;i++{printf”g%d=%-
5.lF,i,g[i];printfn\n\n\nn;printf各任务的装货或卸货时间T[i]为\nn;for i=l;i=n;i4-+{printfnT%d=%-
5.1f,i,T[i];}printfn\n\n\nH;各任务的开始执行的时间范围为printf[ETi,LTi]\n fori=l;i=n;i++{printfn[ET%d,LT%d]=[%-
3.1f,%-
3.1f]\nn,i,i,ET[i],LT[i];printfn\n\n\nn;车场与各任务点间的距离为:printf0\n fori=0;i=8;i++{forj=0;j=8;j++{printfC%5dn,d[i][j];}printfu\nn;}printfn\n\nn;”点对之间连接的费用节约值为printf\nfori=l;i=8;i++{forj=i+l;j=8;j++{s[i]U]=d[i][O]+d[O]U]-d[i][j];第一章课程设计的目的及意义《运输组织学》是交通运输类专业的一门必修专业课，通过理论教学环节，是同学们了解公路运输的基本理论和基本方法，并可以初步掌握公路运输企业生产组织管理的基本理论、基本方法，使同学们具备进行公路运输企业组织管理的基本知识课程设计是理论教学环节的延伸是对学生们的一次实战演练，通过课程设计，以检验和提高学生运用所学理论知识解决实际问题的能力，使学生较全面和系统的实践交通运输组织的基本理论，方法和技能，初步具备运用现代化科学方法进行公路运输生产组织管理的能力，完成培养公路运输业高级管理人才所需的运输组织管理方面的专业知识和技能的基本训练当前，现代物流已被公认为是企业在降低物质消耗、提高劳动生产率以外创造利润的第三个重要源泉，也是企业降低生产经营成本，提高产品市场竞争力的重要途径［1］配送是物流系统中的一个重要环节，它是指按客户的订货要求，在物流中心进行分货、配货工作，并将配好的货物及时送交收货人的物流活动在配送业务中，配送车辆调度问题的涉及面较广，需要考虑的因素较多，对配送企业提高服务质量、降低物流成本、增加经济效益的影响也较大该问题包括集货线路优化、货物配装及送货线路优化等，是配送系统优化的关键国外将配送车辆调度问题归结为VRP（Vehicle RoutingProblem,即车辆路径问题）、VSP（Vehicle SchedulingProblem,即车辆调度问题）和MTSP（Multiple TravelingSalesman Problem,即多路旅行商问题）该问题于1959年由Dantzig和Ramser提出后［2］,很快便引起运筹学、应用数学、组合数学、图论与网络分析、物流科学、计算机应用等学科的专家以及运输计划制定者的极大重视，并一直是运筹学与组合优化领域的前沿与热点问题在现实生产和生活中，邮政投递问题、车船调度问题、电力调度问题、管道铺设问题、计算机网络拓扑设计问题等都可以抽象为配送车辆调度问题可见，研究配送车辆调度问题具有重要的理论和现实意义第二章课程设计的题目及要求
2.1配送车辆调度问题的描述配送车辆调度问题可以描述为在一个存在供求关系的系统中，有若干台车辆、若干个物流中心和客户，要求合理安排车辆的行车路线和出行时间，从而在给定的约束条件下，把客户需求的货物从物流中心送到客户，把客户供应的货物从客户取到物流中心，并使目标函数取得优化配送车辆调度问题可归结为如下的一般网络模型［3］设G=（V,E,A）是一fori=l;i=8;i++；{forj=i+1j=8;j++{printf!s[%d][%d]=%-5dMj,s[i]|j];}printf,,\nu;printfn\nn;fori=0;i=8;i++；{forj=0j=8;j++{t[i]U]=floatd[i][j]/50;}fori=0;i=8;i++〉={ift[O][i]ET[i]UO][ik=LT[i]{k[i]=t[O][i];}ift[O][i]ET[i]{k[i]=ET[i];}}while1{ib=O;jb=O;fori=l;iv=8;i++；{forj=i+l j=8;j++{if s[i][j]s[a][b]{a=i;b=j;}}if s[a][b]==O break;N[l]=0;N
[2]=M[l];N
[3]=M[l]+M
[2];N|4M[l]+M
[2]+M
[3];fori=0;i8;i++{if L[i]==a{ib=l;x=i;}}forj=0;j8;j++{ifL[j]==b{jb=l;y=j;}}if ib==Ojb==O{qq=g[a]+g[b];if qqQ{s[a][b]=0;continue;}EF[b]=k[a]+T[a]+t[a][b].k[b];EF[a]=k[b]+T[b]+t[a][b]-k[a];DERTAbl=LT[b]-k[b];DERTAb2=k[b]-ET[b];DERTAal=LT[a]-k[a];DERTAa2=k[a]-ET[a];ifEF[b]=0DERTAbl=EF[b]||EF[b]0DERTAb2=0-EF[b]{L[N
[4]]=a;L[N
[4]+l]=b;Ln=Ln+l;q[Ln]=qq;k[b]=k[b]+EF[b];s[a][b]=O;M[Ln]=M[Ln]+2;continue;}else if EF[a]=0DERTAal=EF[a]||EF[a]0DERTAa2=0-EF[a]{L[N
[4]]=b;L[N
[4]+l]=a;Ln=Ln+l;q[Ln]=qq;k[a]=k[a]+EF[a];s[a][b]=0;M[Ln]=M[Ln]+2;continue;}if ib==Ojb==1{i=a;a=b;b=i;x=y;ib=1;jb=O;}if ib=ljb=O{if X=N
[1]||X==N
[2]||X==N
[3]{i=a;a=b;b=i;}fori=l;i=3;i++{ifx=N[i]{qq=q[i]+g[a];if qqQ{s[a][b]=0;s[b][a]=0;continue;}EF[b]=k[a]+T[a]+t[a][b]-k[b];ifEF[b]0{DERTAb1=minLT[L[x]]-k[L[x]],LT[L[x+l]]-k[L[x+1]];if EF[b]DERTAbl{s[a][b]=0;s[b][a]=0;continue;}}ifEF[b]0；{DERTAb2=mink[L[x]]-ET[L[x]],k[L[x+l]]-ET[L[x+1]]if0-EF[b]DERTAb2{s[a][b]=0;s[b][a]=0;continue;}}forj=6;j=x;j-{L[j+1]=LU];}L[x]=a;k[L[x+l]]=k[L[x+l]]+EF[L[x+l]];；k[L[x+2]]=k[L[x4-2]]+EF[L[x+l]];q[i]=qq；M[i]=M[i]+lfori=l;i=3;i++{if==N[i+l]-l{qq=q[i]+g[b];xif qqQ{s[a][b]=O;s[b][a]=0;continue;}EF[b]=k[a]+T[a]+t[a][b]-k[b];ifEF[b]=0{DERTAb l=LT[b]-k[b];if EF[b]DERTAbl{s[a][b]=O;s[b][a]=0;continue;}}ifEF|b|0{DERTAb2=k[b]-ET[b];if0-EF[b]DERTAb2{s[a][b]=0;s[b][a]=0;continue;}forj=6;j=x;j—{L[j+2]=L[j+l];L[x+l]=b;}k[L[x+l]]=k[L[x+l]]+EF[L[x+l]];M[i]=M[i]+l;q[i]=qq;s[a][b]=O;s[b][a]=O;printf得到的最终的路线为\nn;fori=l;i=3;i++{printfnO-n;forj=N[i];jN[i+1];j+4-{printfn%d-\L[j];}printfnOn;printfn\n\nn;，printfC\n\nH;printf各路线的总任务量Q[i]为:\nn;fori=l;i=3;i++{printf“Q[%d]=%
3.lf\n”,i,q[i];}printfn\n\nn;各路线的新的开始时间为:printf s[i]\n;fori=l;i=8;i++{printf,,s[%d]=%
3.1f\n;i,k[i];}；printf\n\nsystem pause;returnO;floatminfloatx,float y{float z;z=xvx:y;returnz;个连通的混合网络，V是顶点集（表示物流中心、客户、停车场等），E、A分别为无向的边集和有向的弧集，E中的边和A中的弧均被赋权（可以表示配送的距离、时间或费用），V\E\A分别为V、E、A的子集，求满足约束条件（包括客户的货物需求或供应数量约束、需求或供应时间约束、配送车辆一次配送的最大行驶距离约束、车辆的最大载重量约束等），并包含V\E\A，的一些巡回路线，使目标函数取得优化，目标函数可以取配送总里程最短、2配送车辆总吨位公里数最少、配送总费用最低、配送总时间最少、使用的配送车辆数最少、配送车辆的满载率最高等3配送车辆调度问题的构成要素分析配送车辆调度问题主要包括货物、车辆、物流中心、客户、运输网络、约束条件和目标函数等要素
（1）货物货物是配送的对象可将每个客户需求（或供应）的货物看成一批货物每批货物都包括品名、包装、重量、体积、要求送到（或取走）的时间和地点、能否分批配送等属性货物的品名和包装，是选用配送车辆的类型以及决定该批货物能否与其它货物装在同一车辆内的依据例如，一些货物因性质特殊需要使用专用车辆装运；一些货物因性质特殊不能与其它货物装在同一车辆内；一些货物虽然性质特殊，但由于包装条件很好，故也能与其它货物装在同一车辆内货物的重量和体积是进行车辆装载决策的依据当某个客户需求（或供应）货物的重量或体积超过配送车辆的最大装载重量或容积时，则该客户将需要多台车辆进行配送货物的送到（或取走）时间和地点是制定车辆的出行时间和配送路线的依据允许货物分批配送，是指某个客户的需求（或供应）的货物可以用多辆车分批送到（或取走），即使其需求（或供应）量在一辆车的装载量以下
（2）车辆车辆是货物的运载工具其主要属性包括车辆的类型、装载量、一次配送的最大行驶距离、配送前的停放位置及完成任务后的停放位置等车辆的类型有通用车辆和专用车辆之分，通用车辆适于装运大多数普通货物，专用车辆适于装运一些性质特殊的货物车辆的装载量是指车辆的最大装载重量和最大装载容积，是进行车辆装载决策的依据在某配送系统中，车辆的装载量可以相同，也可以不同对每台车辆一次配送的行驶距离的要求可分为以下几种情况
①无距离限制；
②有距离限制；
③有距离限制，但可以不遵守，只是不遵守时需另付加班费车辆在配送前的停放位置可以在某个停车场、物流中心或客户所在地车辆完成配送任务后，对其停放位置的要求可分为以下几种情况:
①必须返回出发点;
②必须返回某停车场；
③可返回到任意停车场；
④可停放在任何停车场、物流中心或客户所在地
（3）物流中心也称为物流基地、物流据点，是指进行集货、分货、配货、配装、送货作业的配送中心、仓库、车站、港口等在某配送系统中，物流中心的数量可以只有一个，也可以有一个以上；物流中心的位置可以是确定的，也可以是不确定的对于某个物流中心，其供应的货物可能有一种，也可能有多种；其供应的货物数量可能能够满足全部客户的需求，也可能仅能满足部分客户的需求
（4）客户也称为用户，包括分仓库、零售商店等客户的属性包括需求（或供应）货物的数量、需求（或供应）货物的时间、需求（或供应）货物的次数及需求（或供应）货物的满足程度等在某个配送系统中，某个客户的需求（或供应）货物的数量可能大于车辆的最大装载量，也可能小于车辆的最大装载量；而该系统全部客户的货物需求（或供应）总量可能超过全部车辆的总装载量，也可能低于全部车辆的总装载量某客户的需求（或供应）货物的时间，是指要求货物送到（或取走）的时间,对配送时间的要求可分为以下几种情况
①无时间限制；
②要求在指定的时间区间（也称为时间窗）内完成运输任务；
③有时间限制，但可以不遵守，只是不遵守时要给予一定的惩罚3某客户的需求（或供应）货物的次数可能仅有一次，即只需一次配送服务；也可能为多次，即需要多次配送服务某客户对需求（或供应）货物的满足程度的要求可分为两种情况
①要求全部满足；
②可以部分满足，但不满足时要受到惩罚
（5）运输网络运输网络是由顶点（指物流中心、客户、停车场）、无向边和有向弧组成的边、弧的属性包括方向、权值和交通流量限制等某运输网络中可能仅有无向边；也可能仅有有向弧；还可能既有无向边,又有有向弧运输网络中边或弧的权值可以表示距离、时间或费用边或弧的权值变化分为以下几种情况
①固定，即不随时间和车辆的不同而变化；
②随时间不同而变化；
③随车辆的不同而变化；
④既随时间不同而变化，又随车辆不同而变化对运输网络权值间的关系可以要求其满足三角不等式，即两边之和大于第三边；也可以不加限制对运输网络中顶点、边或弧的交通流量要求分为以下几种情况:
①无流量限制;
②边、弧限制，即每条边、弧上同时行驶的车辆数有限；
③顶点限制，即每个顶点上同时装、卸货的车辆数有限；
④边、弧、顶点都有限制
（6）约束条件配送车辆调度问题应满足的约束条件主要包括
①满足所有客户对货物品种、规格、数量的要求；
②满足客户对货物发到时间范围的要求；
③在允许通行的时间进行配送（如有时规定白天不能通行货车等）；
④车辆在配送过程中的实际载货量不得超过车辆的最大允许装载量；
⑤在物流中心现有运力范围内
（7）目标函数对配送车辆调度问题，可以只选用一个目标，也可以选用多个目标经常选用的目标函数主要有
①配送总里程最短配送里程与配送车辆的耗油量、磨损程度以及司机疲劳程度等直接相关，它直接决定运输的成本，对配送业务的经济效益有很大影响由于配送里程计算简便，它是确定配送路线时用得最多的指标
②配送车辆的吨位公里数最少该目标将配送距离与车辆的载重量结合起来考虑，即以所有配送车辆的吨位数（最大载重吨）与其行驶距离的乘积的总和最少为目标
③综合费用最低降低综合费用是实现配送业务经济效益的基本要求在配送中，与取送货有关的费用包括车辆维护和行驶费用、车队管理费用、货物装卸费用、有关人员工资费用等
④准时性最高由于客户对交货时间有较严格的要求，为提高配送服务质量，有时需要将准时性最高作为确定配送路线的目标
⑤运力利用最合理该目标要求使用的较少的车辆完成配送任务，并使车辆的满载率最高，以充分利用车辆的装载能力
2.2任务的特征及要求任务i12345678gi（吨）
21.
54.
531.
542.53Ti小时
121322.
530.8[ETi,LTi[3,
5.[
1.5,[1,4][4,6][1,2][4,7][2,5][5,8]5]4]点之间的距离00123456781040607590200100160802400654010050751101003606507510010075757547540750100509090150590100100100010075751006200501005010007090757100757590757007010081601107590759070010098010075150100751001000第三章题目分析本小组课程设计研究物流配送车辆优化调度问题，即VSP（Vehicle RoutingProblem和Vehicle SchedulingProblem）该问题一般定义为:对一系列装货点和（或）卸货点，组织适当的行车路线，使车辆有序的通过它们，在满足一定的约束条件（如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等）下，达到一定的目标（如路程最短、费用最少等）本小组选题为时间窗约束下的物流车辆优化调度方案，即在一般VSP模型的约束条件中考虑时间要求后安排路线（称车辆调度问题，Vehicle SchedulingProblem）利用C—W节约启发式算法，能有效地解决有时间窗约束的集货或送货的非满载VSP问题，实现有约束情况下的最优解，在满足任务要求的前提下有力的节省了成本通过对有时间窗约束的集货或送货的非满载VSP问题的求解，尽力熟悉和熟练运用C—W节约启发式算法，锻炼了学生实际动手和理解运用能力，有利于学生解决生产生活的实际问题
3.1一般VSP模型为构造数学模型，将车场编号为0,任务编号为1,…」，任务及车场均以点1«=0,1,...,/）来表示定义变量如下1点i的任务由车辆k完成;Y yki0否则’1车辆k从点i行驶至！J j点;V Yxki-0否则则可得到车辆优化调度数学模型如下:min z=W》W GjXijki jkSiyu vqyki=1xuk=ykjxijk-yki=x,jke SXjjk=或1%=01模型中，金表示从i点到j点的运输成本，它的含义可以是距离、费用、变量、时间等，一般根据实际情况确定，可同时考虑车辆数和运行费用，如下确定1）当i为车场时，包括固定费用和运行费用句=+曲1j=L…J2）当i为任务时，只有运行费用，即%•=ClZ01j=1，其中，为相对于运行时间的费用系数；%为车辆的固定费用，即增加一车辆的边际费用一般认为，派出一辆车的固定费用远远高于车辆的行驶费用,因此该模型在极小化车辆数的前提下，再极小化运行费用减小C的值将会是使用的车辆数增多，而线路长度缩短若令则模型目标是使用的车辆数最少
3.2时间窗VSP模型设完成任务i需要时间（装货或卸货）表示为力，又设任务i的开始时间需在一定时SSAWX间范围,看/看】内，其中ETi为任务i所允许的最早开始时间，叫为任务i所允许的最迟开始的时间如果车辆到达i的时间早于，则车辆需在i处等待，如果车辆到达的时间晚于心（，任务i要延迟进度求满足货物需求的费用最少的车辆行驶路线此问题称之为有时间窗的车辆优化调度问题以立表示车辆到达点i的时间，力表示车辆由i行驶到点j的时间，一般应有以下关系式s0=
01.硬时间窗VSP硬时间窗VSP指每项任务必须在要求的时间范围内完成，即必须满足上式若超出这个时间范围，则得到的解为不可行解
2.软时间窗VSP软时间窗VSP指如果某项任务不能在要求的时间范围内完成，则给与一定的惩罚若车辆在£7；.之前到达点j,则车辆在此等待，发生了机会成本损失若车辆在之后达到点j,则服务被延误，须支付一定罚金
3.3关于时间窗的宽度对时间窗VSP的时间特性进行分析，给出以下定义定义1对任务i,要求其在时间范围历0口】内执行，则叱二一£方称为任务i的时间窗宽度定义2对项货物运输任务，每项任务均要求在各自的时间窗内执行，则平均时间窗宽度与平均时间的比值生/1Z/j）/m/i=l j=l称为该问题的时间窗系数当TW在不同的范围内，问题有不同的特征1TW=O,即每项任务有确定的开始时间2TW2,这段时间的时间窗约束放松，可能存在时间可行的回路，时间约束一般能够满足，问题的空间性支出与支配地位，一般来说，根据问题情况安排路线即可30TW2,这是时间窗约束较紧，时间可行的回路较少或没有，问题的时间性质与空间性质相比更可能属于支配地位，在进行车辆调度时，必须考虑时间约束第四章计算原理及流程图
4.1算法原理这里对旅行商问题的算法进行修正，用来求解有时间要求的硬时窗车辆优化调度问题符号说明同前，以C,表示车辆从点i行驶到点j的费用，由CT算法，得到点i和点J连接在一条线路上费用节约值Si.j=Cjo+Co「C当不考虑时间约束时其算法与c-w算法类似.只是在连接点对时.需考虑车辆的量约束，即一条线路上各任务的货运量之和应不大于车辆的容量若各项任务要求在一定的时间范围内完成，按费用节约值，S i,j连接点i与j时.可能会使j后面的任务的执行不满足时间要求当连接点i和点j所在线路时.若车辆到达j点的时间比原线路上j点任务的开始时问提前则车辆在j后面的任务处有可能需要等待;若连接后到达j点的时间比原线路上j点任务的开始时间推迟，则j后面的任务在执行时可能会发生延迟以EF,表示连接点i和点j所在的线路后，车辆到达j点的时间比原线路上车辆到。
个人认证
优秀文档
获得点赞 0
