A Multi-Start Iterated Local Search for a real case Dial-a-Flight Problem

The Dial-a-Flight Problem is a specific case of the well-known Dial-a-Ride Problem. It consists in collecting passengers from their departure locations and delivering them to their required destinations by means of a heterogeneous fleet of airplanes [1][2]. Several operational constraints must be considered, and the aim is to minimize costs while ensuring air travel security and a good-quality service to the passengers.
In our research, we deal with the real case problem incurred by a major airline company in Tanzania, which organizes safaris and transports passengers from/to the main airports and touristic zones of the country. The objective is to minimize the total cost of the trips, calculated by summing up fuel expenses, delay fines, traveled distances and takeoff costs. The planning horizon is set to a period between one to three days. Among the operational rules that the company follows to plan its flights, we consider: a) airplanes capacities, measured in number of passengers; b) time windows both at departure and arrival; c) airplane- and airport-dependent maximum takeoff weight; d) a desirable maximum number of intermediate stops for each passenger; e) refueling allowed only in a subset of airports; and f) a desirable return for each airplane to its base airport at the end of the day.
To solve the problem, we developed a multi-start iterated local search heuristic that starts with a greedy algorithm and then tries to improve the solution through a set of local search procedures, including insertion and removal of flights and passengers on the route of each airplane and changes in the departing time and amount of fuel on takeoff. The initial results showed a quick convergence of the algorithm, with an acceptable number of delays and intermediate stops. In the current phase of the project, we are validating the results with the company and developing a decision support system to facilitate the management of the input and visualization of the problem solution, as well to help the company in the decision-making process.

References:
[1] Cordeau, J. F., Laporte, G., Potvin, J. Y., & Savelsbergh, M. W. (2007). Transportation on demand. Handbooks in operations research and management science, 14, 429-466
[2] Engineer, F. G., Nemhauser, G. L., & Savelsbergh, M. W. (2011). Dynamic programming-based column generation on time-expanded networks: Application to the dial-a-flight problem. INFORMS Journal on Computing, 23(1), 105-119