基于订单位置聚类的雏鸡配送车辆调度优化模型

为解决大型禽业企业物流订单位置跨度大、配送车辆调度工作人工参与度高、雏鸡配送成本高的问题，本研究结合车辆路径优化问题求解思路，提出了基于订单位置聚类的雏鸡配送车辆调度优化模型。模型通过引入K-means聚类算法，实现了基于订单位置的配送单元划分方法，并基于肘部法则与轮廓系数法设计了自动化订单位置聚类流程，实现了订单配送单元的自主式划分。在划分的各组订单基础上，以配送成本最优作为目标函数，建立雏鸡配送车辆调度优化模型，并结合改进的遗传算法进行求解。研究采用北京某禽业企业实际订单数据，对订单未聚类情况下的整体调度优化与聚类分组情况下的调度优化两种情况的结果进行了对比分析，结果表明订单聚类分组情况下，优化模型使配送车辆平均每天总里程比订单未聚类情况降低69.84%，可以得出，加入聚类算法的订单分组优化更适合实际订单位置跨度大、订单数量多的车辆调度场景。基于以上研究，研发设计了适用于雏鸡配送的车辆调度优化服务系统，实现了订单自动化聚类、配送车辆调度优化、定制化模型服务等功能，通过模型的实际应用，达到了为禽业企业提供智能化配送车辆调度优化服务的目的，切实提高了企业运行效率，降低了企业配送成本。

关键词： 雏鸡配送 ; 车辆调度优化模型 ; K-means聚类算法 ; 遗传算法 ; 智慧畜禽 ; 定制化模型服务

Abstract

In order to solve the problems that orders are widely distributed, scheduling of distribution vehicle needs a lot of manpower,and high cost of chicken distribution in large-scale poultry enterprise, in this research, combined with the idea of solving vehicle routing optimization problem, a chicken distribution vehicle scheduling optimization model based on order location clustering was proposed. By introducing the K-means clustering algorithm, a distribution unit division method based on order location was implemented, an automated order location clustering process based on the elbow rule and contour coefficient method to realize the autonomous division of order distribution units was designed. On the basis of the divided groups of orders, the optimal delivery cost was taken as the objective function to establish a chicken delivery vehicle scheduling optimization model, and the model was solved with an improved genetic algorithm.The actual order data of a poultry company in Beijing was used to compare the results of the overall scheduling optimization in the case of orders without clustering and the scheduling optimization in the case of with clustering grouping. The results showed that the model in the case of orders with clustering could reduce the average daily mileage of delivery vehicles by 69% compared with orders without clustering, it could be seen that the optimization of order grouping with clustering algorithm was more suitable for vehicle scheduling scenarios with a large actual order position span and a large number of orders. Based on the above research, a vehicle scheduling optimization service system was developed, functions such as automatic order clustering, delivery vehicle scheduling optimization were realized, and model service application programming interface was customized.The practical application results of the model showed that, the average total mileage per day decreased by 5.04% compared with manual routing, the manual routing time took 20 to 30 minutes per day, and the average time for the model to complete the routing was 14.49 s. The goal of providing intelligent delivery vehicle scheduling optimization services for poultry industry enterprises has been achieved, which could effectively improve the operation efficiency and reduce the distribution cost of the poultry enterprise.

Keywords： chicken delivery ; vehicle scheduling optimization model ; K-means clustering algorithm ; genetic algorithm ; smart poultry ; API

PDF (2529KB) 元数据多维度评价相关文章导出 EndNote| Ris| Bibtex 收藏本文

本文引用格式

陈栋, 陈天恩, 姜舒文, 张驰, 王聪, 鲁梦瑶. 基于订单位置聚类的雏鸡配送车辆调度优化模型[J]. 智慧农业（中英文）, 2020, 2(4): 137-148. doi:10.12133/j.smartag.2020.2.4.202011-SA006

CHEN Dong, CHEN Tian'en, JIANG Shuwen, ZHANG Chi, WANG Cong, LU Mengyao. Optimal Model of Chicken Distribution Vehicle Scheduling Based on Order Clustering[J]. Smart Agriculture, 2020, 2(4): 137-148. doi:10.12133/j.smartag.2020.2.4.202011-SA006

1 引言

随着经济发展和消费升级，人们对畜禽肉类和蛋类产品的需求日益增加，大型畜禽业企业的订单量逐年上升，但同时也普遍面临着物流配送成本居高不下的问题。目前，中国禽业企业仍主要依靠经验进行物流配送排线作业，每天耗费大量时间与人力，还无法确保物流配送时效、成本和客户满意度实现最优化。随着信息技术与智慧物流^［1］的不断发展，传统养殖业正向现代养殖业转变，在此背景下，结合车辆路径问题（Vehicle Routing Problem，VRP）^{［ 2］}的求解思路，基于机器学习与启发式算法，研究配送车辆智能调度优化算法，对提高禽业企业物流效率和降低物流成本具有实际意义。

