浙江大学学报(工学版), 2025, 59(1): 120-129 doi: 10.3785/j.issn.1008-973X.2025.01.012

机械工程、能源工程

基于博弈论的飞机总装物流配送系统资源配置

董玉龙,, 陈璐,, 鲍中凯

上海交通大学 工业工程与管理系,上海 200240

Resource allocation of aircraft final assembly logistics distribution system based on game theory

DONG Yulong,, CHEN Lu,, BAO Zhongkai

Department of Industrial Engineering and Management, Shanghai Jiao Tong University, Shanghai 200240, China

通讯作者: 陈璐,女,教授. orcid.org/0000-0001-7163-7031. E-mail:chenlu@sjtu.edu.cn

收稿日期: 2023-11-28  

基金资助: 国家自然科学基金资助项目(52175475).

Received: 2023-11-28  

Fund supported: 国家自然科学基金资助项目(52175475).

作者简介 About authors

董玉龙(1998—),男,硕士生,从事物流系统资源配置研究.orcid.org/0009-0003-1539-8090.E-mail:dongyulong@sjtu.edu.cn , E-mail:dongyulong@sjtu.edu.cn

摘要

在飞机总装物流配送系统中,仓储与配送多级子系统之间存在资源配置竞争问题,为此基于博弈论建立资源配置模型. 将包括零件总库料包存储区、线边库与工位暂存区在内的仓储子系统和包括货车、自动引导车(AGV)在内的配送子系统抽象为博弈主体. 引入2个效用值指标:资源投入成本和竞争效率,对博弈策略组合进行评价. 提出融合策略空间动态调整的粒子群优化算法进行模型求解,有效利用当前博弈策略组合的可行性信息,加速效用值计算. 算例实验结果表明,所得资源配置方案具有纳什均衡性和飞机产能提升适应能力,所提算法在纳什均衡性、总投入成本和单次迭代时间上的性能均优于对比算法.

关键词: 物流配送 ; 资源配置 ; 博弈论 ; 策略空间 ; 飞机总装

Abstract

A resource allocation model was established based on game theory, aiming at the problem of resource allocation competition between storage and distribution subsystems in an aircraft final assembly logistics distribution system. The storage subsystems such as package storage area in parts warehouse, line warehouse and station storage area, and the distribution subsystems such as truck and automatic guided vehicle (AGV) were abstracted as game players respectively. Two utility value indexes such as resource input cost and competition efficiency were introduced to evaluate the game strategy combination. A particle swarm optimization algorithm with dynamic adjustment of strategy space was proposed to solve the model, and the feasibility information of the current game strategy combination was effectively utilized to accelerate the utility value calculation. The numerical experiments results show that the obtained resource allocation scheme has Nash equilibrium and the adaptability to increased aircraft production capacity, and the proposed algorithm has better performance in Nash equilibrium, total input cost and single iteration time than comparison algorithms.

Keywords: logistics distribution ; resource allocation ; game theory ; strategy space ; aircraft final assembly

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

本文引用格式

董玉龙, 陈璐, 鲍中凯. 基于博弈论的飞机总装物流配送系统资源配置. 浙江大学学报(工学版)[J], 2025, 59(1): 120-129 doi:10.3785/j.issn.1008-973X.2025.01.012

DONG Yulong, CHEN Lu, BAO Zhongkai. Resource allocation of aircraft final assembly logistics distribution system based on game theory. Journal of Zhejiang University(Engineering Science)[J], 2025, 59(1): 120-129 doi:10.3785/j.issn.1008-973X.2025.01.012

飞机总装所需物料繁多,物料配送延迟将导致整条装配线的生产延误[1-2]. 合理配置物流配送系统中各类资源,有效满足给定生产节拍下的物料配送需求是保障飞机总装生产正常运行的关键.

以飞机总装为背景研究物流资源配置问题的文献较少,物流资源投入量常作为总装车间配送车辆调度[2-3]和设施布局优化[4-5]的已知条件或约束. 在飞机装配场景的资源配置方面,学者多关注装配作业资源,特别是人力资源配置对生产调度的影响[6-7]. 以离散制造车间生产场景下物流资源配置为参考,研究方法主要包括仿真优化与集中式建模优化. 仿真优化通过对生产过程进行模拟和多维度评价,完成关键参数优化. 周韶武等[8]采用Petri网和Witness软件对某电装车间生产物流系统进行建模仿真,通过调整瓶颈设备的数量,实现生产线的平衡. Li等[9]基于工厂仿真软件Plant Simulation提出物流系统资源配置方案,通过识别瓶颈资源和实施正交试验,得到包括自动引导车(automatic guided vehicle, AGV)投入数量、暂存区容量在内的物流资源最优决策. Wu等[10]利用数字孪生技术建立虚拟仿真物流系统,确定不同工况下的AGV投入数量,有效提升了资源利用率. 在以上文献中,仿真优化大多着眼于瓶颈资源的识别与调整,难以对多类资源进行联合优化. 此外,由于仿真环境搭建和实验耗时的限制,仿真优化更多应用于有限数量候选方案的择优和现有方案的调整,不适用于飞机总装这类可行方案数量较多、配送周期长的复杂场景. 在集中式建模优化方面,陈炫锐等[11]研究多层车间中自动存取系统的AGV配置优化问题,基于排队网络模型建立含吞吐率和空闲AGV数量2个性能指标的函数,利用启发式迭代算法求解得到最优AGV配置方案. 刘雪梅等[12]考虑装配线平衡与配置的集成优化问题,建立多目标数学规划模型,基于改进遗传算法得到任务分配和缓冲区容量配置的最优结果. 为了提高AGV无人仓储系统的物流效率,Tang等[13]建立任务分配和资源配置的两阶段数学模型,设计双层遗传算法进行求解,得到最优AGV数量和取货站布局方案. 集中式建模优化方法在优化选定的系统运行指标的同时,一定程度上忽视了系统内各子系统的交互和自身运行指标的优化,导致资源配置不均衡和部分子系统运行效率低下.

