基于演化博弈的应急物流最优仓库定位

2021-12-10付江伟吴珊丹

计算机仿真 2021年11期

胡晓，付江伟，吴珊丹

(1.河南工程学院，河南郑州 451191；2.中原工学院，河南郑州 450007；3.内蒙古农业大学计算机技术与信息管理系，内蒙古包头 014109)

1 引言

频发的突发事件对社会、生活造成较大影响，也为应急救援工作带来了诸多不确定性因素。为有效解决该问题，应急物流应时而生并迅猛发展[1]，与此同时，对其中的关键仓储点的运行也提出了更高要求。合理的仓库点能够使流体充裕、流程简洁、流量理想以及流速快捷。因灾害救援物资较为稀缺，且灾区基础设施破坏严重，所以，作为优化、改进应急物流整体运行效率的重要环节，最优仓库定位应以最快的速度将救援物资供应给需求点。综上所述，应急物流仓库的最优定位在合理分配有限救援物资、迅速开展高效救援工作等方面具有举足轻重的意义，不仅是应急灾害管理的工作基础[2]，也是灾害响应顺利开展的关键环节。

研究决策主体行为发生直接相互作用时的决策及其均衡问题的一种理论就叫做博弈论[3]，简而言之，就是基于给定的其他参与者策略，“理性”个体最大化利益时的最优反映。该理论一般由参与者、行动、信息、效用、策略、结果、均衡等要素组成，博弈中的必需要素是参与者、策略以及效用。当博弈阶段变为动态过程，即为演化博弈[4]，其主体需遵循规则，通过不断学习，调整策略并择优，其中，纳什均衡是一种常用的博弈分析判定法[5]。

通常情况下，应急物流仓库定位应符合通用性原则、经济性原则、多样性原则、协调性原则、战略性原则以及安全性原则。而本文则基于演化博弈思想，构建出一种应急物流最优仓库定位策略，为今后大幅提升应急物流效率奠定理论基础与参考数据，实现理论与实践创新，弥补以往应急物流方案应急物流仓库运行效率低下，无法满足高效运作需求的不足。

2 演化博弈下应急物流最优仓库定位

2.1 应急物流仓库定位条件

为降低运算复杂度，做出如下设定：各应急物流仓库候选点呈均匀分布状态，各单位指标呈等分形式；已知各仓库候选点的单位建设成本、紧急交通工具的单位运营成本与物资承载量、到各需求点的单位运输成本、单位物资存储成本、对需求点的物资响应速度；已知供应点紧急交通工具的单位运营成本与物资承载量、到各仓库候选点的单位运输成本，各供应点均可实现库存补给。

从最小化服务时长与最小化需求响应时间两个角度出发，完成应急物流最优仓库定位：

1)最小化服务时长：假设应急物流需求点集合、仓库候选点集合以及物资供应点集合分别是I、J、K，需求点i与候选点j之间的单位运输成本是cij，候选点j的建设费用与库存均值是fj与sj，该点与供电点k的各交通工具运营费分别为pj、pk，需求点i的需求量均值为di，候选点j服务需求点i的概率是Xij，供应点k服务候选点j的概率是Xjk，候选点j的开放状态是Yj，开取值是1，关取值是0，该点与供应点k的紧急交通工具个数分别为Nj与Nk，则以最小化服务时长总和为应急物流仓库定位目标，构建下列函数表达式

(1)

该函数公式的服务时间由候选点建设成本、供应点与候选点紧急交通工具运营成本以及期望运输时间成本、候选点与需求点期望运输时间成本组成。其约束条件方程分别如下列各式所示

(2)

(3)

Xij≤Yj，∀i∈I，∀j∈J

(4)

Xjk≤Yj，∀k∈K，∀j∈J

(5)

Nj≤MYj，∀j∈J

(6)

(7)

(8)

(9)

0≤Xij≤1，∀i∈I，∀j∈J

(10)

0≤Xjk≤1，∀k∈K，∀j∈J

(11)

Yj∈{0，1}，∀j∈J

(12)

Nj，Nk∈Z+，∀j∈J，∀k∈K

(13)

依次定义每个约束条件的含义为：确保仓库候选点服务于所有需求点；确保满足各仓库点全部库存；式(4)、(5)两个约束条件表示只有开放的仓库点才能服务于需求点与供应点；紧急交通工具只存在于开放的仓库点；仓库候选点的全部交通工具运输总量满足全部需求点需求量的配送；仓库候选点对需求点的服务总量不可大于存储极大值；供应点的全部交通工具运输总量满足全部仓库库存量的配送；式(10)、(11)的含义是Xjk、Xij取值范围是0～1；指代Yj是标准二进制；指代Nj，Nk是正整数。

