An evolutionary and constructive approach to a crew scheduling problem in underground passenger transport.

*(English)*Zbl 1230.90122Summary: Operations management of subway systems is associated with combinatorial optimization problems (i.e. crew and train scheduling and rostering) which belong to the np-hard class of problems. Therefore, they are generally solved heuristically in real situations. This paper considers the problem of duty generation, i.e. identifying an optimal trips set that the conductors should complete in one workday. With regard to operational and labor conditions, the problem is to use the lowest possible number of conductors and minimize total idle time between trips. The problem is modeled and solved using a constructive hybrid approach, which has the advantage of visualizing a solution construction similar to the manual approach typically used. Our approach takes advantage of the benefits offered by evolutionary methods, which store a candidate solutions population in each stage, thus controlling the combinatorial explosion of possible solutions. The results thus obtained for problems similar to those that are solved manually in the Santiago metro system were compared with two alternative approaches, based on tabu search and a greedy method. The hybrid method produced solutions with the minimum number of duties in six of the ten problems solved. However, the tabu search method provided better results in terms of idle time than either the hybrid method or the greedy method.

##### MSC:

90B70 | Theory of organizations, manpower planning in operations research |

90B06 | Transportation, logistics and supply chain management |

90C59 | Approximation methods and heuristics in mathematical programming |

##### Software:

Tabu search
PDF
BibTeX
XML
Cite

\textit{R. Elizondo} et al., J. Heuristics 16, No. 4, 575--591 (2010; Zbl 1230.90122)

Full Text:
DOI

##### References:

[1] | Bengtsson, L.R., Galia, T., Gustafson, C., Hjorring, C., Kohl, N.: Railway crew pairing optimization. C. R. a. T. Report, Carmen Systems AB (2004) |

[2] | Caprara, A., Fischetti, M., Toth, P., Vigo, D., Guida, P.L.: Algorithms for railway crew management. Math. Program. 79(1-3), 125–141 (1997) · Zbl 0887.90056 |

[3] | Caprara, A., Fischetti, M., Toth, P.: A heuristic method for the set covering problem. Oper. Res. 47(5), 730–743 (1999) · Zbl 0976.90086 |

[4] | Caprara, A., Monaci, M., Toth, M.: A global method for crew planning in railway applications. In: Daduna, J., Voss, S. (eds.) Computer-Aided Transit Scheduling. Lecture Notes in Economics and Mathematical Systems, vol. 505, pp. 17–36. Springer, New York (2001) · Zbl 0989.90507 |

[5] | Cavique, I., Rego, C., Themido, I.: Subgraph ejection chains and tabu search for the crew scheduling problem. J. Oper. Res. Soc. 50(6), 608–616 (1999) · Zbl 1054.90546 |

[6] | Chaudhry, S.S., Luo, W.: Application of genetic algorithms in production and operations management: a review. Int. J. Prod. Res. 43(19), 4083–4101 (2005) · Zbl 1080.90514 |

[7] | Chew, K.L., Pang, J., Liu, Q.Z., Ou, J.H., Teo, C.P.: An optimization based approach to the train operator scheduling problem at Singapore MRT. Ann. Oper. Res. 108(1-4), 111–122 (2001) · Zbl 0993.90501 |

[8] | Dias, T.G., de Sousa, J.P., Cunha, J.F.: Genetic algorithms for the bus driver scheduling problem: a case study. J. Oper. Res. Soc. 53(3), 324–335 (2002) · Zbl 1103.90339 |

[9] | Ernst, A.T., Jiang, H., Krishnamoorthy, M., Nott, H., Sier, D.: An integrated optimization model for train crew management. Ann. Oper. Res. 108(1–4), 211–224 (2001) · Zbl 1001.90028 |

[10] | Ernst, A.T., Jiang, H., Krishnamoorthy, M., Owens, B., Sier, D.: An annotated bibliography of personnel scheduling and rostering. Ann. Oper. Res. 127(1-4), 21–144 (2004) · Zbl 1090.90078 |

[11] | Freling, R., Wagelmans, A.P.M., Paixao, J.M.P.: An overview of models and techniques for integrating vehicle and crew scheduling. Comput.-Aided Transit Sched., Proc. 471, 441–460 (1999) · Zbl 0948.90015 |

[12] | Freling, R., Huisman, D., Wagelmans, A.P.M.: Models and algorithms for integration of vehicle and crew scheduling. J. Sched. 6(1), 63–85 (2003) · Zbl 1154.90449 |

[13] | Freling, R., Lentink, R.M., Wagelmans, A.P.M.: A decision support system for crew planning in passenger transportation using a flexible branch-and-price algorithm. Ann. Oper. Res. 127(1-4), 203–222 (2004) · Zbl 1087.90036 |

[14] | Friberg, C., Haase, K.: An exact branch and cut algorithm for the vehicle and crew scheduling problem. Comput.-Aided Transit Sched., Proc. 471, 63–80 (1999) · Zbl 0935.90006 |

[15] | Gaffi, A., Nonato, M.: An integrated approach to ex-urban crew and vehicle scheduling. Comput.-Aided Transit Sched., Proc. 471, 103–128 (1999) · Zbl 0948.90016 |

[16] | Glover, F.W., Laguna, M.: Tabu Search. Springer, Boston (1997) |

[17] | Haase, K., Desaulniers, G., Desrosiers, J.: Simultaneous vehicle and crew scheduling in urban mass transit systems. Transp. Sci. 35(3), 286–303 (2001) · Zbl 1069.90528 |

[18] | Lourenco, H.R., Paixao, J.P., Portugal, R.: Multiobjective metaheuristics for the bus-driver scheduling problem. Transp. Sci. 35(3), 331–343 (2001) · Zbl 1069.90530 |

[19] | Morgado, E.M., Martins, J.P.: Scheduling and managing crew in the Portuguese railways. Expert Syst. Appl. 5(3–4), 301–321 (1992) |

[20] | Morgado, E.M., Martins, J.P.: CREWS_NS–Scheduling train crews in the Netherlands. AI Mag. 19(1), 25–38 (1998) |

[21] | Parada, V., Pradenas, L., Solar, M., Palma, R.: A hybrid algorithm for the non-guillotine cutting problem. Ann. Oper. Res. 117(1–4), 151–163 (2002) · Zbl 1028.90043 |

[22] | Pearl, J.: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley, Reading (1984) · Zbl 0527.68075 |

[23] | Russell, S.J., Norvig, P.: Artificial Intelligence: A Modern Approach. Prentice-Hall, Englewood Cliffs (2002) · Zbl 0835.68093 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.