一种大规模订单处理与配送路径优化的方法

1.一种大规模订单处理与配送路径优化的方法，其特征在于，包括以下步骤：
步骤100，根据订单属性，对订单进行ABC分类法初次聚类，划分A类订单、B类订单、C类订单；
步骤200，对所述A类订单、所述B类订单、所述C类订单进行BIRCH算法二次聚类，建立聚类特征树，对所述聚类特征树的叶结点进行聚类，获得特征簇；
步骤300，根据提货站点属性及物流路径属性，分别采用蚁群算法选择提货站点和物流路径；
步骤400，根据步骤200及步骤300的结果，对所述物流路径中所需要经过的站点，采用Dijkstra算法和蚁群算法对所述物流路径进行优化，获得最优路径；
步骤200中，所述二次聚类包括如下步骤：
步骤210，扫描所有数据，建立初始化的CF树，把稠密数据分成簇，稀疏数据作为孤立点；
步骤211，根据全局或半全局聚类算法的范围要求，建立一个更小的CF树；
步骤220，补救由于输入顺序和页面大小带来的分裂，使用全局/半全局算法对全部叶节点进行聚类；
步骤221，将步骤220中的中心点作为种子，将数据点重新分配到最近的种子上，保证重复数据分到同一个簇中，同时添加簇标签；
步骤400后还包括以下步骤：
步骤500，记录实际站点间的交通时间及站点停留时间；
步骤600，将步骤500的结果作为提货站点属性及物流路径属性；
所述订单属性包括订单送达时间、订单紧急程度、订单延迟时限；
所述提货站点属性包括站点停留时间、站点备货品种、站点备货量、站点位置。

