一种基于无人机快递柜优化分配方法论文和设计-朱洁

全文摘要

本发明提供一种基于无人机快递柜优化分配方法，包含快递柜空间优化调度流程和无人机转移包裹流程。在快递柜空间优化流程中，调度中心根据已经放置的包裹信息和快递柜空闲储物格信息，对包裹放置进行二次优化，其优化目标包括空间优化和距离优化，空间优化指尽可能把包裹放置到与其体积最接近的储物格中，距离优化是指尽可能将包裹放置在离消费者接近的快递柜中；在生成优化的放置方案后根据无人机可用状态，利用无人机在给定时间阈值内完成包裹的快速转移，从而提高快递柜存储空间的使用率，提高消费者的满意度。

主设计要求

1.一种基于无人机快递柜优化分配方法，其特征在于，对已经放置入快递柜的包裹进行位置和空间的二次优化，并利用无人机实施包裹的转移，包裹二次优化放置方法包含步骤为：S101、调度中心检查是否有新的包裹放置信息，更新快递柜空闲储物格集合F；S102、调度中心判断新放置包裹当前所放置的储物格是否是位置最佳储物格，如不是位置最佳储物格，则将其存入位置待优化集合L中等待优化；删除L中超期的待优化包裹；S103、判断当前位置待优化集合L是否为空，如果不空则需要执行S104进行优化计算；S104：对L中的每一个包裹pi，在F中查找是否存在位置离目的地更近且空间足够大的储物格；将所有满足要求的储物格暂存入该包裹的候选储物格集合Ci；S105：调度中心对每一个已放置包裹，检查当前所放置的储物格是否是空间最佳储物格，如果否，则将其存入空间待优化集合S中等待优化；删除S中超期的待优化包裹；S106：判断当前空间待优化集合S是否为空，如果不空则需要执行S107进行优化计算；S107：对S中的每一个包裹pi，在F中查找是否存在位置离目的地一样近且空间更接近该包裹的储物格；将所有满足要求的储物格暂存入该包裹的候选储物格集合Ci；S108：对于每一个待优化包裹pi及其候选储物格集合Ci，查看是否可行的包裹转移方案，即存在无人机可以在指定时间阈值T内，完成包裹转移任务；S109：检查S108是否产生了可行的转移方案，如果没有则转至S101等待下一次调度；如果存在可行的转移方案，则进入S110，对转移方案进行进一步的选择；S110：为每个包裹中选择当前最佳的可行方案；S111：判断当前最佳的可行方案是否是位置最佳方案，如果不是，则表明该包裹可能在后续调度周期里面再次被转移；如果是，则执行S112；S112：将选定方案是位置最佳的包裹从L中删除，它将不再进行位置优化；S113：判断当前最佳的可行方案是否是空间最佳方案，如果不是，则表明该包裹可能在后续调度周期里面再次被转移；如果是，则执行S114；S114：将选定方案是空间最佳的包裹从S中删除，它将不再进行空间优化；S115：调度中心向包裹即将转移到的储物柜发送储物格锁定命令，所述锁定储物格命令至少包含待锁定的储物格ID、快递柜ID和锁定时长；S116：调度中心向转移方案中指定的无人机发送包裹转移命令；S117：调度中心实时监控无人机转移包裹过程，并更新新放置包裹信息和新空闲储物格信息，移出已经放置了给定时间阈值的包裹，标记为不可优化包裹；其中，S116中，无人机转移包裹流程为：a、无人机收到来自调度中心的包裹转移命令，所述包裹转移命令至少包含包裹ID、包裹当前所在储物格ID、包裹当前所在快递柜ID和快递柜位置、包裹转移目标快递柜ID和快递柜位置、以及包裹转移目标储物格ID，无人机根据指令中指定的包裹所在位置，飞往包裹所在快递柜A；b、无人机到达包裹所在快递柜A后，向快递柜A发送验证信息请求开柜并装载包裹；c、无人机装载包裹飞至该包裹最佳储物格，向该储物格所在快递柜B发送验证信息请求开柜并存入包裹；d、无人机向调度中心发送完成包裹转移消息；e、无人机在快递柜B等待下一个包裹转移指令。

