In this paper we study a kind of transshipment problem, in which the flows through the crossdock arc constrained by fixed transportation schedules with single release and single delivery, cargos can be delayed in crossdocks but any delay at the last time point of time horizon will incur inventory penalty cost, and the objective is to find a transshipment scheme with minimum cost. The problem is proved to be NP-hard in the strong sense in this paper. We therefore focus on developing efficient heuristics. Based on the problem structure, we propose a self-adaptive genetic algorithm with neighborhood search (AGA with NS) to solve the problem efficiently. Computational experiments under different scenarios show that AGA with NS outperforms CPLEX solver, meanwhile, in order to further test the effectiveness of the adaptive scheme and neighborhood search, we also conduct computational experiments by different algorithms such as AGA without NS, GA with NS and PACO, and GA with NS and PUCO. Finally the results show that AGA with NS is the best one among these algorithms for this problem.%探讨一种固定运输模式下的越库转运问题--采用运输量不可拆分的单次运送方式以最小费用通过选择固定的运输路径将货物经过越库转运到目的地,其货物将可能在越库中停留甚至无法运到目的地,这将会导致库存成本和惩罚成本.文中证明了此类越库转运问题是强NP难题,因此本文针对该问题的特殊结构,提出一种采用了邻域搜索技术的自适应遗传算法(AGA with NS)来有效的解决该类问题,数值试验结果表明该算法比CPLEX求解更加高效.此外文中还分别比较了在不采用邻域搜索或者自适应策略的情况下的三种遗传算法,其数值实验结果表明邻域搜索策略以及自适应策略对提高算法的效率有显著的影响.
展开▼
