Interest in network functions virtualization (NFV) continues to grow due to its perceived benefits to both service providers and users. One of the main challenges in realizing NFV has to do with orchestration of virtual functions deployed in various locations across the network. In this work, we consider the service-concatenation routing problem, where the objective is to construct a path of minimum cost that visits a set of nodes where virtual services are to be applied to the user's traffic in a specific order. We first show that this problem can be modeled as the shortest path tour problem (SPTP) that has been studied in different contexts. We then review and implement a suite of algorithms that use a variety of solution approaches for tackling SPTP, and we also develop a new algorithm. Finally, we carry out a comprehensive experimental evaluation of all algorithms and demonstrate that our algorithm scales well to large problem instances and is suitable for real-time operation as part of the orchestration process in NFV environments.