面向跨区农机集群的动态维护服务网络规划方法

李金良 王西彬 胡耀光 任维波

(1.北京理工大学机械与车辆学院, 北京 100081; 2.中北大学机械工程学院, 太原 030051)

0 引言

维护服务网络是由制造商构建为顾客提供及时、满意的维修服务而形成的网络[1]。服务网络设计规划的研究主要集中于救援、医护、消防等多个领域。但是目前,装备功能愈加复杂,作业任务更加繁重,这对装备的可靠作业及运维服务提出了更高要求[2]。尤其是在农业领域,农机装备已成为提高农业生产效率、降低农民作业负担的关键工具。受限于农作物的地理位置与成熟时间,农机装备分布在广泛的地理区域内[3]。随着农作物由南到北依次成熟,农机装备作业过程随之呈现由南向北的集群跨区作业趋势[4]。尤其是“三夏”农忙时节,农机跨区作业已经成为了重要的农业机械服务模式,可以更好地利用和配置农机装备,提高农田作业效率[5]。

但是由于作业过程的高温和复杂作业环境,农机装备很容易发生故障,而维修服务往往无法及时到达,严重影响集群协同作业效率[6]。因此,农机制造企业需要构建动态维护服务网络来保障对农机装备维护服务的及时高效[7]。一方面,制造企业会建立静态服务站,这些静态服务站布局在固定的位置为其服务区域内的故障农机提供维修服务;另一方面,为了应对农忙时节装备移动与故障激增的情况,制造企业会提供动态服务车来弥补静态服务站能力不足的情况。这些动态服务车也会随着农机装备集群的动态移动而进行调整[8]。因此,本文以农机集群的动态维护服务网络为研究对象,重点研究静态服务站和动态服务车的服务设施选址和服务区域划分问题。

目前,服务网络规划已经广泛应用于各个方面,例如消防和救援服务网络系统、供应链网络系统、医疗保健服务网络系统、农机装备服务网络系统等[9-10]。在服务设施选址方面,服务网络设施选址主要解决在给定的可选位置集合情况下确定相关服务设施的合理位置[11]。在服务设施选址过程中,部分服务设施总是处于固定的位置以满足服务网络客户的需求,如保健医院、物流中心、仓库和维修服务站等[12]。但是,在大部分情况下,服务中心需要调整服务设施的位置以适应用户需求的动态变化[13]。服务设施选址模型主要包括覆盖模型、P-中值模型和P-中心模型[14-15]。服务区域划分是指对每个服务设施划分合适的服务区域,从而保证区域内所有的服务需求及时交付。服务区域划分方法主要包括:P-区域模型、随机优化模型、聚类方法和局部搜索方法等。在求解方法方面,研究人员目前已经开发了许多方法,主要包括精确求解方法和启发式算法等。其中,精确求解算法主要包括商业求解器CPLEX、分支定界算法、Benders分解算法等,启发式算法主要包括禁忌搜索算法、模拟退火算法、粒子群优化算法和遗传算法等[16-18]。如ARABANI等[19]系统分析了动态设施选址决策问题,从决策模型和方法、应用领域和未来趋势等方面对动态设施选址问题进行分类。REN等[1]针对维护服务网络服务区域划分问题,综合考虑服务均衡和服务成本最小化,并以湖南省的服务网络为例进行了实例验证。

尤其是在农机维护服务网络规划领域,REN等[7]针对农机维护服务网络服务商选择问题,综合考虑服务商评价的单体评价和整体评价指标选择最合适的服务商。REN等[8]综合考虑静态服务商和动态服务车选址问题,基于启发式算法实现农机故障动态响应。HAN等[20]针对动态维修站的设施选址和资源分配问题,以最小化运维服务成本为优化目标,构建了混合整数规划模型,提出运用Benders分解算法进行动态设施选址与优化决策。

尽管目前研究服务网络设施选址决策较多,但农机集群动态移动对服务设施选址提出了更高的要求:①与传统的离散点选址不同,农机维护服务网络选址过程中,农机装备集群通常分布在广泛的作业区域内,传统的离散选址难以解决农机装备集群维护服务网络规划问题。更进一步,为了提高农机装备集群维护服务网络规划效率,本文将临近区域的农机装备整合为一个单元区域进行设施选址。②现有的研究忽略了服务网络的服务区域划分问题,尤其是在农机维护服务网络中,必须要考虑每个服务商的服务范围,并且保障服务区域的连续,即静态服务站服务的所有单元区域在地理上是连续的,不允许进行跨区服务。③现有的研究忽略了静态服务设施与动态服务设施的综合选址,往往仅考虑静态服务合适或者动态服务设施的单种设施选址问题。因此,本文从决策优化模型和求解算法两方面提出面向农机装备集群维护服务网络的服务设施选址和区域划分方法。

1 问题描述

基于实际案例,本文考虑一个包括静态服务站和动态服务车的动态服务网络。为了提高计算效率,临近的多个需求点将整合为一个单元区域。因此动态分布式装备集群维护服务网络的服务设施选址问题考虑在单元区域服务需求动态变化的情况下,以最小化运维服务网络成本为目标,在单元区域集合中选择合适的单元区域建立静态服务站或动态服务车。静态服务站的位置固定不变,而动态服务车的位置则将根据单元区域的需求变化而动态调整,同时根据选定的静态服务站确定其服务的单元区域。

如图1所示,整个区域由20个单元区域组成。假设静态服务站和动态服务车的位置以及动态服务车的转移路径如图1所示,整个区域共划分为4个服务区域,并且每个服务区域设置一个静态服务站。如静态服务站8为单元区域1、2、6、7、8提供运维服务。同时,整个运维服务过程划分为3个阶段,通过增加动态服务车以弥补静态服务站服务能力不足的情况。如在T1阶段,动态服务车位于单元区域16,协助静态服务站17为单元区域16提供运维服务。而在T2阶段,动态服务车移动至单元区域7,此时动态服务车协助静态服务站8为单元区域7提供运维服务。以此类推在T3阶段,动态服务车转移至单元区域1,协助静态服务站8为单元区域1提供运维服务。

图1 动态运维服务网络示意图Fig.1 Description of dynamic maintenance service network

假设条件:①单元区域的位置是固定已知的,并且单元区域的需求会进行周期变化。②静态服务站的服务范围有限。③每个单元区域可以同时被静态服务站和动态服务车服务,但同时只能被一个静态服务站服务。④静态服务站在完成维修维护服务后,会回到起点。⑤动态服务车主要是弥补静态服务站的服务能力,只能为动态服务车所在的单元区域提供运维服务。⑥由于动态服务车使用成本高,并且由农机制造商直接分配,因此单元区域的服务需求优先被动态服务车服务。⑦多辆动态服务车可以选择同一个单元区域。⑧静态服务站服务的单元区域是连续的。⑨由于静态服务站的建站成本固定不变,所以本文不考虑静态服务站的建站成本。

2 数学模型

农机装备集群维护服务网络的服务设施选址和区域划分以运维服务网络成本最小化为目标,以确定静态服务站的位置和服务区域以及动态服务车的数量和位置。

2.1 参数与变量设置

(1)集合

I为单元区域集合,J为候选静态服务站位置集合,K为候选动态服务车位置集合,T为运维服务阶段集合,A为相邻单元区域对。

(2)下标

i、i′为单元区域索引,i,i′∈I;j为候选静态服务站位置的索引,j∈J,J⊆I;k、k′为候选动态服务车位置的索引,k,k′∈K,K⊆I;t为运维服务阶段的索引,t∈T。

(3)参数

(4)决策变量

2.2 决策优化模型

以运维服务网络成本最小化为目标,构建决策模型P0,表达式为

minf=f1+f2+f3

(1)

(2)

(3)

(4)

其中,式(1)表示动态服务网络总成本,主要包括两方面:式(2)、(3)表示的动态服务车的转移成本和使用成本;式(4)表示的静态服务站服务里程成本。

约束条件为

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

M=imax

(16)

(17)

其中,式(5)表示在候选静态服务站单元区域选择设置m个静态服务站。式(6)表示每个单元区域只能被一个静态服务站服务。式(7)表示每个服务区域内只有一个静态服务站。式(8)表示所有的单元区域被服务。式(9)表示每个候选动态服务车单元区域在阶段t设置的动态服务车数量与阶段t+1转移的动态服务车数量相同。式(10)约束静态服务站的最大服务距离。式(11)～(13)参考文献[1,16],并扩展到本文的农机装备运维服务网络,保证了分配给静态服务站的单元区域的连续性,其中式(11)保障了单元区域i与服务区域的连续性,式(12)、(13)表示每个服务区域内只有一个假想流槽,保障了服务区域内的连续。式(14)～(17)用来限制各个变量的取值。

