Column Generation Accelerated Algorithm and Optimisation for a High-Speed Railway Train Timetabling Problem
With the rapid development of high-speed railway (HSR) systems, the increasing demand for passenger traffic has put forward higher requirements for HSR train timetabling problems (HSRTTPs). This paper establishes two mathematical optimisation models with different optimisation objectives for an HSRT...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2019-08-01
|
| Series: | Symmetry |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2073-8994/11/8/983 |
| _version_ | 1811187163420688384 |
|---|---|
| author | Jin Wang Leishan Zhou Yixiang Yue |
| author_facet | Jin Wang Leishan Zhou Yixiang Yue |
| author_sort | Jin Wang |
| collection | DOAJ |
| description | With the rapid development of high-speed railway (HSR) systems, the increasing demand for passenger traffic has put forward higher requirements for HSR train timetabling problems (HSRTTPs). This paper establishes two mathematical optimisation models with different optimisation objectives for an HSRTTP and solves these models through a column generation-based algorithm. However, the column generation-based algorithm has the disadvantage of a slow convergence rate, thus we put forward corresponding acceleration strategies for five stages of the algorithm: preprocessing, restricted master problem, pricing problem, branch-and-bound and postprocessing from a symmetry point between the computation efficiency and the accuracy. The effectiveness of the acceleration strategies was validated by a case study of the Beijing−Shanghai HSR. The results show that the proposed optimal acceleration strategies can increase the computation efficiency of the algorithm by 11.8× on average while ensuring the accuracy. |
| first_indexed | 2024-04-11T13:57:35Z |
| format | Article |
| id | doaj.art-ede64c4130d140078a7dbb933ab35643 |
| institution | Directory Open Access Journal |
| issn | 2073-8994 |
| language | English |
| last_indexed | 2024-04-11T13:57:35Z |
| publishDate | 2019-08-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Symmetry |
| spelling | doaj.art-ede64c4130d140078a7dbb933ab356432022-12-22T04:20:12ZengMDPI AGSymmetry2073-89942019-08-0111898310.3390/sym11080983sym11080983Column Generation Accelerated Algorithm and Optimisation for a High-Speed Railway Train Timetabling ProblemJin Wang0Leishan Zhou1Yixiang Yue2School of Traffic and Transportation, Beijing Jiaotong University, Beijing 100044, ChinaSchool of Traffic and Transportation, Beijing Jiaotong University, Beijing 100044, ChinaSchool of Traffic and Transportation, Beijing Jiaotong University, Beijing 100044, ChinaWith the rapid development of high-speed railway (HSR) systems, the increasing demand for passenger traffic has put forward higher requirements for HSR train timetabling problems (HSRTTPs). This paper establishes two mathematical optimisation models with different optimisation objectives for an HSRTTP and solves these models through a column generation-based algorithm. However, the column generation-based algorithm has the disadvantage of a slow convergence rate, thus we put forward corresponding acceleration strategies for five stages of the algorithm: preprocessing, restricted master problem, pricing problem, branch-and-bound and postprocessing from a symmetry point between the computation efficiency and the accuracy. The effectiveness of the acceleration strategies was validated by a case study of the Beijing−Shanghai HSR. The results show that the proposed optimal acceleration strategies can increase the computation efficiency of the algorithm by 11.8× on average while ensuring the accuracy.https://www.mdpi.com/2073-8994/11/8/983high-speed railwaytrain timetablecolumn generationspace-time networkacceleration strategies |
| spellingShingle | Jin Wang Leishan Zhou Yixiang Yue Column Generation Accelerated Algorithm and Optimisation for a High-Speed Railway Train Timetabling Problem Symmetry high-speed railway train timetable column generation space-time network acceleration strategies |
| title | Column Generation Accelerated Algorithm and Optimisation for a High-Speed Railway Train Timetabling Problem |
| title_full | Column Generation Accelerated Algorithm and Optimisation for a High-Speed Railway Train Timetabling Problem |
| title_fullStr | Column Generation Accelerated Algorithm and Optimisation for a High-Speed Railway Train Timetabling Problem |
| title_full_unstemmed | Column Generation Accelerated Algorithm and Optimisation for a High-Speed Railway Train Timetabling Problem |
| title_short | Column Generation Accelerated Algorithm and Optimisation for a High-Speed Railway Train Timetabling Problem |
| title_sort | column generation accelerated algorithm and optimisation for a high speed railway train timetabling problem |
| topic | high-speed railway train timetable column generation space-time network acceleration strategies |
| url | https://www.mdpi.com/2073-8994/11/8/983 |
| work_keys_str_mv | AT jinwang columngenerationacceleratedalgorithmandoptimisationforahighspeedrailwaytraintimetablingproblem AT leishanzhou columngenerationacceleratedalgorithmandoptimisationforahighspeedrailwaytraintimetablingproblem AT yixiangyue columngenerationacceleratedalgorithmandoptimisationforahighspeedrailwaytraintimetablingproblem |