基于改进K-means聚类物流配送区域划分方法研究.pdf

2010年12月 中国管理信息化 Dec．．2010 第13卷第24期 China Inf0珊ationization V01．13．No．24 MaIlagement 谷 炜，张 群，胡 睿 (北京科技大学经济管理学院，北京100083) [摘要]在求解大规模的车辆路径问题时．首先需要将大规模复杂的配送网络根据一定的约束条件并利用相应的方法划分为若 干个小规模的配送区域．而不同的配送区域的划分方法对最后优化效果影响很大，本文从解决实际问题入手，首先明确了使用聚 类算法进行配送区域的划分可以使得到的区域比较紧密且更符合实际需求．然后分析了现有基于K—mealls聚类算法的优劣性，在 此基础上设计了一种新的配送区域均衡的划分方法——改进的两阶段K咄am聚类算法．并经过仿真实验验证了方法的实用性 和有效性。 [关键词]物流配送：区域划分；K111eallS聚类 doi：10．3969／j．issn．1673一0194．2010．24．028 [文献标识码]A [中图分类号]F274；F224D [文章编号]1673—0194(2010)24-0060—04 1 引 言 车辆送货格外少或者格外多的情况出现。 物流配送区域的划分是一个多约束、多目标决策的组合优 第四，每两个聚类不能有重合，否则会发生重复送货的情况； 化问题。属于NP难问题…．现行一般求解VRP问题的算法时间同理每一个点都必须包含在某一个类中。 复杂度大都为0(凡2)．若按此计算规模为lO000个左右节点的 第五。在实际应用中只考虑位于城区的客户分布，对于位于 车辆路径问题预计至少需要数百小时．因此在求解大规模车辆 郊区的客户。可以利用城区的配送原理进行计算。 路径问题上需要寻找合适的解法。目前的解决思想是化整为零。 2 基于GIS的两点间最短距离的确定 各个击破。即首先将大规模复杂的配送网络根据一定的约束条 GIS环境下针对配送道路路线进行规划．将着重分析城市的 件并利用相应的方法划分为若干个小规模的配送区域．然后逐 道路网络图层．道路中两个节点间的最短距离的求解就是基于这 个求解小规模车辆路径问题即在各子区域内设计最优配送路 个图层。在城市道路网图层中进行最短路径分析时．必须首先将 线．以此寻找到整个问题的近似较优解。 现实中的城市道路网络实体抽象化为图论中的网络图的形式，然 而在选择划分方法时．不同的配送区域的划分方法对最后 后通过网络分析来实现道路网络的最短路径分析。在实际应用 优化效果影响很大．所以确定一种比较合理的划分算法对整个 中．城市道路网的表现形式一般为数字化的矢量地图。其网络空 系统是非常关键的。目前配送区域划分的主要方法有扫描法和 间特征中的交叉路口坐标和道路位置坐标是在地图上借助图形 聚类算法。扫描法的基本思路是采用逐次逼近的方法求解物流 来识别和解释的．而为了能够高效率地进行最短路径分析。必须 配送车辆调度问题．一般适用于客户数目不太大且配送区域不 首先将其按节点和边的关系抽象为图的结构。这就需要对原始道 多时；而当客户网点数目较大且配送区域较多时．则采取聚类算 路图进行预处理。建立其相应的网络拓扑关系。经过预处理后，当 对城市道路网进行最短路径分析操作时。系统就可以直接从拓扑 法，把大量的d维数据对象(乃个)聚集成艮个聚类(七n)，使同 一聚类内的对象的相似性尽可能最大．而不同聚类内的对象的 信息表中提取道路网的网络拓扑结构。将配送仓库和每个客户点 相似性尽量达到最小。也就是说形成聚类之后．同一个聚类内的 之间的最短距离．以及每个客户之间的两两最短距离都保存到数 对象具有很高的相似性．而且与不属于该聚类的对象有迥然的 据库中．为求解路径规划问题提供数据。 差异(即不相似)。由于聚类的特殊性．在物流系统中使用聚类算 研究模型与GIS结合时最大的问