摘要
对一个区域内多所学校进行校车路径规划时,允许校车混载不同学校的学生能显著地减少校车数量,从而降低运营成本。已有学者针对允许混载的校车路径问题(SBRP)提出了启发式算法,但这些算法对邻域解的搜索不够全面,在缩减路径方面仍有较大的提升空间。提出了一种以记录更新法(record-to-record travel,RRT)为基础的启发式算法。该算法从初始解出发,利用求解有时间窗装卸问题(PDPTW)时使用的算子搜索邻域解,逐步优化校车路径数目。与现有算法相比,该算法扩展了求解混载SBRP的启发策略,能够在全局范围内对校车路径进行优化,从而获得所需校车较少的路径规划方案。实验结果验证了该算法的有效性。
Mixed load school bus routing problem （SBRP） for multiple schools in a city or county, which allows students from different schools to get on same bus at the same time,aims to reduce the number of school buses needed and total operational costs. Several algorithms for solving mixed load SBRP have been developed since 1990s. However, due to the complexity of mixed load SBRP, the neighborhood solutions are not fully explored in these approaches. This paper proposed a new heuristic method for mixed load SBRP using a record-to-record travel （RRT） algorithm and neighborhood operators of pickup and delivery （PDPTW） to minimize the number of required buses. Test results show the effectiveness of this algorithm. Compared with the existing SBRP solutions, this algorithm expands the neighbor- hood search strategy, and is capable of finding better solutions using fewer buses.
出处
《计算机科学》
CSCD
北大核心
2013年第7期248-253,共6页
Computer Science
基金
国家自然科学基金项目(41201402)
省部共建河南大学科研基金项目(SBGJ090605)资助
关键词
校车路径问题
混载
有时间窗装卸问题
记录更新法
School bus routing problem （SBRP）, Mixed load, Pickup and delivery with time window （PDPTW）, Record-to-record travel （RRT）