设计方案

1.一种基于无人机快递柜优化分配方法，其特征在于，对已经放置入快递柜的包裹进行位置和空间的二次优化，并利用无人机实施包裹的转移，包裹二次优化放置方法包含步骤为：

S101、调度中心检查是否有新的包裹放置信息，更新快递柜空闲储物格集合F；

S102、调度中心判断新放置包裹当前所放置的储物格是否是位置最佳储物格，如不是位置最佳储物格，则将其存入位置待优化集合L中等待优化；删除L中超期的待优化包裹；

S103、判断当前位置待优化集合L是否为空，如果不空则需要执行S104进行优化计算；

S104：对L中的每一个包裹p_{i<\/sub>，在F 中查找是否存在位置离目的地更近且空间足够大的储物格；将所有满足要求的储物格暂存入该包裹的候选储物格集合C i<\/sub>；}

S105：调度中心对每一个已放置包裹，检查当前所放置的储物格是否是空间最佳储物格，如果否，则将其存入空间待优化集合S中等待优化；删除S中超期的待优化包裹；

S106：判断当前空间待优化集合S是否为空，如果不空则需要执行S107进行优化计算；

S107：对S中的每一个包裹p_{i<\/sub>，在F 中查找是否存在位置离目的地一样近且空间更接近该包裹的储物格；将所有满足要求的储物格暂存入该包裹的候选储物格集合C i<\/sub>；}

S108：对于每一个待优化包裹p_{i<\/sub>及其候选储物格集合Ci<\/sub>，查看是否可行的包裹转移方案，即存在无人机可以在指定时间阈值T内，完成包裹转移任务；}

S109：检查S108是否产生了可行的转移方案，如果没有则转至S101等待下一次调度；如果存在可行的转移方案，则进入S110，对转移方案进行进一步的选择；

S110：为每个包裹中选择当前最佳的可行方案；

S111：判断当前最佳的可行方案是否是位置最佳方案，如果不是，则表明该包裹可能在后续调度周期里面再次被转移；如果是，则执行S112；

S112：将选定方案是位置最佳的包裹从L中删除，它将不再进行位置优化；

S113：判断当前最佳的可行方案是否是空间最佳方案，如果不是，则表明该包裹可能在后续调度周期里面再次被转移；如果是，则执行S114；

S114：将选定方案是空间最佳的包裹从S中删除，它将不再进行空间优化；

S115：调度中心向包裹即将转移到的储物柜发送储物格锁定命令，所述锁定储物格命令至少包含待锁定的储物格ID、快递柜ID和锁定时长；

S116：调度中心向转移方案中指定的无人机发送包裹转移命令；

S117：调度中心实时监控无人机转移包裹过程，并更新新放置包裹信息和新空闲储物格信息，移出已经放置了给定时间阈值的包裹，标记为不可优化包裹；

其中，S116中，无人机转移包裹流程为：

a、无人机收到来自调度中心的包裹转移命令，所述包裹转移命令至少包含包裹ID、包裹当前所在储物格ID、包裹当前所在快递柜ID和快递柜位置、包裹转移目标快递柜ID和快递柜位置、以及包裹转移目标储物格ID，无人机根据指令中指定的包裹所在位置，飞往包裹所在快递柜A；

b、无人机到达包裹所在快递柜A后，向快递柜A发送验证信息请求开柜并装载包裹；

c、无人机装载包裹飞至该包裹最佳储物格，向该储物格所在快递柜B发送验证信息请求开柜并存入包裹；

d、无人机向调度中心发送完成包裹转移消息；

e、无人机在快递柜B等待下一个包裹转移指令。

