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**

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. Eective 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 dierential 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).

Transactions on Industrial Engineering (E)

March and April 2018Pages 831-840