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

基于tsp问题的物流配送路径优化模型 摘要：物流配送是直接与消费者相连的。配送线路安排的合理与否对配送速度、成本、效益影响很大,采用科学、合理的方法来进行配送线路优化,是物流配送中非常重要的一项活动。 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模型基本假设 忽略因自然原因及人为等因素造成的交通堵塞的可能。 两点之间的距离是两点之间的最短路径。 司机在送货途中没出现意外情况。 每一条通路的好坏都一样。 往返的路线相同。 3.2 模型符号说明 符号 说明 k 已经历过的城市个数，包括当前所在的城市状态变量表示尚未访问过的城市的集合。空集决策Fk（i，Sk） 最优指标函数表示从城市i出发，经过Sk中每个城市一次且仅一次，最后返回城市的最短距离当前所在的城市 下一站将要到达的城市 F0(i,F) 边界条件 3.3模型的建立 令k=1, 2, …, n , k=n表示从始发点经过n个点回到始发点 Xk=(i, Sk) 则? S1={2,3,…,n}，…，Sn=Sn+1=Fn=(i, F)? ? ? ? i=2,3,…,n，? ? ? ? xn+1=(1, F)dk=( i , j )若当前的状态为? ? ? ? ? ? ? ? k=( i ,Sk)采取的决策为 ? ? ? ? ? ? 则下一步到达的状态为? ? ? ? ? ? ? ? ? ? ? ? xk+1=T(xk,dk)=( j ,Sk\ {j}) {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） 图4.1 各店分布图 距离矩阵如下表 单位：公里 始点 终点 A B C D E A 0 2.