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

详细信息    查看全文 | 推荐本文 |

英文篇名：Column Generation Method for Scheduling Problem with Renewable Resources 作者：陈峰 英文作者：CHEN Feng;Department of Industrial Engineering and Management,Shanghai Jiao Tong University; 关键词：资源约束 ; 可重用资源 ; 列生成 ; 汽车物流 英文关键词：resource constrained;;renewable resource;;column generation;;automotive logistics 中文刊名：GYGC 英文刊名：Industrial Engineering and Management 机构：上海交通大学工业工程与管理系; 出版日期：2015-08-10 出版单位：工业工程与管理 年：2015 期：v.20;No.113 基金：国家自然科学基金资助项目(71272115,70972070) 语种：中文; 页：GYGC201504001 页数：8 CN：04 ISSN：31-1738/T 分类号：5-12

摘要

研究了可重用空箱资源约束下的入厂物流车辆运输调度问题。首先对该问题进行数学描述,建立混合整数线性规划模型。鉴于问题的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.

引文

[1]Francesco M D,Lai M,et al.Maritime repositioning of empty containers under uncertain port disruptions[J].Computers&Industrial Engineering,2013,64(3):827-837.
    [2]Lam S-W,Lee L-H,et al.An approximate dynamic programming approach for the empty container allocation problem[J].Transportation Research Part C:Emerging Technologies,2007,15:265-277.
    [3]李长宏,付壮,秦建法.铁路特种箱空箱调度模型及求解算法[J].铁道货运,2011,3:35-38.
    [4]Ruiz-Torres A J,Centeno G.Scheduling with flexible resources in parallel workcenters to minimize maximum completion time[J].Computers&operations research,2007,34(1):48-69.
    [5]Figielska E.Heuristic algorithms for preemptive scheduling in a two-stage hybrid flowshop with additional renewable resources at each stage[J].Computers&Industrial Engineering,2010,59(4):509-519.
    [6]王旭,陈峰.空箱资源约束下的运输调度模型及算法[D].上海,上海交通大学,2012.
    [7]van den Akker M,Hoogeveen H,et al.Applying column generation to machine scheduling[M]∥Desaulniers G.Desrosiers J.Column generation.Berlin:Springer,2005:303-330.
    [8]Huisman D,Jans R,Peeters M.et al.Combining column generation and Lagrangian relaxation[M]∥Desaulniers G.Desrosiers J.Column generation.Berlin:Springer,2005:247-270.
    [9]Chen Z-L,Xu H.Dynamic column generation for dynamic vehicle routing with time windows[J].Transportation Science,2006,40(1):74-88.
    [10]Pinedo M.Scheduling:theory,algorithms,and systems[M].4th ed.Berlin:Springer,2014.