VRP作为网络优化中最基本的问题之一，近几十年来一直受到国内外学者的广泛关注，该问题的多种延伸和变化形态为特定需求物流系统的成本和效率优化提供了重要途径，其主要采用启发式算法^{［ 3］}、混合算法^{［ 4］}、元启发式算法^{［ 5］}、模拟退火算法^{［ 6］}、禁忌搜索算法^{［ 7］}、蜂群算法^{［ 8］}等现代智能优化算法，根据不同约束条件针对配送过程中时间成本、人力成本、配送成本等进行全局优化。结合物流领域实际特点，当前的研究方向主要分为两类，一类是基于实际需求加入不同优化因子的研究，通过考虑时间和价格成本、客户时间窗等因子的影响以求更贴近实际场景的应用^{［ 9, 10］}。Vahdani等^{［ 11］}采用启发式和元启发式算法对易腐品车辆路径调度进行了研究，同时考虑了不同容量车辆的配送路径和客户时间窗的问题，实现了易腐品配送场景下按订单时间的车辆配送路径优化算法。Ullrich和Christian^{［ 12］}研究了带有时间窗的车辆调度和车辆路径问题，应用遗传算法优化VRP集成模型，实现了一种具有通用性的时间窗车辆优化模型。侯宇超等^{［ 13］}考虑物流配送中客户满意度、成本、大气污染物和温室气体排放量四个因素，结合精英蚁群算法建立了多目标配送路径优化模型，实现了考虑环境因素的配送路径优化模型。另一类是基于不同智能优化算法的研究，通过改进和比对不同算法在实际因子下的表现选择合适求解方案^{［ 14- 16］}。例如，盛强等^{［ 17］}以物流成本最小和时间窗为优化目标，使用改进的遗传算法，提出了一种基于时变路网的有时间窗车辆路径问题（Vehicle Routing Problems with Time Windows，VRPTW）模型。Fu等^{［ 18］}依据惩罚函数的不同，设计出禁忌搜索算法来求解各种软时间窗车辆路径问题。Kok等^{［ 19］}针对具有时间窗的路径优化问题，采用禁忌搜索算法解决时相关路径问题。Wang等^{［ 20］}提出了一种基于扩展粒子群优化和遗传算法（Expanded Particle Swarm Optimization-Genetic Algorithm，EPSO-GA）的混合算法，建立了两级物流配送网络总成本最小化模型。近年来，多目标优化算法在农机调度领域被广泛应用^{［ 21- 23］}，为本研究提供了借鉴思路。

综上，已有物流配送车辆路径规划研究多以城市配送为主要背景，其以不同优化因子作为目标函数，通过对配送车辆路径的规划得到满意解，研究中订单位置跨度较小，无需考虑订单分群问题，而对于订单空间位置跨度大的物流配送场景，则需要考虑订单分群优化的问题。本研究基于禽业企业物流配送需求，选取雏鸡配送作为代表，针对实际订单空间位置跨度大的特点，研究基于订单位置聚类的雏鸡配送车辆调度优化模型，在分析配送位置的基础上，研究位置约束条件下的配送订单聚类算法，通过引入聚类结果自主评价机制，实现配送任务单元自主划分方法；基于配送任务单元，依据成本优化目标函数，以配送成本最优为目标，并结合改进的遗传算法进行求解；最终结合实际雏鸡配送场景进行模型验证评价，并基于以上研究研发设计了适用于雏鸡配送的车辆调度优化服务系统，实现了订单自动化聚类、配送车辆调度优化、定制化模型服务等功能，实现了模型的应用。

2 问题描述与模型构建

2.1　问题描述

雏鸡配送车辆调度优化问题描述如下：北京某禽业企业的雏鸡配送中心需要完成对订单客户群的配送任务，订单覆盖中国北方地区，位置跨度较大。要求根据每天的订单信息，合理安排配送车辆与配送客户顺序，确保配送路线最短。基于企业配送中心实际运行状况，做如下说明：①企业有一个配送中心，每辆车从配送中心出发，完成配送任务后返回配送中心；②每辆配送车辆载重有限，配送订单雏鸡总量不能超过参与配送的所有车辆载重；③实际配送中是跨省配送，属于干线物流，受实时交通影响较小，因此选择使用欧式距离；④允许单个订单进行拆分，并可分配至多辆配送车；⑤单次配送中每个客户的位置和需求量一定，且不考虑客户优先级。

2.2　模型构建

基于问题描述，首先对雏鸡配送车辆调度优化模型（文中简称“模型”）中涉及的参数进行说明，进而确定模型的约束条件与目标函数，构建模型。

（1）参数说明。模型中涉及的参数说明如表1所示。

表1 雏鸡配送车辆调度优化模型参数说明表

Table 1 Parameter specification table of the optimization model of the chicken distribution vehicle scheduling