一种大规模订单处理与配送路径优化的方法\n技术领域\n[0001] 本发明涉及一种大规模订单处理与配送路径优化的方法。\n背景技术\n[0002] 现代物流已被公认为是企业在降低物质消耗、提高劳动生产率以外创造利润的第三个重要源泉，也是企业降低成本，提高产品竞争力的重要途径。\n[0003] 在实际操作中对大规模的订单需要进行规模化的处理并且合理调配各站点仓库中的存储货物并且通过优化配送路径来节约运送成本，使利润最大化。\n发明内容\n[0004] 本发明的目的在于，提供一种云街便利循环物流配送体系的系统操作的算法和物流调配实现的方式，用于实现云街便利循环物流配送体系并且实现高效率的物流调配，增强配送系统对物流订单的处理能力和寻找最优化物流路径的能力。利用实际的反馈数据不断更新数据库内容使得系统对订单的处理能力和寻找最优化物流路径能力更加精准，形成一种积极的正反馈行为。\n[0005] 用于解决问题的方案\n[0006] 为了实现上述目的，本发明创造提供一种大规模订单处理与配送路径优化的方法，包括以下步骤：\n[0007] 步骤100，根据订单属性，对订单进行ABC分类法初次聚类，划分A类订单、B类订单、C类订单；\n[0008] 步骤200，对所述A类订单、所述B类订单、所述C类订单进行BIRCH算法二次聚类，建立聚类特征树，对所述聚类特征树的叶结点进行聚类，获得特征簇；\n[0009] 步骤300，根据提货站点属性及物流路径属性，分别采用蚁群算法选择提货站点和物流路径；\n[0010] 步骤400，根据步骤200及步骤300的结果，对所述物流路径中所需要经过的站点，采用Dijkstra算法和蚁群算法对所述物流路径进行优化，获得最优路径。\n[0011] 优选地，步骤200中，所述二次聚类包括如下步骤：\n[0012] 步骤210，扫描所有数据，建立初始化的CF树，把稠密数据分成簇，稀疏数据作为孤立点；\n[0013] 步骤220，补救由于输入顺序和页面大小带来的分裂，使用全局/半全局算法对全部叶节点进行聚类。\n[0014] 优选地，步骤200中，所述二次聚类包括如下步骤：\n[0015] 步骤210，扫描所有数据，建立初始化的CF树，把稠密数据分成簇，稀疏数据作为孤立点；\n[0016] 步骤211，根据全局或半全局聚类算法的范围要求，建立一个更小的CF树；\n[0017] 步骤220，补救由于输入顺序和页面大小带来的分裂，使用全局/半全局算法对全部叶节点进行聚类；\n[0018] 步骤221，将步骤220中的中心点作为种子，将数据点重新分配到最近的种子上，保证重复数据分到同一个簇中，同时添加簇标签。\n[0019] 优选地，步骤400后还包括以下步骤：\n[0020] 步骤500，记录实际站点间的交通时间及站点停留时间；\n[0021] 步骤600，将步骤500的结果作为提货站点属性及物流路径属性。\n[0022] 优选地，所述订单属性包括订单送达时间、订单紧急程度、订单延迟时限。\n[0023] 优选地，所述提货站点属性包括站点停留时间、站点备货品种、站点备货量、站点位置。\n[0024] 有益效果\n[0025] 1、良好适应云街便利循环物流配送体系的循环动态高效的配送体系。可以支持大量订单的分析与处理，且实现该种方法的软件对硬件要求不高，非常适合计算设备，适合现代电商的物流实际操作。在实际物流配送中与车载移动装置相配合可以实现输入订单显示路径以及预估到达各站点的时间，大大方便了物流配送人员，而且也方便公司对物流配送进行及时调配。该方法能有效节约物流成本提升物流配送效率。\n[0026] 2、该方法解决了三个层次的问题：第一层次是订单的处理，第二层次提货站点及路径的选取，第三层次是各因素信息的及时更新。这三个层次的算法结构互不影响，当有先进算法时，随时可以引进来替换陈旧算法，且也不影响程序的完整性。\n[0027] 3、与以往的物流的提货选址和配送路径选择的单向性相比该方法具有双向性，一个方向是从订单处理到路径选取到货物送达，另一个方向是用完成的各步骤的结果数据(如时间信息)反馈给系统数据库。两个方向互相作用优化整个配送体系，给公司日后大数据处理埋下伏笔。\n[0028] 4、本发明适应性强，对用户友善，可建立云端数据库，有需要的企业可以根据需要自由调取运算。\n具体实施方式\n[0029] 下面对本发明创造实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅是本发明创造部分实施例，而不是全部的实施例。基于本发明创造中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本发明创造保护的范围。\n[0030] 假设有n个订单，每个订单表示为Gi(i＝1，...，n)，设物流调配系统有n个A类站点ai(1≤i≤e)，m个B类站点ai(e＜i≤f)，p个C类站点ai(f＜i≤g)，每个站点表示为ai(i＝\n1，...，n)，在时刻T(t)，站点ai的某物流货物库存量为Qi(T(t))，而在这一时刻该站点对该物流货物的需求量为Di(T(t))，满足的约束条件为Q(T(t))≥D(T(t))，即总在未来某时间点某货物总库存量大于等于对该货物的需求量。且每辆运货车的最大装载量为W。\n[0031] 在初始状态时，各订单毫无规则且其中的数据繁杂，直接对初始订单数据进行聚类可能会导致程序运行缓慢，且聚类的结果不准确等情况。\n[0032] 因此，先对初始订单用ABC分类法的思想先进行初次聚类。\n[0033] 步骤100，根据订单属性，对订单进行ABC分类法初次聚类，划分A类订单、B类订单、C类订单。\n[0034] 云街便利循环物流配送体系中分A、B、C三类站点。A类站点主要为公司自营期间店，主要承载的物流职能为揽件、自提、派送、分拣。B类站点主要为有配送能力的社区点，配送站等，主要承载的物流职能为揽件、自提、派送。C类站点主要为社区点，主要承载的物流职能是揽件和自提功能。配送体系中实行A类站点之间(即仓库之间)定点配送和A类站点、B类站点、C类站点无间配送的循环动态高效的配送体系。\n[0035] ABC分类思想聚类的规则可以是按顾客收货的延迟期限可分为需采取及时配送(JIT配送)的A类订单、允许有一定延迟期限的B类订单以及允许较长延迟期限的C类订单，或者按订单货物调配方式分为各个A类站点和B类站点都有较多存货的A类订单、某些A类站点和B类站点有存货的B类订单以及需要从别的地方调运货物的C类订单。\n[0036] 步骤200，对所述A类订单、所述B类订单、所述C类订单进行BIRCH算法二次聚类，建立聚类特征树，对所述聚类特征树的叶结点进行聚类，获得特征簇。\n[0037] 优选地，所述二次聚类包括如下步骤：\n[0038] 步骤210，扫描所有数据，建立初始化的CF树，把稠密数据分成簇，稀疏数据作为孤立点；\n[0039] 步骤211，根据全局或半全局聚类算法的范围要求，建立一个更小的CF树；\n[0040] 步骤220，补救由于输入顺序和页面大小带来的分裂，使用全局/半全局算法对全部叶节点进行聚类；\n[0041] 步骤221，将步骤220中的中心点作为种子，将数据点重新分配到最近的种子上，保证重复数据分到同一个簇中，同时添加簇标签。\n[0042] 面对大型数据，利用BIRCH算法通过扫描数据库，建立一个初始存放于内存中的聚类特征树，然后对聚类特征树的叶结点进行聚类，聚类出的不同簇可看做是不同的物流路径。\n[0043] BIRCH算法的基本思想是建立一棵树，这棵树能够捕获聚类所必须的信息，聚类仅在这颗树上进行。其中树中结点的标记包含了计算距离值所需要的信息。树的规模由与每个叶结点所对应的阙值T决定。阙值T代表允许的最大直径。这里的直径是指簇中所有两个点之间距离的平均值。\n[0044] BIRCH聚类算法具体分为四个阶段：\n[0045] 1、扫描所有数据，建立初始化的CF树，把稠密数据分成簇，稀疏数据作为孤立点对待。\n[0046] 2、这个阶段是可选的，阶段3的全局或半全局聚类算法有着输入范围的要求，以达到速度与质量的要求，所以此阶段在阶段1的基础上，建立一个更小的CF树。\n[0047] 3、补救由于输入顺序和页面大小带来的分裂，使用全局/半全局算法对全部叶节点进行聚类。\n[0048] 4、这个阶段也是可选的，把阶段3的中心点作为种子，将数据点重新分配到最近的种子上，保证重复数据分到同一个簇中，同时添加簇标签。\n[0049] 步骤300，根据提货站点属性及物流路径属性，分别采用蚁群算法选择提货站点和物流路径。\n[0050] 指派提货站点，利用聚合好的订单数据用指派问题的思想合理规划选择不同物流路径上需要提货以及经过的A类站点和B类站点。\n[0051] 指派问题首先建立数学模型。\n[0052] 设物流调配系统中的A类站点和B类站点共有n个，每个站点都有各自的备货品种和备货量(如站点ak中有A商品a个、B商品b个、C商品c个等等)，步骤二中聚类出的各物流路径上需要取货的货物种类和对应的数量分别设为x和xy，而派送车去第i个站点取打包的货物j(A商品a个、B商品b个、C商品c个等等)所需的成本为c。\n[0053]\n[0054]\n[0055] 由于一个站点可能不满足一条物流路径上的订单取货要求，派送车可能需要去多个站点进行取货，所以我们要指派最优化的取货站点，即取货的成本最低。\n[0056] 最小成本的建模为：\n[0057]\n[0058] 在此模型基础上，用蚁群算法之最大-最小蚁群系统(Max-Min Ant System)进行运算。将cij设为一个节点，信息素集中在节点，到达一个节点信息素立即更新，所有蚂蚁完成一次觅食，比较次优解，进行全局信息素的更新。\n[0059] 产生随机概率w(0＜w＜1)，如果w＞w0，根据下式计算转移概率。蚂蚁移向概率最大的节点，否则在可选节点中随机选择一个。\n[0060]\n[0061] 当蚂蚁选择改节点后，立即更新此节点的信息素τij。\n[0062] 按下式更新全局信息素，\n[0063] τij(t+1)＝(1-ρ)τij(t)+Δτij(t)\n[0064] 式中ρ为蒸发系数，取值为0≤ρ＜1，决定信息素挥发的快慢，Δτij(t)表示本次蚂蚁觅食中在节点cij留下的信息素增量。\n[0065] 程序设置蚂蚁觅食次数，根据各节点的信息素迭代次数来选择最优化取货站点。\n[0066] 步骤400，根据步骤200及步骤300的结果，对所述物流路径中所需要经过的站点，采用Dijkstra算法和蚁群算法对所述物流路径进行优化，获得最优路径。\n[0067] 根据根据步骤200及步骤300的结果，根据该条物流路径中所需要经过的站点ai(i＝1，...，n)，用Dijkstra算法和蚁群算法来进行计算，使得物流路径是最短路径，从而实现云街便利循环物流配送系统中的高效速达的要求。\n[0068] 首先对配送距离进行建模，设站点ai和站点aj之间的距离为dij。建立不同站点之间距离的二维矩阵：\n[0069]\n[0070] 任意站点之间的距离dij为站点ai和站点aj之间的不可分割的最短距离。\n[0071] 根据点对点之间的地理信息、历史积累的人为经验信息等信息在程序中建立初步的距离模型，该各站点初始距离数据将作为已知条件作用到计算最优化路径的Dijkstra算法和蚁群算法中。\n[0072] 步骤500，记录实际站点间的交通时间及站点停留时间；\n[0073] 步骤600，将步骤500的结果作为提货站点属性及物流路径属性。\n[0074] 数据的反馈，这是建立云街便利循坏物流配送系统中的重要步骤。数据反馈对云街便利循环物流配送体系日后的长远发展有举足轻重的作用，数据的反馈能使数据库中的数据保持不断更新的状态，能及时跟上实际变化，以便随时能利用既定的程序始终寻找到最优化的物流配送方式。最终使得该系统运作后，配送高效度逐步增强。\n[0075] 在实际物流操作中，实际的情况为分散点，满足线性回归，而数据的反馈能不断增加分散点的数量从而精确线性回归线。实际的数据反馈对抽象的程序计算形成正反馈作用。\n[0076] 如发车时间的不同，相同站点之间的用时也可能不同，在数据反馈中，该路径车辆拥挤的情况也会由反馈的时间数据来体现，随着数据的不断反馈不断积累，可以从数据库中分析出哪些时间发车进行物流派送可以节约物流成本和配送时间。避免在拥挤时段发车导致的隐性物流配送的迟缓和物流成本的增加。\n[0077] 该种大规模订单处理与配送路径优化的方法中，基于云街便利循环物流配送体系这个平台，以该体系中循环班车的功能为前提，以综合的配送时间以及综合的配送成本为停留站点的选择和路径选取的标准，结合订单信息，各站点库存信息，发货车最大载货量，各站点之间距离等因素对配送时各站点是否停留取货的选择以及各站点之间路径进行最优化规划。\n[0078] 该方法在订单的聚类上采取了两次聚类，第一次聚类采用了ABC分类法的思想，第二次聚类采用适应大数据聚类的BI RCH聚类法。两次聚类相比一次聚类大大提升了计算机运行速度，同时也使得运行结果更加准确。而后，在配送路径的优化上，对于提货站点的选择和路径的选择上使用两次蚁群算法。这种算法很好的适应于现代计算机的计算方式，能有效计算出最佳配送路径。最后，每次配送后对数据的反馈在进行数据处理分析后又能精确程序运行的各条件因素取值，最后再次作用到配送体系中，提升了配送的高效性，保证了信息在配送体系中的流通性和及时性。\n[0079] 数据反馈形成的数据库可以变为云端数据库，方便各单位进行调运运算，且各企业使用后反馈的数据又能增加云端数据库的数据量。各个小数据库结合可以形成强大的物流数据体系。\n[0080] 该方法每个步骤都可以单独设置程序运行，不相互影响，若存在算法发展的进步，可以随时用先进的算法替换其中陈旧的算法，而不影响整体算法效果的运行情况。\n[0081] 以上所述，仅为本发明创造的具体实施方式，但本发明创造的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本发明创造揭露的技术范围内，可轻易想到变化或替换，都应涵盖在本发明创造的保护范围之内。因此，本发明创造的保护范围应所述以权利要求的保护范围为准。