<p>In a highly competitive market environment, outsourcing of logistics service is one of the most significant strategies for enterprises to enhance competitiveness. As a key component of logistics outsourcing, carrier selection directly affects logistics service quality. In general, there are multiple carriers to provide freight service along each route of a logistics network. Each carrier has stochastic capacity owing to that the carrier’s capacity may be partially occupied by other customers. Moreover, goods spoilage often occurs during transportation such that the amount of intact goods delivered may not fulfill the market demand. Thus, each carrier in this study is characterized by stochastic capacity that denotes freight capacity and delivery spoilage that denotes freight quality. Both freight capacity and freight quality are integrated into the carrier selection problem from the viewpoint of network reliability. An effective method that incorporates network reliability algorithm and genetic algorithm is developed to find the optimal carrier selection and the maximum network reliability. A practical logistics network is analyzed to showcase the utility of the algorithm in carrier selection, together with a sensitivity analysis to figure out the important carriers.</p>