Conventional public transportation is one of the basic modes of transportation for urban residents. In order to ensure the efficiency of public transportation and reduce operating costs, it is necessary to perform quantitative analysis and systematic research on the operation of buses. In this paper, in order to minimize the total cost of passengers and bus company operations, a multi-objective bus departure frequency optimization model based on passenger arrival rate is proposed to maximize the benefits of both passengers and operators. The function of passenger arrival rate was used to calculate the passenger waiting time, which could lead to a more realistic waiting time in the optimization calculation. Considering the good convergence of the genetic algorithm and the easy-to-binary encoding of departure frequency, the algorithm of this model was designed based on genetic algorithm. Taking Changzhou Bus Line B1 during the peak time as an example, the optimal departure frequency was 13.9 times per hour. Compared with the other three classic departure frequency determination methods, the total cost of this model was reduced by 18.1%, 1.5%, 1.2%. The results show that the departure frequency model proposed can effectively reduce the overall cost of bus travel by coordinating the waiting time cost of passengers, in-vehicle congestion cost and vehicle purchase cost, fuel cost of bus operation.