3 求解算法

3.1 模型线性化

minf=f1+f2+f3

(18)

(19)

(20)

(21)

约束条件除式(5)～(17),还包括

(22)

(23)

(24)

(25)

(26)

(27)

minf=f1+f2+f3

(28)

(29)

(30)

(31)

约束条件除式(5)～(17)、式(22)～(27)外,还包括

(32)

(33)

(34)

(35)

3.2 Benders分解算法

模型P2包括多个决策变量,其中变量x用来决定静态服务站的选址,变量y用来表示服务单元分配结果,变量z决定动态服务车辆在各个阶段的转移,变量w用来判断分配之后的服务单元是否连续。由于模型中存在多个变量,因此本文采用Benders分解方法将原问题分解为两个子问题:主问题(Master problem)基于变量x、y和z来判断静态服务站的选址和服务分配以及动态服务车在各个阶段的转移;子问题(Subproblem)基于变量w用来判断划分之后的服务单元是否连续。

主问题 min{f:x,y,z}

约束条件为式(5)～(10)、式(14)～(16)、式(22)～(27)和式(32)～(35)。

子问题 min{0:w}

约束条件为式(11)～(13)和式(17)。

(36)

将生成的组合Benders切割公式(36)添加到主问题。这样迭代重复求解主问题和子问题,直到求得原问题的最优解。

4 案例

以河南省农机装备集群的运维服务网络规划为例,确定静态服务站和动态服务车的位置以及服务区域划分结果。

4.1 案例描述

以某农机制造企业在河南省运维服务为例,数据来自于河南省2019年5月16日至6月14日121个县(单元区域)约7.5×104km2的粮食作物面积。这些单元区域如图2所示。随着农作物由南向北依次成熟,整个收获季节可以分为6个阶段,每个阶段5 d左右。每个单元区域的收获作业任务一般持续1～2个阶段。不同时间段内各空间单元的农机故障信息如图3所示。不同时间段内的各空间单元的农机故障信息依据历史故障数据、农机保有量和农田作业面积等[21],通过分析历史故障数据中农机故障数据与农机保有量和农田作业面积等关系,分析每个空间单元各个时间阶段的农机故障数量。

图2 河南省单元区域Fig.2 Service units in Henan Province

图3 不同时间段单元区域的故障数量Fig.3 Maintenance demands in different units at each stage

本文中每个单元区域都可以设置为静态服务站和动态服务车。同时,为了在农忙时节为故障农机提供及时的维修服务,整个维修服务网络共建立12个静态服务站。由于制造商要求静态服务站必须在2 h内达到故障农机的位置,因此静态服务站最大覆盖距离为120 km。运维服务过程中静态服务站每单位里程费用为3元/km,动态服务车转移成本为5元/km,动态服务车每阶段的使用成本为 8 000元,动态服务车在每一阶段可以为40个故障需求提供服务。

基于上述数据,本文所有的求解都是在个人计算机上进行,计算机的基本配置为AMD 4.00 GHz和16 GB RAM。

4.2 案例计算

首先,直接采用求解器GUROBI对动态维护服务网络设施选址与区域划分问题进行求解,最优解无法在24 h内获得。因此,本文采用线性化方法和Benders分解算法对问题进行求解,共经历3次迭代,共计用时1 601 s。运维服务网络维修总成本为2.103×106元。静态服务站选址和区域划分结果如图4所示,动态服务车在各个阶段的位置如图5(图中椭圆表示动态服务车位置)所示。

图4 静态服务站选址和区域划分结果Fig.4 Location of static service stations and service region districting results

图5 动态服务车位置Fig.5 Location of dynamic service vehicles

如图4所示,选择单元区域3、11、17、33、60、70、74、87、96、110、113、117作为静态服务站的位置。计算结果表明,静态服务站一般会选择在服务需求较多的单元区域,如单元区域11、74、87、110、113等。每个服务站服务的单元区域用不同的颜色来区分,可以发现基于选择的静态服务站,单元区域一般会划分给距离最近的静态服务站。例如,位于单元区域11的静态服务站对单元区域8、9、10、11、12、42、44、45、62、63、106的故障农机提供维修维护服务。而位于单元区域110的静态服务站对单元区域88、107、108、109、110的农机提供服务。

