蒙特卡罗算法求排队库存系统的最优策略

麻存义

摘  要：该文讨论了排队服从M/M/1的排队库存系统，当系统在某個时间内由于服务跟不上或者产品卖断货时会产生预订，该预订会转移到下一个时间周期并形成有效需求，同时考虑由不能及时满足需求而产生的商誉损失。在求解过程中，首先用蒙特卡罗模拟算法计算一定时间段特定策略（s，S）对应的总成本，然后通过遗传算法求出最优策略（s*，S*），最后讨论了顾客到达率、服务率以及固定成本对最优策略（s*，S*）的影响。

关键词：排队库存系统  蒙特卡罗拟合  遗传算法  最优策略

中图分类号：G64                              文献标识码：A                   文章编号：1672-3791（2021）01（a）-0039-03

Monte Carlo Algorithm for the Optimal Strategy of Queuing Inventory System

MA Cunyi

（Lanzhou Jiaotong University Bowen College，Lanzhou，Gansu Province，730100  China）

Abstract： The paper discusses the M/M/1 queuing inventory system. When the system fails to keep up with the service or the product is out of stock within a certain period of time， a resevation with be generated. The resevation  will move to the next time period and form an effective demand. At the same time， the loss of goodwill caused by the failure to meet the demand in time is considered.Firstly， Monte Carlo algorithm is used to calculate the total cost corresponding to a specific strategy （s， S） in a certain period of time. Secondly， the optimal strategy （s*， S*）is obtained by genetic algorithm. Finally， the influence of customer arrival rate， service and the fixed cost on the optimal strategy （s*， S*） is discussed.

Key Words： Queuing inventory system; Monte Carlo algorithm; Genetic algorithm; Optimal strategy

在经典的库存管理系统中，总是假设顾客购买商品是瞬时的，不考虑服务时间，但在现实中，服务时间直接影响到了商品的出清速率，从而间接影响库存水平和订货策略，在此基础上发展出了排队库存系统[1-3]。20世纪90年代时Sagman和Simich-Levi研究了M/G/1排队库存模型，并给出了近似计算方法。最近几年研究的重点有一般补货时间、售后服务、退货等[4]。

该文研究（s，S）补货策略的基础上排队服从M/M/1的模型特点，由于该问题是NP-hard问题，而且其中涉及到随即问题，传统的方法在求极值时无能为力，所以该文用人工智能的方法求最优，通过许多智能算法的比较，择选遗传算法求解，所以该文用蒙特卡罗方法模拟求出总利润，然后通过遗传算法计算最优策略。

1  模型描述

1.1 模型假设

假设一：排队过程服从M/M/1排队模型。

假设二：补货策略为当库存小于s时，补货使得库存达到S+预订量（排队等待的量）。

假设三：每个顾客每次只够买一单位货物。

1.2 符号说明

具体情况见表1。

2  模型分析

2.1 模型建立

定义符号函数

（1）

订货量等于上期的排队人数加上使得库存到达S的差额，而t时刻订货的总费用F（t，s，S）=订货的固定成本+订货的货物成本+库存费用+货源不足造成的损失，于是有以下公式：

（2）

对于有服务的库存系统，在一个周期内实际销售额度即受库存货物的制约，同时受到该周期内的服务能力和顾客的需求（到达人数）制约，所以：

（3）

（4）

综上，在一定时期内的最小总费用为：

（5）

由假设一知道顾客的到达服从参数λ的最简单流，服务时间服从参数为μ的负指数分布，所以：

（6）

2.2 数值分析

由公式（1）（2）（3）（4）（5）可知，在求解最小费用时用到排队人数，而某一期的排队人数由受到前一期排队人数的影响，所以求出（5）的解析解有困难。该文在此处的求解思路为首先用蒙特卡罗模拟出不同（s，S）对应的总费用，然后用遗传算法求出最优的进货策略（s*，S*）。

遗传算法最早由美国的J.Holland教授提出，模拟自然界生物进化过程的机制而开发出的随机搜索方法，计算的具体步骤为：

第一步，编码：随机地选择若干个个体（s，S），并对其进行实值编码。

第二步，个体评价：计算每个个体的适应度1/F（t，s，S），使得适应度大的较大概率保留下來，适应度较小的较大概率筛选出去，以达到优胜劣汰的效果。

第三步，遗传和变异：对个体进行评价，对较优的个体基因更大概率的遗传到下一代，同时为了防止陷入局部最优点的循环进行一定比例的基因变异，既做到更快速地收敛到最优解，又能很好地考察到未知领域，以达到求得全局最优的目的。

第四步，通过以上3步形成新的种群，然后对新的群体进行评价。

第五步，终止条件判断：若干次计算没有发生明显改观时停止，否则转到第三步。

该文研究了λ，μ，P*对最优策略的影响

由表2可知，最低进货库存和进货最大库存都随着λ增加而增加，说明随着需求强度的增大，每次需要进更多的货。

由表3可知，最低进货库存和进货最大库存都随着μ增加而增加，说明随着服务水平的提升和服务效率的提高，每次需要进更多的货。

由表4可知，最低进货库存和进货最大库存都随着P*增加而增加，说明随着订货的固定费用的增加，每次需要更多的货摊薄固定成本。

3  结语

该文在假设顾客的到达是最简单流，服务时间服从负指数分布的情况下，运用遗传算法求的不同参数下的最优进货策略。通过数值计算得出以下结论。

第一，最低进货库存和进货最大库存都随着顾客到达率λ增加而增加，说明随着需求的增大，需要备存更多的货物以防断货，同时也需要每次进更多的货增加库存。

第二，最低进货库存和进货最大库存都随着服务效率μ增大而增加，说明随着服务效率的提高，需要备存更多的货物以防断货，同时也需要每次进更多的货增加库存。

第三，最低进货库存和进货最大库存都随着固定订货费率P*的增加而增加，说明随着每次订货的固定费用的增加，为了摊薄固定费用，需要减少订货的次数，同时增加每次的订货量。

参考文献

[1] R?ty Antti， H?kkinen Silja， Kotiluoto Petri.Nuclide inventory of FIRA 1 TRIGA research reactor fuel[J].Annals of Nuclear Energy，2020（10）：141.

[2] Srinivas R Chakravarthy，Alexander Rumyantsev. Analytical and simulation studies of queueing-inventory models with MAP demands in batches and positive phase type services[J].Simulation Modelling Practice and Theory，2020（5）：103.

[3] 李引珍.管理运筹学[M].北京：科学出版社，2018.

[4] 张鹤.基于（r，Q）策略的易腐品M/M/1/N排队库存系统[J].现代商贸工业，2019（33）：205-208.

[5] 陈俊霖，赵晓波，王小劼.一类考虑反S型概率权重的供货中断库存模型[J].管理科学学报，2016（12）：54-57.

[6] 秦磊.基于模拟退火算法的易逝品库存路径问题[J].计算机工程与设计，2017（2）：47-49.