B题问题二模型构想.doc

B题问题二模型构想 问题分析模型的建立及求解 TSP模型的数学描述为：其顶点集合为A0，1，2，3，4，5，650（0表示起点）顶点间的距离为C=Cij| i,jN,1i,jnmin CijXij i=1，j=1满足Xij=1,i=1,2,nj=1Xij=1,j=1,2,nj=1Xij0,1, i=1,2n,Ti=Ti根据上述所列的启发式方法生成一个可行路线安排。由于受时间限制，首先考虑时间。对各邮件到达时间对送货地点进行分组。每组是一个阶段，可分四个阶段然后采用动态规划的插值法（一般而言，比较简单的启发式算法求解TSP模型求解有最邻近法和最近插入法两种。由RosenkrantzStearns等人在1977年提出的最近插入法，能够比最近邻点法，取得更满意的解。）进行优化每一阶段。分组如下：一9:00 13 18 24 二9:30 31 45 34 40三10:15 38 43 42 49四12:00 26 21 14 17 23 32 36 27 16 39路径选择：从0经过13,18,24的一条可行路径为：01813192431以31为起点经过31,45,34,40的一条可行路径为：31344045以45为起点，经过38,43,42,49的一条可行路径为：455049424338以38为起点，经过21,26,14，17,23,36,27,16,39的可行路径为：3835322316141721263127392736然后对四段路径进行优化求出最短路径路段一：Aij 及各点到达时间表二路段一中没有可插入的点，改变路径为018312419131831显然增加了距离D18,31故排除。同理，从026或021都会增加路段D18，31（因为必须先进过九点的送货点，再到第二路段）所以第一路段可行最优路径为01813192431。路段二：路段二要经过的个点如图一在一线上，且没有要到达的拐点可插入，且到达时间满足条件。所以路段二的最优路径为31344045。路段三：路段三从A50出发可行路径有455049424338和454249424338，比较路径长度得第三路段最优路径为454249424338。路段四：可行路径3835322316141721263127392736和383532231614172136273927比较两段路径得第四段路最优路径为383532231614172136273927综上所述最佳路径为0181319243134404542494243383532231614172136273927如图所示问题一求解现在送货员送30件货得最优访问路径安排就是一个典型的单回路问题。可以通过单回路运输模型-TSP模型求解。一般而言，比较简单的启发式算法求解TSP模型求解有最邻近法和最近插入法两种下面用最邻近发求解（1 每一个行程的第一个送货点是距离总部最近的未服务的送货点。用这种方法，即可得到一组运行路线，总的运行公里数最小。（2每一个行程的第一个送货点是距离总部最远的未服务的送货点。然后以该点为基准，选择距它最近的点，加上约束条件，也可得到一组数据。 然后比较两组结果，通过函数拟合即可得到最优化结果。方法一获得的路径为0263127392736-38353223161417210181319243134404542494243方法二获得的路径为01819243134404542494243383627392731262114162317233235经过函数拟合得最佳路径为01813-1831-24-3126-2117141623323538362739273134404542494243-如图所示问题三分析问题三在TSP模型的基础上又增加了限制条件，每次负载不能超过50千克。这样就 9:00 13 18 24 9:30 31 45 34 4010:15 38 43 42 4912:00 26 21 14 17 23 32 36 27 16 39从0经过13,18,24的一条可行路径为：01813192431以31为起点经过31,45,34,40的一条可行路径为：31344045以45为起点，经过38,43,42,49的一条可行路径为：4550494