کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
1132153 1488987 2013 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Evolutionary crew scheduling with adaptive chromosomes
موضوعات مرتبط
علوم انسانی و اجتماعی علوم تصمیم گیری علوم مدیریت و مطالعات اجرایی
پیش نمایش صفحه اول مقاله
Evolutionary crew scheduling with adaptive chromosomes
چکیده انگلیسی


• We exploit a new chromosome representation based on a tight target number of genes.
• The length of a chromosome can vary adaptively during the scheduling process.
• The adaptive change is achieved by using removal and replenishment strategies.
• The algorithm is very fast, robust and can compile efficient schedules.
• High quality results comparable to those of LP relaxation have been achieved.

This paper presents an adaptive evolutionary approach incorporating a hybrid genetic algorithm (GA) for public transport crew scheduling problems, which are well-known to be NP-hard. To ensure the search efficiency, a suitable chromosome representation has to be determined first. Unlike a canonical GA for crew scheduling where the chromosome length is fixed, the chromosome length in the proposed approach may vary adaptively during the iterative process, and its initial value is elaborately designated as the lower bound of the number of shifts to be used in an unachievable optimal solution. Next, the hybrid GA with such a short chromosome length is employed to find a feasible schedule. During the GA process, the adaptation on chromosome lengths is achieved by genetic operations of crossover and mutation with removal and replenishment strategies aided by a simple greedy algorithm. If a feasible schedule cannot be found when the GA’s termination condition is met, the GA will restart with one more gene added. The above process is repeated until a feasible solution is found. Computational experiments based on 11 real-world crew scheduling problems in China show that, compared to a fuzzy GA known to be well performed for crew scheduling, better solutions are found for all the testing problems. Moreover, the algorithm works fast, has achieved results close to the lower bounds obtained by a standard linear programming solver in terms of the number of shifts, and has much potential for future developments.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Transportation Research Part B: Methodological - Volume 56, October 2013, Pages 174–185
نویسندگان
, , , ,