Article ID: | iaor19991313 |
Country: | United States |
Volume: | 46 |
Issue: | 2 |
Start Page Number: | 260 |
End Page Number: | 271 |
Publication Date: | Mar 1998 |
Journal: | Operations Research |
Authors: | Gopalan Ram, Talluri Kalyan T. |
Keywords: | networks: scheduling, vehicle routing & scheduling |
Federal aviation regulations require that all aircraft undergo maintenance after flying a certain number of hours. To ensure high aircraft utilization, maintenance is done at night, and these regulations translate into requiring aircraft to overnight at a maintenance station every three to four days (depending on the fleet type), and to visit a balance-check station periodically. After the schedule is fleeted, the aircraft are routed to satisfy these maintenance requirements. We give fast and simple polynomial-time algorithms for finding a routing of aircraft in a graph whose routings during the day are fixed, that satisfies both the three-day maintenance as well as the balance-check visit requirements under two different models: a static infinite-horizon model and a dynamic finite-horizon model. We discuss an implementation where we embed the static infinite-horizon model into a three-stage procedure for finding a maintenance routing of aircraft.