2019/09/25 by Chongshuang Chen, Jun Zhao, Chen, Chongshuang +1
Business, Management and Accounting · Engineering · #FOS: Computer and information sciences #FOS: Mathematics #Maritime Ports and Logistics #Networking and Internet Architecture (cs.NI) #Optimization and Control (math.OC) #Railway Systems and Energy Efficiency #Transport and Economic Policies
paper · pdf · doi:10.48550/arxiv.1909.11310
openalex publication_date 2019/09/25 · openalex created_date 2019/10/03 · openalex updated_date 2026/07/28
The INFORMS RAS 2019 Problem Solving Competition is focused on the integrated train blocking and shipment path (TBSP) optimization for tonnage-based operating railways. In nature, the TBSP problem could be viewed as a multi-commodity network design problem with a double-layer network structure. By introducing a directed physical railway network and a directed train services (blocks) network, we formulate completely the TBSP problem as a mixed integer linear programming (MILP) model that incorporates all decisions, objectives and constraints especially the merge flow (called intree rule here) in an integrated manner. The scale of the MILP model can be reduced efficiently if we only enumerate the arc selection and block sequence variables for each shipment on the legal paths from its origin to its destination satisfying the given detour ratio. We further develop a sequential algorithm that decomposes the TBSP problem into the shipment path subproblem and train blocking subproblem which are solved sequentially. Computational tests on the three given data sets show that the reduced MILP model can solve DataSet_1 to optimality in 8.48 seconds and DataSet_2 with a gap of 0.16% in 6 hours on a GPU workstation. The reduced model also can provide strong lower bounds for DataSet_2 and DataSet_3. The sequential algorithm can find a high quality solution with 0.04% gap within 0.26 seconds for DataSet_1, 0.42% gap within 4.53 seconds for DataSet_2 and 1.54% gap within 0.58 hours for DataSet_3 respectively on a Thinkpad laptop.