Vehicle scheduling plays a profound role in public transportation. Especially, stochastic vehicle scheduling may lead to more robust schedules. To solve the stochastic vehicle scheduling problem (SVSP), a discrete artificial bee colony algorithm (DABC) is proposed. Due to the discreteness of SVSP, in DABC, a new encoding and decoding scheme with small dimensions is designed, whilst an initialization rule and three neighborhood search schemes (i.e., discrete scheme, heuristic scheme, and learnable scheme) are devised individually. A series of experiments demonstrate that the proposed DABC with any neighborhood search scheme is able to produce better schedules than the benchmark results and DABC with the heuristic scheme performs the best among the three proposed search schemes.