基于聚类的物流管理信息系统设计与实现
|
摘要
近些年来,物流企业的迅猛发展得到了各行业的广泛关注,物流业与信息、网络等技术的结合,加快了物流业现代化发展的脚步。物流中最核心的环节是物流配送,配送的效率直接影响到物流的质量。因而,高效、合理、科学的配送环节是优质物流的基础。
本文的主要内容是设计与实现一个物流管理信息系统,为用户提供便捷、实时、安全的服务,并将物流配送的过程透明地呈现给用户。配送中的难点在于配送路径的确定问题,该问题可归结为VRP(Vehicle Routing Problems), VRP问题自上世纪五十年代被提出后便得到了学者的关注,目前已有大量的方法用于解决此类问题。其中一种有效的解决方法是将VRP问题划分为独立的TSP(Traveling Saleman Problems),而后分别对其求解,这是一种典型的两阶段算法。划分的原则是各子问题之间没有交集,并且子问题内的数据相对集中,而子问题间差异较大,聚类分析方法则恰好适用于处理此类问题。
在第一阶段中,采用IDBSCAN算法来实现VRP问题的划分,IDBSCAN算法是在DBSCAN算法基础上扩展来的。算法的输入是地理数据,为了能够更接近真实情况,使用实际行车路程来衡量两点之间的距离,同时为了体现地区的差异性,对各数据使用因子分析法进行加权处理。DBSCAN算法对邻域参数Eps敏感且不易发现密度变化较大的簇,为克服这两个问题,IDBSCAN算法通过分析数据的近邻分布情况来确定数据的密度区间,在聚类过程中,将数据的近邻值映射到密度区间来判断其是否是核心点,然后按照DBSCAN算法的思路进行聚类。IDBSCAN算法中输出的是相互独立的簇。
在第二阶段中,采用蚁群优化算法对各个簇中的TSP问题进行求解,解的集合即为最终的配送路径。
最后,本文描述了物流管理信息系统实现的功能及两阶段启发式算法在该系统中的应用。
Over the past few years, the fast development of logistics enterprises has drawn great attention from every profession and trade, and the combination of logistics and information and network technology speeds up the modernization of logistics. The most crucial link of logistics is logistics distribution, which influences the quality of logistics directly. Therefore, highly efficient, reasonable and scientific distribution is the foundation of premium logistics.
The main content of this thesis is the design and realization of a logistics management information system, providing convenient, real-time and secure services, and presenting logistics distribution flows to the customers transparently. The difficulties in distribution lie in the determination of distribution routes, which can be reduced to VRP (Vehicle Routing Problems), that was raised and focused by scholars in1950s and lots of methods have been applied to. One of the effective solutions is to divide VRP into independent TSP (Traveling Saleman Problems) and then solve them separately, which is a typical two-phase algorithm. The principle of division is making sure that there is no intersection between sub-problems and the data of sub-problem should be more concentrated inside sub-problem and more different between sub-problems:Clustering Analysis is just right for the problems.
In the first stage, the division of VRP will be realized by IDBSCAN, which is extended from DBSCAN. The input of IDBSCAN algorithm is geographic data. For better simulation, the distance between two points will be measured by practical driving distance, and all data will be weighed by factor analysis to reflect the difference between regions. DBSCAN is sensitive to neighborhood parameters Eps and is hard to discover large density fluctuation cluster. In order to overcome the two shortcomings, IDBSCAN determines density interval of data by analyzing the neighborhood distribution of data; in the process of clustering, neighborhood value of data will be mapped on density interval to determine whether it is the core, and then clustering it in the method of DBSCAN algorithm. The outputs of IDBSCAN are independent clusters.
In the second stage, all TSP in clusters will be solved by Ant Colony Optimization algorithm and the solution set is the ultimate distribution route.
In conclusion, the functions of logistics management information system and the application of two-phase algorithm in this system will be described.
本文的主要内容是设计与实现一个物流管理信息系统,为用户提供便捷、实时、安全的服务,并将物流配送的过程透明地呈现给用户。配送中的难点在于配送路径的确定问题,该问题可归结为VRP(Vehicle Routing Problems), VRP问题自上世纪五十年代被提出后便得到了学者的关注,目前已有大量的方法用于解决此类问题。其中一种有效的解决方法是将VRP问题划分为独立的TSP(Traveling Saleman Problems),而后分别对其求解,这是一种典型的两阶段算法。划分的原则是各子问题之间没有交集,并且子问题内的数据相对集中,而子问题间差异较大,聚类分析方法则恰好适用于处理此类问题。
在第一阶段中,采用IDBSCAN算法来实现VRP问题的划分,IDBSCAN算法是在DBSCAN算法基础上扩展来的。算法的输入是地理数据,为了能够更接近真实情况,使用实际行车路程来衡量两点之间的距离,同时为了体现地区的差异性,对各数据使用因子分析法进行加权处理。DBSCAN算法对邻域参数Eps敏感且不易发现密度变化较大的簇,为克服这两个问题,IDBSCAN算法通过分析数据的近邻分布情况来确定数据的密度区间,在聚类过程中,将数据的近邻值映射到密度区间来判断其是否是核心点,然后按照DBSCAN算法的思路进行聚类。IDBSCAN算法中输出的是相互独立的簇。
在第二阶段中,采用蚁群优化算法对各个簇中的TSP问题进行求解,解的集合即为最终的配送路径。
最后,本文描述了物流管理信息系统实现的功能及两阶段启发式算法在该系统中的应用。
Over the past few years, the fast development of logistics enterprises has drawn great attention from every profession and trade, and the combination of logistics and information and network technology speeds up the modernization of logistics. The most crucial link of logistics is logistics distribution, which influences the quality of logistics directly. Therefore, highly efficient, reasonable and scientific distribution is the foundation of premium logistics.
The main content of this thesis is the design and realization of a logistics management information system, providing convenient, real-time and secure services, and presenting logistics distribution flows to the customers transparently. The difficulties in distribution lie in the determination of distribution routes, which can be reduced to VRP (Vehicle Routing Problems), that was raised and focused by scholars in1950s and lots of methods have been applied to. One of the effective solutions is to divide VRP into independent TSP (Traveling Saleman Problems) and then solve them separately, which is a typical two-phase algorithm. The principle of division is making sure that there is no intersection between sub-problems and the data of sub-problem should be more concentrated inside sub-problem and more different between sub-problems:Clustering Analysis is just right for the problems.
In the first stage, the division of VRP will be realized by IDBSCAN, which is extended from DBSCAN. The input of IDBSCAN algorithm is geographic data. For better simulation, the distance between two points will be measured by practical driving distance, and all data will be weighed by factor analysis to reflect the difference between regions. DBSCAN is sensitive to neighborhood parameters Eps and is hard to discover large density fluctuation cluster. In order to overcome the two shortcomings, IDBSCAN determines density interval of data by analyzing the neighborhood distribution of data; in the process of clustering, neighborhood value of data will be mapped on density interval to determine whether it is the core, and then clustering it in the method of DBSCAN algorithm. The outputs of IDBSCAN are independent clusters.
In the second stage, all TSP in clusters will be solved by Ant Colony Optimization algorithm and the solution set is the ultimate distribution route.
In conclusion, the functions of logistics management information system and the application of two-phase algorithm in this system will be described.
引文
[1]谷炜,张群,胡睿.基于改进k-Means聚类的物流配送区域划分方法研究.中国管理信息化.2010,24期：60-63.
[2]韩家炜,堪博.数据挖掘：概念与技术(原书第二版).范明,孟小峰.机械工业出版社,2007：306-320.
[3]陈宝文.蚁群优化算法在车辆路径问题中的应用研究.哈尔滨工业大学博士学位论文.2009.
[4]王雪峰.连锁经营企业物流配送系统集成规划模型及算法研究.上海交通大学博士学位论文.2008.
[5]朱锦新.基于空间聚类和蚁群算法的车辆路径问题研究.盐城工学院学报.2009,04期：44-47,59.
[6]王晓博.电子商务下物流配送系统优化模型和算法研究.哈尔滨工业大学博士学位论文.2008.
[7]G lark, Wright J W. Schekuling of vehicles from a central depot to a number of delivery point[J]. Opns.Res,1964.569-579.
[8]Fisher M L, Jaikumar R. A generalized assignment heuristic for vechicle routing[J]. Networks,1981.109-124.
[9]B E Gillett, L R Miller. Application Handbook of Genetic Algorithms. CRC Press, 1974.340-349.
[10]J B Bramel, D Simchi-Levi. A location based heuristics for general routing problems[J]. Operation Research, 1995.649-660.
[11]Sam R. Thangiah. Vehicle Routing with time windows Using Genetic Algorithms. CRC Press,1995.253-287.
[12]Kawano. H. Applicability of multi-vechicle scheduling problem based on GPS tracking records.2010 18th International Conference, 2010.1-4.
[13]M. Dorigo, V. Maniezzo, A.Colorni. Ant system:Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics-Part B, 1996.29-41.
[14]程云卿.基于蚁群算法解决“对口支援”的赈灾物资指派问题的研究.中国企业运筹学.2009：98-105.
[15]Rizzolia E, Oliverio F, Montemannir, et al. Ant colony optimization for vechicle routing problems from theory to application[R]. Switzerland:Istituto Dalle Molle di Studi sull Intelligenza Artificale, 2004.
[16]Kasilingam R G. Logistics and transportation:design and planning. Boston. Kluwer Academic Publishers,1998.29-33.
[17]杨燕,靳蕃,Mohamed Kamel一种基于蚁群算法的聚类组合方法.铁道学报.2004,04期：64-69.
[18]Reimannm, Dorenerk, Hartlrf. Insertion based ants for vehicle routing problems with backhauls and time windows. Springer LNCS2463,2002.135-147.
[19]Boubahri, L. Multi-ant colonies algorithms for the VRPSPDTW. Communications, Computing and Control Applications(CCCA),2011 International Conference,2011. 1-6.
[20]王素云,李军.两阶段启发式算法在带时间窗的车辆路径问题中的应用[J].商业现代化.2008,11期：114-115.
[21]王静,王耀球,翁勇南.基于聚类分析与可拓决策方法的化肥物流中心选址研究.中国铁道学会物资管理委员会物资管理与营销暨物资流通系统理论学组学术研讨会.2008：308-316.
[22]丁建立,陈增强,袁著社.遗传算法与蚂蚁算法的融合[J].计算机研究与发展.2003,09期：1531-1536.
[23]崔雪丽,马良,范炳全.车辆路径问题(VRP)的蚂蚁搜索算法[J].系统工程学报.2004,04期：92-96.
[24]李爱梅,尤庆华.基于蚁群智能的物流配送系统VRP优化算法.中国系统工程学会第十四届学术年会.2006：413-421.
[25]刘志硕,柴跃廷,申金升.蚁群算法及其在有硬时间窗的车辆路径问题中的应用.计算机集成制造系统.2006,12期：596-602.
[26]刘洁,刘丹,何彦峰.带中转设施的垃圾收集VRP的改进蚁群算法.西南交通大学学报.2011,02期：333-339.
[27]杨燕.基于计算智能的聚类组合算法研究.西南交通大学博士学位论文.2006.
[28]Michael J. A. Berry, Gordon S. Linoff.数据挖掘技术：市场营销、销售与客户关系管理领域应用.别荣芳,尹静,邓六爱.机械工业出版社,2006：103-105.
[29]邵峰晶,于忠清.数据挖掘原理与算法.中国水利水电出版社,2003：22-28.
[30]王骏.无监督学习中聚类和阈值分割新方法研究.南京理工大学博士学位论文.2010.
[31]Amini. A, The Ying Wah, Saybani.M.R, Yazdi.S.R.A.S. A study of density-grid based clustering algorithms on data streams. In FSKD,2011.1652-1656.
[32]M.Ester, H.P.Kriegel, J.Sander, X.Xu. A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. In Proc. KDD,1996.
[33]Ankerst.M, Breunig.M.M, et al. OPTICS:ordering points to identify the clustering structure. Proc ACM SIGMOD 99th Int Conf on Management of Data, Phil,1999. 49-60.
[34]段瑞飞.数据挖掘中的聚类方法及其应用.厦门大学博士学位论文.2008.
[35]Birant. D, Kut. A. ST-DBSCAN:An algorithm for clustring spatial-temporal data, Data & Knowledge Engineering, 2007.208-221.
[36]何中胜,刘宗田,庄燕滨.基于数据分区的并行DBSCAN算法.小型微型计算机系统.2006,01期：114-116.
[37]张伟莉,倪志伟,赖建章.一种新的基于网格的聚类算法.计算机应用研究.2008,02期：1337-1339.
[38]李桃迎.交通领域中的聚类分析方法研究.大连海事大学博士学位论文.2010.
[39]刘波.蚁群算法改进及应用研究.燕山大学博士学位论文.2010.
[40]孙云山,王学深等.蚁群算法及其在物流系统中的应用研究.科技情报开发与经济.2010,16期：136-145.
[41]A. Colorni, M. Dorigo, V. Maniezzo. Distributed optimization by ant colonies[C]. Proceedings of the 1 st European Conference on Artificial Life, 1991. 134-142.
[42]吴斌,史忠植.一种基于蚁群算法的TSP问题分段求解法.计算机学报.2001,12期：1328-1333.
[43]Ping Guo, Zhujin Liu. Moderate ant system:An improved algorithm for solving TSP. ICNC,2011 Seventh International,2011.1190-1196.
[44]M. Dorigo, Stutzle. T. Ant Colony Optimization. MIT Press, 2004.
[45]S. Tomas, H. H. Holger. MAX-MIN ant system. Future Generation Computer Systems, 2000.889-91.
[46]李新蕊.主成分分析_因子分析_聚类分析的比较与应用.山东教育学院学报.2007,06期：23-26.
[47]曾玉钰.数据挖掘中基于因子分析的聚类方法及其应用.统计教育.2007,07期：10-11.
[48]殷辉,陈劲,谢芳.基于因子聚类分析的区域物流发展评价.管理科学与工程分会场论文集.2010.
[49]彭本红,彭建华.基于因子分析和聚类分析的区域物流中心选址研究.第十一届中国管理科学学术年会论文集.2009,571-575.
[50]孙卫琴.精通Structs基于MVC的Java Web设计与开发[tM].电子工业出版社,2005：95-127.
[51]杨燕,靳蕃.聚类有效性评价综述.计算机应用研究.2008,06期：1-2.
[52]朱星宇,陈勇强.SPSS多元统计方法及应用.清华大学出版社,2011.
[53]Bruce Eckel. Think in Java机械工业出版社,2007.
[2]韩家炜,堪博.数据挖掘：概念与技术(原书第二版).范明,孟小峰.机械工业出版社,2007：306-320.
[3]陈宝文.蚁群优化算法在车辆路径问题中的应用研究.哈尔滨工业大学博士学位论文.2009.
[4]王雪峰.连锁经营企业物流配送系统集成规划模型及算法研究.上海交通大学博士学位论文.2008.
[5]朱锦新.基于空间聚类和蚁群算法的车辆路径问题研究.盐城工学院学报.2009,04期：44-47,59.
[6]王晓博.电子商务下物流配送系统优化模型和算法研究.哈尔滨工业大学博士学位论文.2008.
[7]G lark, Wright J W. Schekuling of vehicles from a central depot to a number of delivery point[J]. Opns.Res,1964.569-579.
[8]Fisher M L, Jaikumar R. A generalized assignment heuristic for vechicle routing[J]. Networks,1981.109-124.
[9]B E Gillett, L R Miller. Application Handbook of Genetic Algorithms. CRC Press, 1974.340-349.
[10]J B Bramel, D Simchi-Levi. A location based heuristics for general routing problems[J]. Operation Research, 1995.649-660.
[11]Sam R. Thangiah. Vehicle Routing with time windows Using Genetic Algorithms. CRC Press,1995.253-287.
[12]Kawano. H. Applicability of multi-vechicle scheduling problem based on GPS tracking records.2010 18th International Conference, 2010.1-4.
[13]M. Dorigo, V. Maniezzo, A.Colorni. Ant system:Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics-Part B, 1996.29-41.
[14]程云卿.基于蚁群算法解决“对口支援”的赈灾物资指派问题的研究.中国企业运筹学.2009：98-105.
[15]Rizzolia E, Oliverio F, Montemannir, et al. Ant colony optimization for vechicle routing problems from theory to application[R]. Switzerland:Istituto Dalle Molle di Studi sull Intelligenza Artificale, 2004.
[16]Kasilingam R G. Logistics and transportation:design and planning. Boston. Kluwer Academic Publishers,1998.29-33.
[17]杨燕,靳蕃,Mohamed Kamel一种基于蚁群算法的聚类组合方法.铁道学报.2004,04期：64-69.
[18]Reimannm, Dorenerk, Hartlrf. Insertion based ants for vehicle routing problems with backhauls and time windows. Springer LNCS2463,2002.135-147.
[19]Boubahri, L. Multi-ant colonies algorithms for the VRPSPDTW. Communications, Computing and Control Applications(CCCA),2011 International Conference,2011. 1-6.
[20]王素云,李军.两阶段启发式算法在带时间窗的车辆路径问题中的应用[J].商业现代化.2008,11期：114-115.
[21]王静,王耀球,翁勇南.基于聚类分析与可拓决策方法的化肥物流中心选址研究.中国铁道学会物资管理委员会物资管理与营销暨物资流通系统理论学组学术研讨会.2008：308-316.
[22]丁建立,陈增强,袁著社.遗传算法与蚂蚁算法的融合[J].计算机研究与发展.2003,09期：1531-1536.
[23]崔雪丽,马良,范炳全.车辆路径问题(VRP)的蚂蚁搜索算法[J].系统工程学报.2004,04期：92-96.
[24]李爱梅,尤庆华.基于蚁群智能的物流配送系统VRP优化算法.中国系统工程学会第十四届学术年会.2006：413-421.
[25]刘志硕,柴跃廷,申金升.蚁群算法及其在有硬时间窗的车辆路径问题中的应用.计算机集成制造系统.2006,12期：596-602.
[26]刘洁,刘丹,何彦峰.带中转设施的垃圾收集VRP的改进蚁群算法.西南交通大学学报.2011,02期：333-339.
[27]杨燕.基于计算智能的聚类组合算法研究.西南交通大学博士学位论文.2006.
[28]Michael J. A. Berry, Gordon S. Linoff.数据挖掘技术：市场营销、销售与客户关系管理领域应用.别荣芳,尹静,邓六爱.机械工业出版社,2006：103-105.
[29]邵峰晶,于忠清.数据挖掘原理与算法.中国水利水电出版社,2003：22-28.
[30]王骏.无监督学习中聚类和阈值分割新方法研究.南京理工大学博士学位论文.2010.
[31]Amini. A, The Ying Wah, Saybani.M.R, Yazdi.S.R.A.S. A study of density-grid based clustering algorithms on data streams. In FSKD,2011.1652-1656.
[32]M.Ester, H.P.Kriegel, J.Sander, X.Xu. A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. In Proc. KDD,1996.
[33]Ankerst.M, Breunig.M.M, et al. OPTICS:ordering points to identify the clustering structure. Proc ACM SIGMOD 99th Int Conf on Management of Data, Phil,1999. 49-60.
[34]段瑞飞.数据挖掘中的聚类方法及其应用.厦门大学博士学位论文.2008.
[35]Birant. D, Kut. A. ST-DBSCAN:An algorithm for clustring spatial-temporal data, Data & Knowledge Engineering, 2007.208-221.
[36]何中胜,刘宗田,庄燕滨.基于数据分区的并行DBSCAN算法.小型微型计算机系统.2006,01期：114-116.
[37]张伟莉,倪志伟,赖建章.一种新的基于网格的聚类算法.计算机应用研究.2008,02期：1337-1339.
[38]李桃迎.交通领域中的聚类分析方法研究.大连海事大学博士学位论文.2010.
[39]刘波.蚁群算法改进及应用研究.燕山大学博士学位论文.2010.
[40]孙云山,王学深等.蚁群算法及其在物流系统中的应用研究.科技情报开发与经济.2010,16期：136-145.
[41]A. Colorni, M. Dorigo, V. Maniezzo. Distributed optimization by ant colonies[C]. Proceedings of the 1 st European Conference on Artificial Life, 1991. 134-142.
[42]吴斌,史忠植.一种基于蚁群算法的TSP问题分段求解法.计算机学报.2001,12期：1328-1333.
[43]Ping Guo, Zhujin Liu. Moderate ant system:An improved algorithm for solving TSP. ICNC,2011 Seventh International,2011.1190-1196.
[44]M. Dorigo, Stutzle. T. Ant Colony Optimization. MIT Press, 2004.
[45]S. Tomas, H. H. Holger. MAX-MIN ant system. Future Generation Computer Systems, 2000.889-91.
[46]李新蕊.主成分分析_因子分析_聚类分析的比较与应用.山东教育学院学报.2007,06期：23-26.
[47]曾玉钰.数据挖掘中基于因子分析的聚类方法及其应用.统计教育.2007,07期：10-11.
[48]殷辉,陈劲,谢芳.基于因子聚类分析的区域物流发展评价.管理科学与工程分会场论文集.2010.
[49]彭本红,彭建华.基于因子分析和聚类分析的区域物流中心选址研究.第十一届中国管理科学学术年会论文集.2009,571-575.
[50]孙卫琴.精通Structs基于MVC的Java Web设计与开发[tM].电子工业出版社,2005：95-127.
[51]杨燕,靳蕃.聚类有效性评价综述.计算机应用研究.2008,06期：1-2.
[52]朱星宇,陈勇强.SPSS多元统计方法及应用.清华大学出版社,2011.
[53]Bruce Eckel. Think in Java机械工业出版社,2007.