Hybrid Column Generation Approaches for Urban Transit Crew Management Problems

Yunes, Tallys H.; Moura, Arnaldo V.; De Souza, Cid C.
May 2005
Transportation Science;May2005, Vol. 39 Issue 2, p273
Academic Journal
This article considers the overall crew management problem arising from the daily operation of an urban transit bus company that serves the metropolitan area of the city of Belo Horizonte, Brazil. Due to its intrinsic complexity, the problem is divided in two distinct subproblems: crew scheduling and crew rostering. We have investigated each of these problems using mathematical programming (MP)and constraint logic programming (CLP) approaches. In addition, we developed hybrid column generation algorithms for solving these problems, combining MP and CLP. The hybrid algorithms always performed better, when obtaining optimal solutions, than the two previous isolated approaches. In particular, they proved to be much faster for the scheduling problem. All the proposed algorithms have been implemented and tested over real-world data obtained from the aforementioned company. The coefficient matrix of the linear program associated with some instances of the scheduling problem contains tens of millions of columns; this number is even larger for the rostering problem. The analysis of our experiments indicates that it was possible to find high-quality, and many times optimal, solutions that were suitable for the company's needs. These solutions were obtained within reasonable computational times on a desktop PC.


Related Articles

  • Scheduling Dial-a-Ride Transportation Systems. Stein, David M. // Transportation Science;Aug78, Vol. 12 Issue 3, p232 

    An analytic investigation into the fundamental aspects of scheduling "Dial-a-Ride" transportation systems is conducted. Based upon simple mathematical models that focus on the combinatorial nature of the problem, a class of algorithms is derived for which performance can be measured in a precise...

  • Cars Drive Up the Costs of URBAN SPRAWL. Sheehan, Molly O'Meara // USA Today Magazine;Jan2002, Vol. 130 Issue 2680, p70 

    Discusses problems with car-dependent development. Various spending on passenger transport around the world; Impact of motor vehicles on the environment; Estimated costs of road transport not covered by drivers.

  • Some Issues Relating to the Optimal Design of Bus Routes. Newell, G. F. // Transportation Science;Feb79, Vol. 13 Issue 1, p20 

    The following is mostly a discussion of some issues relating to the design of minimum cost bus routes serving a multiple origin-multiple destination trip distribution. The main difficulty in determining any "optimal" routing origina tes from the fact that the objective function (total cost) is a...

  • TfL signs Siemens to track its buses. Proud, Sue // Computer Weekly;5/24/2005, p3 

    This article reports that Transport for London has signed a £120m contract with Siemens Business Services Inc. to track and monitor London, England's 8,000 buses. It said that the new systems would improve services for the capital's six million passengers. Siemens will monitor buses with...

  • Rotating Roster for a Transit System. Bennett, Brian T.; Potts, Renfrey B. // Transportation Science;Feb68, Vol. 2 Issue 1, p14 

    The paper discusses the computer construction of the lists of weeks of work that form the basis of the rotating roster for crews operating buses for a transit system. There are two construction phases; the first consists of making a day-off pattern and the second consists of placing daily shifts...

  • Study on the Location Planning Approach of Outbound Collection Centers. Houjun Lu; Huiqiang Zhen; Youfang Huang; Yuwei Zhao // Information Technology Journal;2013, Vol. 12 Issue 24, p8181 

    The collecting and distributing of container highway transportation is the head and the tail of main transport lines. To minimize the unit cost and the complexity of transportation schedules, this paper addresses the Collection Center Location Planning Problem (CCLPP) concerned with how many...

  • Time-Risk Tradeoff of Hazmat Routing Problem in Emergency Situation. Mahmoudabadi, Abbas; Seyedhosseini, Seyed Mohammad // Proceedings of the International Conference on Industrial Engine;2012, p344 

    Risk and cost are important factors in Hazmat routing problem. While the local authorities try to minimize risk, transport companies plan to reduce cost. In emergency situation, time is an important issue and should be minimized to carry vital substances of Hazmat. This is a serious concern when...

  • Earliness-Tardiness Scheduling Around Almost Equal Due Dates. Hoogeveen, J. A.; Van De Velde, S. L. // INFORMS Journal on Computing;Winter97, Vol. 9 Issue 1, p92 

    Discusses the existence of another class of problems that are structurally less complicated than the general earliness-tardiness problem. Details of common due date problems; Logic behind Emmons' matching algorithm; List of earliness-tardiness problems to which the optimality principle of the...

  • Preemptive Scheduling to Minimize Maximum Completion Time on Uniform Processors with Memory Constraints. Martel, Charles // Operations Research;Nov/Dec85, Vol. 33 Issue 6, p1360 

    We consider the problem of preemptively scheduling n jobs on m processors. The ith job has a processing requirement p, and a memory requirement q[sub i]. The ith processor has a speed s, and a memory capacity c[sub i]. The ith job can be run on the jth processor whenever c[sub j] Is greater than...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics