| Home  | About ScienceAsia  | Publication charge  | Advertise with us  | Subscription for printed version  | Contact us  
Editorial Board
Journal Policy
Instructions for Authors
Online submission
Author Login
Reviewer Login
Volume 43 Number 3
Volume 43 Number 2
Volume 43 Number 1
Volume 43S Number 1
Volume 42 Number 6
Volume 42S Number 1
Earlier issues
Volume 40 Number 5 Volume 40 Number 6 Volume 41 Number 1

previous article

Research articles

ScienceAsia 40(2014): 456-462 |doi: 10.2306/scienceasia1513-1874.2014.40.456


A hybrid particle swarm optimization and an improved heuristic algorithm for an airline crew rostering problem


Varis Limlawan, Boontariga Kasemsontitum, Chawalit Jeenanunta*

 
ABSTRACT:     The airline crew scheduling problem is a combinatorial optimization problem and belongs to the class of NP-hard problems. An effective method for solving the airline crew scheduling problem can reduce the crew costs and improve crew satisfaction. Because of its complexity, the problem is divided into two subproblems: the crew pairing problem and the crew rostering problem. In this paper, the crew rostering problem is focused on and the objective is to generate a fairness timetable in which the workloads are distributed among each crew equally. We propose a hybrid particle swarm optimization (PSO) and an improvement heuristic (IH) to solve this problem. The IH is designed to improve the standard deviation of the workloads by picking a workload from the high workload crew and assigning it to the low workload crew. The IH improves the solution of the particle after the particle changes position each generation. The proposed algorithm is tested on actual pairing data from Thai Airways and is compared with PSO without IH and the multi-commodity network flow approach. With the combination of PSO and IH, the algorithm can improve the quality of the solution by more than 20% in most cases, and PSO with IH also outperforms the network approach in 6 out of 9 cases and especially in the large size cases for which the network approach cannot find a feasible solution.

Download PDF

2 Download 27 View


Sirindhorn International Institute of Technology, Thammasat University, Pathum Thani 12121 Thailand

* Corresponding author, E-mail: chawalit@siit.tu.ac.th

Received 4 Jul 2013, Accepted 28 Sep 2014