Primary Care is fundamental to a well-functioning health system. Various geographical small areas including specialized geographies such as Primary Care Service Areas (PCSAs) are used to measure primary care relevant outcomes and services, or to target interventions. PCSAs are small areas, the majority of patients resident in which obtain their primary care services from within the geography. The extent of this self-sufficiency of use is measured by the Localization Index (LI). PCSAs have been built in the US, Australia and Switzerland using an allocation algorithm, which, while simple and easy to implement, may require the use of various ad-hoc parameters. In this article we propose an optimization based approach to creating PCSAs, - an approach which has previously been used to generate labour flow regions in Ireland. The approach is data driven, thus requiring a minimal number of ad-hoc parameters. We compared the resulting PCSAs (or `rPCSAs') with PCSAs generated using the traditional allocation algorithm. We found that rPCSAs were generally larger, offered greater LIs and reflected patient travel patterns better than traditional PCSAs. Accounting for the larger size of rPCSAs showed that rPCSAs offered better LIs than similar sized traditional PCSAs.