考虑商品数量和商品拣选成本的AGV智能仓库订单分批问题研究

AGV(Automated Guided Vehicle,自动导引车)智能仓库是一种基于“货到人”拣选模式的自动化仓库。本文考虑了订单中商品的需求量和货架上商品的存储量,以极小化货架搬运成本和商品拣选成本为目标,建立了AGV智能仓库订单分批问题的整数规划模型。本文针对订单分批问题的特点,提出了一种基于订单和货架交替选择的贪婪求解算法。对比CPLEX求解器的精确最优解,本文提出的贪婪算法的误差百分比不超过10%,平均误差百分比为5.38%;对比基于相似性的分批算法的求解结果,本文提出的贪婪算法不仅运算时间更短,解的质量也更好。进一步地,对比不考虑商品拣选成本的订单分批模型,本文提出的模型在不明显增加货架搬运成本的前提下,可以大幅度降低商品拣选成本。因此,在订单分批模型中考虑商品拣选成本是非常必要的。     

“货到人”拣选系统中电商订单分批优化研究

本文在电商行业迅速发展及人工智能日趋成熟的背景下,研究以自动导引车(AGV)为搬运工具的“货到人”拣选系统订单分批问题。首先以最小化AGV搬运货架次数为目标建立订单分批模型,然后提出了基于货架相似度的两阶段订单分批算法,在第一阶段分为新批次创建及订单加入批次两个步骤得到初始解;在第二阶段采用局部搜索改进初始解。在算法中构造订单选取货架规则,定义货架相似度函数并设计两种方法创建新批次,同时考虑周转箱数量限制求解订单分批方案。最后通过实验测试验证了模型和算法的有效性,分析了两种批次创建方法的适用性,并通过灵敏度分析给出了合理的周转箱数量配置建议。本研究可为采用“货到人”拣选系统的企业通过订单分批优化进一步提高AGV拣选效率提供理论依据和实践指导。     

考虑商品订购数量的“货到人”仓储系统订单分批问题研究

结合"货到人"仓储系统的订单拣选场景,在考虑订单中各种商品订购数量和货箱中商品存储量的情况下,研究了自动小车存储及取货系统的订单分批拣选问题.对于给定的待拣选订单,以货箱出库次数极小化为目标,建立了订单分批问题的整数规划模型,并利用聚类思想设计了两阶段启发式算法.利用不同规模的算例进行仿真实验,验证了模型和算法的有效性.通过对比按照本文模型和算法得到的分批结果与按照先到先服务策略得到的分批结果,可以发现,按照文章模型和算法进行订单分批,拣选效率大约提升了25%-45%.进一步分析了拣选台容量和相似度加权系数等参数变化对订单分批结果的影响.最后利用两个具体算例,对比分析了考虑商品订购数量和不考虑商品订购数量的订单分批模型之间的关系,验证了考虑商品订购数量的订单分批模型的优越性.     

基于商品关联度的智能仓库储位分配问题研究

储位分配方案是直接影响智能仓库工作效率和拣选成本的关键因素.根据历史订单信息定义了商品之间的关联度,以同一货架上的商品之间的关联度之和极大化为目标建立了智能仓库储位分配问题的数学模型,并设计了求解模型的算法.首先根据历史订单信息计算商品之间的关联度,然后结合商品的周转率、商品之间的关联度等信息,设计了启发式算法求解智能仓库储位分配问题,并且分析了启发式算法的时间复杂度.通过大量的模拟计算验证了本文建立的数学模型和设计的启发式算法的有效性,证明了以同一货架上商品之间关联度极大化为目标和以订单拣选过程中搬运货架总次数极小化为目标的一致性.通过对比分析本文算法得到的储位分配结果与随机储位分配结果可以看出,利用基于商品关联度的启发式算法得到的储位分配方案比随机储位分配方案对应的货架搬运次数平均减少了30.08%.     

基于AGV的智能仓库系统储位分配问题研究

