分享+西工大数模竞赛图论题三等奖论文.docVIP

可达0 ksksk 问题的重述 现今社会网购已经成为一种常见的消费方式，随着物流行业也渐渐兴盛，送货员需要以最快的及时将货物送达，而且他们往往一个人送多个地方，这就迫切需要一种解决方案来预测出最短路线以期送货耗时最少。 我们需要解决的问题是： 建立数学模型，分析送货点以及路段长（即图论中的权）对于送货时间的影响； 收集整理出现今对于TSP问题的研究资料及成果。利用其中的方法解决本体送货路线的设计； 写出一份报告，阐释我们对该问题的理解及部分解法。 二、基本假设 假定送货员行进过程中的速度恒定 不考虑天气、路段的好坏对送货的影响 不考虑货主因对货物的不满而引起的对送货员送货时间的拖延 不考虑送货员在一个地方交送多个货物所造成的时耗。为简化起见，交送多个货物时只按一件货物交接时间计时（即在每个地方只耽搁3分钟）。 三、符号假设 符号含义d任意两送货点之间的距离x任意送货点的横坐标y任意送货点的纵坐标u图中的任意一点v图中处u之外的点Pu与v之间的权（路径）A距离矩阵i送货点j与i不相同的送货点d1地点27和39之间的距离m所送货物的质量v所送货物的体积S最优线路的总路程V送货员的速度=24km/hT 送货员沿最优路线完成送货任务所需总时间t每件货物交接花费时间=3min四、问题的分析 本体中给出了一快递公司的送货图要求送货员将货物送到指定地点并达 最优化的目的。 在问题一中，要求将一到三十号货物送到指定地点并返回。为解决此问题，我们首先应该考虑的问题是送货员能否将货物一次性携带，其中包括货物的重量和体积，因为这样才能将时间缩到最短，而题目所给数据恰恰符合我们的期望。第二步，由于送货员送货速度恒定，故可将最快成路线问题问题转化为最短线路问题。第三步，就是将该实际问题转化为数学问题，也就是问题的简化与抽象： 由于送货点大小相对于路程相比??它们要小得多，故可抽象的缩成一个点。两送货点之间的公路可简化为直线段或曲线段。而直线段或曲线段的长即为此段公路长。于是送货线路图在数学上抽象为所谓“加权网络图”或称“赋权图”。送货点成为图的顶点。之间的公路直线或曲线称为图的边。公路长称为此边的长。先求出所有的权，其关系可表示为： 权（即距离）的平方=横坐标之差的平方+纵坐标之差的平方 送货问题可归结为图上的优化问题：在给定加权网络图上寻找从给定点O出发，所有图上的点至少一次，再回到给定点O，且使得总路程最少的闭曲线。（如图所示为送货员的线路） （注：图中为实际坐标的五分之一） 五、模型的建立与求解 问题1 在问题一中，要确定，送货员可以一次性携带要送所有货物不用回到O点去取货物，求最快完成的线路方式可以简化为求从O点到另外22个地点的最短距离。 (一）模型的建立 在图论模型中，最短距离的求解是非常经典的问题，在许多优化问题中有很多广泛的应用。问题就是运用图论方法求解的一个经典例子。 所谓的最短距离就是指在给定的赋权图中指定应一对定点u，v间众多的路中，寻求一条边权之和最小的路。这样的路称之为从u到v的在短距离。其求解公式为： d* d =(X1-X2)*(X1-X2)+(Y1-Y2)* (Y1-Y2) 为方便期间，我们定义图中从u到v的路P（u，v）上所有边权之和称之为路P的权。从u到v的最短路的权称之为u到v间的距离。利用这些距离我们可以得出一个矩阵。 由于TSP问题的复杂性，很难求出最优解，我们可以采用LINGO软件求解 上面我们已经得出了一个距离矩阵A, d ij表示送货点i和j之间的距离. 设0-1矩阵x用来表示经过的各送货点之间的路段。设当送货点i不到送货点j时xij为0，相反，xij为1. 考虑每个送货点后只有一个送货点，则 ＝1 i=1，2，3，…… （2） 考虑每个送货点前只有一个送货点，类比上式可得结果 但仅以以上约束条件不能避免在一次送货过程中产生多余一个连通回路。为此引入额外变量ui（i=1，2，3，……，n）附加以下约束条件，即 ui-uj+n*xij=n-1,1i!=j=n 该约束条件的解释：①i与j不会构成回路，有xij=1，xji=1，则ui-uj=-1, uj-ui=-1,从而有0=-2，导致矛盾。②i，j与k不会构成回路，若构成回路，有xij=1，xji=1,xki=1,则ui-uj=-1, uj-uk=-1,uk-ui=-1,从而有0=-3，导致矛盾。其他情况以此类推。 于是可以得到模型。 （二）模型的求解与验证 由于送货员在一点可能会送去不止一个货物，故我们在模型中可以视为送货员在该点只送去一个货物，其质量为在该点所送货物质量之和。下面我们通过对1—30号货物的分析可知