A hybrid enhanced artificial bee colony algorithm (HEABC) is proposed for solving the problem of bus network design. The algorithm is intended to reduce the weighted sum of the number of transfers and the total travel time of the users through restructured bus routes and new frequencies without increased fleet sizes. The HEABC relies mainly on the enhanced artificial bee colony algorithm to determine the route structure, and the frequency is determined by the frequency-setting heuristic during the fitness evaluation. For an illustration of its performance, the HEABC was compared with a hybrid generic algorithm and a variant of the HEABC. The results indicated that the HEABC could produce better solutions than the other two algorithms could. Moreover, the HEABC could produce a design that was better than the existing design for maximum intermediate stops, total travel time, number of transfers, maximum headway, and total fuel cost. The design should be acceptable to the public and to bus operators.