This paper proposes a new bikeway design problem that determines an optimal bikeway network that (1) minimizes the total travel time, (2) covers all potential cycling demand sources, and (3) satisfies the budget constraints. An efficient two-step solution method, with genetic algorithm and a novel elimination heuristic, is proposed to determine the selected node set and the bikeway layout separately. Numerical studies showed that a higher budget can change the network topology and improve the solution fitness. The case studies in two Hong Kong new towns showed that the model can handle design problems with or without existing bikeways under various budget levels. This model can, therefore, be adapted to similar bike-sharing system designs because (1) it ensures that the resultant bike station locations have complete demand coverage, (2) all bike stations can be well-connected by the bikeway network, and (3) the designed network can satisfy the budget constraint.