Resumen de Solving a dial-a-flight problem using composite variables

I. Campbell, M. Montaz Ali, M. Silverwood

• A dial-a-flight problem (DAFP) is described as experienced by a tourist airline operating in Botswana. Typically, a daily schedule is drawn up manually by a team of experienced schedulers a few days before the day in question. In this research, the problem is modeled and optimized using a composite variable formulation of a multi-commodity network flow model. The method takes many of the problem constraints into account at the variable creation stage, reducing the problem size in terms of variables and constraints. As such the method is mostly suitable for highly constrained problems. Six daily lists of booking requests were supplied by the airline, and these were set up and solved. The results are compared with the actual costs incurred by the airline on the day in question. Additional ten lists of booking requests of various sizes were created and solved, and the results compared to results from an integer linear programming (ILP) formulation.