研究了基于自动引导机器人(AGV)的"货到人"拣选模式下的智能仓库系统补货阶段的储位分配问题.根据待拣选订单信息计算出商品之间的关联度,考虑了货架上存放的物品信息、空余储位数量、待补货物品信息,以同一货架上的各种商品之间的关联度之和最大化为目标函数,建立了补货阶段储位分配问题的整数规划模型;设计了求解模型的贪婪算法,并分析了算法复杂度.利用一个具体实例进行模拟计算,分析了贪婪算法的求解效果.进一步利用不同规模算例进行模拟计算,分析了贪婪算法的计算时间和近似比,结果显示贪婪算法可以在很短的时间内得到近似最优解,近似比不超过1.15.设计的贪婪算法可以作为智能仓库管理信息系统的核心算法.     

基于移动机器人的拣选系统货架动态储位分配研究

为了提高基于移动机器人的拣选系统拣货效率,更好地满足客户动态需求和订单时效要求,提出了考虑货架后续需求频次、需求紧迫程度以及拥堵因素的货架动态储位分配策略,构建了最小化货架搬运距离的动态储位分配模型,并设计了启发式算法进行模型求解.首先,基于货架需求紧迫程度,构造贪婪算法生成动态货架储位分配的初始解;然后,基于货架在后续批次订单的需求频次及通道间负载均衡,采用邻域搜索算法进行动态货架储位优化.最后,通过与其他静态和动态储位分配方法对比,验证文章提出的模型和算法的有效性.     

基于“货到人”拣选模式的储位分配问题研究

研究了“货到人”拣选模式下的储位分配问题,以订单拣选过程中搬运货架总时间最短为目标建立了整数非线性规划模型,并证明其为NP-hard问题,分别设计了求解模型的贪婪算法和单亲进化遗传算法。首先根据订单和物品的关联关系对物品进行聚类,基于聚类结果设计了求解模型的贪婪算法。然后设计了直接求解模型的单亲进化遗传算法,遗传算法中采用了0-1矩阵编码、多点基因倒位算子、单点基因突变算子和精英保留等策略,通过合理选取参数,能够很快求解出问题的近似最优解。最后利用模拟算例和一个具体实例进行计算,并对贪婪算法和遗传算法的求解时间和求解效果进行了比较分析。结果显示,对于小规模问题,两种算法均能在较短的时间内以很高的概率得到问题的全局最优解,对于中等规模的实际问题,利用两种算法得到的储位分配方案均优于企业目前采取的基于出库频率的储位分配方案,遗传算法得到的储位分配方案对应的货架搬运次数、货架搬运总时间等均优于贪婪算法。本文设计的遗传算法可以作为智能仓库管理信息系统的核心算法。     

基于移动机器人的订单拣选系统货位优化模型和算法研究

为了提高基于移动机器人的订单拣选系统的拣选效率,文章提出了基于货品相关性和货架中货品总出库频次的货位优化方法.将货位优化分为货品存放到货架及货架布局到仓库中现有位置两个阶段,为避免拥堵采用分散存储策略建立了最小化货架搬运次数以及最小化机器人总拣选路程的数学模型,并设计两阶段启发式算法求解.结合A网上药店的历史订单数据进行了仿真实验,实验结果表明,文章提出的货位优化方法有效提高了订单拣选效率.     

基于物流AGV的“货到人”订单拣选系统任务调度研究

基于物流AGV的“货到人”订单拣选模式由于其高效率和灵活性,逐渐成为电商物流配送中心订单拣选系统发展趋势。本文通过对基于物流AGV的电商物流配送中心订单拣选作业流程分析,提出多拣选台同步拣选和多拣选台异步拣选两种作业模式。然后对基于物流AGV的订单拣选任务调度问题进行描述,以物流AGV完成所有任务的时间最短为目标,分别建立同步和异步两种拣选模式下物流AGV任务调度模型;针对物流AGV任务调度问题特性,对共同进化遗传算法粗粒度模型进行改进用于模型求解。最后,通过改进前后算法的对比,验证了改进共同进化遗传算法在求解物流AGV任务调度问题中的有效性;通过在求解速度和优化结果上对多拣选台同步拣选和异步拣选两种作业模式进行比较,得出同步拣选优于异步拣选的结果。     

考虑完全拆分的拣选分批与拣选路径集成优化模型

