本发明涉及货物装箱配送技术领域，尤其涉及一种求解三维装箱约束的有限容量路径规划问题的迭代方法。
背景技术：
在实际物流运输过程中，货物配送是极为关键的一环。在集中供货的零售行业，货物需要按时从仓库送到每个零售商。这种调度问题一般可以抽象为：给定一个存放货物的物流中心，若干停在物流中心同类型的可利用车辆，若干客户以及这些客户需要的货物，如何有效安排可利用车辆的路径，把这些货物从物流中心送到每一个客户并使得某项指标最小。其中，以减低所有车辆的总运输距离为目标，同时，在安排一辆车辆的路径时，不仅要求配送货物的重量不能超过车辆的限载重量，还要给出一个切实可行的装箱方案以供工人或机器装载，我们称这个问题为考虑三维装箱约束的有限容量路径规划问题。
这是一个典型的耦合优化问题，包含了两个np难问题：三维装箱问题(3dpp)和有限容量路径规划问题(cvrp)。目前，求解该耦合问题的一个通用求解方法如下，首先忽略三维装箱约束，调用所述有限容量路径规划问题的求解算法(以下简称routsolver)求出一个可行的候选路径规划解决方案，再针对该候选解决方案，用装箱算法(以下简称packsolver)核实该路径是否有可行的装箱解。其中需要注意的是，车辆行驶路径是车辆要进行配送的有序客户点序列，每个客户点包含了该客户所需配送的货物。通过调用routsolver得到的每一条路径，都需要对调用packsolver该路径进行装箱可行性检查，即检查该路径客户所需配送货货物是否可以全部装进车厢。如何控制packsolver在每次调用时搜索解的数量是求解考虑三维装箱约束的有限容量路径规划问题过程中的难题，分配过多或过少都会影响最终解的质量。如果packsolver每次搜索解的数量过多，会导致packsolver花费过多时间，从而导致routsolver尝试的解的数量太少从而影响最终解的质量；如果packsolver每次搜索解的数量过少，会出现一条路径本来存在可行的装箱方案而packsolver误判为不存在，也会影响最终解的质量。
而目前求解时间分配方法一般是直接将求解时间平均分配或通过人工调整迭代次数(下文将该过程统称为调参)，经过长期的测试，从而选定合适固定值。这种方法的局限性是仅对于某种规模的实例有较好的性能表现，而不具备较优的泛化能力，每当实例规模发生改变，就需要重新进行人工调整参数而不能根据实例规模自动地调整参数值，特别是不能根据子问题的初始条件的优劣来调整寻解时间或迭代次数，并且调整参数依赖于调参经验且十分费时，效率较为低下。
技术实现要素：
针对背景技术提出的问题，本发明的目的在于提出一种求解三维装箱约束的有限容量路径规划问题的迭代方法，避免了非必要的装箱算法的调用，有效提高效率，且提高了耦合优化问题的解质量，达到算法提速和性能提升的效果，解决了现有迭代方法繁琐单一、机械化、无法适应规模变化的问题。
为达此目的，本发明采用以下技术方案：
一种求解三维装箱约束的有限容量路径规划问题的迭代方法，包括以下步骤：
(1)调用有限容量路径规划问题的求解算法求得有限容量路径规划问题的一条可行的候选路径解；
(2)判断所述候选路径解是否在hashmap中；
若所述候选路径解不在hashmap中，则跳转到步骤(3)，否则，则跳转到步骤(4)；
(3)调用装箱算法并保存搜索解的结果，将调用装箱算法的信息记录在hashmap中，对hashmap进行更新，输出搜索解的结果；
(4)判断调用装箱算法搜索解的结果是否为存在；
若调用装箱算法搜索解的结果为存在，则输出存在；
否则，则跳转到步骤(5)；
(5)判断调用装箱算法搜索解的结果是否为不存在，且在所述候选路径上调用装箱算法的次数是否小于在所述候选路径上调用装箱算法的次数的上限值；
若调用装箱算法搜索解的结果为不存在，且在所述候选路径上调用装箱算法的次数小于在所述候选路径上调用装箱算法的次数的上限值，则跳转到步骤(6)；
若调用装箱算法搜索解的结果为不存在，且在所述候选路径上调用装箱算法的次数大于或等于在所述候选路径上调用装箱算法的次数的上限值，则输出不存在；
(6)增加在所述候选路径上调用装箱算法的次数，调用装箱算法并将搜索解的结果保存下来，将调用装箱算法的信息记录在hashmap中，对hashmap进行更新，输出搜索解的结果；
其中，调用装箱算法的信息指调用装箱算法搜索到的解的结果以及在所述候选路径上调用装箱算法的次数。
更进一步说明，所述有限容量路径规划问题的求解算法和所述装箱算法均采用启发式搜索算法。
更进一步说明，所述有限容量路径规划问题的求解算法采用模拟退火或随机邻域搜索算法，所述装箱算法采用邻域搜索算法。
更进一步说明，所述步骤(3)中，在所述候选路径上调用装箱算法的次数为1。
更进一步说明，所述步骤(5)中，在所述候选路径上调用装箱算法的次数的上限值为n^2，其中n指三维装箱问题中箱子的数量。
更进一步说明，所述步骤(6)中，在所述候选路径上调用装箱算法的次数为上次在所述候选路径上调用装箱算法的次数的两倍。
更进一步说明，所述步骤(3)中，调用装箱算法搜索解的结果为存在时，则输出存在，调用装箱算法搜索解的结果为不存在时，则输出不存在。
更进一步说明，所述步骤(6)中，调用装箱算法搜索解的结果为存在时，则输出存在，调用装箱算法搜索解的结果为不存在时，则输出不存在。
与现有技术相比，本发明具有以下有益效果：
1、通过将路径信息存储在hashmap中，且在每次调用装箱算法之前，对该路径进行判断，判断该路径是否存在于hashmap中，如果某一条路径的可行装箱方案已经被之前的装箱算法找到，那么通过在hashmap中对该路径的信息进行检索，可以避免对再次搜到的同一条路径调用装箱算法，避免了非必要的装箱算法的调用；
2、如果该路径没有找到装箱的可行解，那么提高在这条路径上所要进行迭代求装箱可行解的次数，使得求解的时间会更多的分配在经常搜索到的路径。经常搜索到的路径可近似认为是局部搜索的局部最优路径，增加它调用装箱算法的次数，有效提高求出最终可行解的概率；
3、通过设定在所述候选路径上调用装箱算法的次数的上限值，若达到所述候选路径上调用装箱算法的次数的上限值仍未找到可行装箱解，那么就认为这条路径没有可行的装箱解，在下次搜到该路径时，便不再进行装箱求解，不需要再调用装箱算法，避免了对同一条路径花费太多的求解时间，有效提高了本发明迭代方法的效率。
附图说明
附图对本发明做进一步说明，但附图中的内容不构成对本发明的任何限制。
图1是本发明一个实施例的求解三维装箱约束的有限容量路径规划问题的迭代方法的流程图；
具体实施方式
一种求解三维装箱约束的有限容量路径规划问题的迭代方法，包括以下步骤：
(1)调用有限容量路径规划问题的求解算法求得有限容量路径规划问题的一条可行的候选路径解；
(2)判断所述候选路径解是否在hashmap中；
若所述候选路径解不在hashmap中，则跳转到步骤(3)，否则，则跳转到步骤(4)；
(3)调用装箱算法并保存搜索解的结果，将调用装箱算法的信息记录在hashmap中，对hashmap进行更新，输出搜索解的结果；
(4)判断调用装箱算法搜索解的结果是否为存在；
若调用装箱算法搜索解的结果为存在，则输出存在；
否则，则跳转到步骤(5)；
(5)判断调用装箱算法搜索解的结果是否为不存在，且在所述候选路径上调用装箱算法的次数是否小于在所述候选路径上调用装箱算法的次数的上限值；
若调用装箱算法搜索解的结果为不存在，且在所述候选路径上调用装箱算法的次数小于在所述候选路径上调用装箱算法的次数的上限值，则跳转到步骤(6)；
若调用装箱算法搜索解的结果为不存在，且在所述候选路径上调用装箱算法的次数大于或等于在所述候选路径上调用装箱算法的次数的上限值，则输出不存在；
(6)增加在所述候选路径上调用装箱算法的次数，调用装箱算法并将搜索解的结果保存下来，将调用装箱算法的信息记录在hashmap中，对hashmap进行更新，输出搜索解的结果；
其中，调用装箱算法的信息指调用装箱算法搜索到的解的结果以及在所述候选路径上调用装箱算法的次数。
需要说明的是，所述有限容量路径规划问题的求解算法(routsolver)和装箱算法(packsolver)均采用现有的搜索算法。
在实际物流运输过程中，货物配送是极为关键的一环。在集中供货的零售行业，货物需要按时从仓库送到每个零售商。这种调度问题一般可以抽象为：给定一个存放货物的物流中心，若干停在物流中心同类型的可利用车辆，若干客户以及这些客户需要的货物，如何有效安排可利用车辆的路径，把这些货物从物流中心送到每一个客户并使得某项指标最小。其中，以减低所有车辆的总运输距离为目标，同时，在安排一辆车辆的路径时，不仅要求配送货物的重量不能超过车辆的限载重量，还要给出一个切实可行的装箱方案以供工人或机器装载，这个问题称为考虑三维装箱约束的有限容量路径规划问题。这是一个典型的耦合优化问题问题，包含了两个np难问题：三维装箱问题(3dpp)和有限容量路径规划问题(cvrp)。
其中子问题cvrp和3dpp的求解均是启发式迭代过程，先对cvrp进行迭代求解，每次得出cvrp的一个的候选解，3dpp都会取的cvrp的求解结果作为自己问题的求解初始条件，进而开始迭代求解，为了区别子问题cvrp和3dpp的求解顺序，称cvrp为主子问题，3dpp为次子问题。对于复杂的耦合优化问题，仅仅将其优化子问题的算法进行组合在一起，无法在合理的时间内得到较好的结果。
本发明在每次调用packsolver之前，对该路径rt进行判断：
情况1：若该路径rt是首次搜得，即不存在于hashmap中，则调用packsolver并将搜索解的结果保存下来，将该路径rt调用装箱算法的信息(is_feasible,calltimes)记录在hashmap中，返回is_feasible；
情况2：若该路径rt已存在于hashmap中，is_feasible＝“existence”，则返回“existence”；
情况3：若该路径rt已存在于hashmap中，is_feasible＝“inexistence”且calltimes≥max_calltimes：返回“inexistence”；
情况4：若该路径rt已存在于hashmap中，is_feasible＝＝“inexistence”且calltimes＜max_calltimes：增加calltimes，调用packsolver(r)并将搜索解数量限制在calltimes个，将返回结果赋值于is_feasible，并将该路径的信息(is_feasible,calltimes)记录在hashmap中,返回“is_feasible”。
其中，hashmap指哈希表，hashmap是键(key)值(value)对映射，key对象存储路径，value对象存储路径信息(在所述候选路径上调用装箱算法的次数和调用装箱算法搜索解的结果是否存在)，is_feasible表示调用packsolver搜索解的结果，calltimes表示在所述候选路径上调用装箱算法的次数，max_calltimes表示在所述候选路径上调用装箱算法的次数的上限值，“existence”表示调用装箱算法搜索解的结果为存在，“inexistence”表示调用装箱算法搜索解的结果为不存在。
该策略可以在如下三个方面节省时间：
1、通过将路径信息存储在hashmap中，且在每次调用装箱算法之前，对该路径进行判断，判断该路径是否存在于hashmap中，如果某一条路径的可行装箱方案已经被之前的装箱算法找到，那么通过在hashmap中对该路径的信息进行检索，可以避免对再次搜到的同一条路径调用装箱算法，避免了非必要的装箱算法的调用。(如上述情况2)
2、如果该路径没有找到装箱的可行解，那么提高在这条路径上所要进行迭代求装箱可行解的次数(如上述情况1、4)。因此，求解的时间会更多的分配在经常搜索到的路径。经常搜索到的路径可近似认为是局部搜索的局部最优路径，所以我们有必要增加它调用装箱算法的次数，以提高求出最终可行解的概率，这也是迭代加深策略的核心。
3、如果一条路径调用装箱算法的次数已经达到在所述候选路径上调用装箱算法的次数的上限值，此时仍未找到可行装箱解，那么就认为这条路径没有可行的装箱解(如上述情况3)，在下次搜到该路径时，便不再进行装箱求解，不需要再调用装箱算法，避免了对同一条路径花费太多的求解时间，有效提高了本发明迭代方法的效率。
综上，所述求解三维装箱约束的有限容量路径规划问题的迭代方法通过存储在hashmap中的路径信息，可以合理动态分配对寻得路径的装箱求解时间，避免了非必要的装箱算法的调用，借用了空间(内存)换时间的思想，合理自动调整耦合优化子问题迭代次数的策略，从而智能地根据迭代进程来分配子问题的求解迭代时间，有效提高效率，且提高了耦合优化问题的解质量，达到算法提速和性能提升的效果。该策略对优化子问题求解时间的动态分配，因而可以适用于不同规模三维装箱约束的有限容量路径规划问题。
更进一步说明，所述有限容量路径规划问题的求解算法和所述装箱算法均采用启发式搜索算法。
装箱算法(packsolver)是十分耗时的，所以尽量避免没必要的检查装箱可行性程序调用，为了快速得到质量好的解，所述有限容量路径规划问题的求解算法(routsolver)和所述装箱算法(packsolver)均采用启发式搜索算法。
具体地，所述有限容量路径规划问题的求解算法采用模拟退火或随机邻域搜索算法，所述装箱算法采用邻域搜索算法。
装箱算法(packsolver)是十分耗时的，所以尽量避免没必要的检查装箱可行性程序调用，为了快速得到质量好的解，所述有限容量路径规划问题的求解算法(routsolver)和所述装箱算法(packsolver)均采用启发式搜索算法，routsolver会通过随机算子构造新的路径，packsolver会通过局部搜索尝试多个装箱布局，以寻求可行装箱解。
具体地，所述步骤(3)中，在所述候选路径上调用装箱算法的次数为1。
在启发式搜索cvrp的路径rt中，越接近局部最优解，就值得调用越多次的packsolver来寻求该路径下的其可行装箱解；
这里，可行装箱解也就是整个耦合问题的可行解，就有越高的概率会多次被搜索到，对于每个首次搜到有限容量路径规划问题的一条可行的候选路径解(即cvrp解)，都会对其装箱解进行1次尝试性搜索(因为无法判别该路径是否为局部最优解，所以选择的最小的尝试搜索次数1)，避免了多次调用packsolver而浪费时间，所以当下一次又搜到所述候选路径的时候，该程序增加calltimes(因为所述候选路径再次被搜到了，是局部最优解的概率更高，更值得调用更多次packsolver来搜寻可行解)。
具体地，所述步骤(5)中，在所述候选路径上调用装箱算法的次数的上限值为n^2，其中n指三维装箱问题中箱子的数量。
通过设定在所述候选路径上调用装箱算法的次数的上限值(max_calltimes)，避免在无解的情况下出现死循环，max_calltimes的确定可以根据次子问题的规模来进行确定，在本发明中，主子问题是有限容量路径规划问题(cvrp)，次子问题是三维装箱问题(3dpp)，那么max_calltimes＝n^2，其中n是3dpp中箱子的数量，也是cvrp所求出的路径rt(所需配送客户的序列，每个客户都需要一定数量的箱子，也就是配送包裹)总的箱子数，那么装箱求解的难度是随着箱子的数量(即规模)的增大而增大，所以箱子越多，所需的最大求解次数也就越大(因为越难求解，且解空间越大)，这里n^2，首先是适应了装箱问题的规模(域适应)，而且是在n较大的情况下，该值是非常大的，这也符合np难问题(此处指装箱问题)随着规模的增大，越难求解的特性。
具体地，所述步骤(6)中，在所述候选路径上调用装箱算法的次数为上次在所述候选路径上调用装箱算法的次数的两倍。
当再次搜到该路径rt时，此时该路径是局部最优解的概率更大，所以更有价值调用更多次packsolver(r)程序对其进行求解；
此外，在耦合问题中，packsolver的求解前提条件是routsolver的可行解rt，在某些情况下，如考虑货物装箱后进先出的约束下，这条路径rt，也就是客户的配送顺序序列，会成为求装箱解的一个较强的约束，所以求得装箱可行解的概率会更小，所以有必要对calltimes进行较大程度的增幅，所以对再次遇到的路径进行加倍次数(加倍上次搜索次数)的搜索；
再之，每碰到同一条路径rt都在上次在所述候选路径上调用装箱算法的次数的基础上进行加倍，那第一次是1*2^(0)＝1次调用次数(调用packsolver)，第2次是1*2^(1)＝2，第3次是1*2^(2)＝4，以此类推，第i次是2^(i-1)，是一个比较合理的指数增长程度，避免了判断语句的多次调用，保证了求解三维装箱约束的有限容量路径规划问题的迭代方法的速度。
具体地，所述步骤(3)中，调用装箱算法搜索解的结果为存在时，则输出存在，调用装箱算法搜索解的结果为不存在时，则输出不存在。
调用装箱算法搜索到的解的结果(is_feasible)有两个取值，存在(“existence”)或不存在(“inexistence”)。is_feasible表示经过加速策略(即一系列elseif判断后调用一定次数的packsolver)后，得到的结果：如果搜到可行装箱解，就返回“existence”，反之返回“inexistence”；
所述步骤3中，即每第一次搜到这条路径rt(这是每条路径都会遇到的情况，所以把它置为情况1，避免了后续的elseif判断)，对于路径rt，在调用calltimes＝1次packsolver的尝试性搜索情况下，是否存在可行的装箱解，如果搜到可行解，就返回“existence”，反之返回“inexistence”。
具体地，所述步骤(6)中，调用装箱算法搜索解的结果为存在时，则输出存在，调用装箱算法搜索解的结果为不存在时，则输出不存在。
调用装箱算法搜索到的解的结果(is_feasible)有两个取值，存在(“existence”)或不存在(“inexistence”)。is_feasible表示经过加速策略(即一系列elseif判断后调用一定次数的packsolver)后，得到的结果：如果搜到可行装箱解，就返回“existence”，反之返回“inexistence”；
所述步骤(6)中，在再次搜到的同一条路径rt，该路径rt的is_feasible＝“inexistence”(即对于路径rt还没搜到可行装箱解)，且calltimes＜max_calltimes(即上次对路径rt的packsolver的调用次数还没到达设定的最大调用次数限制))的情况下，再增加calltimes，进行搜索，此时如果搜到可行解，就返回“existence”，反之返回“inexistence”。
下面详细描述本发明的实施方式，实施方式的示例在附图中示出，其中，相同或类似的标号自始至终表示相同或类似的元件或具有相同或类似功能的元件。下面通过参考附图描述的实施方式是示例性的，仅用于解释本发明，而不能理解为对本发明的限制。
流程图中或在此以其他方式描述的任何过程或方法描述可以被理解为，表示包括一个或更多个用于实现特定逻辑功能或过程的步骤的可执行指令的代码的模块、片段或部分，并且本发明的优选实施方式的范围包括另外的实现，其中可以不按所示出或讨论的顺序，包括根据所涉及的功能按基本同时的方式或按相反的顺序，来执行功能，这应被本发明的实施例所属技术领域的技术人员所理解。
如图1所示，一种求解三维装箱约束的有限容量路径规划问题的迭代方法，其特征在于，包括以下步骤：
(1)调用routsolver(具体采用模拟退火算法)求得cvrp的一条可行的候选路径解rt；
(2)判断rt是否在hashmap中；
若rt不在hashmap中，则跳转到步骤(3)，否则，则跳转到步骤(4)；
(3)调用1次packsolver(具体采用随机邻域搜索算法)并将搜索解的结果保存下来，将搜索解的结果赋值给is_feasible，将调用packsolver的信息记录在hashmap中，对hashmap进行更新，返回is_feasible；
(4)判断is_feasible是否＝“existence”；
若is_feasible＝“existence”，则返回“existence”；
否则，则跳转到步骤(5)；
(5)判断is_feasible是否＝“inexistence”且calltimes＜max_calltimes(具体为max_calltimes＝n^2)；
若is_feasible＝“inexistence”且calltimes＜max_calltimes(具体为max_calltimes＝n^2)，则跳转到步骤(6)；
若is_feasible＝“inexistence”且calltimes≥max_calltimes(具体为max_calltimes＝n^2)，则返回“inexistence”；
(6)增加calltimes的次数(具体为calltimes＝calltimes*2)，调用packsolver(具体采用随机邻域搜索算法)并将搜索解的结果保存下来，将搜索解的结果赋值给is_feasible，将调用packsolver的信息记录在hashmap中，对hashmap进行更新，返回is_feasible；
其中，routsolver指调用cvrp的求解算法，packsolver指装箱算法；
hashmap指哈希表，hashmap是键(key)值(value)对映射，key对象存储路径，value对象存储路径信息(在所述候选路径上调用装箱算法的次数和调用装箱算法搜索解的结果是否存在)，
is_feasible表示调用packsolver搜索解的结果，calltimes表示在所述可行的候选路径上调用packsolver的次数，max_calltimes表示calltimes的上限值，调用packsolver的信息指(is_feasible,calltimes)，n指3dpp中箱子的数量。
尽管已经示出和描述了本发明的实施例，本领域的普通技术人员可以理解：在不脱离本发明的原理和宗旨的情况下可以对这些实施例进行多种变化、修改、替换和变型，本发明的范围由权利要求及其等同物限定。
1.一种求解三维装箱约束的有限容量路径规划问题的迭代方法，其特征在于，包括以下步骤：
(1)调用有限容量路径规划问题的求解算法求得有限容量路径规划问题的一条可行的候选路径解；
(2)判断所述候选路径解是否在hashmap中；
若所述候选路径解不在hashmap中，则跳转到步骤(3)，否则，则跳转到步骤(4)；
(3)调用装箱算法并保存搜索解的结果，将调用装箱算法的信息记录在hashmap中，对hashmap进行更新，输出搜索解的结果；
(4)判断调用装箱算法搜索解的结果是否为存在；
若调用装箱算法搜索解的结果为存在，则输出存在；
否则，则跳转到步骤(5)；
(5)判断调用装箱算法搜索解的结果是否为不存在，且在所述候选路径上调用装箱算法的次数是否小于在所述候选路径上调用装箱算法的次数的上限值；
若调用装箱算法搜索解的结果为不存在，且在所述候选路径上调用装箱算法的次数小于在所述候选路径上调用装箱算法的次数的上限值，则跳转到步骤(6)；
若调用装箱算法搜索解的结果为不存在，且在所述候选路径上调用装箱算法的次数大于或等于在所述候选路径上调用装箱算法的次数的上限值，则输出不存在；
(6)增加在所述候选路径上调用装箱算法的次数，调用装箱算法并将搜索解的结果保存下来，将调用装箱算法的信息记录在hashmap中，对hashmap进行更新，输出搜索解的结果；
其中，调用装箱算法的信息指调用装箱算法搜索到的解的结果以及在所述候选路径上调用装箱算法的次数。
2.根据权利要求1所述的求解三维装箱约束的有限容量路径规划问题的迭代方法，其特征在于，所述有限容量路径规划问题的求解算法和所述装箱算法均采用启发式搜索算法。
3.根据权利要求2所述的求解三维装箱约束的有限容量路径规划问题的迭代方法，其特征在于，所述有限容量路径规划问题的求解算法采用模拟退火或随机邻域搜索算法，所述装箱算法采用邻域搜索算法。
4.根据权利要求1所述的求解三维装箱约束的有限容量路径规划问题的迭代方法，其特征在于，所述步骤(3)中，在所述候选路径上调用装箱算法的次数为1。
5.根据权利要求1所述的求解三维装箱约束的有限容量路径规划问题的迭代方法，其特征在于，所述步骤(5)中，在所述候选路径上调用装箱算法的次数的上限值为n^2，其中n指三维装箱问题中箱子的数量。
6.根据权利要求1所述的求解三维装箱约束的有限容量路径规划问题的迭代方法，其特征在于，所述步骤(6)中，在所述候选路径上调用装箱算法的次数为上次在所述候选路径上调用装箱算法的次数的两倍。
7.根据权利要求1所述的求解三维装箱约束的有限容量路径规划问题的迭代方法，其特征在于，所述步骤(3)中，调用装箱算法搜索解的结果为存在时，则输出存在，调用装箱算法搜索解的结果为不存在时，则输出不存在。
8.根据权利要求1所述的求解三维装箱约束的有限容量路径规划问题的迭代方法，其特征在于，所述步骤(6)中，调用装箱算法搜索解的结果为存在时，则输出存在，调用装箱算法搜索解的结果为不存在时，则输出不存在。
技术总结