2.如权利要求1所述的一种基于无人机快递柜优化分配方法，其特征在于，S101中，包裹放置信息由快递柜的监控系统发给调度中心，其至少包含包裹ID、包裹目的地ID、储物格ID、快递柜ID、包裹的体积参数和包裹放置时间；空闲储物格信息由快递柜的监控系统发给调度中心，至少包含储物格ID和储物格所在的快递柜ID、储物格空间参数和状态信息。

3.如权利要求1所述的一种基于无人机快递柜优化分配方法，其特征在于，S102中，调度中心判断包裹所放置储物格是否是位置最佳的储物格，标准是储物格所在快递柜是否是离包裹的目的地最近的快递柜，距离越近则表示位置越佳。

4.如权利要求1所述的一种基于无人机快递柜优化分配方法，其特征在于，S105中，调度中心判断包裹所放置储物格是否是空间更佳的储物格，标准是是否存在空闲可用的储物格，其空间参数小于包裹所放置储物格的体积参数但是大于包裹的体积参数，如果不存在则表明包裹所放置储物格为空间最佳。

5.如权利要求1所述的一种基于无人机快递柜优化分配方法，其特征在于，S108中，包裹转移方案至少包含包裹ID、包裹当前所在储物格ID、包裹当前所在快递柜ID、包裹转移目标快递柜ID、包裹转移目标储物格ID。

6.如权利要求1所述的一种基于无人机快递柜优化分配方法，其特征在于，S 108中，调度中心判断包裹转移方案是否可行的方法是，计算每台无人机从当前所在位置飞到包裹所在快递柜所需要的时间、取出包裹所需要时间、从包裹所在快递柜飞往包裹转移方案中指定的目的储物格所在快递柜所需时间的总和，如果时间总和大于指定阈值，则该方案不可行；否则可行；可行包裹转移方案存在多个时，根据优先级策略为包裹选定最佳可行包裹转移方案。

7.如权利要求6所述的一种基于无人机快递柜优化分配方法，其特征在于，为包裹选定最佳可行转移方案时，其优先级策略设定为以位置为优先指标或以空间为优先指标或以包裹首次放置时间为优先指标，不可以选定有冲突的转移方案；有冲突的转移方案是指两个不同包裹的转移目标储物格为同一个。

8.如权利要求1所述的一种基于无人机快递柜优化分配方法，其特征在于，调度优化过程为周期性持续过程，在包裹未被转移到最佳储物格之前，会被多次转移，直到其放置时间超过指定阈值，或已经被放置到了最佳储物格内，储物格锁定解除，包裹的最佳储物格是指对该包裹位置最佳且空间最佳的储物格。

9.如权利要求2所述的一种基于无人机快递柜优化分配方法，其特征在于，包裹的体积参数至少包含包裹的长、宽和高度信息；储物格的空间参数至少包含储物格空间的长、宽和高度信息。

设计说明书

技术领域

本发明涉及物流配送、无人机与调度优化领域，在物流配送环节中提出一种利用无人机进行快递柜空间分配二次优化和实施的方法。

背景技术

随着电子商务的发展和人们消费能力的提升，我国电子商务和物流行业进入高速发展时期。与此同时，快递企业不得不面临人工成本高、人员流动性大、从业人员业务水平参差不齐等现状。对于快递企业来说，如何完成“最后一公里”末端配送，找到成本低、效率高且消费者满意的配送方案，是急切需要解决的问题。

随着快递柜的出现和普及，消费者出于安全和收货时间考虑，更期望将包裹送至离家最近的快递柜。而目前很多公寓楼设置有出入门禁，阻止了快递员将快递直接送至消费者手中，也使得很多快递员首选将快递送至空闲的快递柜。但是，快递员在选择快递柜时，会面临需要决策的难题：哪些包裹放在哪些快递柜中。如果目标快递柜已满，该如何选择下一个快递柜。

