基于改进遗传算法的旅客列车席位分配组合优化

Combination Optimization for Seat Allocation of Railway Passenger Car Based on Improved Genetic Algorithm

为了合理分配各车站的车票票额、提高铁路客运收入,根据旅客列车停靠多站的实际情况,建立列车席位与车票关系数学模型;根据数学模型和铁路客流的特点对遗传算法进行改进,定义与席位状态相对应的车票编码方法,通过在车票编码中增加判别符号,以区分乘车区间车票需求的组合情况;由于列车席位分配具有多背包问题的特点,其本质是列车席位组合优化问题,因此,通过定义乘车区间车票需求的组合交叉规则和在优化运算过程中始终保持原始乘车区间车票需求不变的前提下,以车票收入和列车客座利用率最大为优化目标,采用改进的遗传算法选择优秀的子代进行迭代,逆向求解各车站的票额分配数额,并同时完成旅客列车席位的分配与组合优化。通过算例验证了模型和算法的有效性。

In order to allocate train tickets for each station properly and raise the income of railway passenger transport,a mathematical model about the relations between train seats and tickets was established based on the actual situation of passenger train stopping at multiple stations.The genetic algorithm was improved in line with mathematical model and the characteristics of railway passenger flow,and ticket encoding methods corresponding to seat states were defined.Distinguished symbols were added into ticket codes to differentiate the combined conditions of ticket demand for riding interval.Since train seat allocation had the features of multiple-knapsack problem and its essence was the combinatorial optimization problem of train seat allocation,accordingly,combinatorial cross rules for ticket demand of riding interval were defined.Under the premise that the ticket demand of original riding interval always remained unchanged in the process of optimization operation,with the maximum passenger seat utilization rate and ticket revenue as the optimization objectives,the best offspring was chosen by improved genetic algorithm to iterate and conversely solve the seat allotment amount for each station.Meanwhile,the seat allocation and ticket combination optimization for passenger car were completed.The effectiveness of the proposed model and algorithm was verified by examples.