Abstract—Airline sector runs on very high operational costs, strict protocols and complex scheduling process. One of the critical aspect influencing these factors is aircraft maintenance routing. In order to get maintenance at regular intervals as per the FAA regulations, an aircraft is required to be routed towards a feasible maintenance station. Aircraft maintenance routing is one of the major factor that influences the decisions throughout the airline operations. This paper proposes a maintenance feasible route generation technique, based on Breadth first search and Dijkstra’s Algorithms. The proposed technique is able to produce the maintenance feasible routes while ensuring that the overall maintenance cost is minimized.