Setting up a bikeway network has been recognized as one of the most effective measures to motivate cycling. In fact, a highly connected, exclusive bikeway network that covers all demand sources can be an attractive and time-saving measure, but it requires very high setup costs. The planner often needs to have a trade-off between demand coverage and travel time under a given construction cost. This paper introduces a novel bikeway design problem which determines an optimal bikeway network that covers all potential cycling demand sources with minimal total travel time and under budget constraints. In the context of designing a bike sharing system, the resultant node set of the bikeway network can be interpreted as the locations of the shared bike stations which can cover all cycling demands. A two-stage solution method, by combining the genetic algorithm and a novel elimination heuristic, is proposed to solve the problem by firstly determining the subset of nodes (selected nodes) that can cover all the demand sources and then designing the bikeway network that connects all selected nodes within a given budget. Numerical studies illustrate the advantages of elimination heuristics in solving the proposed problem and the effect of the budget towards the solution fitness with or without a solution. Case studies of two proposed new towns in Hong Kong are provided to illustrate the applicability and effectiveness of the method in bikeway design. This optimization model can be applied to bike-sharing system design problems which aims to cover all demand sources by providing bike stations that are also well connected with exclusive bikeways subject to budget constraints.