基于量子遗传算法的云仓储选址分配问题研究

来源：本站 | 发布日期：2023-03-28

1 引言

云仓储是一种新型的仓储模式, 它借助物联网、虚拟化等技术实现仓储作业资源的虚拟化和服务化, 利用云计算等信息技术对信息和资源高效整合, 实现物流服务的智能匹配, 以资源协同的方式满足客户的个性化需求。

云仓储系统的参与者有三种:客户 (仓配服务使用者) 、物流资源提供商和中间商 (仓配云服务整合运营商) , 分布于不同地区的物流资源提供商在平台发布自己的物流资源和物流能力, 仓储云服务整合运营商将资源虚拟化、服务化后在平台集中管理, 建立标准资源库和标准服务子任务库。客户可在平台智能匹配到能满足需求的物流资源及服务。

在云仓储模式下, 系统主要由云仓储服务需求端、云仓储平台及云仓储资源提供端三部分组成。其系统业务流程如图1所示, 云仓储资源提供端聚集了分布在不同地区, 拥有不同物流资源及物流资源的主体, 这些主体将仓储资源、运输资源、计算资源等物流资源及物流能力向云仓储平台发布, 经虚拟化、服务化处理后, 形成一个地理位置分散但逻辑上统一的虚拟资源池。云仓储服务需求端主要指分布在不同地区的云仓储服务使用者, 包括个人企业等需要物流服务的群体, 他们向云仓储平台提出个性化物流服务需求。云仓储平台则是充当前两者之间的连接桥梁, 将资源池的物流资源及能力处理成一个个的标准化的服务模块及物流子任务, 通过服务发现、组合、协作等方式, 为云仓储需求端的物流任务匹配出最优的服务方案, 达到对云仓储服务需求端的动态化的、智能化的按需服务的效果[1]。

图1 云仓储服务的业务流程

在云仓储模式下, 仓配模式同现有的物流服务模式本质不同, 该模式下更加突出虚拟性、集成性、动态性、高柔性、智能性、协同性等特点, 所以势必要求物流资源及物流能力在功能、形态和配置上也要有相应的变化, 本文提出了一种新的能够支持资源集成管理和动态协同分配的选址分配方法, 其设计思路和创新点如下:

传统的选址-分配模型中都假设各配送中心独立运营, 配送中心和需求点之间是“一对一”或“一对多”的关系, 这就使得资源统一调度能力较差, 不能满足云仓储模式下的动态性和智能性要求。本文设计的云仓储模式下基于虚拟资源云的协同仓配选址-分配模型如图2所示, 在这种分配模式下物流资源和物流服务之间的紧密耦合关系被有效解除, 中心仓库和区域仓库及区域仓库和需求点之间形成的服务映射模式是“多对多”的关系。这种模式使得物流资源得到了动态组合, 云仓储平台通过各物流资源的协同实现统一调度, 动态、智能化的为云仓储需求端提供一体化服务[2]。

图2 云仓储选址分配模式

2 覆盖半径和覆盖状态

覆盖半径是指设施服务点以自己为圆心向外辐射服务的最远距离。覆盖状态是指设施服务点有没有向某个需求点提供服务。

传统配送中心的覆盖状态只有两种:当需求点在配送中心的服务半径之内且由该配送中心完全满足其需求时为覆盖, 否则为不覆盖, 即覆盖状态只有0和1两种, 即要么覆盖, 要么不覆盖, 这种覆盖难以与云仓储模式下实际情况不符, 不利于资源的一体化协同服务, 同时也导致选址方式不灵活, 在云仓储模式下分布式的资源一体化调度, 智能、动态、协同地完成物流任务, 本文允许某一云仓只覆盖一个需求点的部分需求, 即覆盖状态是[0, 1]上的连续量, 各云仓协同服务于某一需求点, 其示意如图3, 允许云仓2和3协同满足需求点4和5的需求, 缩小了整体覆盖半径, 提高了系统协同性和灵活性, 降低了物流成本。

