A variable iterated greedy algorithm based on grey relational analysis for crew scheduling

Document Type : Article

Authors

School of Automation, Huazhong University of Science and Technology, Wuhan 430074, China

Abstract

Public transport crew scheduling is a worldwide problem, which is NP-hard. This paper presents a new crew scheduling approach, called GRAVIG, which integrates grey relational analysis (GRA) into a Variable Iterated Greedy (VIG) algorithm. The GRA is served as a solver for the shift selection during the schedule construction process, which can be considered as a multiple attribute decision making (MADM) problem, since there are multiple static and dynamic criteria governing the efficiency of a shift to be selected into a schedule. Moreover, in the GRAVIG, a biased probability destruction strategy is elaborately devised to keep the ‘good’ shifts remained in the schedule without compromising the randomness. Experiments on eleven real-world crew scheduling problems show that the GRAVIG can generate high-quality solutions close to the lower bounds obtained by the CPLEX in terms of the number of shifts.

Keywords

Main Subjects


References
1. Shen, Y.D., Xu, J., and Zeng, Z.Y. Public transit planning and scheduling based on AVL data in China", Int. T. Oper. Res., 23(6), pp. 1089-1111 (2016).
2. Kwan, R.S.K. and Kwan, A. E ective search space control for large and/or complex driver scheduling problems", Ann. Oper. Res., 155(1), pp. 417-435 (2007).
3. Toth, A. and Kresz, M. An ecient solution approach for real-world driver scheduling problems in urban bus transportation", Cent. Eur. J. Oper. Res., 21, pp. 75- 94 (2013).
4. Shen, Y.D., Li, J.P., and Peng, K.K. An estimation
of distribution algorithm for public transport driver
scheduling", Int. J. Operational Research, 28(2), pp.
245-262 (2017)
5. Kwan, R.S.K. Case studies of successful train crew
scheduling optimisation", J. Scheduling., 14(5), pp.
423-434 (2011).
6. Hickman, M., Mirchandani, P., Vo , S. (Eds.), Lecture
Notes in Economics and Mathematical Systems, 600
(2008).
7. Lourenco, H.R., Paix~ao, J.P., and Portugal, R. Multiobjective
metaheuristics for the bus driver scheduling
problem", Transport. Sci., 35(3), pp. 331-343 (2001).
8. Dias, T.G., de Sousa, J.P., and Cunha, J.F. Genetic
algorithms for the bus driver scheduling problem: a
case study", J. Oper. Res. Soc., 53(3), pp. 324-335
(2002).
9. Li, J.P. and Kwan, R.S.K. A fuzzy genetic algorithm
for driver scheduling", Eur. J. Oper. Res., 147(2), pp.
334-344 (2003).
10. Park, T. and Ryu, K.R. Crew pairing optimization by
a genetic algorithm with unexpressed genes", J. Intell.
Manuf., 17(4), pp. 375-383 (2006).
11. Shen, Y.D., Peng, K.K., Chen, K., and Li, J.P. Evolutionary
crew scheduling with adaptive chromosomes",
Transport. Res. B-Meth., 56, pp. 174-185 (2013).
12. Cavique, L., Rego, C., and Themido, I. Subgraph
ejection chains and tabu search for the crew scheduling
problem", J. Oper. Res. Soc., 50(6) pp. 608-616
(1999).
13. Shen, Y.D. and Kwan, R.S.K. Tabu search for driver
scheduling", Lecture Notes in Economics and Mathematical
Systems, 505, pp. 121-135 (2001).
14. Yaghini, M., Karimi, M., and Rahbar, M. A set covering
approach for multi-depot train driver scheduling",
J. Comb. Optim., 29(3), pp. 636-654 (2015).
15. De Leone, R., Festa, P., and Marchitto, E. Solving
a bus driver scheduling problem with randomized
multistart heuristics", Int. T. Oper. Res., 18(6), pp.
707-727 (2011).
16. Hana , R. and Kozan, E. A hybrid constructive
heuristic and simulated annealing for railway crew
scheduling", Comput. Ind. Eng., 70, pp. 11-19 (2014).
17. Li, J.P., and Kwan, R.S.K. A self-adjusting algorithm
for driver scheduling", J. Heuristics., 11(4), pp. 351-
367 (2005).
18. De Leone, R., Festa, P., and Marchitto, E. A bus
driver scheduling problem: a new mathematical model
and a GRASP approximate solution", J. Heuristics.,
17(4), pp. 441-466 (2011).
19. Aickelin, U., Burke, E.K., and Li, J.P. An evolutionary
squeaky wheel optimization approach to personnel
scheduling", IEEE. T. Evolut. Comput., 13(2), pp.
433-443 (2009).
20. Huang, S., Yang, T., and Wang, R. Ant colony
optimization for railway driver crew scheduling: from
modeling to implementation", J. of the Chinese Institute
of Industrial Engineers, 28(6), pp. 437-449 (2011).
840 K. Peng and Y. Shen/Scientia Iranica, Transactions E: Industrial Engineering 25 (2018) 831{840
21. Li, J.P. Fuzzy evolutionary approaches for bus and
rail driver scheduling", Ph.D. Thesis, University of
Leeds, England (2002).
22. Peng, K.K. and Shen, Y.D. An evolutionary algorithm
based on grey relational analysis for crew
scheduling", J. Grey. Syst-UK., 28(3), pp. 75-88
(2016).
23. Framinan, J.M. and Leisten, R. Total tardiness minimization
in permutation
ow shops: a simple approach
based on a variable greedy algorithm", Int. J. Prod.
Res., 46(22), pp. 6479-6498 (2008).
24. Tasgetiren, M.F., Pan, Q.K., Suganthan, P.N., and
Buyukdagli, O. A variable iterated greedy algorithm
with di erential evolution for the no-idle permutation

owshop scheduling problem", Comput. Oper. Res.,
40(7), pp. 1729-1743 (2013).
25. Karabulut, K. and Tasgetiren, M.F. A variable iterated
greedy algorithm for the traveling salesman
problem with time windows", Inform. Sciences., 279,
pp. 383-395 (2014).
26. Yin, M.S. Fifteen years of grey system theory research:
A historical review and bibliometric analysis",
Expert. Syst. Appl., 40(7), pp. 2767-2775 (2013).
27. Rajesh, R. and Ravi, V. Supplier selection in resilient
supply chains: a grey relational analysis approach", J.
Clean. Prod., 86, pp. 343-359 (2015).
28. Wu, L.F., Liu, S.F., Yao, L.G., and Yu, L. Fractional
order grey relational analysis and its application", Sci.
Iran., 22(3), pp. 1171-1178 (2015).
29. Kuo, Y., Yang, T., and Huang, G.W. The use of
grey relational analysis in solving multiple attribute
decision-making problems", Comput. Ind. Eng., 55,
pp. 80-93 (2008).
30. Wang, P., Meng, P., Zhai, J.Y., and Zhu, Z.Q.
A hybrid method using experiment design and grey
relational analysis for multiple criteria decision making
problems", Knowledge-Based Syst., 53, pp. 100-107
(2013).
31. Ding, J., Song, S., Gupta, J.N.D., Zhang, R., Chiong,
R., and Wu, C. An improved iterated greedy algorithm
with a tabu-based reconstruction strategy for
the no-wait
owshop scheduling problem", Appl. Soft.
Comput., 30, pp. 604-613 (2015).
32. Pranzo, M. and Pacciarelli, D. An iterated greedy
metaheuristic for the blocking job shop scheduling
problem", J. Heuristics, 22, pp. 587-611 (2016).