基于集划分求解接送旅客到机场问题的启发式算法

来源期刊：东北大学学报(自然科学版)2009年第5期

论文作者：孔媛 唐加福 潘震东 董纲

文章页码：625 - 1287

关键词：接送服务;车辆调度问题;集划分;满意度;机场;

摘    要：考虑旅客对抵达机场的时间要求严格和绕行给旅客带来的不便,将满意度量化为一段旅客到达机场的时间,建立在一定的满意度下运行时间和绕行时间的权和最小的单目标数学模型.根据问题和模型的特点,设计了一种基于Set-Partition的启发式算法.该算法首先枚举出有效车次集,然后开发启发式算法PNAC（per-node average-cost）,从有效的车次集中选择一组路段访问全部旅客,并结合后优化过程,制定高满意度的调度计划.最后通过仿真实验,验证了算法和模型的有效性.