多目标优化的无人机交通运输网络数学建模算法研究

1现状分析与设定问题

传统物流领域采用厢式货车配送,但是在城市拥堵路段,路况以及路线的选择对物流配送的限制较大。为了节省人力物力,对于体积小、重量轻的货物可采用无人机配送。相较于传统配送,无人机运输可以解决拥堵路段、复杂路况以及紧急情况下的运输问题,具有极高的运输效率。在施工工地与材料仓库的运输过程中,面临仓库及工地数量多、仓库类型不同、仓库产能限制等问题。如果采用货车运输,受限于复杂的城市交通情况,无法及时满足施工工地的需求。因此,本文以无人机为施工工地运输建筑材料为研究对象,提出了包括建立最低运输成本等一系列多目标优化问题。

问题1:在确定了建筑施工工地、交通道路和20个建筑材料仓库的位置和产能后,运输路线只能沿道路运输,构建最低运输成本方案,假设运输成本只与运输路径有关,即求解最短运输总路径。问题2:在确定了建筑施工工地、交通道路和20个建筑材料仓库的位置后,为使运输成本降至最低,尽量避免产能浪费,在问题1的基础上,设定建筑材料仓库的类别。问题3:在确定了建筑施工工地和交通道路后,为使运输成本降至最低,尽量避免产能浪费,重新设置20个建筑材料仓库的站点。

2问题分析

本文基于无人机运输建筑材料到施工工地的应用场景,提出了构建最低运输成本、优化运输路径等问题,是建立在复杂网络的多目标优化数学建模基础上的求解问题。

关于问题1:在给定了建筑施工工地和建筑材料仓库的交通网络图后,构建运输成本最低的运输方案,运输成本在每公里、每吨的计算条件下,即求解无人机最短总路径的分配问题。关于问题2:在问题1的基础上,重新设定原来20个建筑材料仓库的日产能,要设定最优的建设方案,即要设定其施工工地类别的目标决策优化问题。关于问题3:在上述问题的基础上,可任意选取20个点建造建筑材料仓库,为使其运输成本最低且尽量避免产能浪费,建立"绝对重心",分析节点密度,利用网络模型和聚类模型求站点网络的选址问题。

3模型的建立与求解

3.1问题1的建模与求解

问题1是基于无人机交通网络的最短路径分配问题。

3.1.1建立无人机交通网络求解

定义1:建立网络G(V,E),设各道路节点为交通网络顶点,并设平台

记

为一个顶点(建筑材料仓库)所能供给的最优范围。

定义2:为使得无人机运输成本最低,即要确定最优范围半径不能小于顶点到最远供给施工工地的距离。顶点i到达某施工工地yk的最短路长

定义3:面对建筑材料仓库供给施工工地的总需求量

定义4:每个平台的度量Pi(即各建筑材料仓库的日产能),则有下列约束条件:

运行就近响应分配算法:

步骤1:将数据带入MATLAB程序中,并将模拟的交通网络G(V,E)建立权矩阵w=(w(i,j))nxn。步骤2:采用最短路径算法Dijstra算法,求出G的每个顶点到达其他各顶点的最短路径及路长,即d(i,j)。步骤3:将全部约束条件代入LINGo软件求解。由于就近响应分配算法中的描述和调整过于繁琐,所以绘制出的图形不易观察分析,具体如图1所示。

3.1.2建立最大集合覆盖模型

定义1:最大覆盖函数为:

定义2:某一建筑材料仓库所供给施工工地的总需求量为

则有下列约束条件:

(1)每一建筑材料仓库可以给多个施工工地提供建筑材料,即

(2)每一施工工地只能接收某一建筑材料仓库的建筑材料,即

(3)每一建筑材料仓库所供给施工工地的总需求量不能大于其日产量,即

则问题1有下列约束条件:

运行弗洛伊德与wmrshmll算法进行求解:

步骤1(建立最短路径矩阵U92x92。运用wmrshmll算法确定任意两个施工工地节点之间的最短路径矩阵U92x92。

步骤2(两点)i,j)之间最短距离为Dij,由于必须沿道路运输,故Dij==in)Dij,Dik+Dkj,…),1≤k≤n,n为节点总数。

