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

• 作者: 唐加福 孔媛 潘震东 董纲
• 来源期刊: 东北大学学报（自然科学版）
• 学科: 经济
• 关键词: 接送服务 车辆调度问题 集划分 满意度 机场
• 年，卷（期）: 2009,（5）
• 所属期刊栏目: 信息与控制
• 页码范围: 625-627,660
• 页数: 4页
• 分类号: F540.4
• 字数: 2816字
• 语种: 中文
• DOI: 10.3321/j.issn:1005-3026.2009.05.005

摘要

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