飞机总装物流配送系统是多级仓储和多阶段配送的复杂系统. 在系统规划层面,各仓储和配送子系统的资源投入数量是确定车间设施布局中各仓储区域面积和车道设置的重要依据. 各子系统资源的均衡配置有助于车间各功能区域的合理划分,避免物料积压和配送效率低下. 在生产管理层面,物料在各仓储区域的存储时长和各配送阶段的时间窗长度是评价各仓储和配送子系统运行效率的重要指标. 作为研究多主体间理性决策及行为交互的理论,博弈论已被广泛应用于云计算[14]、网络通信[15]、雷达搜索[16]等资源配置场景中. 在生产物流配送系统资源配置领域,博弈论的应用鲜少. 王金凤等[17]将煤炭生产物流系统中的安全和效率水平抽象为博弈主体,基于合作博弈框架和纳什讨价还价法,寻求总资源投入确定下的资源配置方案. 已投入使用的飞机总装物流配送系统主要借鉴前代支线客机和同类型客机总装车间资源配置的经验. 由于产品尺寸、装配工艺的差异,现有车间存在部分仓储区域物料积压和部分物料配送延迟送达的情况. 本研究在飞机总装生产场景中引入博弈论,将配送系统内各类仓储和配送子系统抽象成独立的博弈主体,以成本和效率对各主体的资源投入决策进行评价,建立基于非合作博弈框架的物流配送系统资源配置模型;将纳什均衡条件转化为博弈目标函数,提出改进粒子群算法求解博弈模型,获得兼具经济性和纳什均衡性的物流配送系统资源配置方案,使各子系统运行效率保持在相对均衡的状态.

1. 背景描述

某民用客机总装车间共有3个装配工位,分别负责客机功能系统安装、系统总装与分系统测试以及最终功能试验. 每个工位旁设有工位暂存区,存放待上线装配的物料. 车间西南角设有线边库,作为零件总库料包存储区和工位暂存区之间的缓存区. 厂区内零件总库负责接收采购的物料并打包,是物流配送系统的起点. 总装车间和零件总库的布局如图1所示. 如图2所示为总装车间三级仓储、两阶段配送的流程示意图. 物料一般在上线装配前数日内,根据物料清单(bill of material, BOM)拣选齐套,形成以标准化料箱存储和配送的料包,存储于零件总库内的料包存储区. 料包从零件总库料包存储区至线边库的配送由货车完成,从线边库至目标工位暂存区的配送由AGV完成.

图 1

图 1   总装车间和零件总库布局

Fig.1   Layout of final assembly workshop and parts warehouse


图 2

图 2   飞机总装物流配送系统的配送流程

Fig.2   Distribution process of aircraft final assembly logistics distribution system


本研究的物流配送系统资源配置问题:确定给定生产节拍下零件总库料包存储区、线边库、工位暂存区的容量,以及货车、AGV的数量,为总装车间物流系统规划提供决策依据. 为了简化问题建模和考虑生产实际,进行如下假设:1)物流配送系统仅考虑能够使用标准化料箱进行存储的标准件、中小型构件及成品件物料,使用专用牵引设备直接上线装配的物料(如扰流板)不在研究范围中;2)飞机装配工艺稳定,装配严格按照计划时间执行,料包的最晚送达时刻等于该料包在工位用于装配的时刻;3)车间为各工位预留的暂存区面积相同,因此将3个工位暂存区的容量视为1个决策变量;4)车辆配送使用车间专用道路,不考虑车间人员和其余物料移动对车辆配送耗时的影响;5)配送过程所用车辆相同,同一车辆可以进行多次配送.

2. 飞机总装物流配送系统资源配置博弈模型

2.1. 博弈关系分析

飞机总装物流配送系统各类仓储和配送在合作响应物料配送需求的同时,在提高自身运行效率和降低资源投入成本上存在竞争. 非合作博弈框架常用来对系统内各主体的策略和收益进行单独建模,并分析主体的联合决策行为[18],以便较好地描述配送系统中各类仓储和配送间的竞争合作关系.

将各类仓储和配送抽象为独立的博弈主体,以各主体的资源投入量(仓储容量和配送车辆数量)为博弈策略,得到主体间的博弈关系如图3所示. 图中,时序约束是指料包在各仓储和配送主体间流转的先后顺序约束,库存约束是指仓储主体在任意时刻存储的料包数量不应超过其容量. 各主体在满足库存约束和料包最晚送达时刻约束的基础上,展开博弈,包括不同类主体间的博弈和同类主体内部的博弈. 仓储类主体与配送类主体的博弈体现在:配送主体通过时序约束对仓储主体的资源投入提出要求;仓储主体通过库存约束对配送主体的资源投入进行制约. 以线边库仓储主体和货车配送主体为例,线边库仓储主体的资源投入应当满足货车配送主体将料包送达时的入库需求;线边库仓储主体的资源投入对货车配送主体的资源投入及配送速率进行制约. 此外,同类主体间也存在博弈,各仓储主体均希望减少料包在自身的存储时长以降低仓储管理成本,避免料包在自身出现积压现象,各配送主体均希望争夺更长的配送时间窗口以换取进一步减少资源投入的可能.

图 3

图 3   博弈关系图

Fig.3   Game relationship diagram


2.2. 博弈主体及策略空间

博弈模型包含仓储和配送2个类别的主体;仓储主体有3个,分别是料包存储区$Z$、线边库$E$、工位暂存区$W$,用集合$R = \{ Z,E,W\} $表示;配送主体有2个,分别是货车配送主体$H$和AGV配送主体$A$,用集合$L = \{ H,A\} $表示;所有博弈主体的集合为$P = R \cup L$. 定义${N_p}$为博弈主体$p(p \in P)$的策略空间,${n_p} \in {N_p}$为博弈主体$p$的策略选择. 对仓储主体来说,${n_p}$是仓储容量的决策;对配送主体来说,${n_p}$是车辆数量的决策.