参数	定义
$K$	表示参与配送的车辆总数量， $K \in \{1,2, \dots, K\}$
$C H_{k}$	表示第 $k$ 辆车最大可载的雏鸡数量，只
$c h_{k}$	表示第 $k$ 辆车实际装载的雏鸡数量，只
$N$	表示客户总数量，个
$c h_{i}$	表示第 $i$ 个客户订单的雏鸡需求数量，只， $0 < i \leq N$
$n_{k}$	表示第 $k$ 辆车配送的客户数量，个
$D_{i j}$	表示客户 $i$ 到客户 $j$ 之间的距离，km
$D_{0 i}$	表示配送中心到客户 $i$ 的距离，km
$R_{k}$	表示第 $k$ 辆车的路径集合， $R_{k} = \{r_{k_{i}} \| r_{k_{i}} \in \{1,2, \dots, N\}, i = 1,2, \dots, n_{k}\}$
$r_{k_{i}}$	表示客户 $i$ 在第 $k$ 辆车的路径集合中的顺序

新窗口打开| 下载CSV

（2）模型构建。构建模型目标是实现降低雏鸡配送成本，在雏鸡配送过程中，影响配送成本的因素包括固定成本、运输成本与雏鸡损耗成本。其中，固定成本包括车辆成本与人力成本。车辆的满载率可以影响固定成本，满载率越高越能有效减少配送车辆数量与驾驶员的数量，进而降低固定成本；运输成本包括燃油费与路桥费等，车辆的运行里程可直接反应运输成本；雏鸡损耗成本一般在实际运输中损耗在1%左右，雏鸡损耗可视为一个常数。

经过分析，运输成本在配送成本中所占比例最大，因此，本研究使用车辆运行里程作为模型目标函数的主要组成部分，还包括雏鸡运输损耗常数。另一方面，人工调度时的车辆满载率在80%左右，可引入车辆满载率作为惩罚函数，当整体调度安排的车辆满载率低于80%时进行惩罚。基于此得出模型目标函数表达式如下。

Z = m i n (\sum_{k = 1}^{K} [a_{k} \times [\sum_{i = 1}^{n_{k}} D_{r_{k_{(i - 1)}} r_{k_{i}}} + D_{r_{n_{k}} r_{k_{0}}}] \times s i g n n_{k}] + F_{1} + b \times F_{2})

（1）

其中， $a_{k}$ 代表不同类型车辆的平均每千米运输费用，包括油耗、路桥费与损耗费，本研究中一种类别车型为一个常数，元； $D_{r_{k_{(i - 1)}} r_{k_{i}}}$ 代表第 $k$ 辆车从顺序为 $r_{k_{(i - 1)}}$ 的客户到顺序为 $r_{k_{i}}$ 之间的距离，km； $D_{r_{n_{k}} r_{k_{0}}}$ 代表第 $k$ 辆车中顺序为最后的客户到配送中心之间的距离，km； $s i g n n_{k}$ 为控制参数，具体表示如公式（2）所示。

