空箱资源约束调度的列生成算法研究

Column Generation Method for Scheduling Problem with Renewable Resources

研究了可重用空箱资源约束下的入厂物流车辆运输调度问题。首先对该问题进行数学描述,建立混合整数线性规划模型。鉴于问题的NP难解性,研究求解该问题的列生成方法,提出虚工件等技巧,建立适合序列依赖的可重用资源约束调度的列生成主问题模型以及基于检验数求解的子问题模型,并研究求解子问题的动态规划算法。进一步采用分支定界技巧,最终提出适合本问题求解的列生成算法。数值实验表明方法的有效性与高效性。

This paper studied the vehicle transportation scheduling problem with renewable container resources constraints for inbound logistics management. Firstly, a mixed integer linear programming models built for the problem. Since the problem is NP hard, column generation method is proposed to solve the problem. During the process, concepts of virtual parts are introduced. Set partitioning model is set up for the master problem and the model for the sub problem is built based on test number solving. Moreover, we propose to use dynamic method to solve the sub problem and study Branch and Bound technique. Finally, we propose the whole column generation method that suit for solving this problem and verify the effectiveness of proposed algorithm by the numerical experiments.