计算机科学 ›› 2015, Vol. 42 ›› Issue (4): 221-225.doi: 10.11896/j.issn.1002-137X.2015.04.045

• 人工智能 • 上一篇    下一篇

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

党兰学,侯彦娥,孔云峰   

  1. 河南大学计算机与信息工程学院 开封475004,河南大学计算机与信息工程学院 开封475004;河南大学环境与规划学院 开封 475004,河南大学环境与规划学院 开封 475004
  • 出版日期:2018-11-14 发布日期:2018-11-14
  • 基金资助:
    本文受国家自然科学基金资助

Spatiotemporal Neighborhood Search for Solving Mixed-load School Bus Routing Problem

DANG Lan-xue, HOU Yan-e and KONG Yun-feng   

  • Online:2018-11-14 Published:2018-11-14

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

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

Abstract: Neighborhood search is one of the key issues in the algorithm design for solving mixed-load school bus routing problem (SBRP).For saving the execution time of neighborhood search,this paper introduced the concepts of spatiotemporal distance and spatiotemporal connectivity index to reduce the size of searching space.The spatiotemporal distance between stop nodes was defined as the weighted sum of normalized spatial distance and temporal distance.Moreover,the spatiotemporal connectivity index,a number indicating the feasible connectivity between two SBRP nodes,is determined according to spatiotemporal distance and constraints such as school bus capacity,school time window and maxi-mum riding time.The spatiotemporal connectivity indexes are sorted in a descending order for each node,and the neighborhood lists for all nodes are prepared for neighborhood search operators.In the following step of node moves,the neighborhood node with higher index value will be examined preferentially.Thus the effective node will be accepted as earlier as possible,and the size of neighborhood lists can be reduced substantially.The test of a set of large-scale mixed-load SBRP instances shows that the spatiotemporal neighborhood search is capable of reducing the neighborhood search space and saving the solution time dramatically.

Key words: School bus routing problem,Mixed-load,Neighborhood search,Spatiotemporal distance,Spatiotemporal connectivity index

[1] Newton R M,Thomas W H.Design of school bus routes bycomputer[J].Socio-Economic Planning Sciences,1969,3(1):75-85
[2] Bodin L D,Berman L.Routing and scheduling of school buses by computer[J].Transportation Science,1979,3(2):113-129
[3] Park J,Kim B-I.The school bus routing problem:A review[J].European Journal of Operational Research,2010,2(2):311-319
[4] Bodin L D,Golden B,Assad A,et al.Routing and scheduling of vehicles and crews:the state of the art[J].Computers and Opera-tions Research,1983,0(2):63-211
[5] Braca J,Bramel J,Posner B,et al.A computerized approach to the New York City school bus routing problem[J].IIE Transactions,1997,9(8):693-702
[6] Vidal d S L,Siqueira P H.Heuristic Methods Applied to the Optimization School Bus Transportation Routes-A Real Case[C]∥ IEA/AIE 2010,Part II.Berlin:Springer Verlag,2010:247-256
[7] Park J,Tae H,Kim B-I.A post-improvement procedure for the mixed load school bus routing problem[J].European Journal of Operational Research,2012,7(1):204-213
[8] Nanry W,Barnes J.Solving the pickup and delivery problemwith time windows using reactive tabu search[J].Transportation Research Part B,2000,4(2):107-21
[9] 党兰学,王震,刘青松,等.一种求解混载校车路径的启发式算法[J].计算机科学,2013,0(7):248-253
[10] Fang H,Kilani Y,Lee J H M,et al.Reducing search space in local search for constraint satisfaction[C]∥AAAI/IAAI.2002:28-33
[11] Chen S Y,Smith S F.Improving Genetic Algorithms by Search Space Reductions (with Applications to Flow Shop Scheduling)[C]∥GECCO.1999:135-140
[12] 戚铭尧,丁国祥,周游,等.一种基于时空距离的带时间窗车辆路径问题算法[J].交通运输系统工程与信息,2011,1(1):85-89

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!