图3 基于几个覆盖选址-分配模型覆盖状态

3 模型建立

3.1 问题描述

本文研究的是由中心仓库 (CD) -区域仓库 (RD) -需求点 (R) 构成的三级供应链系统中的多云仓及多末端配送中心选址问题。并且每个候选中心仓库及区域仓库都因仓储资源和设备资源等限制而有能力约束。综合考虑中心仓库和区域仓库两层设施选址, 并确定中心仓库-区域仓库, 以及区域仓库-需求点的分配方案。优化目标是考虑两层设施选址和两层级分配的整体最优方案, 包括如下子决策问题:

两层设施选址决策。在候选的中心仓库和区域仓库中选定设施地址。

两层级分配决策。确定两个层级之间的需求分配关系, 即决策中心仓库-区域仓库, 以及区域仓库-需求点的分配方案。

3.2 符号定义

参数:

I为候选中心仓库集合, i= (1, 2, …, I) ;

J为候选区域仓库集合, j= (1, 2, …, J) ;

K为需求点集合, k= (1, 2, …K) ;

Qk为需求点k对产品的需求量;

Si为中心仓库i的容量限制;

Sj为末端配送中心j的容量限制;

Ai为中心仓库i的建站费用;

ai为中心仓库i的建站及运营成本系数;

Bj为区域仓库j的建站费用;

bj为区域仓库j的建站及运营成本系数;

dij为中心仓库i到区域仓库j的距离;

djk为区域仓库j到需求地k的距离;

v为配送过程中车辆平均行驶速度;

c1为中心仓库到区域仓库之间的单位运量单位运距的平均运输成本;

c2为区域仓库到需求点之间的单位运量单位运距的平均运输成本;

M为规划将建设的中心仓库的数量限制;

N为规划将建设的区域仓库的数量限制;

决策变量

xi为0-1变量, 表示是否在中心仓库i进行建站, 1表示建立, 否则为0;

yj为0-1变量, 表示是否在区域仓库j进行建站, 1表示建立, 否则为0;

zij为中心仓库i对区域仓库j的配送量 (配送比例) ;

wij为区域仓库j对需求点k的配送量 (配送比例) ;

3.3 模型建立

式 (1) 为总成本目标函数, 依次为中心仓库集合I的建设和运营成本, 区域仓库集合J的建设和运营成本, 中心仓库到区域仓库的运输成本, 区域仓库到需求点的配送成本。式 (2) 表示所有区域仓库向任意一个需求点提供总需求满足该需求点的需求, 及区域仓库协同实现对需求点的完全覆盖。

式 (3) 表示中心仓库的配送量与区域仓库的配送量相等。式 (4) 表示每一个区域仓库的进出流量相等, 左边表示中心仓库的流出量, 右边表示需求点的流入量。式 (5) 表示中心仓库建站总数量小于限制最大值M。式 (6) 表示区域仓库建站总数量小于限制最大值N。式 (7) 表示每一个中心仓库的储存量要小于其容量限制。式 (8) 表示每一个区域仓库的储存量要小于其容量限制。式 (9) 和式 (10) 是对决策变量的约束, 为0-1变量, 表示是否在i或j处建站。式 (11) 和式 (12) 是对决策变量的约束, 表示配送量非负。

4 量子遗传算法设计

4.1 量子比特编码

采用二进制编码, 对存在多态的问题进行量子比特编码, 如两态则用一个量子比特进行编码, 四态则用两个量子比特进行编码。针对本文提出了中心仓库-区域仓库-需求点的三级选址分配问题, 提出如下编码方案:[3,4,5,6]

图4

在本编码方案中, 设施选址和分配问题整合在一起编码, 系统编码可分为三部分:即中心仓库编码段、区域仓库编码段、需求点编码段。

采用多量子比特编码m个参数的基因如下:

