Abstract: The vision of using hydrogen energy to replace fossil fuels as the primary energy carrier for our transportation infrastructure has been gaining recognition in recent years. The obstacles facing the hydrogen economy vision are technological feasibilities and the cost of infrastructure buildup. Technological feasibilities include the production, storage, distribution, and refueling of hydrogen energy in a safe and economical manner. The cost of infrastructure development includes the building of production plants, storage facilities, distribution network, and refueling stations of hydrogen energy. The purpose of the research is to develop heuristic algorithms and a spatial decision support system (SDSS) to facilitate efficient planning of the refueling infrastructure of hydrogen energy. Facility location-allocation models, specifically the Flow Refueling Location Model (FRLM), have been applied to determine the combination of refueling stations to be built in order to maximize the flow covered with a fixed investment cost. A mixed-integer programming version of the model has been formulated and published. While the mixed-integer programming model could be used to obtain an optimal solution for a problem, it is slow and inefficient in solving problems with a large network and large number of candidate facilities. In this research, heuristics algorithms, specifically the greedy adding, greedy adding with substitution, and genetic algorithm, are developed and applied to solve the FRLM problem. These algorithms are shown to be effective and efficient in solving complex FRLM-problems. The SDSS presented in this research integrates geographical information systems (GIS) and heuristic search algorithms to provide a flexible and powerful system for selecting the locations of hydrogen refueling stations in a real-world scenario. GIS is used to gather and process the input for the model, such as the candidate facilities and traffic flows. The SDSS also uses GIS to display and verify the inputs and outputs of the model. The flexibility and visualization capability of the SDSS has proved to be very helpful for decision makers in locating hydrogen-refueling stations. For case study purposes, the SDSS is applied to locate hydrogen-refueling stations in the state of Florida for the Florida Hydrogen Initiative project.