Analytic Hierarchy Process (AHP) is often used for making decision with multiple criteria. It helps to breakdown complicated problem into a smaller, less-complicated problem. The use of AHP allows decision maker to see what aspects are more important in the decision making process. While Goal Programming (GP) is used to help calculate the optimum option out of the desired. GP is used in this research because using AHP alone will be too subjective. Combining the two method will be a new approach in selecting new highway location in Indonesia and will increase the accuracy of decision making. This research is focused on making decision to select a new rest area location. Location selection is a crucial decision for any company that may be difficult to solve because of the existence of conflicting factors. In the highway industry, rest area location selection involves several quantitative and qualitative factors such as topography, infrastructure, government policy, social environment and human factors. AHP was used to calculate the relative importance of each criteria and sub-criteria in accordance with the opinions of experts. From this study, we know that human factors and government policy play the most important role in the location selection. The result of this calculation is the selection of two location alternatives for the next rest area. The impact from this research will be beneficial for the safety of road user and will help decrease accident rate in highway.