时空相关的混载校车路径问题邻域搜索

摘要：

为节约混载校车路径问题求解过程中邻域解搜索的时间,引入时空距离和时空相关度概念,将邻域搜索空间限定在合理的范围内.该算法首先计算站点间的时空距离,再附加上简单约束的预判断,从而得到时空相关度矩阵.然后对于任意学生乘车站点,将其他可能与之直接相连的站点按照时空相关度排序,形成一个邻接列表.在邻域搜索过程中,通过限定邻接列表长度,仅尝试最终接受概率较大的一部分移动操作,以此缩小邻域搜索空间,从而提高算法效率.在国际标准案例上的测试结果表明,基于时空相关度的搜索策略能在基本不降低求解质量的情况下,平均节省50％以上的求解时间.

关键词：校车路径问题、混载、邻域搜索、时空距离、时空相关度

所属期刊栏目：42

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家自然科学基金资助项目41401461;河南省教育厅科学技术研究重点项目13A520050

在线出版日期：2015-05-18（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：221-225