基于拉格朗日松弛的铁路行包运输方案编制方法研究  

Method of Development of Railway Package Transportation Scheme Based on Lagrangian Relaxation

作　　者：王泽 谭宇燕[1] 魏玉光[1] WANG Ze;TAN Yuyan;WEI Yuguang(School of Traffic and Transportation,Beijing Jiaotong University,Beijing 100044,China)

机构地区：[1]北京交通大学交通运输学院,北京100044

出　　处：《铁道学报》2021年第11期8-17,共10页Journal of the China Railway Society

基　　金：中国铁路总公司科技研究开发计划(P2018X011)。

摘　　要：编制行包运输方案是铁路行包运输组织的关键环节,在旅客列车挂运行李车的方式下,仍然依靠人工经验编制,存在运输能力与行包流在时空上不完全匹配的问题。根据其性质和特点,采用时空网络建模方法,将其转化为多商品流问题。为保证时效性,以行包运输时间最短为目标,考虑行李车载运能力、行包中转次数以及各项时间约束,建立二元整数规划模型。针对模型规模庞大、精确求解困难的特点,提出基于拉格朗日松弛的求解算法,将原问题分解为一系列最小费用路径子问题;设计上界启发式算法,弥补拉格朗日下界解不可行的不足。经算例验证,模型与算法具有良好的优化效率与实用性。As a vital role of the railway package transport organization,in the case of a passenger train coupled with baggage car,the development of package scheme still relies on manual experience.In this case,the transport capacity and the package flows are not exactly matched in time and space.According to the nature and characteristics of the problem,this paper introduced the space-time network modeling method to transform the problem into the multi-commodity flow formulation.In order to ensure the timeliness,this study took the transport time minimization as the objective,and took into account the carrying capacity of the baggage car,the number of transship times of packages and various time constraints to establish a binary integer programming model.In view of the large scale of the model and the difficulty of accurate solution,an algorithm based on Lagrangian relaxation was proposed to decompose the original problem into a series of minimal cost path subproblems.An upper bound heuristic algorithm was also designed to make up for the insufficiency of the infeasibility of Lagrangian lower bound solution.The numerical experiments show that the model and algorithms are efficient and practicable.

关 键 词：铁路行包运输 时空网络 二元整数规划 拉格朗日松弛 

分 类 号：U294[交通运输工程—交通运输规划与管理]