计算机科学
計算機科學
계산궤과학
COMPUTER SCIENCE
2015年
4期
221-225
,共5页
校车路径问题%混载%邻域搜索%时空距离%时空相关度
校車路徑問題%混載%鄰域搜索%時空距離%時空相關度
교차로경문제%혼재%린역수색%시공거리%시공상관도
School bus routing problem%Mixed-load%Neighborhood search%Spatiotemporal distance%Spatiotemporal connectivity index
为节约混载校车路径问题求解过程中邻域解搜索的时间,引入时空距离和时空相关度概念,将邻域搜索空间限定在合理的范围内.该算法首先计算站点间的时空距离,再附加上简单约束的预判断,从而得到时空相关度矩阵.然后对于任意学生乘车站点,将其他可能与之直接相连的站点按照时空相关度排序,形成一个邻接列表.在邻域搜索过程中,通过限定邻接列表长度,仅尝试最终接受概率较大的一部分移动操作,以此缩小邻域搜索空间,从而提高算法效率.在国际标准案例上的测试结果表明,基于时空相关度的搜索策略能在基本不降低求解质量的情况下,平均节省50％以上的求解时间.
為節約混載校車路徑問題求解過程中鄰域解搜索的時間,引入時空距離和時空相關度概唸,將鄰域搜索空間限定在閤理的範圍內.該算法首先計算站點間的時空距離,再附加上簡單約束的預判斷,從而得到時空相關度矩陣.然後對于任意學生乘車站點,將其他可能與之直接相連的站點按照時空相關度排序,形成一箇鄰接列錶.在鄰域搜索過程中,通過限定鄰接列錶長度,僅嘗試最終接受概率較大的一部分移動操作,以此縮小鄰域搜索空間,從而提高算法效率.在國際標準案例上的測試結果錶明,基于時空相關度的搜索策略能在基本不降低求解質量的情況下,平均節省50％以上的求解時間.
위절약혼재교차로경문제구해과정중린역해수색적시간,인입시공거리화시공상관도개념,장린역수색공간한정재합리적범위내.해산법수선계산참점간적시공거리,재부가상간단약속적예판단,종이득도시공상관도구진.연후대우임의학생승차참점,장기타가능여지직접상련적참점안조시공상관도배서,형성일개린접렬표.재린역수색과정중,통과한정린접렬표장도,부상시최종접수개솔교대적일부분이동조작,이차축소린역수색공간,종이제고산법효솔.재국제표준안례상적측시결과표명,기우시공상관도적수색책략능재기본불강저구해질량적정황하,평균절성50％이상적구해시간.