在电商海量订单背景下,在线订单拣选作业难度加大,因此设计了基于订单完全拆分的拣选分批与拣选路径综合优化模型解决此问题.模型共分两阶段.第一阶段,基于种子算法,设计考虑订单完成度、等待时间与拣选路径的拣选分批模型;第二阶段以拣选单流为单队列,设计多拣选员并行服务的拣选系统.行走策略为基于返回型和遍历型的综合策略,拣选路径优化模型采用模拟退火算法求解.算例分析表明,与传统的不拆分拣选分批模型相比,构建的综合优化模型能够显著提高拣选系统效率.拣选员为4人时,模型能够使总服务时间减少58.79%,订单完成率提高10.09%.     

On-line order batching and sequencing problem with multiple pickers: A hybrid rule-based algorithm

Existing on-line order batching rules, namely fixed time window batching (FTWB) and variable time window batching (VTWB), try to choose the fixed time window in the case of FTWB or the fixed number of orders in the case of VTWB. However, these solutions are not appropriate for the fluctuating order environment. The reasonable assignment of batches to order pickers is also an important issue in order picking systems. Motivated by these issues, we study the problem of integrating on-line order batching and the assignment of the batches, which is called the on-line order batching and sequencing problem with multiple pickers (OOBSPMP). The objective is to minimize the turnover time. To solve the problem, a hybrid rule-based algorithm, referred to FTWB, is proposed in order to form batches and assign them to appropriate pickers under a fluctuating order environment. Three batching situations (off-peak, normal and peak arrival time) and two assigning situations (assigning to one busy picker and assigning to one idle picker) are distinguished. Through a series of experiments, we discover several enlightening findings: (i) the rule-based algorithm demonstrates high effectiveness and efficiency in turnover time with multiple pickers; (ii) the rule-based algorithm leads to an impressive improvement in both saving time and wage costs under different arrival rates, picking devices and time intervals compared with VTWB; (iii) to obtain both good warehouse performance and a reasonable workload distribution, the factors, such as the fixed time window, the average workload per picker and the average idle time per picker are also important issues in analysing the efficiency of order picking systems.     

Loopless generation of up–down permutations

An up–down permutation P=(p₁,p₂,…,p_n) is a permutation of the integers 1 to n which satisfies constraints specified by a sequence C=(c₁,c₂,…,c_n−1) of U's and D's of length n−1. If c_i is U then p_i<p_i+1 otherwise p_i−1>p_i. A loopless algorithm is developed for generating all the up–down permutations satisfying any sequence C. Ranking and unranking algorithms are discussed.     

非负约束稀疏优化问题的一个等价性条件

加权l₁最小化是稀疏优化的主流方法之一。本文对带非负约束的l₀最小化问题与加权l₁最小化问题的解之间的关系进行了研究,给出了加权l₁最小化问题的约束矩阵和目标函数的系数是"s-权优"的定义,并通过该定义给出了加权l₁最小化问题的解是带非负约束的l₀最小化问题的解的条件。进一步,本文给出了"s-权优"的充分条件及其具体表示形式,并对其上下界进行了可计算的有效估计。     

非负约束稀疏优化问题的一个等价性条件

加权l₁最小化是稀疏优化的主流方法之一。本文对带非负约束的l₀最小化问题与加权l₁最小化问题的解之间的关系进行了研究,给出了加权l₁最小化问题的约束矩阵和目标函数的系数是"s-权优"的定义,并通过该定义给出了加权l₁最小化问题的解是带非负约束的l₀最小化问题的解的条件。进一步,本文给出了"s-权优"的充分条件及其具体表示形式,并对其上下界进行了可计算的有效估计。     

On some Rado numbers for generalized arithmetic progressions

The 2-color Rado number for the equation x₁+x₂−2x₃=c, which for each constant we denote by S₁(c), is the least integer, if it exists, such that every 2-coloring, Δ : [1,S₁(c)]→{0,1}, of the natural numbers admits a monochromatic solution to x₁+x₂−2x₃=c, and otherwise S₁(c)=∞. We determine the 2-color Rado number for the equation x₁+x₂−2x₃=c, when additional inequality restraints on the variables are added. In particular, the case where we require x₂<x₃<x₁, is a generalization of the 3-term arithmetic progression; and the work done here improves previously established upper bounds to an exact value.