Unexpected congestion due to incidents may cause a substantial delay for drivers and reduce the roadway safety. Effective incident management relies on many tools to lessen the overall impact of crashes, road debris, and disabled vehicles. Many urban areas have adopted freeway service patrol (FSP) programs that patrol the freeway network searching for incidents, providing aid to motorists, and assisting with incident management and clearance. FSP management must consider the beat configuration, fleet size, and fleet allocation. The beat configuration is how the network is divided into different parts for patrolling, and each part is called a beat. The beat configuration, fleet size, and fleet allocation need to be determined for designing a network for FSP program. However, the literature lacks profound analytical methodologies for this purpose, and a few previous models typically tried to design these elements distinctly while they are strictly interrelated. Therefore, our research presents a comprehensive mixed-integer programming model to design the network for freeway service patrol programs. This model aims to concurrently determine the beat structure, fleet size, and allocation of trucks to beats, to minimize incident delay while the operational cost is considered, as well. The research uses part of the Tarrant County Courtesy Patrol (CP) network in Texas as a numerical example to examine the model’s capability to address different issues in patrol programs and to determine the impact of each factor on the optimal design. Also, to explore the problem with field data and real-size networks, the proposed model and developed heuristics are applied to part of the freeway network in Maryland covered by Coordinated Highways Action Response Team (CHART). Results indicate that a joint model forms a better solution regarding incident delay reduction and operation costs.