An effective competition at the civil aviation sector could be possible by an effective fleet management. One of two important functions of the fleet management is to define the aircraft routes and plan the aircraft maintenance. The aircraft maintenance requirements which have an active role as a constraint have affected the effective aircraft usage. Common approach in practice, aircraft routes and maintenance plans are separately developed, encountered discrepancies are solved by keeping additional aircraft and/or by taking aircraft to maintenance early. The concurrent approach which takes the aircraft routes together with maintenance plans is capable of the increase not only the duration of the aircraft in the air, but also their flight time between maintenances. Considering the maintenance costs which form approximately one quarter of operating costs, concurrent routing and maintenance planning are expected to offer a significant competitive advantage. In this study, the effective usage of aircrafts and minimizing maintenance costs have been aimed by defining the aircraft routes with maintenance requirements. At the direction of these goals, an integer linear goal programming approach is proposed which minimize the remaining legal flying durations of the aircrafts before maintenance. This approach has balanced the flight numbers or flight durations at the direction of decision maker, thus it has provided that the aircraft usage ratio and maintenance costs as possible as equal. During the demonstration of the availability of the approach, the real-life problem of an airline, has been solved by the software of CPLEX/GAMS integer linear program. It has been shown that the proposed method can achieve 95.4% to 100% of utilization rates for the legal flying hours of aircrafts over the experiments.