Combining Benders decomposition and column generation for scheduled service network design problem in rail freight transportation

Abstract

This paper addresses the scheduled service network design problem for rail freight transportation. The proposed model integrates service selection and scheduling, and routing of time-dependent customer shipments based on a connection network representation of the associated operations and decisions along with their relations and time dimensions. Benefiting from the construction method of the connection network, the transfer restrictions of shipments between services can be easily incorporated into our models. We propose two model formulations based on arc variables and path variables respectively. A bespoken solution methodology that combines the Benders decomposition and column generation is proposed to solve the path-based model. Compared with the results of using GUROBI to solve the arc-based model, experimental results show that the proposed approach is effective, yielding high-quality solutions for all test instances, and the acceleration techniques, i.e. trust-region and Pareto-optimal cuts, can significantly improve the convergence efficiency of Benders decomposition.

KEYWORDS:

• Scheduled service network design
• rail freight transportation
• Benders decomposition
• column generation

Acknowledgments

This work was supported by the National Key R&D Program of China under Grant number 2018YFB1201402; the Key issues of China Railway Corporation under Grant number P2019X004; and the National Natural Science Foundation of China under Grant number 62076023, 71901008.

Disclosure statement

No potential conflict of interest was reported by the author(s)

Additional information

Funding

This work was supported by the National Key R&D Program of China under Grant number 2018YFB1201402; the Key issues of China Railway Corporation under Grant number P2019X004; and the National Natural Science Foundation of China under Grant number 62076023, 71901008.