工具类服务
编辑部专用服务
作者专用服务
基于蚁群算法的自动化仓库作业调度研究
物流是社会经济发展的命脉之一，由于世界各国企业间的竞争日趋激烈，依靠生产领域技术的发展来获取更高利润的速度趋于稳定，所以物流领域技术的进步成为获取更高利润新的源泉。自动化仓库是物流领域的一个关键设备，一般由固定货架和旋转货架两大部分来存放货物。所以在自动化仓库中对固定货架、旋转货架拣选路径优化问题的研究将极大地提高自动化仓库的作业效率。在自动化仓库中，输送系统是自动化仓库的重要组成部分，承担着货物运输的任务，由于固定货架和旋转货架的作业速度很快，输送系统可能成为整个系统的速度“瓶颈”。因此，对自动化仓库的输送系统的调度作业进行优化，可以避免或者减轻“瓶颈效应”，提高自动化仓库的整体运行效率。
蚁群算法(ACA：AntColonyAlgorithm)是一种新型的随机优化算法，是意大利学者在20世纪90年代初首先提出来的，在解决经典组合优化问题中取得了较好的结果，引起了国内外学者的广泛关注。本文使用蚁群算法和最大最小蚁群算法(MMASA：Max-MinAntSystemAlgorithm)研究了固定货架、旋转货架拣选路径优化及输送系统的调度优化问题。仿真结果表明，蚁群算法可取得较好结果。此外还分析了单拣选台水平旋转货架系统的工作过程，利用蚁群算法，取得了满意的结果。并对相对比较复杂的输送系统提出了一个简单的输送系统模型，利用蚁群算法，对其优化调度问题进行了初步探讨。仓库作业
学科专业：
授予学位：
学位授予单位：
导师姓名：
学位年度：
在线出版日期：
本文读者也读过
相关检索词
万方数据知识服务平台--国家科技支撑计划资助项目（编号：2006BAH03B01）(C)北京万方数据股份有限公司
万方数据电子出版社您所在位置： &
&nbsp&&nbsp&nbsp&&nbsp
毕业论文-基于蚁群算法的仓库拣货路径优化研究.pdf62页
本文档一共被下载：
次 ,您可免费全文在线阅读后下载本文档
文档加载中...广告还剩秒
需要金币：150 &&
你可能关注的文档：
··········
··········
合肥工业大学
硕士学位论文
基于蚁群算法的仓库拣货路径优化研究
姓名:雷娟娟
申请学位级别:硕士
专业:企业管理及其信息化
指导教师:李兴国
基于蚁群算法的仓库拣货路径优化研究
越来越多的企业构建自己的仓库和配送体系,以期降低物流成本,保持自
己的竞争力。物流作为“第三利润源泉越来越受重视。现代仓库是物流不可
或缺的一部分,拣货作业是仓库的核心作业环节,拣货成本占到整个仓库物流
成本的%,其效率的高低直接影响到整个仓库的效率,而提高拣货作业效率,
缩短拣货路径长度至关重要。本文选择双区型仓库为研究对象,应用蚁群算法
对拣货路径加以优化。
本文首先分析了仓库拣货路径的研究现状和存在的问题,综述了物流拣货
路径的相关问题,包括拣货作业流程、仓库中典型的双区型仓库和影响拣货的
因素等。其次根据双区型仓库中拣货路径问题的特点,将该问题分成不考虑拣
货车辆容积和考虑拣货车容积两种情况,针对不考虑拣货车容积的情况,采用
蚁群算法优化求解其拣货路径问题,并将该算法的结果与形启发式算法进行
比较,验证了该方法的有效性。最后针对考虑拣货车容积的情况,应用蚁群算
法对拣货路径问题进行建模求解,并在 .平台上上实现了该算法,
与遗传算法的优化结果进行比较发现当拣货数量较多时,该算法具有明显优势。
关键词:蚁群算法;双区型仓库;拣货路径..”
图.本文所采用的技术路线.
图.仓库的基本流程图
图?双区型仓库平面图?..
图. 形启发式策略
图拣货返回策略?
图.拣货返回策略
图.基本蚁群算法的流程图?
图. 型启发算法拣货流程图
图.蚁群算法的流程图表格清单
表.影响仓库
正在加载中，请稍后...OALib Journal期刊
费用：99美元
查看量下载量
Order picking problem based on ant colony algorithm基于蚁群算法的拣选作业优化问题
,,,刘臣奇,,
Keywords: ,,,
蚁群算法是一种新型的启发式算法,研究表明该算法具有较强发现较好解的能力,但同时存在一些缺点如易出现停滞现象、收敛速度慢等.在蚁群算法的基础上结合自动化立体仓库固定货架拣选作业的特点,构建了货物拣选路径问题的数学模型,设计了新型的改进蚁群算法用于合理优化货物拣选路径以减少作业时间,并在算法中采取了三个改进措施,改善基本蚁群算法的搜索能力.候选节点集合策略和自适应调整算法参数能有效提高算法的搜索速度,选择算子使问题的解始终保持最优.实验表明该算法具有较好的全局寻优能力,收敛速度大幅度提高,能够很好地满足中大规模的拣选作业要求.
Please enable JavaScript to view the
&&&OALib Suggest
Live SupportAsk us anything订单拣选方法及系统的制作方法
专利名称订单拣选方法及系统的制作方法
技术领域本发明涉及物流仓储中的仓库拣选作业领域，特别涉及一种需要在多个巷道中水 平移动的订单拣选方法及系统。
背景技术仓库拣选作业是现代化物流配送的核心，物流配送的现代化程度的高低取决于拣 选技术。许多大型仓库或配送中心采用高层货架式立体仓库，相邻两排货架之间有一条巷 道，每条巷道有一台堆垛机，堆垛机可以同时沿垂直方向和水平方向移动，存取巷道两侧垂 直货架上的货物。如图1所示，0点为巷道出入口，a、b、C、d、e、f为垂直货架上的几个取货 点，堆垛机一次可以拣选若干个货位上的货物，然后返回到0点将货箱放置到传送系统上。目前，已经存在很多对拣选作业进行优化的方法。《基于蚁群算法的拣选作业优化 问题》(系统工程理论与实践，2009. 2 ，第179-184页)提出一种蚁群算法，对取货点的存 取顺序进行优化，以使得作业时间最短。但是，该方法假定堆垛机一次作业可以拣选所有取 货点的货物，没有考虑堆垛机所携带的货箱的容量限制。针对上述问题，《自动化立体仓库拣选作业路径优化问题研究》(系统工程理论与 实践，2007. 2，第139-143页)提出一种遗传算法，在堆垛机一次作业容量受限的情况下，针 对垂直货架上的多个取货点，安排若干次拣选作业使得总的拣选代价最小。如图2所示，图 2中表示两次拣选作业，第一次的拣选顺序为O-a-e-f-O，第二次拣选顺序为0-b-C-d_0。对 于堆垛机需要行进到其它巷道中进行拣选的问题，该方法不能够解决，当然，对于自动化立 体仓库，一般每个巷道都有一台堆垛机，负责拣选该巷道两侧货架上的货物，某一巷道的堆 垛机不需要行进到其它巷道进行拣选。在某些情况下，需要一台堆垛机拣选多个巷道中的货物，《多巷道固定货架拣选作 业优化问题的研究》(控制与决策，2008. 12，第页)对此问题进行了研究。如图 3所示，堆垛机从0点出发，依次拣选巷道1、巷道2、…、巷道j两侧货架中的货物，而后返 回到0点，在拣选过程中，堆垛机所携带的货箱容量有限，装满一箱货物就返回到0点把货 物放置到传送系统上，并且，前一巷道的拣选作业全部完成后才能进入下一巷道进行作业。但是，对于货架摆放更加复杂，并且需要在多个巷道内移动进行拣选的情况，上述 方法不能解决。仓库中货架长短不一，横竖不一，需要作业人员在多个巷道中移动拣选这些 货物。例如，大型超市、书店、药店、网店、仓库等的补货发货作业。在这类企业中，订单的 批量较小、订单所涉及的商品种类较多，需要在更大范围内进行拣选，在这类仓库中货架高 度不高，许多拣选作业是靠人工进行的，作业人员可以较容易的取下货架高层中的商品，因 此，在垂直方向上的作业距离可以忽略不计，上述方法不能解决此问题。
本发明实施例提供一种订单拣选方法及系统，通过从数据库中查找订单中所需货 物所在的货位、大小及重量后求解最佳拣选路径；可高效地计算出拣选路径，降低作业成本，提高作业效率。为达到上述目的，本发明实施例提供一种订单拣选的方法，应用于需要在多个巷 道中水平移动的订单拣选，所述方法包括根据仓库货架的摆放情况，生成仓库平面布置 图；计算并存储巷道和节点的信息；计算并存储仓库中各节点之间的最短路径；存储货物 的货位信息、货物的大小及重量信息；在进行订单拣选时，从预存的数据中查找所述订单中所需货物的货位、大小及重 量；根据所述订单中所需货物的数量、以及查找到的货物的大小及重量计算所需货物的需 求量；并利用预先存储的各节点之间的最短路径计算任意两个所需货物之间的最短路径；根据拣选设备的容量、所述任意两个所需货物之间的最短路径以及所述订单中所 需货物的需求量，通过遗传算法和LK算法求解最佳拣选路径，以使所述拣选设备根据所述 最佳拣选路径进行订单拣选。本发明实施例还提供一种订单拣选的系统，应用于需要在多个巷道中水平移动的 订单拣选，所述系统包括服务器、无线局域网络与移动终端；其中，所述服务器包括制图单元，根据仓库货架的摆放情况，生成仓库平面布置图；计算出巷道和节点的 信息；计算仓库中各节点之间的最短路径；存储单元，存储货物的货位、大小及重量的信息，以及所述巷道和节点的信息；存 储仓库中各节点之间的最短路径；计算单元，用于从预存的数据中查找所述订单中所需货物的货位、大小及重量；根 据所述订单中所需货物的数量、以及查找到的货物的大小及重量计算所需货物的需求量; 并利用预先存储的各节点之间的最短路径计算任意两个所需货物之间的最短路径；求解单元，用于根据拣选设备的容量、所述任意两个所需货物之间的最短路径以 及所述订单中所需货物的需求量，通过遗传算法和LK算法求解最佳拣选路径，以使所述拣 选设备根据所述最佳拣选路径进行订单拣选。本发明实施例的有益效果在于，通过从数据库中查找订单中所需货物所在的货 位、大小及重量后求解最佳拣选路径；可高效地计算出拣选路径，降低作业成本，提高作业 效率；解决在货架摆放不一、货架高度相对较小、对同一货位不同层的货架上的货物存取时 所用代价差异不大、拣选作业需要优化的主要是拣选作业人员水平移动距离的情况下订单 的拣选问题。
此处所说明的附图用来提供对本发明的进一步理解，构成本申请的一部分，并不 构成对本发明的限定。在附图中图1是现有技术中巷道堆垛机在垂直货架上的存取示意图；图2是现有技术中巷道堆垛机在垂直货架上的两次存取作业示意图；图3是现有技术中堆垛机在多巷道中的拣选示意图；图4是本发明实施例1的订单拣选方法的流程图；图5是本发明实施例2的订单拣选方法的流程图；图6是本发明实施例2的仓库的示意图；图7是本发明实施例2的优化过程的流程图8是本发明实施例2的交叉操作的流程图；图9是本发明实施例2的变异操作的流程图；图10是本发明实施例2的获取最优个体过程中的迭代示意图；图11是本发明实施例2的最优个体表示的拣选路径示意图；图12是本发明实施例3的订单拣选系统的构成13是本发明实施例3的服务器的构成示意图；图14是本发明实施例4的路径获取单元的构成示意图。
具体实施例方式为使本发明的目的、技术方案和优点更加清楚明白，下面结合附图对本发明实施 例作进一步详细说明。在此，本发明的示意性实施例及其说明用于解释本发明，但并不作为 对本发明的限定。实施例1本发明实施例提供一种订单拣选的方法，应用于包括多种所需货物的订单，所需 货物存放在仓库的货位上，纵向巷道和横向巷道形成节点。如图4所示，所述方法包括步骤401，根据仓库货架的摆放情况，生成仓库平面布置图；计算并存储巷道和节 点的信息；计算并存储仓库中各节点之间的最短路径；存储货物的货位信息、货物的大小
及重量信息。步骤402，在进行订单拣选时，从预存的数据中查找订单中所需货物所在的货位、 大小及重量；根据所需货物的数量、以及查找到的货物的大小及重量计算所需货物的需求 量；并利用预先存储的各节点之间的最短路径计算任意两个所需货物之间的最短路径；步骤403，根据拣选设备的容量、任意两个所需货物之间的最短路径、以及订单中 所需货物的需求量，通过遗传算法和LK算法求解最佳拣选路径，以使拣选设备根据最佳拣 选路径进行订单拣选。在本实施例中，订单可包括多种所需货物、以及每种所需货物的数量。每种所需货 物所在的货位、大小及重量等信息可预先存储在数据库中。在本实施例中，订单中的所需货物存放在货架上，同一种货物存放在同一货位。货 架摆放不一、货架高度相对较小、对同一位置不同层的货架上的货物存取时所用代价差异 不大，拣选作业人员需要利用拣选设备在多个巷道中水平移动对订单进行拣选。由上述实施例可知，通过从数据库中查找订单中所需货物所在的货位、大小及重 量后求解最佳拣选路径；可高效地计算出拣选路径，降低作业成本，提高作业效率。实施例2本发明实施例提供一种订单拣选的方法，应用于包括多种所需货物的订单，以下 在实施例1的基础上对上述方法进行详细说明，与实施例1相同的内容不再赘述。如图5所示，上述订单拣选的方法包括步骤501，根据仓库货架的摆放情况，生成仓库平面布置图；计算出巷道和节点的 信息；计算仓库中各节点之间的最短路径。在一个实施例中，所需货物的存取位置在巷道中，纵向巷道和横向巷道形成节点。
6例如，如图6所示，巷道是存取货物的供拣选作业人员行走的通道，假定只有纵向和横向两 种直线巷道。节点是纵向巷道和横向巷道的交叉点。货位是存储货物的单元，必须位于巷 道的特定位置才能存取这个货位中的货物，有的货位存取位置在它的左边巷道，有的货位 存取时必须走到它右侧巷道上，有的货位存取位置在其紧邻的上边的巷道，有的存取位置 在其紧邻的下边的巷道。在一个实施例中，为了生成并存储这些元素的信息，把仓库平面分成若干行和列， 行列交叉位置为一仓库单元格，这个仓库单元格可以是一个巷道单元也可以是货位单元， 因此，可以设计“仓库单元格”这样一种数据结构来记录每个仓库单元格的信息；可以采用 矩阵的形式，矩阵的第m行第η列的元素值为1，表示仓库的第m行第η列的单元格为一货 位，并且取货位置在上方巷道；值为2表示为货位，取货位置在下方巷道；值为3表示为货 位，取货位置在左边巷道；值为4表示为货位，取货位置在右边巷道；值为5表示此单元格 为一巷道单元；值为6表示为一障碍物单元。“仓库单元格”矩阵记录下了每个仓库单元的 信息，由此矩阵可以计算出所有的货位、巷道和节点。在一个实施例中，还可以设计“巷道”这种数据结构，该数据结构也可为一矩阵。例 如，矩阵的一行表示一个巷道，矩阵共有四列。第一列表示巷道类型，为1，表示为横向巷道， 为0表示纵向巷道。第二列表示该巷道所在的行号或列号，如果是横向巷道，该列存储该巷 道在“仓库单元格”矩阵中的行号；如果是纵向巷道，该列存储该巷道在“仓库单元格”矩阵 中的列号。第三列表示巷道的起始位置，横向巷道的起始位置是指该巷道最左边单元在“仓 库单元格”矩阵中的列号，纵向巷道的起始位置是指该巷道最上边单元在“仓库单元格”矩 阵中的行号。第四列表示巷道的结束位置，横向巷道的结束位置是指该巷道最右边单元在 “仓库单元格”矩阵中的列号，纵向巷道的结束位置是指该巷道最下边单元在“仓库单元格” 矩阵中的行号。在一个实施例中，可从“仓库单元格”矩阵的第一行第一列开始逐行逐列查找值为 5的元素，即巷道单元，找到一巷道单元后，记录下其行号和列号，假设其行号为R，列号为 C0在一个实施例中，还可把巷道单元所在的横向巷道找到并保存到“巷道”矩阵中。
具体实施方式
可为遍历“巷道”矩阵，查找行号为R的横向巷道，如果C介于该巷道的起始 列号与结束列号之间，说明该巷道单元位于这个横向巷道上，并且其所在的横向巷道已经 找到并保存在了 “巷道”矩阵中。否则，继续找下一个行号为R的横向巷道，判断该巷道单 元是否位于这个横向巷道上，如果遍历完“巷道”矩阵后，不存在相应的横向巷道，则说明该 巷道单元所在的横向巷道还没有记录在“巷道”矩阵中。这时，从“仓库单元格”矩阵的第R 行第C列开始向右遍历，查找值为5的元素。如果第R行，C+1列、C+2列、…、C+n列的元 素值为5，第C+η+Ι列元素值不为5，则找到了一条横向巷道，该巷道所在行号为R，起始位置 为C，结束位置为C+n，把该巷道的一行信息插入“巷道”矩阵中。同理，可以把该巷道单元 所在的纵向巷道找到并保存到“巷道”矩阵中。在一个实施例中，可继续查找下一个巷道单元所在的巷道，直到遍历完所有的巷 道单元。一个巷道单元至少位于一条巷道上。至此，“巷道”矩阵中记录了所有的巷道信息， 然后根据“巷道”矩阵，可以找出所有的节点，节点是纵向巷道和横向巷道的交叉点。定义 一个“节点”矩阵记录下所有节点的行号、列号、该节点所在横向巷道的编号、该节点所在纵向巷道的编号。一个巷道上的两个相邻的节点为邻接节点。步骤502，存储货物的货位、大小及重量的信息，以及所述巷道和节点的信息；存 储仓库中各节点之间的最短路径。在一个实施例中，可先计算出所有邻接节点间的最短路径和距离。邻接节点指的 是同一个巷道上的两个相邻的节点。对于任意两个互为邻接的节点，如果它们位于一条纵 向巷道上，则其行号之差即为其最短距离，如果它们位于同一条横向巷道上，则其列号之差 即为其最短距离。它们之间的最短路径为沿其所在巷道的一条连接这两个节点的直线段。在一个实施例中，可把任意两个邻接节点的最短距离保存到“节点距离，，矩阵中， 该矩阵的行列编号表示节点编号，元素的值为两个节点之间的最短距离。然后由弗洛伊德 Floyd算法计算出所有节点间的最短距离及最短路径。弗洛伊德算法为现有技术，可参考 《运筹学教程》(清华大学出版社，1998. 6)，此处不再赘述。在一个实施例中，由于节点的数量较少，因此可以把节点之间的最短距离和最短 路径计算完毕后，存储到磁盘上。步骤503，在进行订单拣选时，从预存的数据中查找订单的所需货物的货位、大小
及重量。步骤504，根据所需货物的数量、以及查找到的货物的大小及重量计算所需货物 的需求量；并利用预先存储的各节点之间的最短路径计算任意两个所需货物之间的最短路径。在一个实施例中，若两个所需货物的存取位置位于同一巷道中，则两个存取位置 之间的最短路径和距离为沿同一巷道的路径和距离。例如，设这两个存取位置的行列号分 别为(xl，yl)、(x2, y2)，由于其位于同一个巷道上，因此有xl = χ2或者yl = y2，其最短
距离为+ (少i-P)2，最短路径即是沿该巷道从一个存取位置到另一存取位置的
一条直线段。若两个存取位置位于不同巷道中，则可首先分别确定存取位置的所在巷道距离该 存取位置最近的节点；根据预存的任意两个节点之间的最短路径和距离，确定最近的节点 之间的最短路径和距离；根据最近的节点之间的最短路径和距离、以及两个存取位置到最 近的节点之间的距离确定两个存取位置之间的最短路径和距离。例如，假设这两个存取位置分别为巷道单元A和巷道单元B。A1、A2为A所在巷道 上距离A最近的两个节点，Bi、B2为B所在巷道上距离B最近的两个节点。A与B之间的 路径必须经由其各自的临近节点，因此，计算A、B之间的最短距离就转化为求A-A1-B1-B、 A-A2-B1-B、A-A1-B2-B、A-A2-B2-B这四条路径中的最短路径。任意两个节点之间的最短距 离在步骤502中已经求得，而A与A1、A2之间距离很容易求得，因为它们位于同一直线巷道 上。B与B1、B2之间距离也很容易求得。因此任意两个货位之间的最短路径和距离可以求 得。步骤505，根据拣选设备的容量、任意两个所需货物之间的最短路径、以及订单中 所需货物的需求量求解最佳拣选路径，以使拣选设备根据最佳拣选路径进行订单拣选。在一个实例中，求解最佳拣选路径可在遗传算法(Genetic Algorithm, GA)的基础 上进行求解。遗传算法是Holland教授最早提出的，是求解复杂组合优化问题的有效方法， 典型的遗传算法主要包括选择、交叉、变异三个基本的遗传算子，其中交叉操作是遗传算法的主要搜索手段，是影响算法收敛性及搜索效率的关键因素，常用的交叉操作有单点交叉 和双点交叉，双点交叉能更有效的离散杂交子代群体，更有利于寻找到最优解。可参考现有 技术，此处不再赘述。在一个实施例中，可采用双点交叉的交叉运算。在染色体适应度值的计算以及重 插入的操作中，可使用英国设菲尔德(Sheffield)大学的MATLAB遗传算法工具箱中的有 关函数。具体函数可参考《MATLAB遗传算法工具箱及应用》(西安电子科技大学出版社， 2005. 4)，此处不再赘述。在一个实施例中，步骤505可具体包括如下步骤首先，根据拣选设备的容量、订单中需求点以及所需货物的需求量确定订单的最 大拣选次数，以获得K-I个虚拟需求点；其中，K为订单的最大拣选次数。例如，假设拣选设备容量为Q，一个订单所涉及的需求点个数为n，每个需求点 的需求量不大于Q，总的需求量为P，则使总拣选路径最短的拣选作业次数K满足条件
一种订单拣选方法，应用于需要在多个巷道中水平移动的订单拣选，其特征在于，所述方法包括根据仓库货架的摆放情况，生成仓库平面布置图；计算并存储巷道和节点的信息；计算并存储仓库中各节点之间的最短路径；存储货物的货位信息、货物的大小及重量信息；在进行订单拣选时，从预存的数据中查找所述订单中所需货物的货位、大小及重量；根据所述订单中所需货物的数量、以及查找到的货物的大小及重量计算所需货物的需求量；并利用预先存储的各节点之间的最短路径计算任意两个所需货物之间的最短路径；根据拣选设备的容量、所述任意两个所需货物之间的最短路径以及所述订单中所需货物的需求量，通过遗传算法和LK算法求解最佳拣选路径，以使所述拣选设备根据所述最佳拣选路径进行订单拣选。
2.根据权利要求1所述的方法，其特征在于，所述利用预先存储的各节点之间的最短 路径计算任意两个所需货物之间的最短路径，具体包括若所述两个所需货物的存取位置位于同一巷道中，则所述两个所需货物之间的最短路 径为沿所述同一巷道的路径；若所述两个所需货物的存取位置位于不同巷道中，则分别确定这两个巷道上距离所述 存取位置最近的两对节点；从预先存储的各节点之间的最短路径中获取这两对节点之间的 最短路径；再根据所述存取位置到其最近的节点之间的距离确定所述两个所需货物之间的 最短路径。
3.根据权利要求1所述的方法，其特征在于，所述根据拣选设备的容量、所述任意两个 所需货物之间的最短路径以及所述订单中所需货物的需求量，通过遗传算法和LK算法求 解最佳拣选路径，具体包括根据所述拣选设备的容量、所述订单中需求点以及所需货物的需求量确定所述订单的 最大拣选次数，以获得K-I个虚拟需求点；其中，K为所述订单的最大拣选次数；根据所述虚拟需求点以及所需货物的货位随机产生多个初始的染色体，每个初始的染 色体包括(n+K-1)个需求点；其中，η为所述订单中需求点的数量；利用所述任意两个所需货物之间的最短路径，通过遗传算法和LK算法对所述多个初 始的染色体进行多次迭代优化，并根据优化后的多个染色体确定所述最佳拣选路径。
4.根据权利要求3所述的方法，其特征在于，在通过遗传算法和LK算法对所述多个初 始的染色体进行多次迭代优化中，一次迭代过程包括通过遗传算法对多个染色体进行选择、交叉、变异、重插入操作，获得下一代的染色体；通过LK算法对下一代的最优染色体进行优化。
5.根据权利要求4所述的方法，其特征在于，所述对多个染色体进行选择，具体包括 计算所述多个染色体中每一个染色体的适应度；根据所述适应度获得所述染色体被选择的概率；根据所述被选择的概率从所述多个染色体中选择出下一代的染色体。
6.根据权利要求4所述的方法，其特征在于，所述对多个染色体进行交叉操作，具体包括根据预设的交叉概率，选择待交叉的染色体；为任意两个待交叉的染色体选择交配区域； 交换所述两个选择交配区域后的染色体的交配区域；为每个交换后的染色体去掉重复的基因；具体包括查找到所述重复基因对应的交换 前所述染色体中的等位基因；用所述等位基因替换交换后的染色体中的所述重复基因。
7.根据权利要求4所述的方法，其特征在于，所述对多个染色体进行变异操作，具体包括 根据预设的变异概率，选择待变异的染色体；从所述待变异的染色体中随机选择待变异的基因片段；对所述待变异的基因片段进行翻转操作，以得到变异后的染色体。
8.根据权利要求4所述的方法，其特征在于，所述对多个染色体进行重插入操作，具体 包括将所述多个染色体中最优的若干染色体直接加入到下一代的染色体中。
9.一种订单拣选系统，应用于需要在多个巷道中水平移动的订单拣选，其特征在于，所 述系统包括服务器、无线局域网络与移动终端；其中，所述服务器包括制图单元，根据仓库货架的摆放情况，生成仓库平面布置图；计算出巷道和节点的信 息；计算仓库中各节点之间的最短路径；存储单元，存储货物的货位、大小及重量的信息，以及所述巷道和节点的信息；存储仓 库中各节点之间的最短路径；计算单元，用于从预存的数据中查找所述订单中所需货物的货位、大小及重量；根据所 述订单中所需货物的数量、以及查找到的货物的大小及重量计算所需货物的需求量；并利 用预先存储的各节点之间的最短路径计算任意两个所需货物之间的最短路径；求解单元，用于根据拣选设备的容量、所述任意两个所需货物之间的最短路径以及所 述订单中所需货物的需求量，通过遗传算法和LK算法求解最佳拣选路径，以使所述拣选设 备根据所述最佳拣选路径进行订单拣选。
10.根据权利要求9所述的系统，其特征在于，所述求解单元具体包括次数确定单元，用于根据所述拣选设备的容量、所述订单中需求点以及所需货物的需 求量确定所述订单的最大拣选次数，以获得K-I个虚拟需求点；其中，K为所述订单的最大 拣选次数；路径产生单元，用于根据所述虚拟需求点以及所需货物的货位随机产生多个初始的染 色体，每个初始的染色体包括(η+κ-1)个需求点；其中，η为所述订单中需求点的数量；路径获取单元，用于利用所述任意两个所需货物之间的最短路径，通过遗传算法和LK 算法对所述多个初始的染色体进行多次迭代优化，并根据优化后的多个染色体确定所述最 佳拣选路径。
本发明实施例提供一种订单拣选方法及系统，该方法包括根据仓库货架的摆放情况，生成仓库平面布置图，然后计算仓库中各节点之间的最短路径；从预存的数据中查找订单所需货物的货位、大小及重量；利用节点之间最短路径计算任意两个所需货物之间的最短路径和距离；根据拣选设备的容量、订单中所需货物的需求量求解最佳拣选路径，以使拣选设备根据最佳拣选路径进行订单拣选。通过本发明实施例，可高效地计算出拣选路径，降低作业成本，提高作业效率；解决在货架摆放不一、货架高度相对较小、对同一货位不同层的货架上的货物存取时所用代价差异不大、拣选作业需要优化的主要是拣选作业人员水平移动距离的情况下订单的拣选问题。
文档编号G06Q50/00GKSQ
公开日日 申请日期日 优先权日日
发明者刘军, 岳溥庥, 张海军, 朱杰 申请人:北京物资学院}