考虑空间邻接关系的二维货架空间分配问题研究_郑兰兰.pdf
《考虑空间邻接关系的二维货架空间分配问题研究_郑兰兰.pdf》由会员分享,可在线阅读,更多相关《考虑空间邻接关系的二维货架空间分配问题研究_郑兰兰.pdf(9页珍藏版)》请在咨信网上搜索。
1、第 28 卷 第 2 期2023 年 4 月工业工程与管理Industrial Engineering and ManagementVol.28 No.2Apr.2023考虑空间邻接关系的二维货架空间分配问题研究郑兰兰1,2,吴锋1,2*,毕闰芳1,2(1.西安交通大学管理学院,陕西 西安 710049;2.教育部过程控制与效率工程重点实验室,陕西 西安 710049)摘要:货架资源的紧缺性使货架空间分配问题成为零售市场中被重点关注的领域。本文在二维货架空间分配模型的基础上,考虑了产品空间邻接关系的影响,建立了混合整数非线性规划模型,并设计了改进型随机密钥遗传算法进行求解,最后使用多个算例进行
2、了广泛验证。在小规模问题中,通过本文设计算法、基准遗传算法和Lingo求解结果比较,发现本文设计算法相对于Lingo在求解效率上有很大提升。在大规模问题中,通过本文设计算法和基准遗传算法比较,发现在收敛时间相近的情况下,本文算法效果更好。通过对加入空间邻接关系效应与否进行对比分析,发现在考虑该效应的情境下,所有算例的利润值都有所提升,并且随着上架产品种类数增多,利润及其增量呈现先增后减的趋势。关键词:二维货架;空间分配;空间邻接关系;随机密钥;遗传算法中图分类号:C 934 文献标识码:AA Two-dimensional Shelf Space Allocation Problem Cons
3、idering Products Spatial Adjacency RelationshipZHENG Lanlan1,2,WU Feng1,2*,BI Runfang1,2(1.School of Management,Xian Jiaotong University,Xian,Shaanxi 710049,China;2.The Key Lab of the Ministry of Education for Process Control and Efficiency Engineering,Ministry of Education,Xian,Shaanxi 710049,China
4、)Abstract:Shelf space allocation has always been the retail markets focus because of the shortage of shelf resources.First,a mixed-integer non-linear programming model was established for the two-dimensional shelf space allocation problem with the influence of the product spatial adjacency relations
5、hip(SAR).Secondly,an improved random key genetic algorithm(RKGA)was designed to solve the model.Finally,two-scale instances were simulated to verify it.Results show that the improved RKGA has superior performance over the benchmark genetic algorithm and Lingo.In small-scale instances,the improved RA
6、GA has significantly improved solving accuracy and efficiency compared to Lingo.In large-scale instances,it also performs better when the convergence time is similar to benchmark GA.The profit value of all instances has increased by adding SAR effect.As the 文章编号:1007-5429(2023)02-0090-09DOI:10.19495
7、/ki.1007-5429.2023.02.010收稿日期:2021-07-14基金项目:国家自然科学基金项目(71871177)作者简介:郑兰兰(1986),河北沧州人,博士研究生,主要研究方向为货架管理。E-mail:。*通信作者:吴锋,教授,博士,主要研究方向为外包控制与决策、智能制造。E-mail:。-90第 2期工 业 工 程 与 管 理number of products increases,the profit and its increment appear to increase first and then decrease.Key words:two-dimensiona
8、l;shelf space allocation;spatial adjacency relationship;random key;genetic algorithm1 引言 随着O+O(Online+Offline)商业模型的兴起,实体零售成为新一轮的热点被关注。线下购买的沉浸感和体验感增加了购买速度和满意度,同时减少了退货,提高了运营效率。合理和优雅的货架陈设成为和顾客增进感情的第一条纽带,也成为彰显实体商店级别和增强吸引力的手段1。然而实际中,由于店面的面积、人体工程学考量等因素影响,货架的长宽高都受到限制,因此货架空间也被称作实体商店“最昂贵的资源”2。二维货架分配问题由多个相互联系
9、的背包问题组成。展示空间对需求的不确定影响,以及商品之间错综复杂的替代互补关系更加剧了问题的难度。另外在实际中,由于每种商品上架的数量限制、商品间陈列规则限制、货架容量限制等,随着问题规模的增大,问题的复杂度急速上升。如何用科学的方法获取关键因素,用有效的算法找到最优货架空间分配方案,使有限的货架空间创造更高的收益成为关键。在以往的研究中,研究者们首先用实证研究验证了陈列空间与产品销售之间的关系。DREZE等3估计了一个log-log模型,使用销售额的对数作为因变量,空间弹性和位置影响作为两组自变量,验证了货架重组和产品组合重组对销售的影响,得到了增加产品的展示空间可以增加产品销售的结论,并指
10、出平行于视线的货架层为最佳陈列位置。VAN等4使用分层贝叶斯模型研究了货架陈列和销售额之间的关系,使用丰富的货架布局的描述,如陈列数目、纵向位置、横向位置以及产品特征等,揭示了它们和市场营销工具(如价格、促销方案等)之间的依赖关系。在实证研究揭示出的非线性关系基础上,CORSTJENS和DOYLE5首次建立了货架空间分配的优化模型,包含了主效应、空间弹性和交叉弹性,并采用分支定界方法进行求解,为该领域的模型化研究奠定了数学基础。HWANG等6在此基础上考虑了纵向位置对于需求的影响,采用离散参数进行描述,并使用了梯度搜索和遗传算法求得了满意解。接着,HWANG 等7在接下来的研究中使用了三次多项
11、式来描述连续的纵向位置影响,研究了货架可连续分割情形下的空间分配问题。HANSEN等8则增加了货架横向位置影响的考量,对比了元启发式算法、启发式算法在求解非线性目标函数时的性能。BAI等2综合考虑了主效应、自身和交叉空间弹性以及位置影响,建立了二维货架陈列模型,并使用基于模拟退火的超启发式算法进行求解。综上所述,目前基于货架分配问题的模型方法中,基本围绕产品陈列空间和位置两大因素展开。虽然著名的啤酒尿布营销案例反映了产品上架时邻接关系的重要性,但是至今还没有在优化模型中体现。除了实际案例研究,近来,学者们也开始致力于找出邻接关系的重要性。CHEN等9用关联分析方法发现空间相对位置和产品销售之间
12、隐含的关系。GU和LIU10探讨了两个制造商提供的产品和需求的匹配概率相同的情形,零售商通过把竞争产品陈列在相隔较远的地方来获得较大的利润。OZGORMUS 和 SMITH11采用关联分析方法,找到各个产品品类间的邻接偏好关系,给2M商店提出了区块布局设计方案。ZHAO等12在货架展示和库存控制联合优化问题中考虑了产品陈列的空间关系影响,不过衡量粒度过粗(是否在同一货架),并且没有给出明确的数学表达。本文根据以上研究,定义了产品空间邻接关系因子,建立了非线性整数规划模型,采用基于随机密钥的遗传算法求解,并通过算例研究进行算法效果和效率的比较,为零售商货架陈列策略提供有益参考。2 模型建立 2.
13、1问题描述与分析考虑实体商超中单期货架分配问题,共有M层货架和N种候选上架产品。每层货架拥有固定宽度和高度,每种产品上架数量有限制(最低和最高横向陈列数)。由于产品之间错综复杂的关联性,-91第 28 卷 郑兰兰,等:考虑空间邻接关系的二维货架空间分配问题研究不同的产品邻接关系可能都会导致对需求刺激不同。如对于替代产品,相对位置远可以增大消费者搜索成本,降低竞争性。而对于互补产品,相对近的距离则可以促进产品的组合销售,同时增加销量。本文是在综合考虑产品陈列数量、货架位置以及产品之间邻接关系基础上,给出综合货架空间分配优化方案。基于以上问题描述,做出如下假设:(1)考虑满货架策略情形,即产品总是
14、能及时补货不出现缺货;(2)同一种产品只能陈列在一层货架上,不考虑跨层摆放;(3)同一种产品摆放在一起,不穿插或间隔;(4)产品在同一货架层可堆叠摆放以扩大二维展示区域。另外对符号和变量做如下定义。(1)参数符号i:基本需求规模参数,即所有产品都获得相同的零售支持且不考虑缺货情形下,产品i的基本市场需求13i:产品i的个体空间弹性,即产品i单位需求的相对变化与所陈列空间的相对变化之比14,反映产品i的需求随陈列空间变化的趋势ij:产品i与产品j的交叉空间弹性,反映产品j的陈列空间变化对产品i的需求的影响,详见 15hi,li:产品i的高度和长度lbi,ubi:产品i的最低和最高上架横向限量pi
15、:产品i的单位利润Hk,Lk:货架k的高度和长度k:货架k的位置影响因子ik:产品i在货架层k的堆叠系数,ik=|Hkhi(2)决策变量zik:产品i摆放的货架层指示。如果产品i摆放在货架层k上 zik=1,否则为0sik:产品i出现在货架k层的顺序号nik:产品i出现在货架层k的横向数量2.2数学模型(1)产品空间邻接关系因子定义确定了产品i的陈列货架k*(zik=1时k的取值)以及陈列顺序sik*,可以得到产品i在该货架的横向起始位置为:xi=|j=j|sjk*sik*ljnjk*,sik*20,sik*=1(1)产品i的纵向起始位置为:yi=|k=1k*-1Hk,k*20,k*=1(2)
16、综上,求得产品i在货架上的重心位置为(xCGi,yCGi):xCGi=xi+12linik*,yCGi=yi+12hiik*(3)计算得到产品i和j的实际空间相对距离为:rij=(xCGi-xCGj)2+(yCGi-yCGj)2(4)定 义 空 间 邻 接 关 系 因 子(spatial adjacency relationship,SAR)为:SARij=vijrij(5)其中:vij为产品i的和产品j之间的视觉邻接距离(visual adjacency distance,VAD),定义为消费者在商店中可以看到邻接产品的视线距离,它取决于货架的展示模式和消费者在商店中的位置,具体估计方法见文
17、献 12;而SAR为视觉邻接距离v和实际空间距离r的比值,当SAR1时,表示产品视觉上更加接近,此时对于互补产品来讲,更容易促进产品的销量,而对于替代产品则会产生抑制作用,反之同理。(2)目标函数产品的需求函数基于BAI等2的研究,在考虑市场规模基本效应、个体空间弹性效应、交叉空间弹性效应基础上,增加货架位置效应,需求函数如下:Di(zik,sik,nik)=i(ni)ij=1,jiN(nj)ijSARiji(6)其中,产品i(j)的上架陈列总数量为:ni(nj)=k=1Mnik(njk)ik(jk)zik(7)产品i的货架位置效应取决于产品所在的货架层的位置影响因子k:i=k=1Mkzik(
18、8)因此,目标函数为:-92第 2期工 业 工 程 与 管 理Max(zik,sik,nik)=i=1NpiDi(zik,sik,nik)(9)i=1NniklizikLk,k(10)k=1Mzik=1,i(11)lbik=1Mnikzikubi ,i(12)sik,nikZ,i,k(13)zik0,1,i,k(14)其中:式(10)是货架的容量限制;式(11)表明产品不跨层摆放;式(12)是产品的横向陈列数目的要求,即规定了产品的可见度范围;式(13)和式(14)列出了决策变量的类型和取值范围。定理 1 模型式(1)式(14)对应的考虑产品空间邻接关系的二维货架空间分配问题为 NP 难问题。
19、证明 模型式(1)式(14)描述的问题可以看成由货架选择、顺序排列和空间分配三个子问题组合而成。其中:货架选择问题的决策变量为zik,相关计算和约束条件为式(8)、式(11)和式(14);顺序排列的决策变量为sik,相关计算和约束条件为式(1)式(5)及式(13);空间分配的决策变量为nik,相关计算及约束条件为式(6)、式(7)、式(10)、式(12)和式(13);目标函数为式(9)。在陈列顺序已知(即sik确定)的情况下:当m=1时,问题退化为空间分配问题,属于非线性背包(nonlinear knapsack,NLK)问题,此时,经典的线性背包问题是该问题的特例,因此 NLK 问题也属于N
20、P难16;而当m2时,问题退化为货架选择和空间 分 配 联 合 优 化,成 为 多 重 非 线 性 背 包 问 题(multiple non-linear knapsack problem,MNLKP),该问题已经被证明至少为强NP难问题17。因此,模型式(1)式(14)对应的带有空间邻接关系的货架空间分配问题为NP难问题。3 求解方法 由于该问题属于NP难问题,同时求解受到货架层数、产品数目、货架的横向和纵向空间大小以及多个其他限制条件等影响,只能在较小规模时利用Lingo求得最优解,而随着问题规模的增大,在有限时间内得到可行解都变得十分困难。综合前人研究,遗传算法在非线性的离散多维问题中有
21、良好的表现,同时由于该问题包含顺序排列子问题,在编码中使用随机密钥可以使染色体更好地表达出可行解,为染色体的交叉变异提供了便利。3.1基于随机密钥的二维编码采用二维数组编码方式,每个染色体为5n个基因组成。自下而上分别为产品索引、货架层、产品上架横向最低限、产品陈列增量、随机密钥。随机密钥的使用不仅可以指示产品的陈列顺序从而计算得到产品的相对位置,也可以在保证可行性的情况下增加解的多样性。该编码形式的好处在于限制编码维度前提下,能将模型中的约束尽可能包含进来,同时可以和决策变量进行简洁的互相转化。如R4陈列货架的编码指示决策变量zik,同时可以合并约束式(11)和式(14),R2和R3的编码包
22、含了约束式(12)和式(13),两行之和转化为决策变量nik,而R1的编码则可以转化为决策变量 sik。图1为一个染色体的示例,假设有 3 层货架和 6 种产品。对于产品1而言,陈列在货架2上,陈列横向最低限是1,陈列增量为0。陈列在货架2上面的产品为产品3以及产品6。随机密钥指示三种产品排序为产品1、产品6和产品3。3.2初始解生成根据编码规则,可以初步将染色体分为指示行(R1,R5),约束行(R3)以及控制行(R2,R4)。约束行和指示行可为后续算子操作提供便利,直接按照已有数据或者随机生成即可。生成可行解的关键是如何生成控制行。采取逐一渐进生成方法,具体生成步骤如下:Step 1 生成指
23、示行R1、R5和约束行R3,初始设置R2和 R4行为零。Step 2 按照随机密钥R1顺序排列染色体各行,得到新的R?1R?5。Step 3 按照排列后的序号R?i5,随机生成一个货架序号mi,验证i|R?i4=miR?i3Lmi,即所选货架的图1染色体编码示例-93第 28 卷 郑兰兰,等:考虑空间邻接关系的二维货架空间分配问题研究容量是否能够满足陈列该产品横向最低限的要求。Step 4 若满足,则顺序执行R?i+15;否则,重新执行Step 3。Step 5 按照排列后的产品序号R?5,重复Step 3和Step 4,直至R?4全部生成。Step 6 按照R?i5和R?i4,在满足R?i2
24、+R?i3ubi以及i|R?i4=mi()R?i2+R?i3L条 件 下,生 成 陈 列增量R?i2。Step 7 重复Step 6,直到R?2全部完成。Step 8 按照产品顺序R5重新排列染色体。3.3遗传操作(1)适应度计算适应度的衡量是进行遗传操作的基础,在解的进化判定中起到重要作用。本文设定目标函数式(9)为适应度函数计算式。(2)选择选择是根据“适者生存”法则对可行解优胜劣汰的过程,本文使用锦标赛法对父代种群进行选择。该方法随机选取两条染色体,选择适应度较好的一条,放入子代种群中,选择后的子代种群规模保持不变。(3)交叉交叉算子的有效性影响到算法的全局搜索效率。为了满足进化策略中的
25、染色体多样化的需求,增加全局搜索范围,使算法脱离早熟陷阱,本文采用模式交叉法。首先根据交叉概率确定需要交叉的次数Nindpc/2,其中Nind为种群数目。在交叉之前,先随机生成一个模式,同时另一个模式自动匹配。然后从父代种群随机选取两个个体,依据模式指示进行交叉。相比于单点交叉,模式交叉法可以增加染色体的变异后可行概率,同时使变异更加多元化。如图2为一个模式交叉的例子。(4)变异变异算子在算法的局部搜索中起到关键作用,为了增大算法局部搜索能力,不错过区域内的优解,变异采用互换变异和均匀变异两种方式。首先根据变异概率来确定突变基因的数量Nindpm。对R1随机密钥采用互换变异的方法,即对同一货架
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 考虑 空间 邻接 关系 二维 货架 分配 问题 研究 郑兰兰
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。