面向超大规模物流配送的选址与运输优化方法

1. 一种面向超大规模物流配送的选址与运输优化方法，其特征在于，包括W下步骤： 步骤一:聚类，利用自下而上的聚类方法获得初始聚类结果，将所得初始聚类结果中的 前X个类作的核为直接指派的聚类方法的初始核，再应用直接指派的聚类方法进行计算； 步骤二：选址规划，给定配送中屯、数目为P，W最小化总成本为目标计算出最佳的选址 方案;具体为：
给定配送中屯、数目为P，求解每个配送中屯、最佳位置和服务对象的数学模型如下： 其中，ΣιΣ巧ijdij是由配送中屯、到配送点聚类的距离之和； ， 有且只有P个配送中屯、可供选揖
每个配送点聚类由且只能由一个配送中屯、配送：
，式中，是确定服务对象规划的决策变量，在配送 点聚类i由候选点j服务时，χυ = 1，否则χυ = 〇; 只有当候选点j被选作配送中屯、的时候，才能执行配送：
式中，yj是确定配送中屯、位置的决策变量，在候选点j被 选为配送中屯、时，yj = l，否则yj = 〇; 步骤Ξ:比较步骤二得出的不同配送中屯、数目的选址方案，综合管理成本来选择理想 选址方案； 步骤四：路径规划，根据每个聚类内部的配送点数量的需求、地理信息，计算每个配送 点的配送交接的时间需求和点与点间的交通时间需求； 步骤五:根据步骤四所得计算的时间需求，应用蚁群算法，计算得出最佳配送路径。
2. 如权利要求1所述的面向超大规模物流配送的选址与运输优化方法，其特征在于，所 述步骤一中利用自下而上的聚类方法获得初始聚类结果的具体步骤为： 在初始状态时，每个配送点为一个类； 在类的容量没有达到预设上限时，相邻的类相互聚合，直至没有类可W再聚合时终止。
3. 如权利要求1所述的面向超大规模物流配送的选址与运输优化方法，其特征在于，所 述步骤一中应用直接指派的聚类方法计算的具体步骤为： 在初始状态时，确定类的个数χ，χ为所需求的配送车辆的数目，并选择所得初始聚类结 果中的前X个类的几何中屯、为直接指派的方法的初始核； 在类的容量没有达到上限时，将每个零售点向最接近的类聚合后，更新类的核，直至所 有配送点都已聚合到相应的类时终止。

