基于tsp问题的物流配送路径优化模型

基于tsp问题的物流配送路径优化模型摘要：物流配送是直接与消费者相连的物流活动。在各项物流成本中配送费用占了很大的比例，同时配送线路安排的合理与否对配送速度、成本、效益影响很大,因此采用科学、合理的方法来进行配送线路优化,是物流配送中非常重要的一项活动。本文在此提出了基于tsp问题通过动态规划方法建立物流配送路径的优化模型，并通过相关实例用该模型的求解来验证。关键词：配送费用 tsp问题 动态规划 配送路径优化一、问题 1.1 TSP问题简介旅行商问题(Traveling Salesman Problem，简称TSP，亦称郎担问题)就是典型的组合优化问题。它可以描述为：对于N个城市，它们之间的距离己知，有一旅行商要从某一城市出发走遍所有的城市，且每一个城市只能经过一次，最后回到出发城市，问如何选择路线可使他所走过的路程最短。1.2问题描述我国物流发展一直存在一个很大的问题就是物流成本过高，2010年我国物流费用是西方发达国家的两倍，而其中运输费用占物流总费用的50%左右，所以有效减少运输成本是我国物流亟待解决的重要问题。基于这样的物流发展现状，要减少运输费用，减少配送成本，以达到降低物流成本的目的，就必须实现配送车辆运输路线优化。同时为了解决在配送人员完成送货后能及时返回，我们在本文中运用动态规划的方法就tsp问题，提出了适用于物流公司配送路线优化的模型，并通过实例求解验证，建立配送路线的优化方案。二、 国内外的研究对于物流配送路径优化一直是国外研究的重点，而我国由于近几年对物流成本的重视，许多的学者都对此进行了研究，他们研究的方向主要倾向于用智能算法来对配送路径进行优化。J. Renaud, F.F. Boctor, and G. Laporte提出了改进的启发式算法进行路径优化，Tailand E对禁忌搜索算法用于车辆路径优化进行了研究，冯国莉、杨晓冬对用Hopfield神经网络车辆路径的优化进行了研究, 王俊、郭婷婷基于改进蚁群算法的物流配送路径的研究，刘芳华、赵建、,朱信忠对基于改进遗传算法的物流配送路径优化的研究等许多的学者对此进行了研究。而对于tsp问题许多学者也进行了大量的研究，李萍,高雷阜,刘旭旺针对Hopfield神经网络解旅行商问题(TSP)经常出现无效解和局部优化解，将模拟退火智能算法与Hopfield神经网络相结合,提出了一种混合优化算法(SA-HNN)，还有国外学者G.V.Wilson, G.S.Pawley对用Hopfield神经网络解旅行商问题(TSP)提出了一定观点。除此之外谢胜利对用遗传算法求解tsp问题进行了研究，Grefenstette J研究了遗传算法在tsp问题中的应用。另外还有吴斌,史忠植基于蚁群算法的TSP问题分段求解研究，王茂芝,郭科,徐文皙,黄光鑫关于用蚂蚁算法求解TSP问题的性能分析及改进的研究。虽然很多学者对tsp问题及配送路径优化问题进行了大量的研究，但对于用tsp模型来实现物流配送路径优化的研究则很少，为此我们提出了用tsp模型来进行配送路线的优化。三、 模型的建立、求解及分析3.1模型基本假设1. 忽略因自然原因及人为等因素造成的交通堵塞的可能。2. 两点之间的距离是两点之间的最短路径。3. 司机在送货途中没出现意外情况。4. 每一条通路的好坏都一样。5. 往返的路线相同。3.2 模型符号说明符号说明k已经历过的城市个数，包括当前所在的城市Xk状态变量Sk表示尚未访问过的城市的集合。F空集dk决策函数Fk（i，Sk）最优指标函数，表示从城市i出发，经过Sk中每个城市一次且仅一次，最后返回始发城市的最短距离。i当前所在的城市j下一站将要到达的城市F0(i,F)边界条件3.3模型的建立令k=1, 2, , n , k=n表示从始发点经过n个点回到始发点 Xk=(i, Sk) 则 S1=2,3,n，Sn=Sn+1=FXn=(i, F) i=2,3,n， xn+1=(1, F)dk=( i , j )若当前的状态为 Xk=( i ,Sk)采取的决策为dk=（i，j） 则下一步到达的状态为 xk+1=T(xk,dk)=( j ,Sk j)则最优决策函数 Fk（i，Sk）=min dij+Fk(j, S(k-1)（k=1,2,n-1。I=2,3,n）最后由Fk（i，Sk），即可求得最优路线及最小路径。 F0(i,F)=d1i四、模型应用举例位于船山西路的衡阳雁达物流有限公司最近接到一项业务，即为衡阳市内4家香江百货店（香江百货总店、船山店、湘江店、岳屏广场店）配送货物，为了尽可能的节约成本，该公司要求司机在将货物送到各个店，并及时返回的情况下实现路径最短（因货物数量问题，该公司只配备了一辆货车）。（各店分布如图4.1）香江百货船山店(B)雁达物流有限公司(A)香江百货岳屏广场店(D)香江百货总店(E)香江百货湘江店(C)图4.1 各店分布图距离矩阵如下表 单位：公里始点 终点ABCDEA02.13.63.74.6B2.102.31.65.6C3.62.301.85.6D3.71.61.805.4E4.65.65.65.40例题的求解（求解过程见附件）我们通过建立tsp模型，并用动态规划算法求解， 最后得出该司机的配送路线优化方案为ACDBEA 总长度为：17.2公里 优化路线图如图4.2 香江百货船山店(B)雁达物流有限公司(A)香江百货岳屏广场店(D)香江百货总店(E)香江百货湘江店(C) 图4.2 优化路线图五、 模型的分析评价本文针对配送路径优化问题通过动态规划方法建立tsp模型来进行求解，并通过实例计算得出了比较优的结果，可因为该实例中地点数目不多，所以得出了最优解，但随着送货地点数目的增加，用此方法得到的则不一定是最优解，同时计算量也相当大。而且由于送货是一个比较复杂的问题涉及到众多的变量，在我们的模型中尚有许多因素没有考虑在内。比如有的路况比较好，有的路比较很不好走，可以绕道等问题没有考虑在内等。但总的来说，该模型还是可行的，因其不但考虑了送货路径，还将回程考虑在内，这样做的好处是可以实现整个物流配送的闭合回路，减少了配送人员的迂回绕行，使他在完成了各个点配送任务后能及时的返回公司，极大的减少了配送成本，同时还能有效地提高配送效率。同时该模型的实用性很强，它可以很好地用于中小城市城内的对于送货地点不多的情况，同时通过对该模型的延伸，还可以实现多个城市之间的物流配送路径的优化。六、 总结本文所研究的主要是基于tsp问题建立配送路径优化模型，对于tsp问题，学者们对其的研究数不胜数，同样对于配送路径优化问题近几年也引起了众多学者们的关注，进行了大量的研究，但是对于用tsp问题的解法应用于配送路径优化问题上的研究则很少。为此本文在基于众多学者研究的基础上提出了用tsp问题的求解方法来建立物流配送路径优化模型，此模型不仅实现了货物的有效配送及运输路线的优化，还实现了配送中心与各个送货点网络的连接及运输路线的闭合回路。同时本文还通过将该模型用于实例验证，得到了最优路径优化方案，证明了该模型具有一定的现实实用性及可行性。这也是本文所研究的主要目的，即能够通过该模型的建立以解决物流配送活动当中的问题。但是因能力有限本文所研究仅仅是浅层次的基于配送地点不多的情况，而对于实际当中多地点的配送仍需进一步的研究及改进，同时用动态规划的方法计算也太过繁琐、计算量大，所以对于此问题还 要加强算法的改进及使用新的方法来进行建模，这些都是以后仍需努力和研究的方向。 参考文献：1 J. Renaud, F.F. Boctor, and G. Laporte. An improved petal heuristic for the vehicle routing problem .Journal of Operational Research Society, 19962 Tailand E. A tabu search heuristic for the vehicle routing problem with soft time windows .Transportation Science, 19973 王俊,郭婷婷. 基于改进蚁群算法的物流配送路径研究J. 价值工程, 2009.4 刘芳华,赵建民,朱信忠. 基于改进遗传算法的物流配送路径优化的研究J. 计算机技术与发展, 2009. 5 李仁安,袁际军. 基于改进遗传算法的物流配送路线优化研究J武汉理工大学学报, 2004 .6 冯国莉,杨晓冬. 基于Hopfield神经网络车辆路径的优化研究J信息技术, 2006,7 李萍,高雷阜,刘旭旺. 一种基于模拟退火和Hopfield神经网络求解TSP算法J. 科学技术与工程, 2008, (14) .8 G.V.Wilson, G.S.Pawley. On the stability of the travelling salesman problem algorithm of Hopfield and Tank J. Biol. Cybern., vol.58, 19889 谢胜利等,基于遗传算法的旅游商问题求解.温州师范学院学报，2002.10 Grefenstette JGenetic algorithms for the travehng salesman pmblemin：proeof1 intcoufon genetic algorithms andtheir applications JLawrence erlbatm association，1985.11 吴斌,史忠植. 一种基于蚁群算法的TSP问题分段求解算法J计算机学报, 2001.12 王茂芝,郭科,徐文皙,黄光鑫. 蚂蚁算法求解TSP问题的性能分析及改进J成都理工大学学报(自然科学版), 2009.附件：对于如图4.1所示的问题，（图中的地点ABCDE对应下面的12345）求解步骤如下：边界条件f0(i,F)的值列表如下：i f0(i, F)2 2.13 3.64 3.75 4.6对于k=1时，有 f1(i, S1)=minCij+f0(j,S1) f1(i,S1)的值列表如下：(i,S1) j Cij+ f0(i, F) f1(i,S1) (2,3) 3 2.3+f0(3,F)=2.3+3.6=5.9 5.9 (2,4) 4 1.6+f0(4,F)=1.6+3.7=5.3 5.3 (2,5) 5 5.6 +f0(5,F)=5.6+4.6=10.2 10.2 (3,2) 2 2.3+f0(2,F)=5.7 5.7 (3,4) 4 1.8+f0(4,F)=5.5 5.5 (3,5) 5 5.6+f0(5,F)=10.2 10.2 (4,2) 2 1.6+f0(2,F)=3.7 3.7 (4,3) 3 1.8+f0(3,F)=5.4 5.4 (4,5) 5 5.4+f0(5,F)=10 10 (5,2) 2 5.6+f0(2,F)=7.7 7.7 5,3) 3 5.6+f0(3,F)=9.2 9.2 (5,4) 4 5.4+f0(4,F)=9.1 9.1 对于k=2时，有 f2(i,S2)=minCij+f1(j,S1)f2(i,S2)的值列表如下：(i,S2) j Cij+f1(j,S1) f2(i,S2) (2,3,4) 34 2.3+f1(3,4)=7.8,1.6+f1(4,3)=7 7 (2,3,5) 35 2.3+f1(3,5)=12.5,5.6+f1(5,3)=14.8 12.5(2,4,5) 45 1.6+f1(4,5)=11.6,5.6+f1(5,4)=14.7 11.6(3,2,4) 24 2.3+f1(2,4)=7.6,1.6+f1(4,2)=5.5 5.5(3,2,5) 25 2.3+f1(2,5)=12.5,5.6+f1(5,2)=13.3 12.5(3,4,5) 45 1.8+f1(4,5)=11.8,5.6+f1(5,4)=14.7 11.8 (4,2,3) 23 1.6+f1(2,3)=7.5,1.8+f1(3,2)=7.5 7.5(4,2,5) 25 1.6+f1(2,5)=11.8,5.4+f1(5,2)=13.1 11.8(4,3,5) 35 1.8+f1(3,5)=12*5.4+f1(5,3)=12 12(5,2,3) 23 5.6+f1(2,3)=11.5*5.6+f1(3,2)=11.3 11.3(5,2,4) 24 5.6+f1(2,4)=10.9*5.6+f1(4,2)=9.1 9.1(5,3,4) 34 5.6+f1(3,4)=11.1,5.4+f1(4,3)=10.8 10.8对于k=3时有 F3(1,S3)=minCij+f2(j,S2)(i,S3) j Cij+f2(j,S2) f3(i,S3) (2,3,4,5) 345 2.3+f2(3,4,5)=14.1,5.6+f2(4,3,5)=16.4,1.6+f2(5,3,4)=13.6 13.6 (3,2,4,5) 245 2.3+f2(2,4,5)=13.9,1.8+f2(4,2,5)=13.6,5.6+f2(5,2,4)=14.7 13.6(4,2,3,5) 235 1.6+f2(2,3,5)=14.1,1.8+f2(3,2,5)=14.3,5.4+f2(5,2,3)=16.7 14.1(5,2,3,4) 234 5.6+f2(2,3,4)=12.6,5.6+f