s i g n (n_{k}) = \{\begin{matrix} 1 n_{k} \geq 1 \\ 0 其 他 \end{matrix}

（2）

$F_{1}$ 为损耗成本函数，0.01表示损耗成本在1%左右，就是每辆车的运输过程中会导致车辆上1%的雏鸡不能存活，具体如公式（3）所示。

F_{1} = \sum_{k = 1}^{K} 0.01 \times c h_{k}

（3）

$b \times F_{2}$ 为惩罚成本，b为惩罚常数变量， $F_{2}$ 为惩罚函数，当整体调度安排的车辆满载率低于80%时进行惩罚。具体如公式（4）所示。

F_{2} = \{\begin{matrix} 1 \sum_{k = 1}^{K} \frac{c h_{k}}{C H_{k}} < 0.8 \\ 0 \sum_{k = 1}^{K} \frac{c h_{k}}{C H_{k}} \geq 0.8 \end{matrix}

（4）

根据问题的描述，确定约束条件如下。

（1） $\sum_{i = 1}^{n_{k}} c h_{i} \leq C H_{k}$

（2） $0 \leq n_{k} \leq N$

（3） $\sum_{k = 1}^{K} n_{k} = N$

（4） $R_{k_{1}} ⋂ R_{k_{2}} = ϕ, \forall k_{1} \neq k_{2}$

其中，约束条件（1）中ch_i为表示第 $i$ 个客户订单的雏鸡需求数量，约束条件（1）代表约束每辆车装载的客户订单雏鸡需求量之和不超过配送车辆的最大雏鸡载装量，只；约束条件（2）中n_k代表约束每辆车上的客户订单数不超过总客户数；约束条件（3）代表每个客户都得到配送服务；约束条件（4）中R_k1和R_k2表示第 $k$ 辆车的配送的路径集合元素，代表约束每个客户仅能有一台配送车辆送货。

3 求解流程与算法设计

3.1　求解流程

针对雏鸡配送订单中客户位置跨度大的特点，本研究采用先对订单按位置进行聚类分群，然后对各子群的配送路线优化的求解思路；这样可实现订单的分组，有效避免同一辆车运输跨度过大。具体求解流程如图1所示。

图1

新窗口打开| 下载原图ZIP| 生成PPT

图1 雏鸡配送车辆调度优化问题求解流程

Fig. 1 Solution flow of chicken distribution vehicle scheduling optimization problem

①对客户订单数据进行预处理，提取出订单中订单编号、地址（经纬度）与雏鸡需求量等信息。

②根据订单的地址（经纬度）信息，采用基于位置的K-means聚类方法，对订单进行聚类分组，这样可以将订单按其地理位置分成多个订单簇。

③将每个订单簇中的订单信息与车辆信息作为调度优化算法的输入，调度优化算法基于遗传算法实现，对每个订单簇中的订单按照优化目标函数，匹配相应的配送车辆，经过算法的复制—交叉—变异等迭代操作，最终选择表现最好的个体输出。

④将对每个订单簇优化的结果进行合并，作为整体调度结果输出。

由以上流程可得，整个问题求解过程中最为关键的两个部分分别是订单聚类与车辆调度优化。

3.2　基于聚类算法的订单配送单元划分

关于雏鸡订单配送单元的划分，一方面是由于雏鸡物流配送场景中，不同于城市内部配送任务，其订单空间位置跨度大，因此需要将订单按照地域进行分组；另一方面，在实际场景中往往通过省域进行划分，这种划分方法能够按照省界将配送区域划分为不同的单元，但不同省份内的订单数量不同，而且在相同省份内不同订单间的距离往往会比相邻省份的订单距离要长。因此，研究利用聚类方法实现订单配送单元的自主划分是解决雏鸡配送车辆调度优化问题的前提。

K-means聚类算法是一种非层次聚类算法，在最小误差的基础上将数据划分了特定的类，类间利用距离作为相似度指标，两个向量之间的距离越小，其相似度就越高。聚类开始前，聚类数K的值是未知的，本研究引入肘部法与轮廓系数法实现了K值的确定。结合雏鸡订单位置数据，实现的聚类流程具体如图2所示。

图2

新窗口打开| 下载原图ZIP| 生成PPT

图2 雏鸡订单基于位置的K-means聚类流程

Fig. 2 Location-based K-means clustering process for chicken orders

结合北京某禽业有限公司（以下简称：禽业公司）雏鸡订单数据，对K均值聚类算法进行分析验证，数据来自2018年9月1日—30日连续30天的订单（共计802条），面向中国北方地区。试验订单数据散点分布如图3所示。

图3

新窗口打开| 下载原图ZIP| 生成PPT

图3 试验订单数据散点分布

Fig. 3 Splashes distribution of experimental order data

基于以上数据，采用肘部法则确定K值范围，如图4所示。取不同K值的平均畸变程度曲线，曲线曲率最高的K值范围在4~7之间。

图4

新窗口打开| 下载原图ZIP| 生成PPT

图4 K-means聚类肘部法则平均畸变曲线

Fig.4 Average distortion curve of K-means based on elbow rule

使用轮廓系数法对K的取值进行验证，图5为K分别取4、5、6、7时的聚类效果与轮廓系数。显然，当K取4时，轮廓系数最大，聚类效果满足订单的实际地理区划分布。由此说明使用肘部法则与轮廓系数法则可以确定K的合理取值，本研究基于此确定了程序自动确定的聚类簇数K值的步骤如下。

图5

新窗口打开| 下载原图ZIP| 生成PPT

图5 K取不同值对应的聚类效果图

Fig. 5 Clustering effect with different K values

①提取订单中的订单编号与对应的经纬度数据。

②用肘部法则生产畸变曲线，并根据曲线曲率确定K的取值范围。

③求解K在不同取值时的聚类轮廓系数，取轮廓系数最大的作为K的具体取值。

④对订单进行聚类，聚类数为K，按聚类结果进行订单配送区域划分依据，并将各个划分的订单子类作为路径优化算法的输入。

3.3　配送路径优化算法设计

本研究采用改进的遗传算法对雏鸡配送路径优化问题进行求解，以下是算法详细设计。

（1）改进的遗传算法流程。按照遗传算法一般的求解流程，结合实际雏鸡订单配送路径优化问题，确定问题求解的具体流程如下。

①算法参数与数据初始化，对种群规模PopulationSize、交叉概率Pc、变异概率Pm、进化代数GenerationNum，以及惩罚函数Pw等参数进行初始化设置，提取雏鸡订单中的订单编号、订单经纬度、订单的雏鸡需求量等数据。

②初始化种群，对种群个体进行编码，生成对应规模的种群矩阵。

③计算种群中每个个体的目标函数值，根据目标函数值确定每个个体的适应度，选取适应度最优的个体保留。

④对种群中的个体进行交叉、变异操作，生成新的种群。

⑤重复③—④步，直到满足进化代数。

⑥将适应度最优（适应度值最小）的个体作为最优解输出。

（2）算法中个体与种群编码。使用遗传算法进行求解的首要问题是确定种群的编码方式，本研究将订单客户进行顺序编号，订单客户总数为 $N$ ，订单客户的编号 $i \in [1,2, \dots, N]$ ，将配送订单客户顺序作为种群中的一个个体。如图6所示，将订单客户进行编号后，随机排序产生种群个体，一个种群个体代表一种配送方案，从左至右代表配送顺序，排在左侧的客户编号优先配送。共生成M个个体，M为种群规模。将生成的M个个体转换成种群矩阵，最终完成种群编码。

图6

新窗口打开| 下载原图ZIP| 生成PPT

图6 个体与种群编码示意图

Fig.6 Coding diagram of individual and population

（3）适应度函数。遗传算法中以个体适应度的大小来评定各个个体的优劣程度，从而决定其遗传机会的大小。本研究中 $F (x_{i})$ 为适应度， $i \in [1,2, 3, \dots, m]$ ； $m$ 代表种群规模，如公式（5）所示，即对目标函数去倒数，实现最大值与最小值间的转换。

F (x_{i}) = \frac{1}{m i n Z}

（5）

（4）选择操作。是确定如何选择父代种群中的优秀个体遗传到下一代群体。选择操作时遗传算法中的常规步骤，在本研究中，首先选择父代种群中目标函数最小的个体，即个体适应度最大的保留遗传至下一代；然后其他个体选择则采用轮盘赌法确定遗传的个体，轮盘赌法具体流程如下。

①在父代种群中，计算每个个体的适应度值 $F (x_{i})$ 。

②计算父代种群中每一个体被遗传到下一代群体中的概率： $P (x_{i}) = \frac{F (x_{i})}{\sum_{i = 1}^{m} F (x_{i})}$ 。

③基于步骤②中计算的概率，进行轮盘赌操作，选出遗传个体。

（5）交叉操作。是对两个相互配对的染色体按某种方式相互交换其部分基因，从而形成两个新的个体。通过交叉，遗传算法的搜索能力可以飞跃提高。如图7所示，本研究中采用位置连续交叉方法（Order Crossover），首先在种群中随机选择一对交叉个体，然后随机产生两个交叉点，将交叉点之间的基因片段作为交叉段。分别将两个个体相互交换交叉段，然后将本个体中的非交叉段编号按顺序插入空白基因位，交叉操作完成后，生产两个新的个体。通过交叉操作，提高了雏鸡配送排线路径方案的个体的丰富度，增加种群个体的多样性，提高了算法的搜索能力。

图7

新窗口打开| 下载原图ZIP| 生成PPT

图7 位置连续交叉操作示意图

Fig.7 Flow chart of order crossing operation

（6）变异操作。这是将个体编码串中的某些基因位置上的基因值用该基因位置上的其它等位基因来替换，从而形成新的个体。遗传算法引入变异的目的有两个：一是使遗传算法具有局部的随机搜索能力。当遗传算法通过交叉算子已接近最优解邻域时，利用变异算子的这种局部随机搜索能力可以加速向最优解收敛。如图8所示，每次进行变异操作时，随机在种群中选择需变异的个体，随机确定两对交换基因位置，对基因位上的基因进行互换后生成新的个体。通过变异操作，维持了雏鸡配送排线路径方案的个体的多样性，提高了每种配送路径方案的局部优化能力。

图8

新窗口打开| 下载原图ZIP| 生成PPT

图8 个体变异操作示意图

Fig. 8 Schematic diagram of individual variation operation

4 算例验证与分析

4.1　数据与参数初始化

北京某禽业有限公司拥有雏鸡配送中心一个，载货量3万只的车辆20辆，公司每天订单量在26单左右。本研究使用公司2018年9月1日—30日连续30天的订单数据（共计802条）对算法进行比对分析，雏鸡订单分布在北京、天津、河北、甘肃、山西、辽宁、吉林、黑龙江等省区，订单位置跨度大，运输里程较长。对遗传算法参数进行设置，种群数量为100个，交叉概率为0.5，变异概率为0.05，迭代次数为1000次。经对遗传算法的测试可以发现，其平均适应度收敛程度在迭代300次后算法曲线基本趋于平缓，代表模型的目标值趋于最优，如图9所示。

图9

新窗口打开| 下载原图ZIP| 生成PPT

图9 遗传算法平均适应度收敛程度曲线

Fig. 9 Convergence curve of average fitness of genetic algorithm

4.2　结果比较与分析

基于订单数据和参数设置，分别对比以下两种情况的优化效果：①订单不聚类情况下直接进行调度优化；②订单在聚类之后再分组进行调度优化，之后再合并结果。如表2所示，对样本数据中每天的订单进行未聚类优化和聚类优化，对比两种方法优化后的配送总里程。在经过订单聚类后，配送运行总里程大幅度降低，效果明显。通过实际数据进行验证对比可以得出，订单在聚类之后再分组进行调度优化比不聚类的整体优化的配送总里程降低69.84%。由于订单位置跨度大，运输总里程长，经过聚类分组后再进行小范围内的智能优化，能够避免整体优化时出现的车辆大跨度转移，从而降低了运输里程，算法对比结果符合实际预想，具有合理性。

表2 订单未进行聚类和进行聚类的两种配送排线模型的对比结果

Table 2 Comparison results of distribution vehicle scheduling optimal model without order clustering algorithm and with order clustering algorithm

编号	订单数	配送总里程/km		里程下降/%
编号	订单数	未聚类的调度优化	聚类后调度优化	里程下降/%
均值	26.77	40,012.71	12,065.25	69.84
1	25	14,357.24	7870.43	45.18
2	25	89,620.55	17,991.63	79.92
3	25	46,060.12	12,292.41	73.31
4	25	49,528.33	13,103.08	73.54
5	25	31,910.77	11,412.31	64.24
6	25	46,543.57	22,146.43	52.43
7	25	30,845.42	14,960.61	51.50
8	25	40,745.56	15,121.34	62.89
9	25	31,560.11	10,443.16	66.91
10	29	31,550.06	10,939.32	65.33
11	28	40,582.79	9983.61	75.40
12	27	34,148.18	14,052.96	58.85
13	29	23,263.46	12,326.16	47.01
14	28	18,005.59	11,056.26	38.60
15	26	22,420.93	9851.59	56.06
16	27	9582.22	7073.87	26.18
17	37	119,803.46	22,140.61	81.52
18	33	71,705.96	13,236.93	81.54
19	30	46,370.98	13,648.17	70.57
20	30	8211.26	7924.14	3.50
21	30	22,935.24	8244.37	64.05
22	30	12,505.73	9889.75	20.92
23	25	23,823.09	9720.49	59.20
24	28	76,706.99	16,339.00	78.70
25	20	9579.36	6732.31	29.72
26	24	44,905.16	9973.75	77.79
27	20	16,569.03	6969.47	57.94
28	29	117,780.64	17,364.96	85.26
29	23	19,002.08	7417.75	60.96
30	25	49,757.51	11,730.75	76.42

新窗口打开| 下载CSV

5 模型应用

基于以上研究，课题组研发了适用于雏鸡配送的车辆调度优化服务原型系统，实现了订单自动化聚类、配送车辆调度优化API等功能。系统采用B/S架构，系统的核心功能是通过API的方式为雏鸡企业提供配送车辆调度优化服务，其输入是来自全国各地的雏鸡需求订单，经过订单聚类分群调度优化后，聚类过程采用本文2.2节中所述的方法，自动分群后则使用本文3.3节所述的遗传算法进行优化，最终将每辆车对应的订单配送顺序作为输出，其核心流程如图10所示。

图10

新窗口打开| 下载原图ZIP| 生成PPT

图10 订单排线优化服务流程

Fig.10 Optimizing service progress of order routing

原型系统还提供了算法调用说明页面，并已经在禽业公司进行了试运行，效果良好。系统实际运行界面图11为算法调用接口说明，图12为算法调用接口日志。

图11

新窗口打开| 下载原图ZIP| 生成PPT

图11 算法调用接口说明

Fig.11 Call interface description of the algorithm

图12

新窗口打开| 下载原图ZIP| 生成PPT

图12 算法调用接口日志

Fig. 12 Call interface log of the algorithm

本研究连续收集了23天系统试运行的结果，并同时采用人工排线进行对照。在实际应用中，使用系统排线的排线总里程平均为2232.91 km，平均每次耗时为14.49 s；人工排线的总里程平均为2120.30 km，每次平均耗时20~30 min。

6 结论

本研究针对雏鸡配送场景中订单位置范围跨度大，订单数量多等特点；引入了基于订单位置聚类算法，实现了订单自主分群方法；并基于改进的遗传算法，实现了订单配送调度优化；提出基于订单位置聚类的雏鸡配送车辆调度优化模型。通过实际数据进行验证对比可以得出，订单在聚类之后再分组进行调度优化比不聚类的整体优化的配送总里程降低69.84%，能够避免订单位置跨度大情况下整体优化时出现的车辆大跨度转移问题。

基于订单位置聚类算法与车辆调度优化算法，本研究设计研发了用于雏鸡配送的车辆调度优化服务原型系统，系统实现了订单自动化聚类、配送车辆调度优化等功能。通过试运行，与人工排线对比后，使用本研究的优化模型，平均每天总里程下降了5.04%；排线时间人工每次耗费20~30 min，算法完成排线的时间平均耗费14.49 s；达到了为禽业企业提供了智能化配送车辆调度优化服务的目的，切实提高了企业运行效率，降低了企业配送成本。

参考文献

原文顺序

文献年度倒序

文中引用次数倒序

被引期刊影响因子

[1]

焦凯琳, 于自强.

智慧物流分布式计算模型与创新服务研究

[J]. 计算机技术与发展, 2019, 29(1): 206-210.

[本文引用: 1]

JIAO

, YU

Research on distributed computing model and innovative services about intelligent logistics

[J]. Computer Technology and Development, 2019, 29(1): 206-210.

[本文引用: 1]

The truck dispatching problem

[J]. Management Science, 1959, 6: 80-91.

[本文引用: 1]

[3]

EL-SHERBENY

N A

Vehicle routing with time windows: An overview of exact, heuristic and metaheuristic methods

[J]. Journal of King Saud University-Science, 2010, 22(3): 123-131.

[本文引用: 1]

A hybrid algorithm for a vehicle routing problem with realistic constraints

[J]. Information Sciences, 2017: 167-182.

[本文引用: 1]

Solving the multidepot vehicle routing problem with limited depot capacity and stochastic demands

[J]. International Transactions in Operational Research, 2019, 26(2): 458-484.

[本文引用: 1]

Vehicle routing problems with multiple trips

[J]. 4OR-A Quarterly Journal of Operations Research. 2018, 271(1): 127-159.

[本文引用: 1]

[7]

XIA

, FU

An adaptive tabu search algorithm for the open vehicle routing problem with split deliveries by order

[J]. Wireless Personal Communications, 2018, 103(1): 595-609.

[本文引用: 1]

[8]

ZHANG

, XIONG

Routing optimization of emergency grain distribution vehicles using the immune ant colony optimization algorithm

[J]. Applied Soft Computing, 2018, 71: 917-925.

[本文引用: 1]

[9]

邵举平, 曹倩, 沈敏燕, 等.

生鲜农产品配送中带时窗的VRP模型与算法

[J]. 工业工程与管理, 2015, 20(1): 122-127, 134.

[本文引用: 1]

Research on multi-objective optimization for fresh agricultural products VRP problem

[J]. Industrial Engineering and Management, 2015, 20(1): 122-127, 134.

[本文引用: 1]

[10]

张源凯, 黄敏芳, 胡祥培.

网上超市订单分配与物流配送联合优化方法

[J]. 系统工程学报, 2015(2): 251-258.

[本文引用: 1]

ZHANG

, HUANG

, HU

Integrated optimization approach to order allocation and delivery problem of online supermarket

[J]. Journal of Systems Engineering. 2015(2): 251-258.

[本文引用: 1]

Production-inventory-routing coordination with capacity and time window constraints for perishable products: Heuristic and meta-heuristic algorithms

[J]. Journal of Cleaner Production, 2017, 161(10): 598-618.

[本文引用: 1]

Integrated machine scheduling and vehicle routing with time windows

[J]. European Journal of Operational Research, 2013, 227(1): 152-165.

[本文引用: 1]

[13]

侯宇超, 白艳萍, 胡红萍, 等.

基于精英蚁群算法的多目标生鲜配送路径优化研究

[J]. 数学的实践与认识, 2018, 48(20): 50-57.

[本文引用: 1]

Study of multi-objective fresh food distribution route optimization based on elite ant colony algorithm

[J]. Mathematics in Practice and Theory, 2018, 48(20): 50-57.

[本文引用: 1]

[14]

汪涛, 潘郁, 潘芳, 等.

基于改进人工蜂群算法的生鲜农产品配送路径优化

[J]. 广东农业科学, 2018, 45(10): 143-149.

[本文引用: 1]

WANG

, PAN

, et al.

Fresh agricultural product distribution path optimization based on improved artificial bee colony algorithm

[J]. Guangdong Agricultural Sciences, 2018, 45(10): 143-149.

[本文引用: 1]

[15]

侯文英, 秦驰越.

基于蚁群算法鲜活农产品配送路径优化研究

[J]. 安徽农业科学, 2009, 37(1): 109-110, 118.

HOU

, QIN

On the optimization of distribution routes for fresh agricultural products based on ant algorithm

[J]. Journal of Anhui Agricultural Sciences, 2009, 37(1): 109-110, 118.

[16]

詹长书, 李正娇.

基于改进蚁群算法的鲜活农产品配送路径优化

[J]. 物流技术, 2017, 36(9): 89-91, 149.

[本文引用: 1]

ZHAN

, LI

Optimization of fresh farm produce distribution route based on improved ant algorithm

[J]. Logistics Technology, 2017, 36(9): 89-91, 149.

[本文引用: 1]

[17]

盛强, 郑鹏飞, 孙军艳.

动态时变路网下带时间窗车辆路径规划问题研究

[J]. 物流技术, 2018, 37(10): 36-39.

[本文引用: 1]

SHENG

, ZHENG

, SUN

Research on vehicle routing problem with time windows under dynamic road network

[J]. Logistics Technology, 2018, 37(10): 36-39.

[本文引用: 1]

A unified tabu search algorithm for vehicle routing problems with soft time windows

[J]. Journal of the Operational Research Society, 2008, 59(5): 663-673.

[本文引用: 1]

Optimizing departure times in vehicle routes

[J]. European Journal of Operational Research, 2011, 210(3): 579-587.

[本文引用: 1]

Two-echelon logistics distribution region partitioning problem based on a hybrid particle swarm optimization-genetic algorithm

[J]. Expert Systems with Applications, 2015, 42(12): 5019-5031.

[本文引用: 1]

[21]

赵冉, 石晨, 谭骥.

农机安全生产信息系统的设计——基于混合遗传资源调度算法

[J]. 农机化研究, 2021, 43(6): 231-234.

[本文引用: 1]

ZHAO

, SHI

, TAN

Design of agricultural machinery safety production information system—resource scheduling algorithm based on hybrid genetic algorithm

[J]. Journal of Agricultural Mechanization Research, 2021, 43(6): 231-234.

[本文引用: 1]

[22]

李作山

农业机械调度问题中算法改进的研究

[J]. 南方农机, 2019, 50(23): 21, 26.

Research on algorithm improvement in agricultural machinery scheduling problem

[J]. China Southern Agricultural Machinery, 2019, 50(23): 21, 26.

带时间窗农机调度问题模型及算法研究

[本文引用: 1]

Research on model and algorithm of agricultural machinery scheduling problem with time window

[D]. Hangzhou: Zhejiang University, 2019.

[本文引用: 1]

智慧物流分布式计算模型与创新服务研究

2019

... 随着经济发展和消费升级，人们对畜禽肉类和蛋类产品的需求日益增加，大型畜禽业企业的订单量逐年上升，但同时也普遍面临着物流配送成本居高不下的问题.目前，中国禽业企业仍主要依靠经验进行物流配送排线作业，每天耗费大量时间与人力，还无法确保物流配送时效、成本和客户满意度实现最优化.随着信息技术与智慧物流^［1］的不断发展，传统养殖业正向现代养殖业转变，在此背景下，结合车辆路径问题（Vehicle Routing Problem，VRP）^［2］的求解思路，基于机器学习与启发式算法，研究配送车辆智能调度优化算法，对提高禽业企业物流效率和降低物流成本具有实际意义. ...

智慧物流分布式计算模型与创新服务研究

2019

The truck dispatching problem

1959

Vehicle routing with time windows: An overview of exact, heuristic and metaheuristic methods

2010

... VRP作为网络优化中最基本的问题之一，近几十年来一直受到国内外学者的广泛关注，该问题的多种延伸和变化形态为特定需求物流系统的成本和效率优化提供了重要途径，其主要采用启发式算法^［3］、混合算法^［4］、元启发式算法^［5］、模拟退火算法^［6］、禁忌搜索算法^［7］、蜂群算法^［8］等现代智能优化算法，根据不同约束条件针对配送过程中时间成本、人力成本、配送成本等进行全局优化.结合物流领域实际特点，当前的研究方向主要分为两类，一类是基于实际需求加入不同优化因子的研究，通过考虑时间和价格成本、客户时间窗等因子的影响以求更贴近实际场景的应用^［9,10］.Vahdani等^［11］采用启发式和元启发式算法对易腐品车辆路径调度进行了研究，同时考虑了不同容量车辆的配送路径和客户时间窗的问题，实现了易腐品配送场景下按订单时间的车辆配送路径优化算法.Ullrich和Christian^［12］研究了带有时间窗的车辆调度和车辆路径问题，应用遗传算法优化VRP集成模型，实现了一种具有通用性的时间窗车辆优化模型.侯宇超等^［13］考虑物流配送中客户满意度、成本、大气污染物和温室气体排放量四个因素，结合精英蚁群算法建立了多目标配送路径优化模型，实现了考虑环境因素的配送路径优化模型.另一类是基于不同智能优化算法的研究，通过改进和比对不同算法在实际因子下的表现选择合适求解方案^［14-16］.例如，盛强等^［17］以物流成本最小和时间窗为优化目标，使用改进的遗传算法，提出了一种基于时变路网的有时间窗车辆路径问题（Vehicle Routing Problems with Time Windows，VRPTW）模型.Fu等^［18］依据惩罚函数的不同，设计出禁忌搜索算法来求解各种软时间窗车辆路径问题.Kok等^［19］针对具有时间窗的路径优化问题，采用禁忌搜索算法解决时相关路径问题.Wang等^［20］提出了一种基于扩展粒子群优化和遗传算法（Expanded Particle Swarm Optimization-Genetic Algorithm，EPSO-GA）的混合算法，建立了两级物流配送网络总成本最小化模型.近年来，多目标优化算法在农机调度领域被广泛应用^［21-23］，为本研究提供了借鉴思路. ...

A hybrid algorithm for a vehicle routing problem with realistic constraints

2017

Solving the multidepot vehicle routing problem with limited depot capacity and stochastic demands

2019

Vehicle routing problems with multiple trips

2018

An adaptive tabu search algorithm for the open vehicle routing problem with split deliveries by order

2018

Routing optimization of emergency grain distribution vehicles using the immune ant colony optimization algorithm

Production-inventory-routing coordination with capacity and time window constraints for perishable products: Heuristic and meta-heuristic algorithms

2017

Integrated machine scheduling and vehicle routing with time windows

2013

基于精英蚁群算法的多目标生鲜配送路径优化研究

2018

基于精英蚁群算法的多目标生鲜配送路径优化研究

2018

基于改进人工蜂群算法的生鲜农产品配送路径优化

2018

基于改进人工蜂群算法的生鲜农产品配送路径优化

动态时变路网下带时间窗车辆路径规划问题研究

2018

动态时变路网下带时间窗车辆路径规划问题研究

2018

A unified tabu search algorithm for vehicle routing problems with soft time windows

2008

Optimizing departure times in vehicle routes

2011

Two-echelon logistics distribution region partitioning problem based on a hybrid particle swarm optimization-genetic algorithm

2015

农机安全生产信息系统的设计——基于混合遗传资源调度算法

2021

农机安全生产信息系统的设计——基于混合遗传资源调度算法