Computer Science ›› 2018, Vol. 45 ›› Issue (4): 240-246.doi: 10.11896/j.issn.1002-137X.2018.04.040

Previous Articles     Next Articles

Greedy Randomized Adaptive Search Procedure Algorithm Combining Set Partitioning for Heterogeneous School Bus Routing Problems

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

  • Online:2018-04-15 Published:2018-05-11

Abstract: In practice of school bus route planning,there are a variety of planning applications with different optimization objectives under the types of school buses constraints.This paper dealt with a class of heterogeneous school bus routing problem(HSBRP) with different objectives.A greedy randomized adaptive search procedure(GRASP) algorithm combining set partition(SP) procedure was proposed in this paper.First,the routes generated in the execution of GRASP are used to build the set partition model,and then the model is solved by the CPLEX optimization software.To keep the algorithm suitable for different HSBRP problems,the initialization solution generation procedure of GRASP is adapted for these problems to obtain a valid solution,and the routes of this initialization solution are put into the route pool.In the local search phase,the many neighborhood operators and variable neighborhood descent procedure are executed for improving the solution.At the same time,the routes of the solution that is improved and the best local optimization in every iteration are both put into the route pool.The test results on the benchmark datasets show that the SP procedure of the proposed algorithm can improve the quality and stability of the algorithm.The proposed algorithm can effectively solve two types of HSBRP with different objectives,and it is effective when compared with the existing HSBRP algorithms.

Key words: Heterogeneous school bus routing problem,Set partitioning,Greedy randomized adaptive search procedure,Hybrid meta-heuristic

[1] NEWTON R M,THOMAS W H.Design of school bus routes by computer[J].Socio-Economic Planning Sciences,1969,3(1):75-85.
[2] PARK J,KIM B I.The school bus routing problem:A review [J].European Journal of Operational Research,2010,202(2):311-319.
[3] DANG L X,CHEN X P,KONG Y F.Review of School BusRouting Problem:Concept,Model and Optimization Algorithms [J].Journal of Henan University(Natural Science),2013,43(6):682-691.(in Chinese) 党兰学,陈小潘,孔云峰.校车路径问题模型及算法研究进展[J].河南大学学报(自然科学版),2013,3(6):682-691.
[4] KE X.School bus selection,routing and Scheduling [D].Canada,Windsor:University of Windsor,2005.
[5] RIPPLINGER D.Rural school vehicle routing problem [J].Transportation Research Record:Journal of the Transportation Research Board,2005,1992(1):105-110.
[6] DE SOUZA L,SIQUEIRA P H.Heuristic Methods Applied to the Optimization School Bus Transportation Routes-A Real Case[C]∥23rd International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems.2010:247-256.
[7] THANGIAH S R,FERGANY A,WILSON B,et al.School Bus Routing in Rural School Districts[C]∥Proceedings of the 9th International Conference on Computer-Aided Scheduling of Public Transport.Spring,2008:209-232.
[8] 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,217(1):204-213.
[9] HOU Y E,DANG L X,KONG Y F,et al.GRASP Algorithmwith Parameter Selection Mechanism for Heterogeneous Fleet School Bus Routing Problem [J].Computer Science,2016,43(8):233-239.(in Chinese) 侯彦娥,党兰学,孔云峰,等.求解多车型校车路径问题的带参数选择机制的GRASP算法[J].计算机科学,2016,3(8):233-239.
[10] HOU Y E,KONG Y F,DANG L X,et al.Model and Algorithm for Heterogeneous Fixed Fleet School Bus Routing Problem [J].Computer Science,2016,43(12):234-240.(in Chinese) 侯彦娥,孔云峰,党兰学,等.车辆数限制的多车型校车路径问题模型及算法研究[J].计算机科学,2016,3(12):234-240.
[11] PISINGER D,ROPKE S.A general heuristic for vehicle routing problems[J].Computer & Operations Research,2007,34(8):2403-2435.
[12] SUBRAMANIAN A,PENNA P H V,UCHOA E,et al.A hybrid algorithm for the Heterogeneous Fleet Vehicle Routing Problem [J].European Journal of Operational Research,2012,221:285-295.
[13] SUBRAMANIAN A,UCHOA E,OCHI L.A hybrid algorithm for a class of vehicle routing problems [J].European Journal of Operational Research,2013,40:2519-2531.
[14] VIDAL T,CRAINIC T,GENDREAU M,et al.A unified solution framework for multi-attribute vehicle routing problems [J].European Journal of Operational Research,2014,234:658-673.
[15] ROCHAT Y,TAILLARD E D.Probabilistic diversification and intensification in local search for vehicle routing [J].Journal of Heuristics,1995,1:147-167.
[16] ALVARENGA G,MATEUS G,DE TOMI G.A genetic and set partitioning two-phase approach for the vehicle routing problem with time windows [J].Computers and Operations Research,2007,34(6):1561-1584.
[17] HANSEN P,MLADENOVIC N.Variable Neighborhood Search:Principles and Applications [J].European Journal of Operations Research,2001,130(3):449-467.

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!