An evolutionary and constructive approach to a crew scheduling problem in underground passenger transport
Résumé
Operation management of underground passenger transport systems is associated with combinatorial optimization problems (known as crew and train scheduling and rostering) which belong to the np-hard class of problems. Therefore, their resolution in real situations is generally addressed using heuristic methods. This paper considers the duty generation problem, which consists of identifying an optimal trips set that the conductors should complete in a labor day. With regard to the operational and labor conditions, the trains should be driven with the lowest number of conductors and a minimized 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 approach typically used by operators who manually solve the problem. This approach takes advantage of the benefits offered by evolutionary methods, which hardly store a candidate solutions population in each stage, controlling in this way the combinatorial explosion of possible solutions. The results that we obtained for problems with similar characteristics to those that are performed manually in the Santiago Metro System were compared with two alternative approaches based on tabu search and a greedy method. The hybrid method produced similar results to those generated by the tabu search, and both found better results than the greedy method.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...