针对这样的问题，目前存在一些研究，规划快递员投递包裹的调度方案：根据当前快递员负责区域的快递柜剩余空间情况和待运送的包裹目的地，以包裹尽可能靠近消费者为目标，为每一个包裹计算应该送至的快递柜（包裹放置方案），并为快递员规划尽可能短的运送路线（运送路径规划）。这样的调度算法，能够完美实施的前提是：快递柜的空闲空间会为了该放置方案而锁定不被其他快递员使用。而这往往是不现实的，因为快递员可能需要花费很长时间（以小时计）完成一趟运送，而快递柜空闲储物格不可能长时间被某家快递公司独占，因为快递柜通常是共享的。更可能的场景是：快递员到达快递柜后，发现快递柜空闲储物格少于预期，不得不重新调整包裹放置方案。所以，更加现实的应用场景是快递员根据初始规划的放置方案和运送路径规划进行包裹运送，该方案会随着快递柜空闲空间的变化而实时调整，需要快递员听从指挥，根据实时调度方案进行运送。但是这样的方案实施起来代价不小：需要一整套的调度系统；为快递员配备通信设备和定位装置；系统需要接入快递柜系统获取实时信息等。所以目前暂未有快递公司实施这样的方案，快递员在决定包裹放置位置时，主要根据经验判断送达哪些快递柜（一个目的地地址对应一组合适的快递柜）比较合适，并将包裹放置到遇到的第一个有空闲储物格且位置合适的快递柜。

随着时间的推移，有的快递柜可能有包裹被取走，产生新的空闲位置，而此时可能存在包裹在原来的调度方案中因为空间不足而放置到离消费者次近的快递柜，此时如果能够根据快递柜实时空闲情况进行调度方案的调整，可能能得到更加好的放置方案。但是这种设想如果需要实现，会面临很多问题，例如如果此时包裹已经放置完毕，如何将它移动到其他更好的位置。

此外，快递员在放置包裹时，如果当前快递柜只剩下一个空闲位置，哪怕这个位置的存储空间远大于其所要运送包裹，在无法预知下一个快递柜有多少剩余空间的情况下，快递员极可能会将一个小包裹安放到一个大的储物格里，造成空间浪费。让快递员个体去遵从空间优化的放置原则，从心理学角度而言并不现实。

从共享快递柜的角度，它的用户有两类：快递公司和消费者。让共享快递柜实施已放置包裹的二次放置优化并利用无人机进行包裹转移，可提高其空间使用率，提高快递员的送货效率，并让快递更接近消费者，无论对快递公司还是消费者而言都可以极大的提高用户体验。

发明内容

为了提高快递柜存储空间的使用效率，并优化包裹放置方案，本发明提供一种基于无人机的共享快递柜优化分配方法，对同一区域快递柜中已经放置的包裹生成二次优化的放置方案，优化目标包括空间优化和距离优化，空间优化指尽可能把包裹放置到与其体积最接近的储物格中，距离优化是指尽可能将包裹放置在离消费者接近的快递柜中；在生成放置方案后利用无人机实施包裹位置的转移，从而提高快递柜存储空间的使用率，并通过优化包裹放置方案来提高消费者的满意度。

本发明所述的一种基于无人机快递柜优化分配方法，其采用的技术方案为：对已经放置入快递柜的包裹进行位置和空间的二次优化，并利用无人机实施包裹的转移，包裹二次优化放置方法包含步骤为：

S101、调度中心从快递柜处接收新放置包裹信息、更新快递柜空闲储物格集合F；新放置包裹信息至少包含包裹ID、包裹目的地ID、储物格ID、快递柜ID、包裹的体积参数和包裹放置时间，新空闲储物格信息至少包含储物格ID和储物格所在的快递柜ID、储物格空间参数和状态信息，调度中心对于每一个新产生的空闲储物格，将其信息存入空闲储物格集合F中；

S102、调度中心调度中心对每一个新放置包裹，判断新放置包裹当前所放置的储物格是否是位置最佳储物格，即检查其是否被放置到离目的地最近的快递柜，距离越近则表示位置越佳；如果否，则将其标记为位置待优化包裹，存入位置待优化集合L中等待优化；检查当前位置待优化集合L中是否有存在较长时间都未能优化的包裹，将它们标记为不可优化包裹，将其从L中删除；