此外,在动态服务网络中,26辆动态服务车参与农机装备维修服务,动态服务车在每个阶段的位置如图5所示。计算结果表明,动态服务车一般会选择每个阶段除静态服务站所在单元区域外故障需求数量较多的单元区域。在阶段1,26辆动态服务车主要位于单元区域93、94、95、97、98、99、101、118,主要位于河南省的最南端。在阶段2,动态服务车主要移动至单元区域75、84、109、111、112、118、120。之后动态服务车逐步向北移动,最后在阶段6,动态服务车移动至单元区域31、32、34、40、53、54、55、56。收获期间动态服务车从南到北移动,这与农作物从南到北成熟的趋势也基本相同,这证明了本文模型和算法的有效性。

4.3 与两阶段决策对比

在实际生活中,农机企业通常采用两阶段求解的方法来解决动态维护服务网络设施选址与区域划分问题。所谓的两阶段求解方法是指首先解决静态服务站的选址和区域划分问题,然后再根据静态服务站的位置去决策动态服务车在不同阶段的位置。因此,本节将两阶段求解方法与本文提出的联合求解方法进行对比。

两阶段求解结果如图6所示,总成本为2.300×106元,与联合决策结果相比增加9.37%,这也证明了本文提出模型的有效性。此外,基于联合优化方法和两阶段方法的动态服务车的移动成本和静态服务站的服务里程成本如表1所示。在两阶段决策结果中,28辆动态服务车参与农机装备维护服务,因此,动态服务车的使用和转移成本高于联合决策中的动态服务车使用和转移成本。而因为多辆动态服务车的参与,静态服务站的服务里程成本则低于联合优化决策的服务里程成本。

表1 优化结果对比Tab.1 Comparison between two methods 元

图6 两阶段静态服务站选址与区域划分结果Fig.6 Service region districting and service stations location in two-stage method

更进一步,基于两阶段独立决策,在进行静态服务站选址和服务区域划分过程中,静态服务站通常会选择单元区域故障数量较多的单元区域,如33、87、113、60、74等单元区域。其他单元区域则基于连续性约束分配给距离最近的静态服务站,以此获得较低的静态服务站服务里程成本。而在动态服务车动态选址决策中,动态服务车则选择在故障数量较多的单元区域。而在联合决策中,静态服务站的选址不仅考虑总故障数量最多的单元区域,同样考虑在各个阶段故障数量最多的单元区域。在这种情况下,静态服务站则会选择单元区域96、3、70、12等。如在图4中位于单元区域96的静态服务站,其服务区域包括94、95、96、97、98、99、100、101等单元区域。在阶段1,动态服务车主要位于静态服务站的服务区域内。在这种情况下,这些单元区域的故障维护主要由动态服务车服务,以保障总服务成本最小。而在阶段2～阶段6,单元区域96的维护需求大于单元区域95的维护需求,因此在这种情况下,静态服务站选择在单元区域96,可以获得更小的服务成本。

因此,与两阶段决策相比,联合调度决策综合考虑各单元区域的总维护需求与各个阶段的单元区域的故障维护需求,通过综合决策静态服务站和动态服务车的位置,进而获得更小的维护服务成本。

4.4 参数敏感性

首先通过进行参数敏感性分析来判断静态服务站数量m变化对总成本的影响,进而选择构建最佳数量的静态服务站。通过改变静态服务站数量m来评估静态服务站数量对计算结果的影响。首先通过减小m来获得m的下限。结果表明当m小于10时,无法获得最优解。因此将m从10开始逐渐增加,假设单个静态服务站的建站成本为1.0×105元,考虑静态服务站建站成本的总成本和不考虑静态服务站建站成本的总成本如表2所示。在不考虑静态服务站建站成本时,总成本随着静态服务站数量的增加而降低,但随着静态服务站数量的增加,总成本的变化逐渐变小。例如,静态服务站的数量从10增加到11,总成本降低2.10×105元,而静态服务站的数量从16增加到17,总成本只降低5.60×104元。在考虑静态服务站建站成本时,当静态服务站数量小于12时,总成本随着静态服务站数量的增加而降低,而当静态服务站数量大于12时,总成本随着静态服务站数量的增加而增加。因此,在本案例中,当静态服务站的数量设置为12时,总服务成本最低。

表2 不同数量静态服务站的成本Tab.2 Total costs for different value of m 元

其次,分析动态服务车数量对总服务成本的影响。通过改变动态服务车数量来评估动态服务车数量对计算结果的影响,计算结果如表3所示。

