全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...

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

DOI: 10.3724/SP.J.1047.2013.00879, PP. 879-886

Keywords: 校车路径问题,带时间窗的车辆路径问题,模拟退火算法,校车调度问题

Full-Text   Cite this paper   Add to My Lib

Abstract:

校车调度问题(SBSP)是通过调度使一辆校车服务完一个学校后继续服务其他学校,以减少一个地区所需的校车总数,进而降低校车采购成本和运营成本。目前的SBSP求解方法是将其转化为指派问题或运输问题,使用混合整型规划算法或者简单启发式算法进行求解,但求解性能有局限。本文在单校校车路径规划的基础上,将单校路径抽象为虚拟站点,进而将SBSP转换为带有时间窗的车辆路径问题(VRPTW),设计元启发算法进行求解。使用构造启发式算法获得初始解后,在模拟退火算法框架中通过典型的局部搜索算子搜索邻域解,逐步改善求解质量。搜索算子包括单点移动、两点交换、2-OPT和Cross-Exchange。迭代优化过程中以校车路径数为主要目标,路径长度为次要目标。为避免邻域搜索陷入局部最优,算法以一定的概率接受部分使路径长度增加的解。15个案例实验验证了本算法的有效性,与现有算法相比,能够获得更好的优化目标,适用于大规模的校车调度。

References

[1]  党兰学, 王震, 刘青松, 等.一种求解混载校车路径的启发式算法[J].计算机科学, 2013, 40(7):248-253.
[2]  Gro?r C, Golden B, Wasil E. A library of local search heuristics for the vehicle routing problem[J]. Mathematical Programming Computation, 2010, 2(2):79-101.
[3]  Br?ysy O, Gendreau M. Vehicle routing problem with time windows, Part Ⅰ: Route construction and local search algorithms[J]. Transportation science, 2005, 39(1):104-118.
[4]  Solomon M M. Algorithms for the vehicle routing and scheduling problems with time window constraints[J]. Operations research, 1987, 35(2):254-265.
[5]  Newton R M, Thomas W H. Design of school bus routes by computer[J]. Socio-Economic Planning Sciences, 1969, 3(1):75-85.
[6]  Park J, Kim B I. The school bus routing problem: A review[J]. European Journal of Operational Research, 2010, 202(2):311-319.
[7]  Swersey A J, Ballard W. Scheduling school buses[J]. Management Science, 1984, 30(7):844-853.
[8]  Desrosiers J, Ferland J A, Rousseau J M, et al. An overview of a school busing system[M].//Jaiswal N K (Ed.). Scientific Management of Transport Systems, Amsterdam: North-Holland, 1981:235-243.
[9]  Desrosiers J, Ferland J A, Rousseau, et al. A multi-period school bus routing and scheduling system[M].//TIMS Studies in the Management Sciences, Amsterdam: Elsevier Science Publishers, 1986, 22:47-71.
[10]  Fügenschuh A. Solving a school bus scheduling problem with integer programming[J]. European Journal of Operational Research, 2009, 193(3):867-884.
[11]  Kim B I, Kim S, Park J. A school bus scheduling problem[J]. European Journal of Operational Research, 2012, 218(2):577-585.
[12]  Spada 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.
[13]  Swersey A J, Ballard W. Scheduling school buses[J]. Management Science, 1984, 30(7):844-853.
[14]  Spada 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.
[15]  Fügenschuh A. A set partitioning reformulation of a school bus scheduling problem[J]. Journal of Scheduling, 2011, 14(4):307-318.
[16]  Fügenschuh A, Martin A. A multicriteria approach for optimizing bus schedules and school starting times[J]. Annals of Operations Research, 2006, 147(1):199-216.
[17]  Chen D S, Kallsen H A, Snider R C. School bus routing and scheduling: an expert system approach[J]. Computers & Industrial Engineering, 1988, 15(1):179-183.
[18]  Braca J, Bramel J, Posner B, et al. A computerized approach to the New York City school bus routing problem[J]. ⅡE transactions, 1997, 29(8):693-702.
[19]  Bent R, Van Hentenryck P. A two-stage hybrid local search for the vehicle routing problem with time windows[J]. Transportation Science, 2004, 38(4):515-530.
[20]  Bent R, Hentenryck P V. A two-stage hybrid algorithm for pickup and delivery vehicle routing problems with time windows[J]. Computers & Operations Research, 2006, 33(4):875-893.

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133