S103、判断当前位置待优化集合L是否为空，如果不空则需要执行S104进行优化计算，如果当前位置待优化集合L为空，则回到S101；

S104：对L中的每一个包裹p_{i<\/sub>，在F 中查找是否存在位置离目的地更近且空间足够大的储物格；将所有满足要求的储物格暂存入该包裹的候选储物格集合C i<\/sub>；}

S105：调度中心对每一个已放置包裹p_{i<\/sub>，检查当前所放置的储物格是否是空间最佳储物格，如果否，则将其存入空间待优化集合S中等待优化；删除S中超期的待优化包裹；}

S106：判断当前空间待优化集合S是否为空，如果不空则需要执行S107进行优化计算，如果为空，则返回S101；

S107：对S中的每一个包裹p_{i<\/sub>，在F 中查找是否存在位置离目的地一样近且空间更接近该包裹的储物格；将所有满足要求的储物格暂存入该包裹的候选储物格集合C i<\/sub>；}

S108：对于每一个待优化包裹p_{i<\/sub>及其候选储物格集合Ci<\/sub>，查看是否产生可行的包裹转移方案，即调度中心根据当前可用无人机位置和状态，为新放置包裹计算可在在指定时间阈值T内实施包裹转移任务的无人机，得到可行的包裹转移方案；}

S109：检查S108是否产生了可行的转移方案，如果没有则转至S101等待下一次调度；如果存在可行的包裹转移方案，则进入S110，对包裹转移方案进行进一步的选择；

S110：调度中心为每个包裹p_{i<\/sub>选择当前最佳的可行方案；}

S111：调度中心判断当前最佳的可行方案是否是位置最佳方案，如果不是，则表明该包裹可能在后续调度周期里面再次被转移；如果是，则执行S112；

S112：调度中心将选定方案是位置最佳的包裹p_{i<\/sub>从L中删除，它将不再进行位置优化；}

S113：调度中心判断当前最佳的可行方案是否是空间最佳方案，如果不是，则表明该包裹p_{i<\/sub>可能在后续调度周期里面再次被转移；如果是，则执行S114；}

S114：调度中心将选定方案是空间最佳的包裹p_{i<\/sub>从S中删除，它将不再进行空间优化；}

S115：调度中心向包裹转移方案中指定的转移目的地储物柜发送储物格锁定命令，锁定储物格命令至少包含待锁定的储物格ID、快递柜ID和锁定时长，锁定为待优化包裹选择的最佳储物格，在指定时间阈值T内不允许该储物格被其他包裹占用；

S116：调度中心向转移方案中指定的无人机发送包裹转移命令；

S117：调度中心实时监控无人机转移包裹过程，并更新新放置包裹信息和新空闲储物格信息，移出已经放置了给定时间阈值T的包裹，标记为不可优化包裹。

进一步的，S105中，调度中心判断包裹所放置储物格是否是空间更佳的的储物格，标准是是否存在空闲可用的储物格，其空间参数小于包裹所放置储物格的体积参数但是大于包裹的体积参数，如果不存在则表明包裹所放置储物格为空间最佳，在考虑储物格空间是否能够容纳包裹体积时，需要综合考虑包裹横、竖等多种放置方法。

进一步的，S108中，包裹转移方案至少包含包裹ID、包裹当前所在储物格ID、包裹当前所在快递柜ID、包裹转移目标快递柜ID、包裹转移目标储物格ID。

进一步的，S108中，调度中心判断包裹转移方案是否可行的方法是，计算每台无人机从当前所在位置飞到包裹所在快递柜所需要的时间、取出包裹所需要时间、从包裹所在快递柜飞往包裹转移方案中指定的目的储物格所在快递柜所需时间的总和，如果时间总和大于指定阈值，则该方案不可行；否则可行；可行包裹转移方案存在多个时，根据一定的优先级策略为包裹选定最佳可行包裹转移方案。

