考虑便乘的地铁乘务任务配对的约束优化模型研究

Research on Constraint Optimization Model for Metro Crew Pairing Problem with Passenger Tasks

为了提高地铁正线的运营效率和保障乘务人员的身心健康,针对便乘情况下的地铁乘务任务配对问题,综合考虑了乘务人员总的工作量、乘务人员连续工作量、乘务任务的班次划分、出勤和退勤地点、轮换休息时间和地点、用餐时间和地点、乘务任务完整性、乘务任务的均衡性等因素,以形成的乘务任务数量最少为目标,建立乘务任务配对的约束优化模型。为提高求解效率,使用约束传播算法对变量论域进行动态约减,并设计了约束传播与启发式回溯的混合算法求解模型。实际算例验证表明:约束优化模型符合实际业务需求,提高了乘务排班计划的兑现率;混合搜索算法求解效率较高,提高了计划编制的实时性。

To improve operation efficiency of the metro main line and ensure the physical and mental health of the crew,a constraint optimization model of the metro crew pairing problem with the Caboose Working System was established to minimize the sum of the crew tasks based on Constraint Programming.In the model,the constraints such as the total workload of the crew,the continuous workload of the crew,the shift division of the crew tasks,on or off duty stations,rest time and places,dining time and places,crew mission integrity and crew mission equalization,were taken into comprehensive consideration.To solve the optimal solutions efficiently,the constraint propagation algorithm was designed to reduce the domains of variables dynamically,which was imbedded in backtracking algorithm to solve the model.Finally,the on-site instance show that the constraint optimization model meets the actual business needs and improves the fulfillment rate of crew scheduling plan.The hybrid search algorithm with higher efficiency improves the real-time performance of scheduling.