2.3. 效用值函数

效用值函数是衡量博弈主体在不同策略组合下自身收益的函数,用来分析主体的最优策略选择及博弈的均衡状态. 将所有博弈主体选择的策略组成的集合记作$ N $,$ N = \{ {n_p}|p \in P\} $. 在资源配置博弈模型中,1种博弈策略组合视作1个资源配置方案. 采用成本和效率这2类效用值函数对策略组合$ N $下各主体的博弈策略进行评估. 成本效用值反映各主体在资源投入成本的竞争,效率效用值反映同类主体在优化自身运行效率上的竞争.

成本效用值$ u_p^1 $用来评估博弈主体的资源投入成本:

$ u_p^1(N) = {c_p}{n_p}. $
(1)

式中:$ {c_p} $为单位资源的投入成本. 效率效用值$ u_p^2 $的定义与博弈主体的类别有关. 1)仓储主体$ r(r \in R) $的效率效用值定义为在基于策略组合生成的物流配送计划下,料包在该主体存储时长占在所有仓储主体存储总时长的比例:

$ u_r^2(N) = \frac{1}{{\left| I \right|}}\sum\limits_{i \in I} {\frac{{{R_{ir}}}}{{{R_i}}}} . $
(2)

式中:$ {R_{ir}} $为料包$i$在主体$r$的存储时长,$ {R_i} $为料包$i$在所有仓储主体的存储总时长,$ \left| I \right| $为某架次飞机总装所需的料包总数. 2)配送主体$l(l \in L)$的效率效用值定义为在基于策略组合生成的物流配送计划下,该主体配送时间窗长度占配送总时间窗长度的比例:

$ u_l^2(N) = \frac{1}{{\left| I \right|}}\sum\limits_{i \in I} {\frac{{{L_{il}}}}{{{L_i}}}} , $
(3)

$ {L_{il}}(N) = {\mathrm{BT}}_i^l - {\mathrm{AT}}_i^l. $
(4)

式中:$ {L_i} $为料包$i$的配送总时间窗长度;$ {L_{il}} $为料包$i$在配送主体$ l $的配送时间窗长度,即料包$i$允许被配送主体$ l $开始配送的最早时刻$ {\mathrm{AT}}_i^l $和配送主体$ l $将料包$i$送达下一仓储主体的最晚时刻$ {\mathrm{BT}}_i^l $的差值. 在成本效用值方面,各博弈主体都希望降低自身的资源投入成本,因此以最小化为优化方向. 在效率效用值方面,仓储主体希望降低仓储管理成本和避免物料积压情况,因此以最小化为优化方向;配送主体希望提高自身配送窗口占总时间窗的比例以松弛配送时间约束,因此以最大化为优化方向. 为了统一表达,将式(3)改写为

$ u_l^2(N) = \frac{1}{{\left| I \right|}}\sum\limits_{i \in I} {\left(1 - \frac{{{L_{il}}}}{{{L_i}}}\right)} . $
(5)

此时,各主体均以最小化自身成本效用值和效率效用值为优化目标:

$ {\begin{array}{*{20}{c}} {\min u_p^1(N)}, \; {\min u_p^2(N)} .\end{array}} $
(6)

2.4. 基于纳什均衡的博弈目标函数

为了优化成本效用值和效率效用值,博弈主体不断调整资源投入$ {n_p} $,获得不同的资源配置方案. 若存在某方案使得任一主体在其他主体策略不变的前提下,无法通过改变策略选择以优化效用值,则称该方案为纳什均衡方案[19]. 纳什均衡方案${N^*}$满足约束:

$ u_p^1({N^*}) \leqslant u_p^1({N^*}||{n_p}), $
(7)

$ u_p^2({N^*}) \leqslant u_p^2({N^*}||{n_p}). $
(8)

其中$ {N^*}||{n_p} $表示博弈主体以调整后的资源投入$ {n_p} $代替方案$ {N^*} $中归属自身的策略后与$ {N^*} $中其他主体策略构成的新方案. 基于式(7)、(8)建立成本效用值增幅函数$ f_p^1 $和效率效用值增幅函数$ f_p^2 $,分别衡量方案$ N $下博弈主体单方面改变自身策略能够获得的成本和效率效用值的最大优化量.

$ f_p^1(N) = {\max _{{n_p} \in {N_p}}}\{ u_p^1(N) - u_p^1(N||{n_p}),0\} , $
(9)

$ f_p^2(N) = {\max _{{n_p} \in {N_p}}}\{ u_p^2(N) - u_p^2(N||{n_p}),0\} . $
(10)

为了统一量纲,对$ f_p^1(N) $$ f_p^1(N) $进行归一化处理:

$ f_p^{1'}(N) = \frac{{f_p^1(N)}}{{{{\max }_{p \in P}}f_p^1(N)}}, $
(11)

$ f_p^{2'}(N) = \frac{{f_p^2(N)}}{{{{\max }_{p \in P}}f_p^2(N)}}. $
(12)

记方案$ N $下所有博弈主体单方面改变自身策略获得的成本与效率效用值最大优化量的平均值函数分别为$ {f_1}(N) $$ {f_2}(N) $

$ {f_1}(N) = \frac{1}{{\left| P \right|}}\sum\limits_{p \in p} {f_p^{1'}(N)}, $
(13)

$ {f_2}(N) = \frac{1}{{\left| P \right|}}\sum\limits_{p \in p} {f_p^{2'}(N)} . $
(14)

式中:$ \left| P \right| $为博弈主体总数. $ {f_1}(N) = 0 \cup {f_2}(N) = 0 $与式(7)、(8)等价. 基于纳什均衡概念,博弈模型以最小化$ {f_1} $$ {f_2} $为优化目标,对2个目标赋以不同权重,转化为求解单一目标$f$的最小值问题. 将$f$作为物流配送系统资源配置模型的博弈目标函数,衡量当前方案的纳什均衡性. 当$f = 0$时,$ {f_1} = {f_2} = 0 $,模型找到纳什均衡资源配置方案.

$ \min f = \lambda {f_1}+(1 - \lambda ){f_2}. $
(15)

式中:$ \lambda $为调节效用值增幅函数权重的参数,$0 < \lambda < 1$. $ \lambda $的取值表征决策者对成本和效率效应值增幅优化的重视程度,优化成本效用值增幅反映对系统总资源投入成本最小化的追求,优化效率效用值增幅反映对系统建成使用时各子系统运行效率均衡的追求.

3. 资源配置博弈模型求解

粒子群优化算法(particle swarm optimization algorithm, PSO)具有设计简单、收敛速度快的特点,被广泛应用于纳什均衡求解中[20]. 本研究提出融合策略空间动态调整的粒子群优化算法(particle swarm optimization algorithm with dynamic adjustment of strategy space, PSODASS)求解博弈模型. 粒子与博弈策略组合一一对应,粒子的每个维度取值对应1个博弈主体的策略选择,搜索空间为该主体的策略空间. 如图4所示为粒子示意图,其中方格表示粒子的维度,$ {n_Z} $$ {n_E} $$ {n_W} $分别为零件总库料包存储区、线边库、工位暂存区3个仓储主体选择的仓储容量,$ {n_H} $$ {n_A} $分别为货车、AGV 2个配送主体选择的车辆数量.

图 4

图 4   粒子编码示意图

Fig.4   Particle coding scheme


3.1. 算法流程

基于粒子对应的博弈策略组合(资源配置方案),利用启发式规则实现当前方案下物流配送计划的快速生成,进而对各主体效用值进行评价;为了减少无效搜索,加快效用值计算,提出策略空间动态调整策略. 为了避免算法陷入局部最优解,在初始化种群时引入相斥个体对的概念;在迭代过程中引入精英改选操作,即当全局极值连续不更新代数超过设定值后,对群体中后20%的个体进行变异操作,并将变异个体和原群体一起进行当次迭代全局极值的选取. 算法流程如图5所示.

图 5

图 5   所提粒子群优化算法的流程图

Fig.5   Flow chart of proposed particle swarm optimization algorithm


3.2. 物流配送计划生成

由式(2)、(4)、(5)可知,基于资源配置方案生成物流配送计划是计算博弈各主体效率效用值的前提. 物流配送计划求解为典型的车辆调度问题[21]. 诸多学者以任务分配和配送时刻为核心决策变量,考虑包括库存约束、送达时刻约束在内的核心约束,建立混合整数规划模型进行问题求解[22]. 由于车辆调度为NP-hard问题,现有基于数学建模的求解方法在飞机总装这类大规模配送任务数的场景下求解效率不高,难以适应粒子群算法的快速迭代需要,

本研究设计基于以下规则的启发式物流配送计划生成方法. 1)以车辆容量为组合大小,按照最晚送达时刻(料包上线装配时刻)和目标暂存区一致性进行料包分组. 2)优先为平均最晚送达时刻较小的料包组合安排配送. 3)优先选择可使用时刻最早的车辆进行配送,当车辆被安排配送任务,更新该车辆可使用时刻为完成当次配送任务的返回时刻. 4)当前车辆配送批次的开始配送时刻为该车辆可使用时刻、批次所含料包进入待配送状态时刻(对于货车配送,该时刻等于料包进入零件总库料包存储区域的时刻;对于AGV配送,该时刻等于料包进入线边库的时刻)和目标仓储区域基于库存约束允许该批次开始配送的最早时刻这3个时刻的最大值. 计算每个粒子表征的资源配置方案各博弈主体的成本效用值;基于上述规则快速生成当前方案下的配送计划,计算得到各主体的效率效用值;基于效率效用值、成本效用值和配送计划,完成粒子适应度的评价.

3.3. 策略空间动态调整策略

为了评估粒子的纳什均衡状态,算法须遍历每个博弈主体的策略空间,并计算效用值. 为了提高算法效率,通过分析效用值函数和粒子不可行性信息动态调整策略空间,减少无效计算. 基于以下策略,在历次迭代中动态调整各博弈主体的策略空间,加快适应度函数计算和算法求解.

策略1 在保证粒子可行的前提下,仓储主体和货车配送主体均存在降低自身资源投入量以进一步优化自身效用值的倾向. 设定策略空间的上界为当前资源投入量.

策略2 当仓储主体存在库存溢出时,策略空间搜索起点调整为当前容量与溢出库存容量之和.

策略3 当出现延迟送达时,各主体不应减少自身资源投入量.

3.4. 适应度函数

粒子群优化算法以博弈目标函数为适应度函数,基于策略空间动态调整策略,实现对博弈主体单方面改变自身策略能够获得的最大效用值优化量的快速计算,利用式(15)实现对粒子纳什均衡性的评价. 考虑到非合作博弈框架仍以各主体合作完成物料配送为前提,因此对于可能出现的不可行状况:物料延迟送达和库存溢出,引入惩罚因子

$ D = {p_1}\sum\limits_{r \in R} {n_r^{\text{O}}} +{p_2}\sum\limits_{i \in I} {\max (T_i^{\text{W}} - T_i^{\text{N}},0)} . $
(16)

式中:$ n_r^{\text{O}} $为仓储主体$r$的溢出库存,$ T_i^{\text{W}} 、 T_i^{\text{N}} 、 \max (T_i^{\text{W}} - T_i^{\text{N}},0) $分别为料包$i$进入目标工位暂存区的时刻、最晚送达时刻和延迟送达时长,$ {p_1}、{p_2} $分别为库存溢出和延迟送达的单位惩罚成本. 为了比较纳什均衡性相同的可行方案的优劣,引入物流配送系统的整体资源投入成本作为第3个评估指标,

$ S = \sum\limits_{p \in P} {{c_p}{n_p}} . $
(17)

式中:$ {c_p}、{n_p} $分别为博弈主体$p$的单位资源投入成本及资源投入量. 粒子适应度函数$F$共包含3个指标:纳什均衡性$ f $、惩罚因子$ D $和总投入成本$ S $

$ F = [1 - {\mathrm{sign}}\;(D)] \times [f+S \times (1 - {\mathrm{sign}}\;(f))]+D. $
(18)

$ {\mathrm{sign}} $函数保证了粒子可行性优先于纳什均衡性、纳什均衡性优先于总投入成本的优先级关系,表达式为

$ {\mathrm{sign}}\;(x) = \left\{ {\begin{array}{*{20}{l}} {{\text{1,}}\;\;x > 0}; \\ {0,\;{\text{其他}}}. \end{array}} \right. $
(19)

4. 实例验证

开展计算实验,验证所提博弈模型与求解算法. 算例源于某民用客机制造企业总装车间. 计算程序代码语言为Python 3.8.2,电脑配置为Intel Pentium G4600 CPU 4.60 GHZ 8.0 GB RAM.

4.1. 算例描述

当前飞机总装生产节拍为14 d,单架次飞机装配要求完成812个料包的存储及配送. 综合考虑采购成本、变动成本、使用年限、维修成本等因素,确定料包存储区、线边库、工位暂存区的单位成本分别为3、6、9千元/料包,货车和AGV的单位成本分别为120、12千元/辆. 结合访谈调研中决策者对系统建设成本和运行效率的重视程度,$\lambda $取值为0.5.

4.2. 算法性能分析

选择经典粒子群优化算法(PSO)、融合遗传交叉和变异操作的粒子群优化算法(BreedPSO)[23]和融合模拟退火思想的粒子群优化算法(SimuAPSO)[24]与本研究所提算法进行对比,以分析改进算法的性能. 4个算法的通用参数保持一致,粒子群体规模、最大迭代次数、群体学习因子、个体学习因子分别设为50、100、1.5、1.5. 采用线性惯性权重,惯性权重的最大值和最小值设为0.9和0.4. 对于BreedPSO, 交叉和变异概率设置为0.6和0.2;对于SimuAPSO,初始温度和退火系数设置为100和0.9;对于本研究所提算法,精英改选的范围为适应度后20%的个体.

基于实际生产数据生成8个不同规模的算例. 针对每个算例,每种算法运行10次,选取最优结果进行对比. 算法求解结果如表1所示. $N$为求解得到的最优资源配置方案,其中各元素取值依次表示料包存储区容量、线边库容量、工位暂存区容量、货车数量和AGV数量. $ K $$ {t_{\text{C}}} $$ t $分别表示解的收敛代数、算法总耗时和单次迭代耗时. 针对这5个算法评价指标生成相应的差距衡量指标:

表 1   所提粒子群优化算法的最优性和求解速度分析

Tab.1  Optimization and solving speed analysis of proposed particle swarm optimization algorithm

$ \left| I \right| $算法$ N $$ f $$ S $/千元$ K $$ {t}_{{\mathrm{C}}}/{\mathrm{s}} $
$ t/{\mathrm{s}} $
$ G_f/{\text{%}} $$ G_S/{\text{%}} $$ G_K/{\text{%}} $$ G_{{t}_{{\mathrm{C}}}}/{\text{%}} $
$ G_t/{\text{%}} $
100PSO{80,24,12,1,7}0.10912231.240.050.000.0017.39−8.06−20.00
BreedPSO{80,24,12,1,7}0.10912251.150.050.000.008.00−0.87−20.00
SimuAPSO{80,24,12,1,7}0.10912251.170.050.000.008.00−2.56−20.00
本研究{80,24,12,1,7}0.10912271.140.04
200PSO{180,20,20,1,3}0.101356249.500.40−100.003.5462.50−6.21−42.50
BreedPSO{180,28,20,1,3}0.001404267.130.270.000.0050.0024.96−14.81
SimuAPSO{180,20,20,1,3}0.101356317.880.25−100.003.5425.8113.07−8.00
本研究{180,28,20,1,3}0.001404398.910.23
300PSO{280,36,32,1,3}0.1020764827.290.57−100.00−19.0810.42−29.83−36.85
BreedPSO{280,20,20,1,8}0.1017163121.000.68−100.00−2.1070.97−8.81−47.06
SimuAPSO{280.20,20,1,5}0.0016804525.370.560.000.0017.78−24.52−35.71
本研究{280,20,20,1,5}0.0016805319.150.36
400PSO{298,60,24,1,1}0.1020343070.442.35−100.00−3.8363.33−72.25−82.98
BreedPSO{281,72,20,1,10}0.1120553043.821.46−100.00−4.8263.33−55.39−72.60
SimuAPSO{292,64,20,1,3}0.0019563259.811.870.000.0053.13−67.32−78.61
本研究{292,64,20,1,3}0.0019564919.550.40
500PSO{252,104,68,1,3}0.22337233133.664.05−54.55−21.6254.55−66.74−78.52
BreedPSO{292,68,40,3,10}0.13284439103.962.67−23.08−7.0730.77−57.23−67.42
SimuAPSO{296,68,44,1,5}0.10266444129.692.950.00−0.7915.91−65.72−70.51
本研究{281,72,44,1,5}0.1026435144.460.87
600PSO{299,72,64,2,10}0.11341734229.276.74−9.09−14.9341.18−69.96−78.78
BreedPSO{294,76,52,1,7}0.10294640160.494.010.00−1.3220.00−57.09−64.34
SimuAPSO{294,92,48,1,10}0.10297045226.845.0411.11−2.126.67−69.64−71.63
本研究{285,108,44,1,8}0.1029074868.871.43
700PSO{339,32,64,2,10}0.11329733330.4510.01−100.00−23.9378.79−46.92−70.33
BreedPSO{347,76,32,1,10}0.10260136262.047.28−100.00−3.5863.89−33.06−59.20
SimuAPSO{347,100,20,1,6}0.11237339356.779.15−100.005.6951.28−50.83−67.54
本研究{348,76,32,1,2}0.00250859175.422.97
812PSO{352,32,52,2,4}0.13294038365.659.62−100.00−25.8236.84−19.73−41.37
BreedPSO{396,20,32,1,10}0.10241237302.978.19−100.00−9.5840.54−3.13−31.14
SimuAPSO{399,44,20,1,5}0.00218144382.628.700.000.0018.18−23.29−35.17
本研究{399,44,20,1,5}0.00218152293.505.64

新窗口打开| 下载CSV


$ \begin{split} {G_j} =& \frac{{{j_{{\text{PSODASS}}}} - {j_m}}}{{{j_m}}} \times 100{\text{%}};\; j \in \{ f,\;S,\;K,\;{t_{\text{C}}},\;t\} , \\& m \in \{ {\text{PSO,\;BreedPSO,\;SimuAPSO}}\} . \end{split} $
(20)

$ f $$ S $$ {t_{\text{C}}} $$ t $对应的$ {G_j} $为负,$ K $对应的$ {G_j} $为正,则说明改进粒子群优化算法性能更优. 由表可知,在纳什均衡性方面,所提算法在料包数量为200、300、400、700、812的算例中均得到纳什均衡解,在剩余算例中相较PSO、BreedPSO和SimuAPSO分别平均提升了约21.21%、7.69%和3.03%. 在资源总投入成本方面,所提算法与SimuAPSO表现相当. 与PSO和BreedPSO相比,所提算法在料包数量为300、400、500、600、700、812的算例中得到更优的资源配置方案,成本平均节约了18.20%和4.74%,在剩余2个算例中,所提算法得到的方案的资源投入成本至多增加了3.54%. 计算结果验证了引入相斥个体对的初始化群体策略和精英改选机制的有效性. 在计算效率方面,所提算法的收敛代数较PSO、BreedPSO和SimuAPSO分别平均增加了约45.62%、43.44%和24.59%,但在单次迭代的耗时上,所提算法平均减少了约56.42%、47.07%和48.40%,验证了策略空间动态调整策略能够有效减少博弈策略的遍历数量,加快了效用值的计算.

4.3. 实际场景求解及纳什均衡解验证

验证算法所得资源配置方案的纳什均衡性. 以料包数量为812的实际场景为例,对应最优解为$N = \{ 399,44,20,1,5\} $,表明料包存储区、线边库、暂存区的容量分别可容纳399、44和20个料包,货车和AGV的投入数量分别为1辆和5辆. 该最优解为当前生产节拍下响应物料配送需求的稳定资源配置方案,可为厂区规划中各仓储区域容量建设比例、各车辆投入数量和配送频次等决策提供依据.

随机改变$N$中任意博弈主体的策略,生成$N$的80个邻域解. 使用效用值优化量${G_p}$评估邻域解与$N$各主体效用值的差异. 当邻域解$ N||{n_p} $可行时,${G_p}$定义为博弈主体$p$单方面改变自身策略得到的成本效用值变化量$ u_p^1(N||{n_p}) - u_p^1(N) $和效率效用值变化量$ u_p^2(N||{n_p}) - u_p^2(N) $的加权值;当邻域解$ N||{n_p} $不可行时,${G_p}$定义为不可行惩罚成本$ D(N||{n_p}) $与原投入成本$ S(N) $的比值. 以${G_p} = 0.5$为分界线对可行和不可行状况进行区分,由于效用值变化量的取值范围为$[ - 1,1]$,设置成本和效率效用值变化量的权重为0.25,保证邻域解可行时,${G_p} \leqslant 0.5$;邻域解不可行时,在惩罚成本与原投入成本比值基础上加上0.5,同时引入$\min $函数,保证${G_p} \in (0.5,1.0]$

$ {G}_{p}=\left\{ \begin{array}{l}0.25 [{u}_{p}^{1}(N||{n}_{p})-{u}_{p}^{1}(N)]+\\\quad 0.25 [{u}_{p}^{2}(N||{n}_{p})-{u}_{p}^{2}(N)],\;\;\;\;N\left|\right|{n}_{p}可行;\\ \mathrm{min}\left(\dfrac{D(N||{n}_{p})}{S(N)},0.5\right)+0.5,\;\;\;\,\text{其他}.\end{array}\right. $
(21)

${G_p} < 0$,表明博弈主体能够获得更优的效用值,则$ N $不满足纳什均衡条件;反之$ N $为纳什均衡解.

所有邻域解的${G_p}$图6所示. 各子图横坐标表示邻域解中该主体改换的资源投入量(对于仓储主体,资源投入量的单位为料包个数;对于配送主体,资源投入量的单位为车辆数量),纵坐标为对应的效用变化量${G_p}$. 由图可知,生成的所有邻域解均在0以上,说明在当前方案$N$下,任意博弈主体单方面改变自身策略均无法优化自身效用值;部分邻域解的${G_p}$在区分可行与不可行邻域解的分界线${G_p} = 0.5$(图中以虚线表示)之上,说明博弈主体单方面改变自身策略还有一定概率使得资源配置方案不可行. 以上结果表明,所提算法所得解满足纳什均衡条件,是当前物流配送系统的最优稳定资源配置方案.

图 6

图 6   博弈主体单方面改变策略得到的效用值变化

Fig.6   Variation of utility value obtained by unilateral change of strategy of game players


4.4. 资源配置方案的适应性评价

物流配送系统资源配置属于中长期决策,应具有一定柔性,能够应对产能变化,为此对物流配送系统资源配置方案进行适应性评估. 将求解得到的生产节拍为14 d的物流配送系统资源配置方案应用于节拍为10~13 d的生产场景中. 如表2所示为不同生产节拍$T_{\mathrm{P}}$下的各仓储主体的资源利用率$U$. 可以看出,物流配送系统资源配置方案能够响应10~13 d生产节拍下的物料配送需求,没有出现延迟送达和库存溢出的情况,证明了方案对节拍加快的适应性. 当生产节拍为10 d时,线边库的资源利用率达到93.98%. 此时,须调整当前资源配置方案,使物流配送系统中各资源利用率维持在合理区间内,保证物流配送系统稳定高效的运行. 在车间正式建成投入使用后,生产管理者也可通过重点关注各仓储区域尤其是线边库的资源利用率,判断系统对节拍加快的适应情况并及时采取调整措施.

表 2   不同生产节拍下的仓储资源利用率

Tab.2  Storage resource utilization rate under different production takts

TP/dU%
料包存储区线边库工位暂存区
1451.7276.0751.45
1354.3079.8854.02
1257.1584.0856.86
1160.3388.7560.02
1063.8893.9863.55

新窗口打开| 下载CSV


5. 结 语

本文研究某民用客机总装车间物流配送系统的资源配置优化,构造博弈决策模型,建立博弈策略集合和粒子维度变量空间的映射,提出融合策略空间动态调整的改进粒子群算法,求解各仓储区域容量和配送车辆数量. 算例求解结果表明,所提算法在纳什均衡性、总成本和求解速度上均优于对比算法,验证了策略空间动态调整策略和精英改选机制能够改善求解质量,提高优化效率. 针对实际生产场景,所提算法能够快速得到最优的资源配置方案. 对所得结果的纳什均衡性验证结果证明,各子系统的资源配置达到均衡状态. 基于数值实验,对所得资源配置方案对生产节拍加快的适应性进行评估,结果表明基于博弈模型求解的物流配送系统资源配置方案能够较好地响应车间的产能提升需求. 随着中国民用飞机的产能提升,总装生产节拍将不断加快. 如何在节拍不断加快的生产场景下,建立资源配置方案的适应性评价体系和设计动态调整策略将是未来可延伸的研究方向.

参考文献

ZHENG Y, HAN D, NI Y, et al

Research and application of bottom-up route-based product data conformity inspection approach for civil aircraft

[J]. International Journal of Computer Integrated Manufacturing, 2014, 27 (6): 591- 607

DOI:10.1080/0951192X.2013.834464      [本文引用: 1]

陆志强, 胡鑫铭, 杜鑫

物料配送与线边存储集成决策模型与算法

[J]. 浙江大学学报: 工学版, 2018, 52 (7): 1354- 1363

[本文引用: 2]

LU Zhiqiang, HU Xinming, DU Xin

Integrated modeling and algorithm of material delivery and line-side storage problem

[J]. Journal of Zhejiang University: Engineering Science, 2018, 52 (7): 1354- 1363

[本文引用: 2]

朱永国, 李俊杰, 刘春锋, 等

基于正态模糊时间窗约束的飞机装配物料配送路径规划

[J]. 中国机械工程, 2017, 28 (21): 2534- 2541

[本文引用: 1]

ZHU Yongguo, LI Junjie, LIU Chunfeng, et al

Aircraft assembly material delivery path planning based on normal fuzzy time window constraints

[J]. China Mechanical Engineering, 2017, 28 (21): 2534- 2541

[本文引用: 1]

段胜文. 飞机脉动总装线生产物流布局方法研究[D]. 南京: 南京航空航天大学, 2016: 1–66.

[本文引用: 1]

DUAN Shengwen. Research on the production logistics layout method of the aircraft pulse final assembly line [D]. Nanjing: Nanjing University of Aeronautics and Astronautics, 2016: 1–66.

[本文引用: 1]

马小丽. 飞机总装配生产线优化设计研究[D]. 杭州: 浙江大学, 2017: 1–60.

[本文引用: 1]

MA Xiaoli. Research on optimal design for aircraft final assembly line [D]. Hangzhou: Zhejiang University, 2017: 1–60.

[本文引用: 1]

吴怡薇, 陆志强

飞机移动装配线资源水平问题的建模研究

[J]. 工业工程与管理, 2017, 22 (1): 95- 101

[本文引用: 1]

WU Yiwei, LU Zhiqiang

Modeling resource leveling problem for aircraft moving assembly line

[J]. Industrial Engineering and Management, 2017, 22 (1): 95- 101

[本文引用: 1]

鲍中凯, 裘柯钧, 陈璐

考虑工时可变的飞机总装资源配置与作业调度

[J]. 计算机集成制造系统, 2022, 28 (5): 1424- 1434

[本文引用: 1]

BAO Zhongkai, QIU Kejun, CHEN Lu

Resource allocation and process scheduling problem of aircraft final assembly considering variable processing time

[J]. Computer Integrated Manufacturing Systems, 2022, 28 (5): 1424- 1434

[本文引用: 1]

周韶武, 胡晓兵, 彭正超, 等

基于Petri网和Witness的SMT生产物流系统仿真及优化

[J]. 现代制造工程, 2020, (11): 99- 105

[本文引用: 1]

ZHOU Shaowu, HU Xiaobing, PENG Zhengchao, et al

Modeling and simulation optimization of SMT production logistics system based on Petri net and Witness

[J]. Modern Manufacturing Engineering, 2020, (11): 99- 105

[本文引用: 1]

LI G Z, YANG S L, XU Z G, et al

Resource allocation methodology based on object-oriented discrete event simulation: a production logistics system case study

[J]. CIRP Journal of Manufacturing Science and Technology, 2020, 31: 394- 405

DOI:10.1016/j.cirpj.2020.07.001      [本文引用: 1]

WU S Q, XIANG W T, LI W D, et al

Dynamic scheduling and optimization of AGV in factory logistics systems based on digital twin

[J]. Applied Sciences, 2023, 13 (3): 1762

DOI:10.3390/app13031762      [本文引用: 1]

陈炫锐, 陈庆新, 毛宁, 等

多层车间中自动存取系统的AGV配置优化

[J]. 计算机集成制造系统, 2023, 29 (5): 1562- 1575

[本文引用: 1]

CHEN Xuanrui, CHEN Qingxin, MAO Ning, et al

AGV configuration optimization of autonomous vehicle storage and retrieval system in multi-floor workshop

[J]. Computer Integrated Manufacturing Systems, 2023, 29 (5): 1562- 1575

[本文引用: 1]

刘雪梅, 刘涛, 顾佳巍, 等

随机型装配线平衡与缓冲区配置集成优化

[J]. 同济大学学报: 自然科学版, 2018, 46 (8): 1098- 1106

[本文引用: 1]

LIU Xuemei, LIU Tao, GU Jiawei, et al

Simultaneous balancing and buffer allocation for assembly line with stochastic task times

[J]. Journal of Tongji University: Natural Science, 2018, 46 (8): 1098- 1106

[本文引用: 1]

TANG H T, CHENG X Y, JIANG W G, et al

Research on equipment configuration optimization of AGV unmanned warehouse

[J]. IEEE Access, 2021, 9: 47946- 47959

DOI:10.1109/ACCESS.2021.3066622      [本文引用: 1]

杨波. 基于博弈论的云计算资源配置优化方法研究[D]. 长沙: 湖南大学, 2018: 1–112.

[本文引用: 1]

YANG Bo. Optimization of research configuration for cloud computing based on game theoretical methods [D]. Changsha: Hunan University, 2018: 1–112.

[本文引用: 1]

毕晓君, 郭柳, 胡菘益

基于非合作博弈论的CoMP-JP资源分配算法

[J]. 中南大学学报: 自然科学版, 2015, 46 (8): 2906- 2913

[本文引用: 1]

BI Xiaojun, GUO Liu, HU Songyi

Resource allocation algorithm for CoMP-JP based on non-cooperative game theory

[J]. Journal of Central South University: Science and Technology, 2015, 46 (8): 2906- 2913

[本文引用: 1]

刘一鸣, 盛文

相控阵雷达搜索和跟踪资源博弈分配策略

[J]. 浙江大学学报: 工学版, 2020, 54 (10): 1883- 1891

[本文引用: 1]

LIU Yiming, SHENG Wen

Game strategy of resource allocation for phased array radar search and tracking

[J]. Journal of Zhejiang University: Engineering Science, 2020, 54 (10): 1883- 1891

[本文引用: 1]

王金凤, 杜雪珂, 翟雪琪, 等

基于合作博弈的煤矿生产物流系统资源配置研究

[J]. 工矿自动化, 2015, 41 (12): 25- 30

[本文引用: 1]

WANG Jinfeng, DU Xueke, ZHAI Xueqi, et al

Research of resource allocation of coal mine production logistics system based on cooperative game

[J]. Industry and Mine Automation, 2015, 41 (12): 25- 30

[本文引用: 1]

FANG F, LIU S T, BASAL A, et al. Introduction to game theory [M]// KAMHOUA C A, KIEKINTVELD C D, FANG F, et al. Game theory and machine learning for cyber security . Hoboken: John Wiley & Sons, 2021: 21–46.

[本文引用: 1]

NASH J

Non-cooperative games

[J]. Annals of Mathematics, 1951, 54 (2): 286- 295

DOI:10.2307/1969529      [本文引用: 1]

MENG Y F, HE J H, LUO S C, et al

An improved predator-prey particle swarm optimization algorithm for Nash equilibrium solution

[J]. PLOS ONE, 2021, 16 (11): e0260231

DOI:10.1371/journal.pone.0260231      [本文引用: 1]

付建林, 张恒志, 张剑, 等

自动导引车调度优化研究综述

[J]. 系统仿真学报, 2020, 32 (9): 1664- 1675

[本文引用: 1]

FU Jianlin, ZHANG Hengzhi, ZHANG Jian, et al

Review on AGV scheduling optimization

[J]. Journal of System Simulation, 2020, 32 (9): 1664- 1675

[本文引用: 1]

VIVALDINI K C T, ROCHA L F, BECKER M, et al. Comprehensive review of the dispatching, scheduling and routing of AGVs [C]// The 11th Portuguese Conference on Automatic Control . Porto: Springer, 2015: 505–514.

[本文引用: 1]

谭叶青, 李萍, 李潇, 等

基于BreedPSO算法及交叠法的紧凑型大角度双自由曲面透镜设计

[J]. 光学技术, 2018, 44 (1): 123- 128

[本文引用: 1]

TAN Yeqing, LI Ping, LI Xiao, et al

Optimization of double freeform-surface lens with large view angle based on BreedPSO algorithm and overlapping method

[J]. Optical Technique, 2018, 44 (1): 123- 128

[本文引用: 1]

黄炯, 艾剑良, 万婧

基于模拟退火粒子群算法的飞机气动参数辨识

[J]. 复旦学报: 自然科学版, 2016, 55 (3): 336- 341

[本文引用: 1]

HUANG Jiong, AI Jianliang, WAN Jing

Identification of aircraft aerodynamic parameters based on SA-PSO algorithm

[J]. Journal of Fudan University: Natural Science, 2016, 55 (3): 336- 341

[本文引用: 1]

/