进一步的，为包裹选定最佳可行转移方案时，其优先级策略设定为以位置为优先指标或以空间为优先指标或以包裹首次放置时间为优先指标，不可以选定有冲突的转移方案；有冲突的转移方案是指两个不同包裹的转移目标储物格为同一个。

进一步的，调度优化过程为周期性持续过程，在包裹未被转移到最佳储物格之前，会被多次转移，直到其放置时间超过指定阈值，或已经被放置到了最佳储物格内，储物格锁定解除，包裹的最佳储物格是指对该包裹位置最佳且空间最佳的储物格。

进一步的，包裹的体积参数至少包含包裹的长、宽和高度信息；储物格的空间参数至少包含储物格空间的长、宽和高度信息。

进一步的，S116中，无人机转移包裹流程为：

a、无人机收到来自调度中心的包裹转移命令，所述包裹转移命令至少包含包裹ID、包裹当前所在储物格ID、包裹当前所在快递柜ID和快递柜位置、包裹转移目标快递柜ID和快递柜位置、以及包裹转移目标储物格ID，无人机根据指令中指定的包裹所在位置，飞往包裹所在快递柜A；

b、无人机到达包裹所在快递柜A后，向快递柜A发送验证信息请求开柜并装载包裹；

c、无人机装载包裹飞至该包裹最佳储物格，向该储物格所在快递柜B发送验证信息请求开柜并存入包裹；

d、无人机向调度中心发送完成包裹转移消息；

e、无人机在快递柜B等待下一个包裹转移指令。

本发明所述的有益效果为：在快递柜空间优化流程中，调度中心根据已经放置的包裹信息和快递柜空闲储物格信息，对同一区域快递柜中已经放置的包裹生成空间和距离二次优化的放置方案，在生成优化的放置方案后根据无人机可用状态，利用无人机在给定时间阈值内完成包裹的快速转移，从而提高快递柜存储空间的使用率，提升快递员的送货效率，进而提高消费者的满意度。

附图说明

为了使本发明的内容更容易被清楚地理解，下面根据具体实施例并结合附图，对本发明作进一步详细的说明。

图1是本发明一种基于无人机的快递柜优化分配方法的调度中心调度流程示意图。

图2是本发明一种基于无人机的快递柜优化分配方法的无人机转移包裹流程示意图。

图3是包裹放置信息表。

图4是空闲储物格信息表。

图5是目的地与快递柜距离矩阵。

图6是快递柜的距离矩阵表。

图7是无人机位置信息表。

具体实施方式

本发明提供一种基于无人机的快递柜优化分配方法，旨在优化包裹放置位置和快递柜空间使用，以下分别进行详细说明。

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完善地描述，显然，所描述的实施例仅仅是本发明的一部分实施例，而不是全部实施例。基于本发明中的实施例，本领域普通技术人员在没有做出劳动成果的前提下所获得的所有其他实施例，都属于本发明的保护范围。

图1为本发明一种基于无人机的快递柜优化分配方法的调度中心调度流程示意图，具体包括如下步骤：

S101：调度中心检查是否有新的包裹放置信息，更新快递柜空闲储物格集合F；

调度中心收到一组消息，包含若干条新的包裹放置信息和新的空闲储物格信息。一条包裹放置信息应该包含包裹ID，包裹目的地ID，快递柜ID，储物格ID和包裹的体积参数。空闲储物格消息应该至少包含储物格ID和快递柜ID。调度中心维护一个空闲的储物格表格F<\/i>，将新到达的空闲储物格信息存入表格中。

例如，调度中心存储的包裹放置信息如图3所示，为了便于信息查找，包裹所存储的储物格空间参数和包裹首次放置时间也在图3中显示，体积\/空间参数包含三个数值：长、宽、高。包裹首次放置的时间用于后面判断包裹是否超期。快递柜一般是在包裹入柜后立刻给消费者发送包裹取货通知，在本发明场景中，快递柜可以稍迟一点再发出信息，例如延迟20分钟发送，利用这20分钟的延迟时间进行二次优化的，一旦包裹取货信息发出，再转移包裹位置，会造成用户体验的下降。

