This paper presents a network-based multi-agent optimization model for strategic planning of service facilities in a competitive market. We focus on the type of service facilities that are of intermediate nature (i.e., service is sought along a path in-between an user’s origin and destina- tion). This problem has many applications in transportation science and logistics but presents great modeling and computational challenges due to complex user-network interactions. The main theoretical contribution of this paper is in establishing this new modeling framework, and providing rigorous analysis of its mathematical and computation properties including existence of system equilibrium. In addition, we provide a solution method based on variational analysis to overcome computational challenges imposed by non-convexity of the problem to efficiently reach a stable equilibrium solution.