2)最小化需求响应效率：该策略可实现T时长路程中应急物流仓库为尽可能多的需求点提供服务，并最小化建设、运营、存储、时间以及惩罚等各种成本。其函数表达式如下所示，约束条件同最小化服务时长函数：

(14)

该函数公式的需求响应时间由候选点建设成本、供应点与候选点紧急交通工具运营成本、候选点物资存储成本、候选点与供应点期望运输时间成本、因未及时满足需求点需求而产生的惩罚成本组成。其中，单位惩罚成本为W，Ij={i:cij>T*V}表示与候选点距离超过T时长路程的需求点集合，候选点紧急交通工具均速为V。

2.2 演化博弈下最优仓库定位

(15)

博弈效用函数为最小化服务时间与最小化需求响应时间的目标函数[6]，而最优定位的求解过程即为基于博弈空间的最优效用策略搜索演化博弈过程，因此，在最优仓库定位演化博弈G=[Q，S，U]中，引入扰动操作[7]，操作原则用ξ表示，构建下列最优仓库定位演化博弈G′

G′=[Q，S，U，ξ]

(16)

其中，博弈参与对象的多个仓库候选点为Q=[q1，q2，…，qj，…，qn]，仓库候选点总数是n；对应策略集合为S=[S1，S2，…，Sj，…，SN]，仓库j的策略集是Sj，各仓库候选点qj都存在两种情况：一个是该仓库点不是最优物流定位，此时Sj=0，另一个是该仓库点是物流最优定位之一，此时Sj={sj，j′}∪{0}(1≤j′≤M)，sj，j′表示需求点Ij′附近的全部仓库候选点。每次博弈中各仓库点只可选取一种策略，防止仓库点同时为多个需求点或供求点服务的情况。

应急服务与需求响应所需总时长U=[U1，U2，…，Uj，…，Un]中Uj的条件式如下所示

(17)

若相同需求点或供应点定位的各仓库点具有相同的应急服务与需求响应所需总时长，则仓库候选点i为最优定位时的适应度函数是F(si)，常数用C表示[8]。针对需求点Ii的应急服务与需求响应所需总时长共有两种情况：一个是该需求点至少存在三个最优仓库定位点，即合理状态，此时适应度函数可映射成C-F(si)；另一个是仓库定位点小于三个，即不合理状态，此时对应效用函数取值为0。

扰动原则ξ在最优仓库定位演化博弈G′中的作用是模拟博弈对象的竞争、演化阶段，就最优仓库候选点j的对应策略Sj生成随机数rand(0，1)，若该数小于扰动概率Pd，则从对应策略集合Sj=[sj，1，sj，2，…，sj，j′]中任选一个策略作为当前策略；反之，则继续使用当前策略。

图1 最优仓库定位流程图

演化博弈的应急物流最优仓库定位具体流程描述如下：

1)博弈阶段初始化处理：设置终止条件、扰动概率Pd以及初始策略s(0)；在各仓库候选点的对应策略集合里任选一个策略，实现初始策略集合s(0)架构；

2)按照扰动原则处理当前策略集合，获取新策略集合s(t)；

4)求取最优反映动态策略的应急服务与需求响应所需总时长，以纳什均衡为判定依据，如下式所示，推断当前策略集合是否需要更新：

(18)

5)停止条件是否成立。若满足停止条件，操作终止，获取最优仓库定位策略集合；反之，则返回第二步，开始重新运算。

3 应急物流最优仓库定位模拟分析

3.1 应急物流实验背景

假定某市不同区域中共有六个应急储备仓库、十个需求点、两个供应点，其中，2号仓库点是应急仓库运行频率最高的仓库点，示意图见图2。表1所示为各项已知参数统计表与各需求点物资需求量统计表，其总成本随着需求程度的升高而升高。

图2 区域设定示意图

表1 已知参数统计表(单位：万元)

表2 各需求点物资需求量统计表

3.2 响应时间与成本相关性分析

依据未及时满足需求的单位惩罚成本，计算出随单位惩罚成本变化的成本结果、未及时满足需求比例以及基于不同安全参数的权衡曲线，计算结果分别如下所示。

从上列图3-图5趋势走向可知：建设成本、惩罚成本均随着未及时满足需求单位惩罚成本的上升而提高，其中，惩罚成本的上涨速度最快，使得总成本的曲线走势上扬明显，而运营成本与存储运输成本增幅较小，与未及时满足需求单位惩罚成本呈弱相关性；未及时满足需求比例呈线性下降，当降至一定数值后，该比例不再随单位惩罚成本的变化而变化；通过总成本与未及时满足比例的权衡曲线图可以看出，总成本与未及时满足需求比例之间呈正相关，由此说明大量投入建设成本，能够在一定程度上提升仓库对应急需求的实时响应性。