期刊文献+

一种求解大规模校车调度问题的元启发式算法 被引量:6

A Meta-heuristic Algorithm to Solve the Large-Scale School Bus Scheduling Problem
原文传递
导出
摘要 校车调度问题(SBSP)是通过调度使一辆校车服务完一个学校后继续服务其他学校,以减少一个地区所需的校车总数,进而降低校车采购成本和运营成本。目前的SBSP求解方法是将其转化为指派问题或运输问题,使用混合整型规划算法或者简单启发式算法进行求解,但求解性能有局限。本文在单校校车路径规划的基础上,将单校路径抽象为虚拟站点,进而将SBSP转换为带有时间窗的车辆路径问题(VRPTW),设计元启发算法进行求解。使用构造启发式算法获得初始解后,在模拟退火算法框架中通过典型的局部搜索算子搜索邻域解,逐步改善求解质量。搜索算子包括单点移动、两点交换、2-OPT和Cross-Exchange。迭代优化过程中以校车路径数为主要目标,路径长度为次要目标。为避免邻域搜索陷入局部最优,算法以一定的概率接受部分使路径长度增加的解。15个案例实验验证了本算法的有效性,与现有算法相比,能够获得更好的优化目标,适用于大规模的校车调度。 Given school bus trips for each school in a school district, if a school bus can serve multiple trips, the efficiency of school bus service can be improved in terms of the number of buses needed and the total travelcost. The school bus scheduling problem (SBSP), a class of school bus routing problem (SBRP), is concerned with assigning a fleet of buses to serve all the given trips and aims to get optimal bus schedules. Each school has its xed time window within which school bus must arrive at the destination school of the trip. In existing litera- tures, SBSP is usually formulated as a transportation problem (TP) or an assignment problem (AP). However, many existing algorithms for vehicle routing problem (VRP) have not been fully utilized to solve the problem ef- fectively. This paper proposes a meta-heuristic algorithm for large-scale SBSP. Treating a trip as a virtual stop with time window, the problem can be converted to a vehicle routing problem with time windows (VRPTW). Therefore, the SBSP can be solved in a VRP algorithm framework. After a set of feasible solutions are generated using construction heuristic algorithm, a simulated annealing (SA) algorithm is designed to improve the initial so- lutions iteratively. Four general operators for VRP, one-point move, two point move, two-opt move and cross-ex- change move, are used in the neighborhood search. In addition to the SBSP objectives of minimizing the number of the routes and the total travel distance, the sum of squared number of route stops is added as a new objective. This will guide the neighborhood search toward the situation that deleting some routes more easily. For avoiding local optimum, some worsening neighborhood solutions can be accepted with a certain probability. Computation- al tests on 15 instances with a homogeneous fleet show the effectiveness of the proposed approaches. Compared with the existing SBSP solutions, the proposed algorithm can solve large-scale SBSP in a reasonable time and find better solutions using fewer buses. In addition, the algorithm can be easily integrated with GIS for solving real world school bus scheduling.
出处 《地球信息科学学报》 CSCD 北大核心 2013年第6期879-886,共8页 Journal of Geo-information Science
基金 国家自然科学基金项目(41201402) 省部共建河南大学科研基金项目(SBGJ090605) 河南省教育厅科学技术研究重点项目(13A520050)
关键词 校车调度问题 校车路径问题 带时间窗的车辆路径问题 模拟退火算法 school bus scheduling problem school bus routing problem vehicle routing problem with time win-dows (VRPTW) simulated annealing
  • 相关文献

参考文献21

  • 1Newton R M, Thomas W H. Design of school bus routes by computer[J]. Socio-Economic Planning Sciences, 1969,3(1):75-85.
  • 2Park J, Kim B I. The school bus routing problem: A review [J]. European Journal of Operational Research, 2010,202 (2):311-319.
  • 3Swersey A J, Ballard W. Scheduling school buses[J]. Man- agement Science, 1984,30(7):844-853.
  • 4Desrosiers J, Ferland J A, Rousseau J M, et al. An over- view of a school busing system[M].//Jaiswal N K (Ed.). Scientific Management of Transport Systems, Amster- dam: North-Holland, 1981:235-243.
  • 5Desrosiers J, Ferland J A, Rousseau, et al. A multi-period school bus routing and scheduling system[M].// TIMS Studies in the Management Sciences, Amsterdam: Elsevi- er Science Publishers, 1986,22:47-71.
  • 6Fiigenschuh A. Solving a school bus scheduling problem with integer programming[J]. European Journal of Opera- tional Research, 2009,193(3):867-884.
  • 7Kim B I, Kim S, Park J. A school bus scheduling problem [J]. European Journal of Operational Research, 2012,218 (2):577-585.
  • 8Spada M, Bierlaire M, Liebling T M. Decision-aiding methodology for the school bus routing and scheduling problem[J]. Transportation Science, 2005,39(4):477-490.
  • 9Swersey A J, Ballard W. Scheduling school buses[J]. Management Science, 1984,30(7):844-853.
  • 10Swersey A J, Ballard W. Scheduling school buses[J]. Management Science, 1984,30(7):844-853.

