摘要
目前对于拼出租车调度问题的研究多集中于静态的或者“一个起点到多个终点”和“多个起点到一个终点”的动态拼车。针对“多个起点到多个终点”的动态拼出租车问题,首先对拼车和任务调度两个问题进行了分析比较,建立了拼车问题的任务调度模型;然后给出了计算拼车任务完成时间的算法;最后根据任务完成时间计算任务的sufferage值,并基于任务调度中的sufferage算法的原理,给出了一种动态拼出租车调度算法。实验结果表明,提出的动态拼出租车调度算法可以有效提高整个拼车系统的成功率,缩短乘客的平均拼车完成时间。
The study of taxipooling problem is mainly focus on static case or the dynamic case of "one origin to many destinations" and " many origins to one destination". For the case of "many origins to many destinations", this paper first analyzed and compared taxipooling problem and task scheduling problem, and established the schedule model for taxipooling problem. Then, an algorithm to calculate the completion time of taxipool was presented. Finally, the sufferage value of taxipool was calculated by the completion time, and a dynamic taxipooling scheduling algorithm was proposed based on the principle of suffrage algorithm in task scheduling. The experimental results showed that the proposed algorithm can improve the success rate of taxipooling and reduce the average completion time as well.
作者
冯田
FENG Tian (Key Laboratory of Embedded System and Service Computing of Ministry of Education, Tongji University, Shanghai 201804, China)
出处
《电脑知识与技术》
2011年第10期7019-7023,共5页
Computer Knowledge and Technology