调度中心维护的一张空闲储物格表格如图4所示。为了便于信息查找，空闲储物格的空间参数和状态也在图4中显示。空闲储物格的状态有“正常”和“锁定”两种。当一个储物格将要被用于二次优化时，会处于“锁定”状态，等待包裹到达。

S102：调度中心对每一个已放置包裹，检查其是否被放置到离目的地最近的快递柜；如果否，则将其存入位置待优化集合L中等待优化；删除L中超期的待优化包裹；

调度中心维护一张该区域所有建筑物与快递柜之间的距离矩阵表格，如图5所示。

根据图5数据表明，包裹P1并没有放入离其目的地B1最近的快递柜L2（P1当前存在L1内，与其目的地B1距离500米，而与B1最接近的快递柜L2距离只有200米），包裹P1为位置待优化包裹；P2和P3都已经放置到与其目的地最接近的快递柜。

S103：判断当前位置待优化集合L是否为空，如果不空则需要执行步骤104进行优化计算。

当前L至少存在包裹P1待进行位置优化。

S104：对L中的每一个包裹，在F 中查找是否存在位置离目的地更近且空间足够大的储物格；将所有满足要求的储物格暂存入该包裹的候选储物格集合C _i<\/sub>；

对于包裹P1，通过图4和图5的信息得出，存在空闲储物格G5、G6、G7和G8所在快递柜都比P1当前所在快递柜L1更接近其目的地B1，且储物格空间可放下P1，令P1的候选储物格集合C_{1<\/sub>={G5, G6, G7, G8}。}

S105：调度中心对每一个已放置包裹，检查其是否被放置在空间最合适的储物格；如果否，则将其存入空间待优化集合S中等待优化；删除S中超期的待优化包裹；

调度中心根据图4的当前空闲储物格的信息，计算得出对于包裹P1、P2都存在比目前储物格更小且能放下包裹的空闲储物格，因此将P1、P2标记为空间待优化包裹。

S106：判断当前空间待优化集合S是否为空，如果不空则需要执行步骤107进行优化计算；

当前S至少存在包裹P1和P2待进行空间优化。

S107：对S中的每一个包裹p_{i<\/sub>，在F 中查找是否存在位置不比当前位置离目的地更远的且空间足够大的储物格；将所有满足要求的储物格暂存入该包裹的候选储物格集合C i<\/sub>；}

调度中心根据图4当前的空闲储物格信息，计算得出对于P1而言，存在储物格G4、G6和G7不比G1离B1更远且存储空间比G1更小，将它们更新至P1的候选储物格集合C_{1<\/sub>中，此时C1<\/sub>={G4, G5, G6, G7, G8}。对P2而言，存在储物格G8比其当前所在储物格G2更小且能放得下P2，并且G8离目的地B2的距离与G2相同，所以C 2<\/sub>={G8}。}

S108：对于每一个待优化包裹p<\/i>_{i<\/i><\/sub>及其候选储物格集合C<\/i>i<\/i><\/sub>，查看是否可行的包裹转移方案，即存在无人机可以在指定时间阈值T内，完成包裹转移任务；}

确定了包裹转移方案后，为了保证包裹转移过程中，目的储物格不会被其他快递员或消费者使用，因此需要对该储物格进行锁定，锁定的时间不能太长，否则失去了空间优化的意义，因此设置一个阈值T，用于判断转移方案是否可行。一个包裹转移方案可表述为一个向量<包裹ID,包裹原储物格ID,包裹的候选储物格ID>。

例如在该实施例中T设置成2分钟。调度中心维护当前空闲无人机的位置信息，空闲的无人机一般都停留在该区域某个快递柜上方安置的充电桩\/停机坪处等待任务。假设空闲无人机电量足以进行时长为T的飞行任务，且假设无人机每次只能装载一个包裹。无人机载重足以承重任何一个待优化包裹（超重包裹将默认不考虑进行二次优化）。调度中心需要维护一张快递柜的距离矩阵表（如图6所示）和无人机位置信息表（如图7所示）。

