中国铁道科学
中國鐵道科學
중국철도과학
CHINA RAILWAY SCIENCE
2014年
1期
122-129
,共8页
何必胜%宋瑞%何世伟%李晋
何必勝%宋瑞%何世偉%李晉
하필성%송서%하세위%리진
城市轨道交通%列生成算法%大规模邻域搜索算法%车底运用计划
城市軌道交通%列生成算法%大規模鄰域搜索算法%車底運用計劃
성시궤도교통%렬생성산법%대규모린역수색산법%차저운용계화
Urban rail transit%Column generation algorithm%Large-scale neighborhood search algorithm%Rolling stock assignment
以车底需要担当的运输任务和虚拟车场为节点,以2个运输任务间的衔接以及运输任务与虚拟车场间的衔接关系为弧,构建不固定区段运营的城市轨道交通车底运用网络图.在满足相关约束条件下,以车底总运营费用最低为目标,建立城市轨道交通车底运用计划编制优化模型,并设计模型求解的混合列生成算法.该算法的原理是:在分支定价算法的基础上,再采用大规模邻域搜索算法,以当前最优整数解为初始解进行邻域搜索得到新的解,将此新解作为新增列加入到列生成算法中,避免出现退化问题;同时,根据此新解对搜索树上界进行更新,运用更有效的上界进行减枝,从而提升模型求解的效率.应用实例证明,提出的混合列生成算法在求解大规模的车底运用计划编制问题时,可以获得较高质量的求解结果.
以車底需要擔噹的運輸任務和虛擬車場為節點,以2箇運輸任務間的銜接以及運輸任務與虛擬車場間的銜接關繫為弧,構建不固定區段運營的城市軌道交通車底運用網絡圖.在滿足相關約束條件下,以車底總運營費用最低為目標,建立城市軌道交通車底運用計劃編製優化模型,併設計模型求解的混閤列生成算法.該算法的原理是:在分支定價算法的基礎上,再採用大規模鄰域搜索算法,以噹前最優整數解為初始解進行鄰域搜索得到新的解,將此新解作為新增列加入到列生成算法中,避免齣現退化問題;同時,根據此新解對搜索樹上界進行更新,運用更有效的上界進行減枝,從而提升模型求解的效率.應用實例證明,提齣的混閤列生成算法在求解大規模的車底運用計劃編製問題時,可以穫得較高質量的求解結果.
이차저수요담당적운수임무화허의차장위절점,이2개운수임무간적함접이급운수임무여허의차장간적함접관계위호,구건불고정구단운영적성시궤도교통차저운용망락도.재만족상관약속조건하,이차저총운영비용최저위목표,건립성시궤도교통차저운용계화편제우화모형,병설계모형구해적혼합렬생성산법.해산법적원리시:재분지정개산법적기출상,재채용대규모린역수색산법,이당전최우정수해위초시해진행린역수색득도신적해,장차신해작위신증렬가입도렬생성산법중,피면출현퇴화문제;동시,근거차신해대수색수상계진행경신,운용경유효적상계진행감지,종이제승모형구해적효솔.응용실예증명,제출적혼합렬생성산법재구해대규모적차저운용계화편제문제시,가이획득교고질량적구해결과.