面向超大规模物流配送的选址与运输优化方法
技术领域
[0001 ]本发明涉及一种面向超大规模物流配送的选址与运输优化方法。
背景技术
[0002] 配送中心选址与运输路径优化（LRP，location and routing problem)，是指在 给定顾客位置和仓库可能位置的情况下，确定仓库的数量、位置和车辆的运输路线，使总成 本最小，同经典的设施选址问题和车辆路径问题密切相关。事实上，这两个问题可以视为配 送中心选址与运输路径优化问题的特殊情况。从实践的角度来看，配送中心选址与运输路 径优化是物流配送和分销管理面临的实际问题;然而从数学的角度来看，这通常可以被描 述为一个组合优化问题。这是一个NP难问题，因为它包含了两个NP困难问题：设施选址 (LAP, location assignment problem)和车辆路径（VRP，vehicle routing problem)。
[0003] LRP的概念最初由20世纪70年代提出。但到了 20世纪80年代后期，由于实际应用的 迫切需要，LRP的研究才得到了广泛重视。在算法研究上，基于LRP是LAP和VRP两个 NP问题的集合，求解上有很大的难度。目前主要应用的方法有，启发式算法、禁忌搜索算 法，遗传算法。其中，启发式算法简单实用、运用比较广泛;遗传算法因为其全局搜索能力 强，有效避免组合优化问题，并且在VRP问题求解上非常有效，因此可以结合启发式算法 和遗传算法来求解。
[0004] 21世纪以来，电子商务和物流配送相互促进、快速发展。物流配送的需求急剧增 长，配送问题的规模呈爆炸性增长。在传统中，上百个配送点的LRP问题已经属于大规模问 题。但在21世纪的今天，拥有上万个配送点，甚至数十万配送点的配送系统习空见惯。原有 的传统算法已经无法有效应对由于配送规模增长带来的巨大计算压力。因此，设计面向超 大规模物流配送的选址与运输综合优化的高效计算方法，是经济快速发展所带来的实际需 求，可以有效促进我国物流的高效、集约化发展。
[0005] 上述问题是在超大规模物流配送的选址与运输综合优化过程中应当予以考虑并 解决的问题。
发明内容
[0006] 本发明的目的是提供一种面向超大规模物流配送的选址与运输优化方法解决现 有技术中存在的拥有上万个配送点，甚至数十万配送点的配送系统时，原有的传统算法已 经无法有效应对由于配送规模增长带来的巨大计算压力的问题。
[0007] 本发明的技术解决方案是：
[0008] -种面向超大规模物流配送的选址与运输优化方法，包括以下步骤：
[0009] 步骤一:聚类，利用自下而上的聚类方法获得初始聚类结果，将所得初始聚类结果 中的前X个类作的核为直接指派的聚类方法的初始核，再应用直接指派的聚类方法进行计 算；
[0010] 步骤二:选址规划，给定配送中心数目为P，以最小化总成本为目标计算出最佳的 选址方案；
[0011] 步骤三：比较步骤二得出的不同配送中心数目的选址方案，综合管理成本来选择 理想选址方案；
[0012] 步骤四：路径规划，根据每个聚类内部的配送点数量的需求、地理信息，计算每个 配送点的配送交接的时间需求和点与点间的交通时间需求；
[0013] 步骤五:根据步骤四所得计算的时间需求，应用蚁群算法，计算得出最佳配送路 径。
[0014] 优选地，所述步骤一中利用自下而上的聚类方法获得初始聚类结果的具体步骤 为：
[0015] 在初始状态时，每个配送点为一个类；
[0016] 在类的容量没有达到预设上限时，相邻的类相互聚合，直至没有类可以再聚合时 终止。
[0017] 优选地，所述步骤一中应用直接指派的聚类方法计算的具体步骤为：
[0018] 在初始状态时，确定类的个数x，x为所需求的配送车辆的数目，并选择所得初始聚 类结果中的前X个类的几何中心为直接指派的方法的初始核；
[0019] 在类的容量没有达到上限时，将每个零售点向最接近的类聚合后，更新类的核，直 至所有配送点都已聚合到相应的类时终止。
[0020] 优选地，所述步骤二的具体步骤为：
[0021 ]给定配送中心数目为P，求解每个配送中心最佳位置和服务对象的数学模型如下：
其中
I由配送中心到配送点聚类的距离之和；
[0022] 有且只有p个配送中心可供选择
[0023]
[0024]
[0025] 每个配送点聚类由且只能由一个配送中心配送：
[0026]
，式中，S是确定服务对象规划的决策变量，在 配送点聚类i由候选点j服务时=1，否则％ ;
[0027] 只有当候选点j被选作配送中心的时候，才能执行配送：
[0028]
，式中，h是确定配送中心位置的决策变量，在候选点j 被选为配送中心时，A ^，否则A=〇。
[0029] 本发明一种面向超大规模物流配送的选址与运输优化方法，提供一种解决超大规 模物流配送的选址与运输综合优化问题的方法，提出基于空间聚类、整数规划等方法的快 速、高效的计算方法，提供优化计算的核心引擎库和调用接口，使其适用于现实需求。
[0030] 该种面向超大规模物流配送的选址与运输优化方法中，聚类是设计合适的聚类方 法是解决面向超大规模物流配送的选址与运输综合优化问题的核心所在，是选址规划和路 径规划可以开展的基础。聚类是空间数据挖掘中的一个重要的研究领域，它是指将物理的 或抽象的对象分组成为由类似对象组成的多个类的过程。在解决方案中，聚类算法主要可 以发挥两个重要作用:一、在做战略层面的在选址规划时，聚类结果可以充分反应战术层面 路径规划的影响;根据聚类的特性，以配送车辆的容量为类的容量上限，将地理上相近的零 售户聚成一个类，有助于未来路径规划时取得较短的配送距离。二、合理简化问题，方便规 划的求解。通过聚类，可以将拥有上万个配送点的配送问题的规模合理简化，方便求解。 [0031 ]该种面向超大规模物流配送的选址与运输优化方法中，采用自下而上的聚类方法 和基于指派的聚类算法相结合的方法。具体而言，首先利用自下而上的聚类方法获得初始 聚类结果，并将这一结果中的前X个类，X的值根据需求具体确定，作的核为直接指派的方法 的初始核，再应用直接指派的方法进行计算。
[0032] 利用自下而上的聚类方法获得初始聚类结果的算法步骤如下：
[0033] 初始步骤:初始状态:每个配送点都是一个类；
[0034] 中间步骤:如果类的容量还没有达到预设上限，如配送车量的容量上限，临近的类 相互聚合；
[0035]终止条件:没有类可以再聚合；
[0036] 应用直接指派的方法进行计算的步骤如下：
[0037] 初始状态:根据需求确定类的个数x，x的值通常为所需求的配送车辆的数目，并在 自下而上的聚类方法获得初始聚类结果中选定前X类的几何中心为每个类的初始核；
[0038] 中间步骤:如果类的容量还没有达到上限，将每个零售点向最接近的类聚合;更新 类的核；
[0039]终止条件:所有配送点都已聚合到相应的类。
[0040]该种面向超大规模物流配送的选址与运输优化方法中，上一步骤的聚类算法为选 址规划问题提供决策所需的数据输入。选址规划是要确定配送中心的数目、各个配送中心 的位置以及各个配送中心的所服务的配送点，使得配送的总成本最小。该种面向超大规模 物流配送的选址与运输优化方法中，为了有效解决同时确定三类不同决策变量所面临的困 难，提出了给定配送中心的数目求解最佳配送中心位置和服务对象的计算方法。然后通过 比较不同配送中心数目情况下的计算结果，选取最佳的解决方案。具体求解流程如下所示： 给定配送中心数目，以最小化总成本为目标，计算最佳的选址方案；比较不同配送中心数目 的选址方案，综合管理成本，选择理想选址方案。
[0048] 其中，A是确定配送中心位置的决策变量，如果候选点j被选为配送中心，则h=：!， 否则W是确定服务对象规划的决策变量，如果配送点聚类i由候选点j服务，则％ = 1，
[0041 ] 给定D个配送中心，求解每个配送中心最佳位置和服务对象的数学模型如下所示：
[0042]
[0043]
[0044]
[0045]
[0046]
[0047]
『公式是目标函数，其t
是由配送中心到配送点聚类的距离之
和；
：式则表明，有且只有P个配送中心可供选择。 式则 表明，只有当候选点j被选作配送中心的时候，才能执行配 公式表明，每个配送点聚类由且只能由一个配送中心配送。
[0050] 该种面向超大规模物流配送的选址与运输优化方法中，在已计算获得配送中心位 置的前提下，对每一个聚类结果内部的车辆行驶路径进行规划。以综合作业时间作为送货 线路划分、优化的主要标准，建立综合作业时间与送货量、送货户数和行驶里程等相关因素 之间关系模型，即送货线路标准模型，把多维，如送货数量、送货户数、送货里程等，标准转 换为单维，即综合作业时间的标准，统一送货工作量。有效解决当前行业对送货数量、送货 户数、送货里程做出多维弹性描述作为送货线路标准，难以与具体的线路划分实际操作相 匹配的问题。该种面向超大规模物流配送的选址与运输优化方法中路径规划分两步执行： 根据每个聚类内部的配送点数量的需求、地理信息，计算每个配送点的配送交接时间需求 和点和点之间的交通时间需求;根据计算的时间需求，应用蚁群算法，计算最佳配送路径。
[0051] 该种面向超大规模物流配送的选址与运输优化方法突破传统选址-路径规划技 术，引入和设计独特的空间聚类算法用于合理简化模型，具有较大创新意义。同时，该方法 实现简单，开销轻量，该方法的软件实现对硬件运算要求低，适用于计算设备。该方法部署 简单能够轻松的部署在云端，根据预先定义的借口标准，各个有需要的企业可以根据需要 自由调用计算。该方法架构清晰，应用灵活。该方法的分三个解决层次，各层次相互关联又 相互独立。用户可根据需要自由选择所需应用。如选址层次的需求由于属于战略决策，不需 经常应用，但路径决策可能在实际中经常调整，则企业可单独使用路径决策模块。并且在当 前架构中，每个层次的决策模块都可以置换成别的决策方法，而不影响其他决策模块的应 用。
[0052]本发明的有益效果是：本发明一种面向超大规模物流配送的选址与运输优化方 法，能够有效解决由于配送点大规模增长后带来的大计算量问题，如一个市有26000多个配 送点，应用本发明中的方案，可以节约经费1000万元，与现有选址-路径规划相比，计算开销 大幅降低、效率明显提高。该方法的软件实现对硬件运算要求低，适用于计算设备。该方法 部署简单能够轻松的部署在云端，根据预先定义的借口标准，各个有需要的企业可以根据 需要自由调用计算。该方法架构清晰，应用灵活。该方法的分三个解决层次，各层次相互关 联又相互独立。用户可根据需要自由选择所需应用。如选址层次的需求由于属于战略决策， 不需经常应用，但路径决策可能在实际中经常调整，则企业可单独使用路径决策模块。并且 在当前架构中，每个层次的决策模块都可以置换成别的决策方法，而不影响其他决策模块 的应用。
具体实施方式
[0053]下面详细说明本发明的优选实施例。
[0054]本实施例提供一种面向超大规模物流配送的选址与运输优化方法，包括以下步 骤：
[0055] 步骤一:聚类，利用自下而上的聚类方法获得初始聚类结果，将所得初始聚类结果 中的前X个类作的核为直接指派的聚类方法的初始核，再应用直接指派的聚类方法进行计 算；
[0056] 步骤二:选址规划，给定配送中心数目为p，以最小化总成本为目标计算出最佳的 选址方案；
[0057]步骤三：比较步骤二得出的不同配送中心数目的选址方案，综合管理成本来选择 理想选址方案；
[0058]步骤四：路径规划，根据每个聚类内部的配送点数量的需求、地理信息，计算每个 配送点的配送交接的时间需求和点与点间的交通时间需求；
[0059] 步骤五:根据步骤四所得计算的时间需求，应用蚁群算法，计算得出最佳配送路 径。
[0060] 优选地，所述步骤一中利用自下而上的聚类方法获得初始聚类结果的具体步骤 为：
[0061 ]在初始状态时，每个配送点为一个类；
[0062] 在类的容量没有达到预设上限时，相邻的类相互聚合，直至没有类可以再聚合时 终止。
[0063] 优选地，所述步骤一中应用直接指派的聚类方法计算的具体步骤为：
[0064] 在初始状态时，确定类的个数x，x为所需求的配送车辆的数目，并选择所得初始聚 类结果中的前X个类的几何中心为直接指派的方法的初始核；
[0065] 在类的容量没有达到上限时，将每个零售点向最接近的类聚合后，更新类的核，直 至所有配送点都已聚合到相应的类时终止。
[0066]优选地，所述步骤二的具体步骤为：
[0067] 给定配送中心数目为p，求解每个配送中心最佳位置和服务对象的数学模型如下：
，其中
是由配送中心到配送点聚类的距离之和；
[0068] 有且只有p个配送中心可供选S
[0069]
[0070]
[0071 ] 每个配送点聚类由且只能由一个配送中心配送：
[0072]
式中，S是确定服务对象规划的决策变量，在 配送点聚类i由候选点j服务时否则碜=«> ;
[0073] 只有当候选点j被选作配送中心的时候，才能执行配送：
[0074]
式中，A是确定配送中心位置的决策变量，在候选点j 被选为配送中心时：
[0075] 本实施例一种面向超大规模物流配送的选址与运输优化方法，提供一种解决超大 规模物流配送的选址与运输综合优化问题的方法，提出基于空间聚类、整数规划等方法的 快速、高效的计算方法，提供优化计算的核心引擎库和调用接口，使其适用于现实需求。
[0076] 该种面向超大规模物流配送的选址与运输优化方法中，聚类是设计合适的聚类方 法是解决面向超大规模物流配送的选址与运输综合优化问题的核心所在，是选址规划和路 径规划可以开展的基础。聚类是空间数据挖掘中的一个重要的研究领域，它是指将物理的 或抽象的对象分组成为由类似对象组成的多个类的过程。在解决方案中，聚类算法主要可 以发挥两个重要作用:一、在做战略层面的在选址规划时，聚类结果可以充分反应战术层面 路径规划的影响;根据聚类的特性，以配送车辆的容量为类的容量上限，将地理上相近的零 售户聚成一个类，有助于未来路径规划时取得较短的配送距离。二、合理简化问题，方便规 划的求解。通过聚类，可以将拥有上万个配送点的配送问题的规模合理简化，方便求解。
[0077] 该种面向超大规模物流配送的选址与运输优化方法中，采用自下而上的聚类方法 和基于指派的聚类算法相结合的方法。具体而言，首先利用自下而上的聚类方法获得初始 聚类结果，并将这一结果中的前X个类，X的值根据需求具体确定，作的核为直接指派的方法 的初始核，再应用直接指派的方法进行计算。
[0078] 利用自下而上的聚类方法获得初始聚类结果的算法步骤如下：
[0079] 初始步骤:初始状态:每个配送点都是一个类；
[0080] 中间步骤:如果类的容量还没有达到预设上限，如配送车量的容量上限，临近的类 相互聚合；
[0081 ]终止条件:没有类可以再聚合；
[0082]应用直接指派的方法进行计算的步骤如下：
[0083]初始状态:根据需求确定类的个数x，x的值通常为所需求的配送车辆的数目，并在 自下而上的聚类方法获得初始聚类结果中选定前X类的几何中心为每个类的初始核；
[0084]中间步骤:如果类的容量还没有达到上限，将每个零售点向最接近的类聚合;更新 类的核；
[0085]终止条件:所有配送点都已聚合到相应的类。
[0086] 该种面向超大规模物流配送的选址与运输优化方法中，上一步骤的聚类算法为选 址规划问题提供决策所需的数据输入。选址规划是要确定配送中心的数目、各个配送中心 的位置以及各个配送中心的所服务的配送点，使得配送的总成本最小。该种面向超大规模 物流配送的选址与运输优化方法中，为了有效解决同时确定三类不同决策变量所面临的困 难，提出了给定配送中心的数目求解最佳配送中心位置和服务对象的计算方法。然后通过 比较不同配送中心数目情况下的计算结果，选取最佳的解决方案。具体求解流程如下所示： 给定配送中心数目，以最小化总成本为目标，计算最佳的选址方案；比较不同配送中心数目 的选址方案，综合管理成本，选择理想选址方案。
[0087] 给定p个配送中心，求解每个配送中心最佳位置和服务对象的数学模型如下所示：
[0088]
[0089]
[0090]
[0091]
[0092]
[0093]
[0094] 其中，A是确定配送中心位置的决策变量，如果候选点j被选为配送中心，则J>=1，
否贝1 :服务对象规划的决策变量，如果配送点聚类i由候选点j服务，则％=1， 否贝I
[009 公式是目标函数，其M
I由配送中心到配送点聚类的距离之
禾
式则表明，有且只有P个配送中心可供选择<= J表 明，只有当候选点j被选作配送中心的时候，才能执行面 公式表明，每个配送点聚类由且只能由一个配送中心配送。
[0096] 该种面向超大规模物流配送的选址与运输优化方法中，在已计算获得配送中心位 置的前提下，对每一个聚类结果内部的车辆行驶路径进行规划。以综合作业时间作为送货 线路划分、优化的主要标准，建立综合作业时间与送货量、送货户数和行驶里程等相关因素 之间关系模型，即送货线路标准模型，把多维，如送货数量、送货户数、送货里程等，标准转 换为单维，即综合作业时间的标准，统一送货工作量。有效解决当前行业对送货数量、送货 户数、送货里程做出多维弹性描述作为送货线路标准，难以与具体的线路划分实际操作相 匹配的问题。该种面向超大规模物流配送的选址与运输优化方法中路径规划分两步执行： 根据每个聚类内部的配送点数量的需求、地理信息，计算每个配送点的配送交接时间需求 和点和点之间的交通时间需求;根据计算的时间需求，应用蚁群算法，计算最佳配送路径。
[0097] 该种面向超大规模物流配送的选址与运输优化方法突破传统选址-路径规划技 术，引入和设计独特的空间聚类算法用于合理简化模型，具有较大创新意义。同时，该方法 实现简单，开销轻量，该方法的软件实现对硬件运算要求低，适用于计算设备。该方法部署 简单能够轻松的部署在云端，根据预先定义的借口标准，各个有需要的企业可以根据需要 自由调用计算。该方法架构清晰，应用灵活。该方法的分三个解决层次，各层次相互关联又 相互独立。用户可根据需要自由选择所需应用。如选址层次的需求由于属于战略决策，不需 经常应用，但路径决策可能在实际中经常调整，则企业可单独使用路径决策模块。并且在当 前架构中，每个层次的决策模块都可以置换成别的决策方法，而不影响其他决策模块的应 用。
[0098] 本实施例的有益效果是:本实施例一种面向超大规模物流配送的选址与运输优化 方法，能够有效解决由于配送点大规模增长后带来的大计算量问题，如一个市有26000多个 配送点，应用本发明中的方案，可以节约经费1000万元，与现有选址-路径规划相比，计算开 销大幅降低、效率明显提高。该方法的软件实现对硬件运算要求低，适用于计算设备。该方 法部署简单能够轻松的部署在云端，根据预先定义的借口标准，各个有需要的企业可以根 据需要自由调用计算。该方法架构清晰，应用灵活。该方法的分三个解决层次，各层次相互 关联又相互独立。用户可根据需要自由选择所需应用。如选址层次的需求由于属于战略决 策，不需经常应用，但路径决策可能在实际中经常调整，则企业可单独使用路径决策模块。 并且在当前架构中，每个层次的决策模块都可以置换成别的决策方法，而不影响其他决策 模块的应用。