表3 不同动态服务车数量的成本Tab.3 Total costs for different number of vehicles 元

如表3所示,当动态服务车数量为26时,总服务成本最小。因此在本案例中,最优的动态服务车数量为26。此外,当动态服务车数量大于26时,总服务成本随着动态服务车数量的增加而增加,并且增加幅度变大。

因此,在实际案例中,决策者需要综合考虑动态服务车数量和静态服务站数量,以便获得更小的服务成本,更高的服务效率。

4.5 区域连续性

区域连续性主要通过式(11)～(13)和式(17)进行约束。因此,采用线性化方法和Benders分解算法对去掉约束式(11)～(13)和式(17)的动态服务网络选址和区域划分问题进行求解,静态服务站选址和区域划分结果如图7所示。忽略区域连续性约束的总服务成本为2.034×106元,总服务成本降低3.28%。

图7 不考虑区域连续性的服务网络规划结果Fig.7 Location and districting results without contiguity

如图7所示,静态服务站103、104服务的单元区域107、119不连续,因此在对其进行维修服务时,必须进行跨区服务。这种跨区服务方案在农业生产过程中通常是不可行的,这会导致服务延长和服务资源浪费。决策者更愿意将单元区域104分配给其最近的静态服务站107,从而保障静态服务站107服务的单元区域是连续的。

通过改变m,对不同参数下的区域连续性约束进行分析,计算结果如表4所示。

表4 不同静态服务站数量的区域连续性分析Tab.4 Analysis of contiguity constraints with different value of m

如表4所示,在不考虑区域连续性约束时,总服务成本均会降低。并且总服务成本的变化与静态服务站的数量之间没有关系。例如,当m为 10时,总服务成本降低0.93%,而当m为16时,总服务成本降低0.85%。

综上所述,在维修服务过程中应考虑区域连续性约束,以保障分配给静态服务站的单元区域是连续的,以避免生成不可行的解决方案。

4.6 算法性能

对于动态服务网络选址和区域划分问题,求解器GUROBI均不能在24 h内获得最优解。对于线性化方法,部分案例可以在3 h内求得最优解,而其他案例的求解时间则大于6 h,甚至超过12 h。但是使用线性化方法结合Benders分解算法,所有案例的计算时间均在1 h内。

此外,通过分析不同案例,本文所提出的线性化方法结合Benders分解算法的计算时间如表5所示。对于不同案例,Benders分解算法结合线性化方法始终是计算时间最短的一种方法。此外,对于求解器GUROBI,当单元区域数量n小于100时,最优方案可以在24 h获得,当单元区域数量大于100时,求解器GUROBI无法在24 h求得最优解。对于线性化方法,当单元区域数量大于200时,计算时间大于12 h。对于线性化结合Benders分解方法,则所有的案例都可以在最短的时间内求解,尤其是当单元数量大于等于200时,最优解可以在3 h内获得,远小于其他两种方法的时间。

表5 不同案例的计算时间Tab.5 Calculation time for cases with different sizes

总之,本文提出的Benders分解结合线性化方法对于求解动态服务网络选址和服务区域划分问题表现出了良好的计算性能。

5 结论

(1)研究了面向农机装备的动态维护服务网络设施选址和区域划分问题,以确定静态服务站的位置和服务区域以及动态服务车的动态位置变化为目标,构建了以最小化服务成本为目标的决策模型。同时,结合线性化方法和Benders分解算法进行求解,并通过在河南省的实际案例证明了模型与算法的有效性和高效性。

(2)计算结果表明,静态服务站一般会选择在故障数量较多的单元区域,而随着农作物成熟,动态服务车会移动到其他故障数量较多的单元区域。更具体地,静态服务站负责为服务区域内的多个单元区域提供维护服务。但在农忙季节,随着作物成熟,一些单元区域的维修需求急剧增加,动态服务车会向这些单元区域移动,以弥补静态服务站服务能力的不足。而这些动态服务车可以在维修服务后转移到其他单元区域。

(3)进行了相关参数敏感性分析。分析结果表明,在不考虑静态服务站建站成本时,总服务成本会随着静态服务站数量的增加而下降。当考虑静态服务站建站成本时,总服务成本随着静态服务站数量的增加先降低而后增加。并对算法的性能进行分析,本文所提出的线性化方法结合Benders分解算法优于现有的求解器 GUROBI 和线性化方法。