二级参考文献30

  • 1郭强,李育安,郭耀煌.社区儿童接送服务车辆的线路优化[J].西南交通大学学报,2006,41(4):486-490. 被引量:8
  • 2Newton R M, Thomas W H. Design of school bus routes by computer[J]. Socio-Economic Planning Sciences, 1969,3(1) : 75- 85.
  • 3Braca J, Bramel J, Posner B, et al. A computerized approach to the New York City school bus routing problem[J]. IIE Transac- tions, 1997,29 : 693-702.
  • 4de Souza L V, Siqueira P H. Heuristic Methods Applied to the Optimization School Bus Transportation Routes-A Real Case[C]// IEA/AIE 2010, Part n. Berlin: Springer Verlag, 2010 : 247-256.
  • 5Park J, Tae H, Kim B-I. A post-improvement procedure for the mixed load school bus routing problem[J]. European Journal of Operational Research, Z012,217 204-213.
  • 6Dueck G. New optimization heuristics: The great deluge algo- rithm and the record-to-record travel[J]. J. Comput. Phys. , 1993,104:86.
  • 7Nanry W, Barnes J. Solving the pickup and delivery problem with time windows using reactive tabu seareh[J]. Transporta- tion Research Part B, 2000,34:107-21.
  • 8Li H, LimA. A metaheuristie for the pickup and delivery prol lem with time windows[C]//13th IEEE International Conf1 rence on Tools with Artificial Intelligence(ICTAI). 2001:161 167 /.
  • 9Lau H, Liang Z. Pickup and delivery with time windows: algo- rithms and test case generations[C]//Proceedings of the 13th IEEE Conference on tools with Artificial Intelligence(ICTAI). 2001 : 333-340.
  • 10Golden B,Assad A,Levy L,et al. The fleet size and mix vehicle routing problem[J]. Computers and Operations Research, 1984, 11(1) :49-66.

共引文献14

同被引文献52

  • 1周康,强小利,同小军,许进.求解TSP算法[J].计算机工程与应用,2007,43(29):43-47. 被引量:31
  • 2NEWTON R M, THOMAS W H. Design of school bus routes by computer[J]. Socio-Economic Planning Sciences, 1969, 3(1) 75-85.
  • 3BRACA J, BRAMEL J, POSNER B, et al. A computerized approach to the New York city school bus routing problem[-J-. Iie Transactions, 1997, 29(8).. 693-702.
  • 4KIM B I, KIM S, PARK J. A school bus scheduling problem[J]. European Journal of Operational Research, 2012, 2182)= 577-585.
  • 5PARK 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.
  • 6FUGENSCHUH A, MARTIN A. A multicriteria approach for optimizing bus schedules and school starting times[J]. An nals of Operations Research, 2006, 147(1).. 199-216.
  • 7FUGENSCHUH A. Solving a school bus scheduling problem with integer programming[J]. European Journal of Opera tional Research, 2009, 193(3) :867-884.
  • 8KE X, ANEJA Y P, CARON R J. The school bus routing and scheduling problem with heterogeneous bus capacity: for mulations and their solutions[R]. University of Windsor, March 2006.
  • 9SCHITTEKAT P, SEVAUX M, ,SORENSEN K. A mathematical formulation for a school bus routing problem[C]//In- ternational Conference on Service Systems and Service Management, 2006: 1552-1557.
  • 10TOTH P, VIGO D. An overview of vehicle routing problems[C]//P Toth, D Vigo, The Vehicle Routing Problem, SI- AM Monographs on Discrete Mathematics and Applications, Philadelphia, 2002: 1-26.

引证文献6

二级引证文献11

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部