自动化立体仓库“一车双箱”模式订单分批与存取决策优化
李浩霖 谭哲一 汪小帆 镇璐
摘 要：自动化立体仓库使用双工位穿梭车与升降机可实现两件料箱同时搬运的“一车双箱”存取模式。本文针对“一车双箱”存取模式下穿梭车立体仓库拣选作业订单分批与存取选择问题，建立数学规划模型，并设计了双层变邻域禁忌搜索算法求解问题。双层变邻域禁忌搜索算法中，外层变邻域禁忌搜索算法优化订单分批决策，内层启发式算法则可生成存取决策及时序安排。根据数值实验结果，该算法能在一定時间内得到满意解。与传统“一车单箱”存取模式相比，“一车双箱”存取模式可显著提高存取效率。
关键词：穿梭车立体仓库;订单分批;存取选择;变邻域禁忌搜索算法
中图分类号：TP18文献标识码：A文章编号：2097-0145（2022）02-0041-08doi：10.11847/fj.41.2.41
Integrated Optimization of Order Batching and Retrieving Location
Assignment in Automated Storage and Retrieval Systems
with Double-load Storage and Retrieval Mode
LI Hao-lin， TAN Zhe-yi， WANG Xiao-fan， ZHEN Lu
（School of Management， Shanghai University， Shanghai 200444， China）
Abstract：The application of double-load shuttles and lifts in shuttle-based storage and retrieval systems makes it possible to retrieve or store two unit loads simultaneously， and introduces double-load storage and retrieval mode in warehouse operation. This paper investigates the operational problem of double-load mode in shuttle-based storage and retrieval systems， and proposes a mixed-integer linear programming model to jointly optimize the order batching and retrieving assignment. An efficient two-stage variable neighborhood tabu search algorithm is developed for problem solving. The upper level of the algorithm is a variable neighborhood tabu search algorithm developed for optimizing order batching assignment. The lower level of the algorithm is a heuristic algorithm for generating the retrieving plan and sequence. Numerical experiments show the efficiency of the proposed algorithm. Compared with traditional single-load storage and retrieval mode， the double-load storage and retrieval mode can significantly improve system efficiency.
Key words：shuttle-based storage and retrieval systems; order batching; retrieving problem; variable neighborhood tabu search algorithm
1 引言
近年来，智能仓库系统极大地变革了仓储运作模式，为电子商务等行业的发展提供了高效的物流服务支持。智能仓库依靠多种多样的智能化设备，实现了仓库作业的自动化与集成化。在众多智能仓库系统中，穿梭车系统具有高速度、高灵活性、节能的特点，广泛应用于仓库内部水平方向物料搬运。部分仓库将穿梭车系统与高层货架相结合，对传统自动化立体仓库进行创新，设计了穿梭车立体仓库（Shuttle-based storage and retrieval systems，见图1）[1]。穿梭车立体仓库应用穿梭车与升降机协同接力完成存取作业，丰富并发展了智能仓库系统。多数文献围绕穿梭车与升降机等核心设备及其运行特征，论证了穿梭车立体仓库在能耗、行程时间、系统投资等效率指标上的优势[2，3]，并建立了系统评价模型，为系统设计等战略决策提供决策参考[4～8]。一些文献针对穿梭车立体仓库中工作量平衡、巷道拥堵等运作问题展开探讨[9～11]。一般的穿梭车立体仓库中，穿梭车与升降机每次存取作业只可运载一件料箱，以“一车单箱”存取模式（下文简称“单箱模式”）进行。部分仓储企业在穿梭车立体仓库中应用了双工位穿梭车及双工位升降机（见图1），实现了两个料箱同时存取的“一车双箱”存取模式（下文简称“双箱模式”）。宋振波[12]建立了双载位单深位多层穿梭车系统的出库作业时间模型，并研究了储位分配与任务调度优化等相关问题。双箱模式一般应用于同层同巷道料箱的存取作业，而部分零散料箱存取作业则以单箱模式执行。双箱模式可减少仓库存取作业的执行次数，降低大规模料箱存取作业的时间消耗与总存取成本。双箱模式需对哪些料箱在何时使用双箱模式进行决策，这一决策过程直接改变了料箱存取选择决策机制，同时与仓库订单拣选需求密切相关。41A2FBCC-B472-4D65-9D48-38B623931BB4
仓库出库作业工作量较大，作业较为复杂，因而常需对订单及存取任务进行排序、分批等方式处理[13，14]。订单分批的要义在于整合不同订单中的零碎需求，以批次为单位进行拣选，以降低需求的零碎性与拣选复杂程度，减少拣选作业中的无用功。基于电商仓库的背景，许多学者对传统人到货仓库中订单分批与拣货路径[15]、订单分批与存储策略[16]、订单分批与配送[17]等问题的集成优化问题展开了研究。智能仓库系统中，机器人订单拣选系统的订单分批与货位分配[18]、存取选择[19]、机器人排程[20]等问题的集成优化也得到了学者关注。订单分批应用于穿梭车立体仓库等智能仓库系统，可通过改变各批次需求特征影响料箱存取决策，减少料箱、托盘出库及回库作业次数，同时为双箱模式应用创造条件。
通过归纳现有研究，可发现穿梭车立体仓库运营管理研究得到了国内外学者的广泛关注，订单分批操作在穿梭车立体仓库拣选中具有实践价值。现有文献中，穿梭车立体仓库相关研究多通过建立解析模型分析系统行程时间，或通过仿真等方法研究穿梭车路径规划、死锁控制等问题，针对双箱模式下穿梭车立体仓库的研究较少。尽管已经有学者研究了自动化仓库系统的订单分批问题，然而穿梭车立体仓库的订单分批研究较为少见。本文以“一车双箱”存取模式穿梭车立体仓库为研究主体，研究了双箱模式下仓库拣选作业的订单分批决策与存取选择决策，并运用数学规划方法建立模型，设计了双层变邻域禁忌算法求解问题，通过数值实验验证了算法的有效性及双箱模式对系统运行效率的提升。本文的创新点可归纳为以下三点：（1）本文研究了穿梭车立体仓库双箱模式，丰富了智能仓库的运作研究。（2）实现了穿梭车立体仓库中的订单分批决策与存取选择决策的集成优化，为仓库拣选作业提供了指导。（3）设计的双层变邻域搜索算法具有较高的求解效率，为问题的实际应用提供了有效的工具。
2 问题描述
本文从订单拣选总成本的角度研究了双箱模式穿梭车立体仓库订单拣选，通过存取决策与订单分批的优化，实现系统效率的提升。本节通过对穿梭车立体仓库流程介绍，阐述各部分决策之间的内在联系机理。
订单分批通过将不同待分拣订单组合为一个批次，整合不同订单不同品项的零散需求，以降低订单需求零散度与波动性，减少不必要的存取作业。订单分批为各拣货台提供了拣选任务的指导，各拣货台需按一定先后顺序执行分配的各批次拣选任务。受拣货台处理能力限制，每个批次的订单数量、每个拣货台执行的批次任务数量需限制在合理范围内。本文的订单分批决策包含着将订单组合为批次、将批次任务分配至拣货台的决策问题，同时还关联着各拣货台各批次任务执行顺序。为简化决策流程，本文将每个拣货台所有可执行批次进行统一编号，并按照编号顺序规定了各拣货台批次执行先后顺序，建立起批次-拣货台间的对应关系，将订单分批决策定义为将订单分配至某一编号的批次，从而将拣货台分配、批次执行顺序决策合并至订单分批决策中。
订单分批后需进行料箱存取作业计划。穿梭车立体仓库中所有零散的商品由料箱装载，并存储于高层货架内的指定库位。订单拣选中需根据各批次需求对料箱执行取货作业，使用穿梭车、升降机以单箱模式或双箱模式协同接力将料箱出库，再由传送带送至各拣货台。料箱出库后若有剩余货物即为散数箱，需执行存储作业（即取货作业的相反操作）将散数箱回库至原货位等待后续拣选。料箱内若无剩余货物则为空箱，不需回库。存取决策中还包含着料箱作业时序安排问题，即对料箱在各批次中的取货作业开始时间、存储作业完成时间、料箱间存取作业先后顺序进行决策。所有作业都必须在一定的时间窗限制内完成。升降机处以串行作业的顺序依次执行各存取任务，而不同层的穿梭车可并行作业。根据作业关系可得出各存取作业间最短时间间隔，并通过时间间隔卡控的方式，保证穿梭车与升降机在执行完前一个任务后，有充足时间运动到下一个任务的作业位置。
仓库运营管理决策常关注时间及成本两个目标。时间目标直接体现了仓库系统的运行效率，常与订单排序等调度决策相关联。成本目标则
从经济角度考察仓库系统运行。穿梭车立体仓库中，穿梭车与升降机执行存取作业时需消耗电能，并随之产生相应的存取成本。本文对存取成本的控制，可直接减少电能消耗，为仓库系统节能減排目标的实现提供指导。根据双箱模式所使用设备可知，双箱模式只在货位-货架出入口区域执行，因此本文以货架出入口为界，将料箱出库与回库的存取成本拆分为两部分，即货架区域存取成本及拣货台区域存取成本。货架区域存取成本和料箱货位直接相关，货位距离货架出入口越远，则货架区域存取成本越高，耗时越长。拣货台区域存取成本与拣货台位置有关，拣货台距离货架出入口越远，则成本也越高。为简化模型，本文利用前述批次与拣货台间的对应关系，将拣货台区域存取成本转化为各批次在拣货台区域的存取成本表示，即根据各批次所对应的拣货台，计算出该批次在拣货台区域的存取成本。
为简化问题，本文根据上述问题设定，提出如下假设：（1）所有订单的需求信息均为已知信息。（2）每一料箱内只可存储一个品项的商品，料箱内商品数量已知，各料箱具有固定的库位。（3）考虑到调度复杂度与升降机运行效率，双箱模式只可应用于同一层料箱的取货或存储作业。（4）料箱存取成本与搬运时间根据历史运行数据归纳，取穿梭车、升降机、传送带在不同工况下的运行成本平均值，因而假设单箱双箱模式存取成本相同，作业耗时相同，与穿梭车、升降机所承载的料箱数量与重量、运动方向无关。
3 数学模型
3.1 符号说明
模型中所涉及到的符号及其含义如下：
集合与下标。
I为所有料箱的集合，下标为i。
P为所有品项的集合，下标为p。
O为所有订单的集合，下标为o。
B为所有批次的集合，下标为b。y（b），y′（b）表示开始与结束的虚批次，并由此定义集合B0=B∪{y（b）}，BT=B∪{y′（b）}。41A2FBCC-B472-4D65-9D48-38B623931BB4
参数。
dp，o为订单o中品项p的需求量。
ui，p为料箱品项参数，若料箱i中产品品项为p，则为1，反之为0。
ci为料箱i从其货位到出入口间的搬运成本。
cb′为料箱在批次b对应拣货台与货架出入口间的搬运成本。
qb1，b2，若批次b2允许在批次b1拣选完成后开始拣选，则为1，反之为0。
zi1，i2，若箱i1与箱i2位于同一层，且i1存取成本大于i2，则为1，反之为0。
ki，b为箱i在批次b的最短处理时间。
k′i，b为箱i在批次b允许最长处理时间。
li1，i2为箱i1与i2出库（回库）作业最短时间间隔。
l′i1，i2为箱i1某批次回库作业与箱i2某批次出库作业最短时间间隔。
l″i1，i2为“一车双箱”操作时箱i1与i2出库（回库）作业的时间间隔。
决策变量。
βo，b，0-1变量，若订单o被分配至批次b，则为1，反之为0。
αi，b，整数变量，为箱i在批次b中的取货量。
γi，b，0-1变量，若箱i需在批次b拣选，则为1，反之为0。
ιi，b，若箱i需在批次b拣选，则该变量表示箱i批次b拣选作业的开始时间。
κi，b，若箱i需在批次b拣选且料箱未被取空，则该变量表示箱i批次b拣选作业的结束时间。
δi，b，0-1变量，若箱i在批次b拣选后被取空，则为1，反之为0。
λi，b1，b2，整数变量，若箱i先在批次b1拣选，后在批次b2拣选，则为批次b1取货量，反之为0。
θb1，b2，0-1变量，若批次b1完成时间早于批次b2开始时间则为1，反之为0。
νi1，b1，i2，b2，0-1变量，若箱i1批次b1拣选开始时间需早于箱i2批次b2拣选开始时间则为1，反之为0。
ξi1，b1，i2，b2，0-1變量，若箱i1批次b1拣选结束时间需早于箱i2批次b2拣选结束时间则为1，反之为0。
οi1，b1，i2，b2，0-1变量，若箱i1批次b1拣选结束时间需早于箱i2批次b2拣选开始时间则为1，反之为0。πi1，b1，i2，b2，0-1变量，若箱i1批次b1与箱i2批次b2取货作业可通过双箱模式取货则为1，反之为0。
ρi1，b1，i2，b2，0-1变量，若箱i1批次b1与箱i2批次b2存储作业可通过双箱模式存储则为1，反之为0。
3.2 数学模型
min∑i∈Ici∑b∈B（2γi，b-δi，b-∑i2∈I∑b2∈B
（πi2，b2，i，b+ρi2，b2，i，b））+∑b∈Bcb′∑i∈I（2γi，b-δi，b）（1）
s.t.∑b∈Bβo，b=1o∈O（2）
∑o∈Oβo，b≤nb∈B（3）
∑i∈Iui，pαi，b=∑o∈Odp，oβo，bp∈P，b∈B（4）
αi，b≤Mγi，bi∈I，b∈B（5）
M（θi，b1，b2-1）≤ιi，b2-κi，b1≤Mθi，b1，b2i∈I，b1，b2∈B（6）
θi，b1，b2≤qb1，b2i∈I，b1，b2∈B（7）
ιi，b+ki，b（γi，b-δi，b）≤κi，b≤ιi，b+ki，b′（γi，b-δi，b）i∈
I，b∈B（8）
si-∑b1∈Bλi，b1，b≤M（1-δi，b）i∈I，b∈B（9）
δi，b≤γi，bi∈I，b∈B（10）
λi，b1，b2≤Mθi，b1，b2i∈I，b1，b2∈B，b1≠b2（11）
αi，b1-M（1-θi，b1，b2 ）≤λi，b1，b2≤αi，b1i∈I，b1，b2∈B，b1≠b2（12）
λi，b，b=αi，bi∈I，b∈B（13）
ιi1，b1-ιi2，b2≥li1，i2-M（2+νi1，b1，i2，b2 -γi1，b1-γi2，b2）i1，i2∈I，i1≠i2，b1，b2∈B（14）
κi1，b1-κi2，b2≥li1，i2-M（2+ξi1，b1，i2，b2-γi1，b1-γi2，b2+δi1，b1+δi2，b2）i1，i2∈I，i1≠i2，b1，b2∈B（15）
κi1，b1-ιi2，b2≥l′i1，i2-M（2+οi1，b1，i2，b2+δi1，b1-
γi1，b1-γi2，b2）i1，i2∈I，i1≠i2，b1，b2∈B（16）
νi1，b1，i2，b2+νi2，b2，i1，b1 -πi1，b1，i2，b2-πi2，b2，i1，b1=1i1，i2∈I，i1≠i2，b1，b2∈B（17）
ξi1，b1，i2，b2+ξi2，b2，i1，b1-ρi1，b1，i2，b2-ρi2，b2，i1，b1=1i1，i2∈I，i1≠i2，b1，b2∈B（18）
οi1，b1，i2，b2+οi2，b2，i1，b1=1i1，i2∈I，i1≠i2，b1，b2∈B（19）
2πi1，b1，i2，b2≤zi1，i2（γi1，b1+γi2，b2）i1，i2∈I，b1，b2∈B（20）
2ρi1，b1，i2，b2≤zi1，i2（γi1，b1-δi1，b1+γi2，b2-δi2，b2）i1，i2∈I，b1，b2∈B（21）
∑i2∈I∑b2∈B（πi，b，i2，b2+πi2，b2，i，b）≤1i∈I，b∈B（22）
∑i2∈I∑b2∈B（ρi，b，i2，b2+ρi2，b2，i，b）≤1i∈I，b∈B（23）41A2FBCC-B472-4D65-9D48-38B623931BB4
M（πi1，b1，i2，b2-1）-l″i1，i2≤ιi1，b1-ιi2，b2≤M（1-πi1，b1，i2，b2）-l″i1，i2i1，i2∈I，b1，b2∈B，i1≠i2（24）
M（ρi1，b1，i2，b2-1）+l″i1，i2≤κi1，b1-κi2，b2≤M（1-ρi1，b1，i2，b2）+l″i1，i2i1，i2∈I，b1，b2∈B，i1≠i2（25）
αi，b≥0i∈I，b∈B（26）
γi，b，δi，b∈{0，1}i∈I，b∈B（27）
βo，b∈{0，1}o∈O，b∈B（28）
λi，b1，b2≥0i∈I，b1，b2∈B（29）
θi，b1，b2∈{0，1}i∈I，b1，b2∈B（30）
ιi，b，κi，b≥0i∈I，b∈B（31）
νi1，b1，i2，b2，ξi1，b1，i2，b2，οi1，b1，i2，b2，πi1，b1，i2，b2，
ρi1，b1，i2，b2∈{0，1}i1，i2∈I，b1，b2∈B，i1≠i2（32）
（1）式表示本模型的目标为最小化存取总成本，即各存取任务货架区域存取成本与拣货台区域存取成本的和。（2），（3）式表示每个订单能且只能被分配至一个批次，每个批次最多可包含n个订单。（4）式通过各批次各品项拣选需求使订单分批与存取选择决策相关联。（5）式表示箱存取与取货量的逻辑关系。（6）式用以确定某一箱各批次拣选作业间的时间先后顺序关系。（7）式保证各料箱各批次存取顺序的合理性。（8）式定义各箱各批次拣选开始时间与结束时间的时间差关系。（9），（10）式用于判断料箱在某一批次是否被取空。（11）～（13）式计算料箱各批次拣选作业结束后的剩余货量。（14）～（16）式要求两料箱两批次存取作业未以双箱模式进行时需根据时间顺序满足最小时间间隔限制。（17）～（19）式定义了两料箱两批次非双箱模式时存取作业时序关系的唯一性。若两料箱两批次存取任务以双箱模式进行，则不受非双箱模式时序关系限制。（20），（21）式表示双箱模式需满足双箱模式的要求。（22），（23）式确保双箱模式只可对两个料箱执行。（24），（25）式定义双箱模式时两箱的存取时间差。约束（26）～（32）式定义了各决策变量。
4 算法设计
根据前序章节论述，本文主要决策包含订单分批与存取选择两大部分。与常见的订单分批问题类似，本文问题亦为NP-hard问题，采用商业求解工具或精确解算法难以在较短时间内求解实际应用中的大规模问题。现有订单分批研究多采用变邻域搜索、禁忌搜索算法等启发式算法求解问题[16，21～23]。本文根据问题特征设计了基于变邻域禁忌搜索算法的双层启发式算法，其中外层针对订单分批问题，应用变邻域禁忌搜索算法迭代优化，内层则设计了启发式算法，输出相应的存取方案及存取总成本。本文算法流程整体思路如下：
（1）应用初始解算法生成初始订单分批方案。（2）使用外層算法进行订单分批决策邻域变换，并应用内层算法计算适应度值，对比选出局部最优解，然后多次迭代，通过禁忌策略避免在后续迭代过程中重复搜索该局部最优解。（3）若算法在多次迭代后无法进一步优化现有局部最优解，则触发扰动策略，生成新的初始解，并应用新初始解重新执行第二步操作，避免陷入局部最优。
4.1 外层变邻域禁忌算法设计
本文外层算法使用变邻域禁忌算法，通过不同邻域结构对解向量进行邻域变换，搜索局部最优解，不断迭代，逐步向全局最优解靠近。本文外层的变邻域禁忌算法流程如算法1所示。
算法1外层变邻域禁忌搜索算法
输入：最大迭代次数iterMax，历史最优解保持不变迭代次数阈值iterHisMax
输出：全局最优解
1.初始化已迭代次数iter←0， 历史最优解保持不变的迭代次数iterHis←0， 清空禁忌表tabuList
2.调用种子算法得到初始解与扰动策略备选解，并调用内层算法计算初始解的适应度值，将初始解赋值于局部最优解curr与历史最优解hist
3.While iter 4.通过邻域变换生成一组候选解，并使用内层算法计算候选解适应度值，选取适应度最优候选解作为候选最优解cand 5.If candtabuList，或cand∈tabuList，且cand满足蔑视准则，then 6.curr←cand 7.End if 8.If curr优于hist， then 9.hist←curr， iterHis←0 10.Else iterHis←iterHis+1 11.End if 12.If iterHis=iterHisMax， then 13.触发扰动策略，重新生成当前解，iterHis←0 14.End if 15.iter←iter+1 16.End while 17.Return hist 4.1.1 编码策略 外层算法选取订单在各批次的分配决策变量β作为关键变量，并对这一变量使用自然数编码方式降维，以便后续算法计算与迭代。定义共有B·n个元素的解向量L表示订单分批的解。解向量中每一个元素代表一个订单的订单编号，前n个元素表示批次1所分配的订单，第 n+1到2n个元素表示批次2所分配的订单，以此类推，同时使用占位符-1表示某一元素不对应任何订单。根据（4）式可知，每个订单只可被分配到一个批次，因而此编码策略中，除占位符-1外，其余元素的数字不能重复。41A2FBCC-B472-4D65-9D48-38B623931BB4 4.1.2 初始解的确定 为生成迭代初始解，本文对订单分批中常用的启发式算法——种子算法，应用了不同的标准，即存取次数标准与平均存取成本标准进行改进，设计了本文的初始解算法。批次b中包含的所有订单可使用集合Ob表示，而品项p料箱中初始存货量可通过sp表示。存取次数标准以订单存取次数作为算法计算的标准，单独执行每一个订单存取作业的存取次数为TSRo=∑p∈P「dp，osp，其中「a为向上取整函数。算法首先选取订单存取次数最少的订单作为种子，然后选取与目前批次内订单组合后压缩率最低的订单加入批次内，直到该批次达到订单数量上限后停止该批次分批，开启新一批次分批，其中订单批次b的压缩率为 CRTOb=∑p∈P「∑o∈Obdp，osp∑o∈ObTSRo 压缩率数值越低，表示这一分批方案的存取次数节约量越大。平均存取成本标准以存取次数標准为基础，将每一品项的平均存取成本 CPp=∑i∈I∑b∈Bui，p×ci，b|B|×∑i∈Iui，p 作为权重，对订单存取次数进行加权，得到单独执行每一个订单存取作业的存取成本TSRo=∑p∈P「dp，osp×CPp与将几个订单合并为同一批次后批次Ocomp的压缩率 CRTOb=∑p∈P「∑o∈Obdp，osp×CPp∑o∈ObTSRo 两套标准一般可生成两组不同的初始订单分批方案，此时应用内层启发式算法，求得两订单分批方案各自的适应度值，选取存取成本最低的一组为初始解进行后续迭代，将另一组解暂存作为后续扰动策略中所运用的备选解，在触发扰动策略时调用。 4.1.3 变邻域搜索策略 根据前述解向量的编码策略与解的结构特征，本文选取了点交换策略与2-opt策略用于邻域变换。点交换策略随机选取解向量中属于不同批次的两个元素进行交换。2-opt策略随机选取解向量中至少包含三个元素，且各元素至少分别属于两个批次的连续片段，将该片段中元素以相反顺序排列。 4.1.4 禁忌搜索策略 本文将禁忌算法融合于变邻域算法中，以避免问题陷入局部最优。单次迭代禁忌表记录每次邻域变换的变换方式，以避免该次迭代中重复同一邻域搜索操作，并在该次迭代结束后清空。问题求解全局禁忌表记录每次邻域变换后求得的最优解，并保证在规定的长度内禁忌解无法被再次采用。通过这一策略，可避免算法在某一特定邻域结构上的无意义迭代，扩大搜索范围。本文禁忌搜索算法中应用了蔑视准则与释放准则。蔑视准则为若某邻域解的目标函数值小于当前全局最优解的目标值，无论该解是否在全局禁忌表中，该解均应作为下次迭代的初始解。释放准则为每次迭代中，全局禁忌表中的解均存在一定概率可被释放。当禁忌表长度达到一定阈值后，随着新的禁忌解的加入，旧禁忌解按照“先进先出”原则，从禁忌表中删去。 4.1.5 扰动策略设计 若某一局部最优解在经过一定迭代次数后无法被继续优化，则触发扰动策略，根据扰动策略生成新的解作为当前解，用于下一次迭代。扰动策略被触发时，首先检查是否有暂存扰动解，若有则调用扰动解，若没有则执行随机种子算法，随机生成新的扰动解与备选解。随机种子算法原理与本文初始解算法中的种子算法类似，其不同之处在于随机种子算法的“种子”解为待分配订单中随机选出的一个订单，其余流程与前述初始解算法类似。随机种子算法生成两备选解后，选取其中适应度较小的解替换当前解，适应度较大的解作为扰动策略备选解。 4.2 内层启发式算法设计 本文算法内层根据穿梭车立体仓库的存取作业特征设计了启发式算法，用于求解存取作业方案，具体包括如下三个步骤： 第1步 应用首次适应降序算法（First-Fit Decreasing Algorithm，FFD），得出各个批次需取货料箱γi，b与取货量αi，b。首次适应降序算法是装箱问题中的一个近似算法。本文问题中，每一批次每一品项的需求可视为装箱问题中的“货物”，而装载该品项产品的所有料箱则可视为容量为其初始货量的箱。本文的问题目标存取成本最小化与装箱问题中的目标使用箱数量最小化具有一致性，因而本文的存取选择问题即可转化为装箱问题进行求解。 第2步 基于第1步中求得的初步拣选方案，调整第1步求解结果，并据此求解变量δi，b，以及一车双箱方案πi1，b1，i2，b2与ρi1，b1，i2，b2。方案修正的基本思想为通过对需求进行拆分、重组，排序等方式，减少存取成本较高的料箱的存取次数，并充分利用取空与一车多件等存取成本节省方式。 第3步 根据前序两步骤得到的γi，b、πi1，b1，i2，b2与ρi1，b1，i2，b2，形成存取任务taskj，将排序问题转化为有 ∑i∈I∑b∈Bγi，b-∑i1∈I∑b1∈B∑i2∈I∑b2∈B（πi1，b1，i2，b2+ρi1，b1，i2，b2） 个客户点的旅行商问题，并应用内层的变邻域禁忌算法对这些任务进行排序。内层变邻域禁忌算法将各个存取任务作为客户点，形成存取任务的序列，并对存取任务序列运用点交换策略与2-opt策略进行邻域变换，逐步迭代寻找最优解。若某次迭代后求得的最优解小于等于存取时间限制，则可停止迭代，输出当前最优解，表示存取方案可行。若当前最优解大于存取时间限制，则进入下一步迭代，逐步寻找满足存取时间限制要求的解。若多次寻找仍无法找到满足存取时间限制要求的解，则表示该存取方案不可行。 5 数值实验 本文通过数值实验，检验本文算法有效性，并进行敏感性分析。本文研究所用实验平台CPU为Intel i7-6500U@2.50GHz，内存8GB，采用Windows 10 64位操作系统，在Visual Studio 2015环境中运用C#语言进行代码编写与实现。实验中调用了IBM ILOG CPLEX 12.6.1求解器。41A2FBCC-B472-4D65-9D48-38B623931BB4 5.1 算法測试 本节将本文提出的算法最优解与CPLEX求解器求得解、算法初始解的目标值进行比较，在不同问题规模下进行实验，验证算法的有效性。算例规模以|I|-|O|-|B|-|P|-|W|-n的形式表示，其中|W|表示拣货台数量。为保证可在适当时间内求得解，本文设定算法与CPLEX求解器的求解时间上限为7200秒。算法最大迭代次数为25次，每次生成候选解数量为10个，禁忌表长度为15，并设定若累计4次迭代后最优解未更新，则触发扰动策略，即历史最优解保持不变迭代次数阈值为4。 由表1可知，在小规模算例中，CPLEX能在多数算例中求得最优解。随着订单数量增加，CPLEX求解时间逐步增长，当料箱数量达到50个时，CPLEX已无法在7200秒时限内求得最优解。与此同时，本文设计的算法在小规模算例中平均求解时间55秒，在求解时间整体上优于CPLEX。另外本文设计算法在25个料箱的算例中可在较短时间内求得最优解，在50个料箱的算例中求得的解可接近或优于CPLEX在7200秒内求得的可行解。 大规模算例中，CPLEX已无法在7200秒内求出可行解。由表2可计算出本文算法平均求解时间336秒，这说明本文算法可在一定时间内求解大规模问题。本文小规模算例中初始解与最优解平均相对差异为10.57%，大规模算例中初始解与最优解平均相对差异为10.49%，本文算法在大规模问题中依然保持了一定的优化能力，因而本文设计的算法表现出了较强的实际规模问题求解能力。 5.2 “一车双箱”模式的有效性分析 本文通过敏感性分析实验，比较双箱模式与传统单箱模式在拣选同样订单时的拣选成本，说明双箱模式对总拣选成本的影响。实验使用本文模型及算法进行，而单箱模式实验则通过在本文模型中令πi1，b1，i2，b2与ρi1，b1，i2，b2为零，使穿梭车以单箱模式运行，得出“一车单箱”的拣选成本。由表3中结果可知，与单箱模式相比，双箱模式平均可节省约20%存取成本。 6 结论与启示 本文研究了双箱模式下穿梭车自动立体仓库的订单分批决策与存取决策的集成优化问题，建立了以总存取成本最小化为目标的混合整数规划模型，并通过建立双层变邻域禁忌搜索算法，提供了穿梭车立体仓库多种模式下订单分批与存取决策的指导工具。数值实验表明，本文设计的算法可高效求解这一问题，双箱模式在大规模存取作业下可有效降低系统运行成本。 “一车双箱”存取模式是对一般“一车单箱”模式穿梭车立体仓库在设备上、效率上、运作模式上的全方位突破。“一车双箱”存取模式的推广对推动仓库系统机电设备更新换代，推行实现仓储行业设备的全面自动化与流程的全面集成化具有显著意义。尽管在近期，“一车双箱”模式的推广仍受系统投资大、建设要求高、运营管理要求高等瓶颈因素制约，但随着相关仓库设备与系统的大范围应用及仓库系统运营管理研究的逐步完善，该模式进一步推广应用的瓶颈将被逐步打破。根据本文研究结果，“一车双箱”存取模式可节省约20%的存取成本，这说明了“一车双箱”存取模式在仓库运作效率提高方面的潜力。“一车双箱”对仓库订单拣选总时间系统效率的影响，还可从总拣选时间、料箱等待时间等指标的角度进行进一步论述，同时对存取成本进行细化，详细计算穿梭车与升降机在不同工况下的存取成本与时间，得出更为精准的结论。 参 考 文 献： [1]Marchet G， Melacini M， Perotti S， et al.. Analytical model to estimate performances of autonomous vehicle storage and retrieval systems for product totes[J]. International Journal of Production Research， 2012， 50（24）： [2]Tappia E， Roy D， Melacini M， et al.. Integrated storage-order picking systems： [3]Wu Y， Zhou C， Ma W， et al.. Modelling and design for a shuttle-based storage and retrieval system[J]. International Journal of Production Research， 2020， 58（16）： [4]Ning Z， Lei L， Zhang S， et al.. An efficient simulation model for rack design in multi-elevator shuttle-based storage and retrieval system[J]. Simulation Modelling Practice and Theory， 2016， 67： [5]Ekren B Y. Graph-based solution for performance evaluation of shuttle-based storage and retrieval system[J]. International Journal of Production Research， 2017， 55（21）： [6]Lerher T， Ekren B Y， Dukic G， et al.. Travel time model for shuttle-based storage and retrieval systems[J]. International Journal of Advanced Manufacturing Technology， 2015， 78（9-12）： [7]Dantonio G， De Maddis M， Bedolla J S， et al.. Analytical models for the evaluation of deep-lane autonomous vehicle storage and retrieval system performance[J]. International Journal of Advanced Manufacturing Technology， 2018， 94（5-8）： [8]Lerher T， Ekren Y B， Sari Z， et al.. Simulation analysis of shuttle based storage and retrieval systems[J]. International Journal of Simulation Modelling， 2015， 14（1）： [9]Ha Y， Chae J. Free balancing for a shuttle-based storage and retrieval system[J]. Simulation Modelling Practice and Theory， 2018， 82： [10]Roy D， Krishnamurthy A， Heragu S， et al.. Stochastic models for unit-load operations in warehouse systems with autonomous vehicles[J]. Annals of Operations Research， 2015， 231（1）： [11]Lerher T. Travel time model for double-deep shuttle-based storage and retrieval systems[J]. International Journal of Production Research， 2016， 54（9）： [12]宋振波.雙载位单深位多层穿梭车系统建模与优化[D].济南：山东大学，2020. [13]黄敏芳，张源凯，王颜新.网上超市拆分订单的合并打包优化决策方法[J].系统工程理论与实践，2021，41（2）：286-296. [14]冯晓春，胡祥培.基于学习效果的蔬菜电商成组拣货排序方法[J].系统工程理论与实践，2020，40（2）：449-461. [15]Li J， Huang R， Dai J. Joint optimisation of order batching and picker routing in the online retailers warehouse in China[J]. International Journal of Production Research， 2017， 55（2）： [16]Yang P， Zhao Z， Guo H. Order batch picking optimization under different storage scenarios for e-commerce warehouses[J]. Transportation Research Part E-Logistics and Transportation Review， 2020， 136： [17]Zhang J， Liu F， Tang J， et al.. The online integrated order picking and delivery considering Pickers learning effects for an O2O community supermarket[J]. Transportation Research Part E-Logistics and Transportation Review， 2019， 123： [18]Xiang X， Liu C， Miao L. Storage assignment and order batching problem in Kiva mobile fulfilment system[J]. Engineering Optimization， 2018， 50（11）： [19]Li Z， Zhang J， Zhang H， et al.. Optimal selection of movable shelves under cargo-to-person picking mode[J]. International Journal of Simulation Modelling， 2017， 16（1）： [20]Li Z， Barenji A V， Jiang J， et al.. A mechanism for scheduling multi robot intelligent warehouse system face with dynamic demand[J]. Journal of Intelligent Manufacturing， 2020， 31（2）： [21]Scholz A， Schubert D， Wscher G. Order picking with multiple pickers and due dates-simultaneous solution of order batching， batch assignment and sequencing， and picker routing problems[J]. European Journal of Operational Research， 2017， 263（2）： [22]Zulj I， Kramer S， Schneider M. A hybrid of adaptive large neighborhood search and tabu search for the order-batching problem[J]. European Journal of Operational Research， 2018， 264（2）： [23]Muter I， Oncan T. Order batching and picker scheduling in warehouse order picking[R]. IISE Transactions， 10.1080/24725854.2021.1925178.13， 2021.41A2FBCC-B472-4D65-9D48-38B623931BB4
7134-7148.
technology， performance models， and design insights[J]. European Journal of Operational Research， 2019， 274（3）：
947-965.
4808-4828.
100-116.
6516-6526.
1705-1725.41A2FBCC-B472-4D65-9D48-38B623931BB4
1811-1824.
48-59.
12-31.
129-155.
2519-2540.
447-461.
101897.
180-199.
1941-1962.
145-156.
469-480.
461-478.
653-664.