交通运输系统工程与信息
交通運輸繫統工程與信息
교통운수계통공정여신식
JOURNAL OF COMMUNICATION AND TRANSPORTATION SYSTEMS ENGINEERING AND INFORMATION
2014年
1期
144-149,179
,共7页
系统工程%列生成法%加速策略%乘务调度%问题特征
繫統工程%列生成法%加速策略%乘務調度%問題特徵
계통공정%렬생성법%가속책략%승무조도%문제특정
systems engineering%column generation%accelerating strategies%crew scheduling%problem-specific knowledge
列生成法是求解乘务调度问题的有效数学规划方法,但传统列生成法存在收敛速度慢的缺点.基于乘务问题特点,提出三种加速列生成求解的策略:在列生成迭代过程中,每隔一定周期移除受限主问题的部分“差”变量,以减小问题规模;提出基于乘务问题特征的强标号消除准则和基于该准则的二阶段子问题求解法以加速子问题求解;利用分支树求解整数解时,提出一个能充分利用已有解信息的班次池策略,以减小整数解求解时间.利用实际公共交通中的10组案例对所提加速策略进行测试.实验结果表明,这些加速策略能够有效加速列生成的求解,适用于求解大规模的乘务调度问题.
列生成法是求解乘務調度問題的有效數學規劃方法,但傳統列生成法存在收斂速度慢的缺點.基于乘務問題特點,提齣三種加速列生成求解的策略:在列生成迭代過程中,每隔一定週期移除受限主問題的部分“差”變量,以減小問題規模;提齣基于乘務問題特徵的彊標號消除準則和基于該準則的二階段子問題求解法以加速子問題求解;利用分支樹求解整數解時,提齣一箇能充分利用已有解信息的班次池策略,以減小整數解求解時間.利用實際公共交通中的10組案例對所提加速策略進行測試.實驗結果錶明,這些加速策略能夠有效加速列生成的求解,適用于求解大規模的乘務調度問題.
렬생성법시구해승무조도문제적유효수학규화방법,단전통렬생성법존재수렴속도만적결점.기우승무문제특점,제출삼충가속렬생성구해적책략:재렬생성질대과정중,매격일정주기이제수한주문제적부분“차”변량,이감소문제규모;제출기우승무문제특정적강표호소제준칙화기우해준칙적이계단자문제구해법이가속자문제구해;이용분지수구해정수해시,제출일개능충분이용이유해신식적반차지책략,이감소정수해구해시간.이용실제공공교통중적10조안례대소제가속책략진행측시.실험결과표명,저사가속책략능구유효가속렬생성적구해,괄용우구해대규모적승무조도문제.
