送货路线-数学建模-一等奖

1摘要摘要本文讨论了送货员送货路线的优化设计问题,即在给定送货地点和给定设计规范的条件下，综合考虑最大载重范围、最大带货体积以及各货物送货时限，确定业务员的最佳运行路线策略.并总结出一些在这类图中求解近似最优回路的有效法则.对于问题1，采用了两种方法进行了计算，第一种是通过Floyd算法做出各顶点间的最短路径矩阵，然后选出1~30号货物所送达的顶点间的最短路径及距离，用二边逐次修正法求解Hamilton圈；第二种是通过蚁群算法获得多条近似优解，选取最佳线路.对于第二问，则采用改进的遗传算法，求解有时间约束条件的TSP问题，根据线路规划问题的特点，基于遗传算法（GA）建立了一个适用于带有时间约束的送货路线规划模型.实验证明了此算法的有效性和可行性.对于第三问，利用分割求解法和蚁群算法的合成算法，运用共同链分割全图，对每一个分图进行最优求解，由此得到全图的最优解。关键词送货问题；优化路线；TSP模型；蚁群算法2送货路线设计的数学模型1问题重述现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛，每个送货员需要以最快的速度及时将货物送达，而且他们往往一人送多个地方，请设计方案使其耗时最少.现有一快递公司，库房在图1中的O点，一送货员需将货物送至城市内多处，请设计送货方案，使所用时间最少.该地形图的示意图见图1，各点连通信息见表3，假定送货员只能沿这些连通线路行走，而不能走其它任何路线.各件货物的相关信息见表1，50个位置点的坐标见表2.假定送货员最大载重50公斤，所带货物最大体积1立方米.送货员的平均速度为24公里/小时.假定每件货物交接花费3分钟，为简化起见，同一地点有多件货物也简单按照每件3分钟交接计算.现在送货员要将100件货物送到50个地点.请完成以下问题.1.若将1~30号货物送到指定地点并返回.设计最快完成路线与方式.给出结果.要求标出送货线路.2.假定该送货员从早上8点上班开始送货，要将1~30号货物的送达时间不能超过指定时间，请设计最快完成路线与方式.要求标出送货线路.3.若不需要考虑所有货物送达时间限制(包括前30件货物)，现在要将100件货物全部送到指定地点并返回.设计最快完成路线与方式.要求标出送货线路，给出送完所有快件的时间.由于受重量和体积限制，送货员可中途返回取货.可不考虑中午休息时间..2模型的假设与符号说明2.1模型假设1．假设送货员只能沿如图所示连通线路行走，而不能走其它任何路线；2．在连通线路中业务员可以任意选择路线；3．假设送货员每到达一个地点，交接一件货物花费都为3分钟，交接完毕马上前往下一个地点，期间不花费时间；34．假设送货员的速度保持匀速，即保持24公里/小时，不考虑堵车，发生意外等现象；2.2符号说明iW：第i个货物的重量；(,)ixy：序号为i的送货点的坐标；iV：第i个货物的体积；C：送货路线总路程；N：送货员送货次数；t：送货所用总时间；(,)GVE：赋权连通图；iG：(,)GVE的第i个子图；iL：子图iG中的最佳回路；()e：边e的边权；()v：点v的点权；il：iL的各边权之和；ie：iL的各点权之和；T：送货中的停留时间；u：送货员的行驶速度；点权()ivTV.为叙述方便起见，我们在文中不加说明地使用上述变量和符号的变形形式，它们的含义可以通过上下文确定.3模型的分析与建立3.1模型的建立把快递公司送货地点示意图抽象为一赋权连通图(,)GVE，在权图G中，iv()VG对应示意图中的快递公司地点及货物送达点，0v表示快递公司所在地，je()EG对应示意图中路径.边权()je对应示意图中的路径长度.建立的数学模型如下：0(),(),(G),(),eEGeNvVvTVvV求G中回路12,,,(1)kLLLk，使得满足：（1）0(),1,2,,;ivVLik（2）1()();kiiVLVG（3）1()()min(inieELe目标为总距离最短）4或1()()max()()min(iijkeELeVLev目标为时间最短）为了讨论方便，先给出图论中相关的一些定义.定义1经过图G的每个顶点正好一次的圈，称为G的哈密顿环路，也称Hamilton圈.定义2在加权图(,)GVE中(1)权最小的哈米顿圈称为最佳Hamilton圈；(2)经过每个顶点至少一次且权最小的闭通路称为TSP回路问题.由定义2可知，本问题是一个寻找TSP回路的问题.TSP回路的问题可转化为最佳Hamilton圈的问题.方法是由给定的图(,)GVE构造一个以V为顶点集的完备图(,)GVE，E中每条边(,)xy的权等于顶点x与y在图中最短路径的权，即111min{,}mmmmijimmjijdddd在图论中有以下定理：定理1加权图G的送货员回来的权和G的最佳Hamilton圈的权相同；定理2在加权完备图中求最佳Hamilton圈的问题是NPC问题.在解决问题的过程中，我们用到以下算法：算法一（Floyd算法）：令nD表示一个NN矩阵，它的(,)ij元素是mijd．1．将图中各顶点编为1,2,,N．确定矩阵0D，其中(,)ij元素等于从顶点i到顶点j最短弧的长度(如果有最短弧的话)．如果没有这样的弧，则令0ijd．对于i，令00ijd．2．对1,2,,mN，依次由m-1D的元素确定mD的元素，应用递归公式111min{,}mmmmijimmjijdddd．每当确定一个元素时，就记下它所表示的路．在算法终止时，矩阵nD的元素(,)ij就表示从顶点i到顶点j最短路的长度．5算法二：求加权图(,)GVE的TSP问题回路的近似算法：1．用算法一（Floyd算法）求出(,)GVE中任意两个顶点间的最短路，构造出完备图(,)GVE，(,),(,)min(,)GxyExydxy．2．输入图G的一个初始Hamilton圈；3．用对角线完全算法产生一个初始Hamilton圈；4．随机搜索出(,)GVE中若干个Hamilton圈，例如2000个；5．对2、3、4步所得的每个Hamilton圈，用二边逐次修正法进行优化，得到近似最佳Hamilton圈；6．在第5步求出的所有H圈中，找出权最小的一个，此即要找的最佳Hamilton圈的近似解.算法三：蚁群算法蚁群算法是一种新型的模拟进化算法.该算法由意大利学者M.DorigoV.Maniezzo和A.Colorini等人在90年代首先提出，称之为蚁群系统(antcolonysystem)，应用该算法求解TSP问题、分配问题，取得了较好的结果.算法受到真实蚁群觅食行为的启发，科学家发现虽然单个蚂蚁没有太多的智力，也无法掌握附近的地理信息，但整个蚁群却可以找到一条从巢穴到食物源之间的最优路线.经过大量细致观察研究发现：蚂蚁个体之间通过一种称之为外激素(pheromone)的物质进行信息传递.蚂蚁在运动过程中,能够在它所经过的路径上留下该种物质，而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运动方向，因此，由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象：某一路径上单位时间走过的蚂蚁越多，表明该路线的可用性越好，则后来者选择该路径的概率就越大.蚂蚁个体之间就是通过这种信息的交流寻找最优的到达食物源的线路.蚁群算法具有实现简单、正反馈、分布式的优点.6图1蚁群算法说明在图1中，从A到E（或者从E到A）有两条路径（ABCDE和ABHDE），其中B到H、D到H的距离为1，B到C和D到C的距离为0.5.下面分别考虑在时刻t=0,1,2..时蚁群的运动情况.如图2b，在时刻t=0,设有30只蚂蚁从A运动到B.此时路径BH、BC上没有外激素(蚂蚁留下的信息量)，故蚂蚁将以相同的概率向BC、BH运动，于是各有15只蚂蚁分别选择路径BH和BC.在真实蚁群中，外激素的数量会随时间的流逝而蒸发掉一部分，为说明方便，此处假设：①所有蚂蚁运动的速度相等；②外激素蒸发量与时间成正比例，即路径上外激素的剩余量与路径的长度成反比；③蚂蚁选路的概率与所选路上外激素的浓度成正比.因为路径BHD的长度是路径BCD的2倍，当B点的蚂蚁到达D点后，路径BCD上的外激素是BHD上的2倍.如图2c，在时刻t=1有30只蚂蚁从E到达D.因为路径DC上的外激素量是DH上的2倍，根据蚂蚁选路特点，将会有20只蚂蚁选择DC，而只有10只蚂蚁选择DH.以此类推，当t=2,3,4...时，将会有更多的蚂蚁选择路径BCD.经过较长时间运动后，蚁群最终会沿着最优路径ABCDE运动.网络的路由问题与蚁群寻路的问题有很大的可比性，都是寻找可以到达目的地的最优路线.目前已经证明蚁群算法在解决路由问题上具有分布式、正反馈、全局收敛等优点.73.2求解准备1）根据已知位置点的坐标和连接情况，使用Matlab做出各点位置图如下：图2各点位置与连通情况图82）根据已知各点坐标，由两点间距离公式221212()()dxxyy求得图中相邻连通点间的距离如下表：表1相邻连通点距离表序号点1点2距离（m）序号点1点2距离（m）序号点1点2距离（m）11319163116232098613836153721828643217231775623927178032207823331831210463403416314242293341924225964404532175381958352022149965414423666343536362126219266413726027422293372136288067414627358515500538211718246842439189521253392230128769424919711061129440231717757043382618117185918412431178071444821531271196842254141557244504987138121757432519196673455031031491426814425291886744542235215910194645273110687546481494161018591046283313267647402331171072059472922109877484421531811121418483028101878495035691912131457493041499879494219712012255757503126153780504030432112154806513134232581O1821822213183113523235111482O2117972313193456533223131283O2613922413111670543346375925141853425533281326261416260856344016312714172196573538141028142132975836453182291522286159362722043015254235603740209093.3模型的求解3.3.1问题1问题1要求将1—30号货物送到指定地点并返回，不考虑各货物的送达时间，考虑到30048.550iiW，且3000.881iiV，故不用考虑重量、体积对送货次数的影响，即只需一次送货，无需中途返回取货.方法一：Floyd算法+二次逐项修边法1．由表1中的数据，做出图(,)GVE的邻接矩阵(0)A，根据Floyd算法，求得任意两点间的最短距离(51)A；2．经过分析，发现运送1~30号货物只涉及22个点（含0v），由于其中21个送货点中有5个含2货物，2个含3货物；3、将这22个顶点令为点集iX={(,)iiab，0,1,2,,21i}，令矩阵B为仅含有点iX的最短距离方阵，构成加权图完备图(,)GVE；05296509474933621218217975395470913923997292967