关键词:
物流配送
聚类分析
蚁群算法
因子分析
车辆路径问题
摘要:
近些年来,物流企业的迅猛发展得到了各行业的广泛关注,物流业与信息、网络等技术的结合,加快了物流业现代化发展的脚步。物流中最核心的环节是物流配送,配送的效率直接影响到物流的质量。因而,高效、合理、科学的配送环节是优质物流的基础。
本文的主要内容是设计与实现一个物流管理信息系统,为用户提供便捷、实时、安全的服务,并将物流配送的过程透明地呈现给用户。配送中的难点在于配送路径的确定问题,该问题可归结为VRP(Vehicle Routing Problems), VRP问题自上世纪五十年代被提出后便得到了学者的关注,目前已有大量的方法用于解决此类问题。其中一种有效的解决方法是将VRP问题划分为独立的TSP(Traveling Saleman Problems),而后分别对其求解,这是一种典型的两阶段算法。划分的原则是各子问题之间没有交集,并且子问题内的数据相对集中,而子问题间差异较大,聚类分析方法则恰好适用于处理此类问题。
在第一阶段中,采用IDBSCAN算法来实现VRP问题的划分,IDBSCAN算法是在DBSCAN算法基础上扩展来的。算法的输入是地理数据,为了能够更接近真实情况,使用实际行车路程来衡量两点之间的距离,同时为了体现地区的差异性,对各数据使用因子分析法进行加权处理。DBSCAN算法对邻域参数Eps敏感且不易发现密度变化较大的簇,为克服这两个问题,IDBSCAN算法通过分析数据的近邻分布情况来确定数据的密度区间,在聚类过程中,将数据的近邻值映射到密度区间来判断其是否是核心点,然后按照DBSCAN算法的思路进行聚类。IDBSCAN算法中输出的是相互独立的簇。
在第二阶段中,采用蚁群优化算法对各个簇中的TSP问题进行求解,解的集合即为最终的配送路径。
最后,本文描述了物流管理信息系统实现的功能及两阶段启发式算法在该系统中的应用。