其中n表示种群规模, 为qjt染色体, 表示第t代的第j个个体的染色体;m为染色体的基因个数, k为编码每一个基因的量子比特数。

把单个中心仓库、区域仓库及需求点都按一个基因编码, 在每个编码段中, 依据上级设施点的基因数量来确定本层每个基因的量子比特数。如上级设施点基因数为x, 本层设施点编码时, 为同时考虑选址问题和分配问题, 可用y个量子比特位编码来表示每个设施点, y与x需要满足条件:

因此, 量子比特数y可计算得:

根据y位量子比特位观测得到的二进制编码串对应的十进制, 用取值为零和非零表示设施选址, 即若对应的十进制值为0, 对应的设施点未被选中;若对应的十进制值>0, 则对应的设施点被选中, 且其对应的十进制值还表示和上一级设施点的分配关系。

4.2 量子进化算法运算步骤:

(1) 确定量子进化算法系统参数, 包括群体大小, 观测次数、最大运算代数、体制条件等;

(2) 初始化种群, Q (t0) ={q1t, q2t…qjt…, qnt}等概率随机的生成n个以量子比特位编码的染色体, 此处t=0;

(3) 对初始种群Q (t0) 中的每个个体进行观测, 得到二进制解集P (t0) ={x1t, x2t, …xjt, …, xnt}即为第0代个体;

(4) 对P (t) 所对应的方案进行有效性检验, 保证其对应的方案的可行性, 同时对各解进行适应度评估;

(5) 记录P (t0) 中最优个体和其对应的适应度;

(6) 检查是否满足结束条件, 若满足, 则停止运算, 输出最优个体及相关数据, 否则, 继续下一步;

(7) 对种群Q (t) 中的每个个体进行观测, 生成二进制解集P (t) ;

(8) 对P (t) 中各解进行有效性检验及适应度评估;

(9) 利用量子旋转门更新种群, 得到新种群Q (t+1) ;

(10) 记录P (t) 中最优个体和其对应的适应度;

(11) 迭代次数t加1, 转向步骤 (6) ;

(12) 结束, 输出最优个体及其他相关信息。

5 案例分析

A公司成立于2004年, 是全球领先的第三方电商物流供应链企业, 天猫超市仓储管理服务的核心提供商。为提升企业竞争力, 拟在浙江省建立至多3个中心仓库 (CD) 及至多7个区域配送中心 (RD) , 实现物流响应时效性质的提升, 为客户提供次日达、限时达等服务, 提高客户满意度。本文将66个主要县市区抽象为节点, 如图5, 以其当地政府所在地位置作为节点位置, 以两点间的公路距离作为两点间的距离, 据A公司2017年运营数据, 分析处理得, A公司在浙江省对各个区县的单日配送量均值为3.05千件, 所以, 每个需求点的需求量按正态分布N (3.05, 0.5) 的密度产生, 经考察调研, 选取1、10、16、27、40号节点为候选中心仓库, 其相关参数见表1, 选取4、9、24、31、48、55、59号节点为候选区域仓库, 其相关参数见表2, 选取39个节点为需求点。模型中的其他参数, 参考采用同类文献和经验判断的方式给出:c1=25元, c2=50元。

表1 候选中心仓库相关参数

图5 节点分布示意图

表2 候选区域仓库相关参数

以Matlab 2014a为操作平台, 在Inter (R) , Pentium (R) , Core (TM) i5—3520MCPU, 2.9GHz, 4.00 GB内存, Windows 7操作系统上执行算法。参数设置为:种群大小为5, 即量子进化计算中有两条量子染色体, 观测次数设定为10, 即子群体大小为10, 最大进化运算代数为4000。经计算, 最终选取1、16、40号节点作为中心仓库, 选取4、9、31、55、59作为区域仓库, 其分配方案如表3和表4所示, 各需求点的需求得到满足, 每个仓库的容量未超过容量限制, 总的物流系统成本为4522.4万元。

表3 中心仓库选址结果及分配方案