Free-ranging domestic dogs (FRD) are not only vectors of zoonoses of public health concern, but also pose direct threats to humans, livestock, and endangered wildlife. Many developing countries have struggled to control FRD, despite using both lethal and non-lethal methods. India has amongst the highest FRD populations globally and the highest incidences of dog-mediated human rabies, but only deploys Catch-Neuter-Vaccinate-Release (CNVR) for FRD control as a humane alternative to lethal methods, without evidence of it working successfully. Here, we use an agent-based dog population dynamics model to examine the time, effort, financial resources, and conditions needed to successfully control FRD in a typical urban setting. We simulate several scenarios, from an "ideal world" closed population with easily accessible dogs, to a more realistic open population with heterogeneity in catchability of dogs. In only one "best-case" scenario, CNVR resulted in a significant and lasting reduction in FRD, but with vaccination rates peaking only at 35%, which is half the WHO-recommended coverage. The customisable and portable modelling tool that we have developed allows managers to simulate real world processes and understand the expected effort needed to reduce regional dog populations, and assess methods for achieving effective anti-rabies vaccination coverage.