给定无人机的平均飞行速度，根据图6和图7的信息，计算得出对P1的所有转移方案<P1, G1, G4>, <P1, G1, G5>,<P1, G1, G6>,<P1, G1, G7>,<P1, G1, G8>中，只有方案<P1, G1, G7>,<P1, G1, G8>可以通过无人机U1在T时间内完成。对于P2的转移方案<P2,G2, G8>可以通过无人机U2在T时间内完成。

S109：检查S108是否产生了可行的转移方案，如果没有则转至S101等待下一次调度；如果存在可行的转移方案，则进入S110，对转移方案进行进一步的选择；

根据S108对包裹P1和P2都产生了可行的转移方案。

S110：为每个包裹中选择当前最佳的可行方案；

如果某个包裹存在多个可行的转移方案，需要为该包裹选择离包裹目的地最近且空间最接近的最佳储物格；也可以从当前所有可行转移方案里面进行全局的优化选择，因为可行转移方案可能存在冲突，例如两个包裹的转移方案中目的地储物格相同。在转移方案有冲突的情况下，可以设定一定的优选策略，例如先到达的包裹优先；或者比较可行方案中更佳的优先。

已知P1的可行转移方案有方案<P1, G1, G7>,<P1, G1, G8>；P2的转移方案有<P2, G2, G8>。如果比较<P1, G1, G7>和<P1, G1, G8>这两个方案，发现它们在同一个快递柜上，也就是说离目的地的距离一样近，G7比G8的空间小，所以G7更适合存储P1，因此为P1选定方案<P1, G1, G7>。P2的转移方案只有一个<P2, G2, G8>，且与P1的选定方案无冲突，因此为P1和P2都选择好了当前最佳可行方案。

S111：判断当前最佳的可行方案是否是位置最佳方案，如果不是，则表明该包裹可能在后续调度周期里面再次被转移；如果是，则执行S112；

经过计算，对P1而言位置最佳快递柜是L2，而G7所在快递柜是L3，不是位置最佳快递柜；对P2而言位置最佳快递柜是L1和L2，而G8所在快递柜是L3，也不是位置最佳方案。虽然生成的方案不是全局最佳，但是比当前它们放置的位置要好。

S112：将选定方案是位置最佳的包裹从L中删除，它将不再进行位置优化；

S113：判断当前最佳的可行方案是否是空间最佳方案，如果不是，则表明该包裹可能在后续调度周期里面再次被转移；如果是，则执行S114；

经过计算，对P1而言空间最佳储物格是G6，因此当前对P1生成的最佳可行方案不是空间最佳方案；对P2而言位置最佳空间储物格是G8，而当前对P1生成的最佳可行方案是空间最佳方案。

S114：将选定方案是空间最佳的包裹从S中删除，它将不再进行空间优化；

在为P2选择的方案<P2, G2, G8>中，达到空间最佳，所以将P2从S中删除。

S115：向包裹即将转移到的储物柜发送储物格锁定命令；

调度中心向快递柜L3发送锁定G7命令，向快递柜L3发送锁定G8命令，并更新表2，将储物格G7和G8的状态修改为“锁定”；

S116：向转移方案中指定的无人机发送包裹转移命令；

调度中心向无人机U1发送包裹转移命令执行转移方案<P1, G1, G7>，向无人机U2发送包裹转移命令执行转移方案<P2, G2, G8>。

S117：实时监控无人机转移包裹的完成情况和快递柜实时信息。

调度中心实时监控无人机转移包裹的情况，当U1和U2取出包裹后，更新空闲储物格信息，将G1和G2作为新的空闲储物格添加到图4中；当U1和U2完成包裹转移任务后，更新P1和P2包裹在图3中的信息，同时将G7和G8从图4中删除。并准备实施下一个周期的调度优化。

以上所述仅为本发明的优选方案，并非作为对本发明的进一步限定，凡是利用本发明说明书及附图内容所作的各种等效变化均在本发明的保护范围之内。

设计图