No universal strategy exists for discovering periodic orbits in highly non-keplerian environments. A combination of analytical and numerical approaches have been proposed, but these approaches often rely on approximations of the gravitational potential or initial guesses that are sufficiently close to a true solution. In the case of small body settings, these problems are further exacerbated due to the computationally expensive gravity models needed to propagate spacecraft dynamics generated by the bodies’ irregular geometries. This paper aims to extend the set of tools and algorithms used to search for periodic orbits in small body settings. An emphasis is placed on two novel contributions: First, reducing the computational overhead of this process through the use of the novel Physics-Informed Neural Network Gravity Model (PINN-GM); second, combining the differentiability of the PINN-GM with the Lagrange planetary equations (LPE) to conduct a shooting algorithm in orbital element space rather than cartesian space. Results show that the PINN-GM can achieve order-of-magnitude faster orbit search times than with the polyhedral model without sacrificing dynamical fidelity, and demonstrate how the PINN-GM enhanced orbital element shooting method can be used to assist mission designers in searching for for desirable orbits that are otherwise challenging to determine using the past cartesian methods.