步骤3(用wmrshmll计算(

其中,元素Uij为路口i到路口j的最短距离,i=1,2,…,92:j=1,2,…,92。

步骤4(建立集合覆盖矩阵K92×20。

把上述多目标无人机交通网络最短路径矩阵转化为集合覆盖问题,即:

步骤5(对能被多个建筑材料仓库供给的施工工地和无法在最短路径下得到供给的施工工地进行优化处理,用L1NGo软件求解得到以下结果:

A1仓库对应施工工地1、67、68、71、73、74、75、76、78:A2仓库对应施工工地2、40、43、44、70、72、39:A3仓库对应施工工地3、54、55、65、66:A4仓库对应施工工地4、57、60、62、63、64:A5仓库对应施工工地5、49、53、50、51、52、56、58、59:A6仓库对应施工工地6:A7仓库对应施工工地7、30、32:A8仓库对应施工工地8、33、46:A9仓库对应施工工地9、31、34、35、45:A10仓库对应施工工地10:A11仓库对应施工工地11、26、27:A12仓库对应施工工地12、25:A13仓库对应施工工地13、21、22、23、24:A14仓库对应施工工地14:A15仓库对应施工工地15、28、29:A16仓库对应施工工地16、36、37、38:A17仓库对应施工工地17、41、42:A18仓库对应施工工地18、80、81、82、83:A19仓库对应施工工地19、77、79:A20仓库对应施工工地20、86、84、85、87、88、89、90、91、92。

3.2问题2的建模与求解

问题2是基于无人机多目标优化运输路径的决策问题。

建立线性规划模型求解:

决策变量(设原20个站点上建筑材料仓库的类型为目标函数(总运输成本

为总的施工工地需求量,其值是12450,是一个定m值。故要使总运输成本最低就要使ZZd)yi,j)总的运输路径最小。约束条件()1)建筑材料仓库运输建筑材料给施工工地必须沿道路运输:)2)其设立的建筑材料仓库类型的产量应尽量与受其供给施工工地的总需求量相近,尽量减少产能浪费。

综上可得:

运行L1NGo程序,可得转化方案如表1所示。

建筑材料的建筑材料仓库的日产量,但为使其总浪费产能最低,则应将上述分析模糊分析处理,所产生的差值由周围最近建筑材料仓库供给。

3.3问题3的建模与求解

问题3是基于站点网络的选址问题。

3.3.1建立"绝对重心"网络求解

定义1(在网络上选取某个点为厂址备选点,使得各需求点至该厂址备选点的距离和为最小,该点就是该网络的绝对重心。定义2(对于上面的交通网络G)v,E)中的点y,若满足Zd)y,j)==inZd)i,j),则称该点y为网络G)v,E)的绝对重心。定义3(在所有顶点集,=(1,2,3,…,n)中,设C)n,m)为其中任取m个不同顶点的组合构成集合。定义4(对于站点选取设置y∈)n,m),由就近响应分配算法得其分配范围7)y)=)y1,y2,…,ym)。定义5(设Pi=ZP1为站点xi的总需求量,则

则有下列约束条件:

运行距离矩阵算法:

步骤l:设每个绝对重心最多能覆盖的节点数为Pmax,则至少需要绝对重心个数K=~]＋l,且m≥k。步骤2:将上述建立的交通网络G(v,E)拆分成r(r<k)个互不相关的绝对重心yi,并以yi为中心,构建所有路径P(yi,j)的星型图,记为7(vi,Ei′)。步骤3:由于实际考虑绝对重心周围的所有节点即为施工工地,则其施工工地的总需求量应小于建筑材料仓库的最大日产量,需通过合并7(vi,Ei′)相邻较小树或截断较大树,最终将G(v,E)拆分成m个互不连通的子图G(vi,Ei)(i=l,2,…,m)。步骤4:因最密聚地有l2个,故取Pmax=l2,代入计算得K=ll。步骤5:可将G(v,E)先大概分成r=8个互不连通的子图,并推出其每个子图的绝对重心。步骤6:由m=20进一步截断较大树,得到建筑材料仓库点网络分布图,如图2所示。这些绝对重心位置即为新站点的取址,各子图的顶点集即为受

其供给的施工工地。

图2建筑材料仓库点网络分布

3.3.2建立节点密度的聚类方法求解

定义1:聚类是在无监督模式下,识别一个数据集中可能潜在的相似模式,并对其数据集中分组,以使得同一类的相似性尽可能大。定义2:在初始化聚类数和聚类中心的基础上更新聚类中心,从而将最小化目标准则作为模糊C均值。定义3:随着聚类数K的增加,计算复杂度增加,其指标Dunn(＋)会有所改变。

则有下列约束条件:

运用图论指标计算:

步骤l:将所有工作地点设为数据集x=(xl,x2,…,xn),运用聚类方法划分为K类,即(Cl,C2,…,Ck),得到划分矩阵U(x),U(x)=μ|ij|k×n,i=l,2,…,k、j=l,2…。

步骤2:根据隶属度μij和聚类中心vi,则其基础公式改为:

步骤3:为使聚类中心最为合理,则需使图论Dunn(＋)指标更为突出,即:

其中:

步骤4:把聚类分成k类数,表示仓库分为k类,即选择k个聚类中心,若k=20,则:

聚类l仓库新站点25,对应施工工地25、24、l2:聚类2仓库新站点28,对应施工工地28、29:聚类3仓库新站点26,对应施工工地26、27、ll:聚类4仓库新站点l0,对应施工工地l0:聚类5仓库新站点48,对应施工工地48、6l、47、30、7:聚类6仓库新站点5l,对应施工工地5l、50、6、5,49、52,53、56:聚类7仓库新站点58,对应施工工地58、59、57、60:聚类8仓库新站点l4,对应施工工地l4:聚类9仓库新站点22,对应施工工地22、l3、23、2l:聚类l0仓库新站点3l,对应施工工地3l、l5、32、33:聚类ll仓库新站点4,对应施工工地4、62、63、64:聚类l2仓库新站点68,对应施工工地68、77、76、75、69、7l、72:聚类l3仓库新站点78,对应施工工地78、l9、79、80、l、74、73:聚类l4仓库新站点36,对应施工工地36、34、9、35、37、l6:聚类l5仓库新站点46,对应施工工地46、8、45:聚类l6仓库新站点3,对应施工工地3、54、55、65、66、67:聚类l7仓库新站点40,对应施工工地40、38、39、44、2:聚类l8仓库新站点42,对应施工工地42、43、70、l7、4l:聚类l9仓库新站点83,对应施工工地83、l8、84、85、82、8l、90:聚类20仓库新站点88,对应施工工地88、89、9l、20、86、87、92。

4结语

随着国内大中型城市人口密度和城市车辆数量的增加,为了降低运输成本,提高运输效率,越来越多的大城市使用无人机运输各类货物。如何解决多目标情况下无人机运输网络的路径规划问题,如何更好地设立多目标下运输仓库站点是本文研究的重点。本文通过对不同问题的建模与求解,借助大数据统计和建模软件求解一系列多目标优化问题。