Routing related costs constitute a significant portion of the overall logistics costs in most service industries. Private companies are continuously striving to reduce their vehicle routing costs to maintain a better standing in the competitive business world. In contrast, the public sector has not paid enough attention to its vehicle routing efficiency. Vehicle routing inefficiencies have resulted in wasting resources. Due to the recent funding cuts and economic hardship, public agencies need to improve their vehicle routing efficiencies. To aid public agencies in resolving inefficiencies in their operations, we propose some challenging vehicle routing problems in the public sector through mathematical modeling. To achieve this goal, in this dissertation, we study vehicle routing problems in two fields: i) vehicle routing model in public safety, i.e., how state troopers can patrol more efficiently and effectively on the roadways; and ii) vehicle routing model in health care, i.e., how caregivers are assigned to patients with home care needs and how they schedule their visit sequences. In the context of public safety, we present two models: i) a single-period, single-depot team orienteering problem with time windows and ii) a multi-period, multi-depot team orienteering problem with time windows. In the context of home health care, we present a multi-period, multi-depot vehicle routing problem with constraints specific to the health care industry. All of these models are mixed integer, and considered as computationally intractable. We solve them using either heuristics (local search, tabu search, simulated annealing) or decomposition method (column generation). Model one in public safety finds efficient patrolling plan with one single state trooper post. Model two in public safety improves the coverage of the roadway by allowing multiple state trooper posts. And, model three in home health care demonstrates improvements over the current practice with respect to the traveling cost and workload balance, and answers the question whether to invest in purchasing centrifuges.