I agree, the icons are not intuitive. I couldn't correctly interpret them from just looking at the UI. Before reading your description, I thought the airplane icon means this flight is operating or active. And wondered why do they show flights that are not operating? It was eventually clear, after reading the description. Your question is now serving as instruction on how to read this UI. If a user has to think what a signifier means, or needs instructions on how to read a signifier, that's a design failure.
Placing the frequent flight routes in a separate section at the top of the list eliminates the need for icons of any kind. You can also decide to show only frequent flights at first, the rest of the result will be exposed when user taps/clicks on a button labelled "more". The list can be collapsed also by clicking on "less". See (1) and (2) in the sketch. Added benefit, the non frequent flights can be lazy loaded. The first call to your backend returns only the frequent flights instead of the entire list of matching flights. These can also be cached to respond faster.
If you must use icons, I recommend using an icon that stronger associated with a product being in high demand. Concepts like favourites, popular, most viewed etc. in other product listings have similar meaning as frequent in this case. Favourites or populars are often signified with a star. I think that icon has more universal meaning than airplanes.
Another option is to use a badge instead. You get to keep the aesthetics of a small visual signifier aligned to the right edge while eliminating chances of misunderstanding. I'm using "frequent" in the example, but you can chose whatever works for you.