Blocking and Runcutting

Vehicle Assignment and Runcutting Techniques in The Master Scheduler
Edward Sitarski, Vice President of Technology (e.sitarski@schedule-masters.org)

Computer Aided Transit Scheduling (CATS) has had an important effect on the operation of transit properties throughout the world. Some of the primary added-value components of CATS systems are the ability to optimally assign vehicle to trips (blocking), drivers to vehicles (runcutting), and to create work weeks for drivers (rostering). This paper explains how The Master Scheduler solves blocking and runcutting.
A scheduling system only adds real business value if it is actually used, and this depends on how accurately it models the operations of the property, the quality of its user interface, and its ability to communicate the schedules to the rest of the organization. In addition to algorithms, TMS has a highly indexed relational data model, completely user-defined rules and costs, Microsoft Windows interface, bundled street-mapping (MapInfo), and report writer (Crystal Reports). This total approach to functionality and usability has enabled TMS to keep delivering exceptional return on investment.

Vehicle Assignment

Vehicle assignment is the process of assigning vehicles to required trips so that all the trips are "covered” by a vehicle. There are two basic considerations of vehicle assignment - minimizing the vehicles required, then minimizing the total waiting and deadhead time.

Trip Specification

Optimal vehicle assignment really starts with the trip times that are entered. In the general case, connection times are entered once into the system. Connection times which deviate from the general case are also only entered once. Actual trip times are generated automatically and "on the fly” from the base rules, and a specified "maximum load point” (MLP), indicating a timepoint and time for the trip. Of course, the MLP can change during the day. All trip time deviations are stored explicitly for easy reference and modification. This ensures that the times used for blocking are always the most recent, and there is no way to create timing problems that do not follow directly from the rules. Different service days can be defined to reflect weekday, weekend, holiday or special events.

There is no preset software limit to the number of trips, the number of timepoints, or the number of nodes. The method of generating trips "on the fly” provides another advantage. Unlike other systems, TMS automatically "smoothes” the times on trips which cross time boundaries. For example, say the total running time of a trip is 10 minutes during off-peak, and 20 minutes during peak (rush-hour). TMS will automatically graduate the running times of trips which cross the boundary so that they gradually increase from ten to twenty. This leads to a much more realistic representation of the running times, and leads to a much more accurate schedule that can be followed in the real world.

Layovers and Deadheads:

Layover times are the lower and upper limits that a vehicle can wait after performing a trip. Increasing the minimum layover time increases schedule adherence, as the vehicles have an opportunity to absorb delays during the wait. Increasing the maximum layover potentially allows more trips to be considered at a given location. In TMS, layover time can be expressed as a global down to the trip level as a fixed time min/max, as a percentage of the trip time, or any combination of fixed or percentage. Specifying minimum layover as a percentage of trip time is a good way to achieve more balanced schedule adherence. Deadheads are connections between trips that do not arrive and leave from the same location. In TMS, deadhead times can vary in availability and duration by time of day from any location.

Blocking Algorithm:

Once accurate trip and potential layover and deadhead times are determined, TMS uses an optimal algorithm for assigning vehicles. TMS can consider all trips and deadheads of the property, and block all the trips at once. The scheduler can choose to allow interlining, and can also specify the maximum allowable duration of a deadhead to be considered. He/she can also manually create blocks, and those blocks will be left alone by the optimal blocking algorithm. The manual blocker shows the scheduler a list of all the accessible trips from the current one, sorted by increasing layover time. The scheduler only needs to choose the next trip that the block should "hook” with. The scheduler can unblock trips at any time and make those trips available to the optimal blocker for reconsideration. He/she can also specify whether there are vehicle restrictions on the combination of certain trips (for example, trolleys, articulated or accessible vehicles). This ensures that, for example, that a trip requiring an articulated vehicle will never connect to a trolley.

Optimal Blocking:

The optimal blocking problem has been extensively described in the literature (Orloff (1976)¹ and Mojsilovic (1983)², Gavish / Schweitzer / Shilfer (1978)³ and Gavish / Shilfer (1978)⁴, Carraresi / Gallo (1984)⁵ and Luedtke (1985)⁶, Paixão / Branco (1987)⁷and (1988)⁸, Berossi / Carraresi / Gallo (1987)⁹). For reasons of robustness, customer need, and business value, TMS uses the Transportation Model as proposed by Gavish / Schweitzer / Shilfer (1979) and Gavish / Shilfer (1978). This technique builds a "network” of all unassigned trips, and assigns them optimally to vehicles based on minimizing the number of vehicle blocks as well as the total waiting and deadhead time. It should be stressed that this technique provably minimizes the number of vehicle blocks required because it considers all possibilities of layovers and deadheads simultaneously.

The network is generated by creating "vertices” which correspond to all the trips to be considered. Then, all compatible trips at each location which fall between the minimum and maximum layover time are connected by "waiting arcs”. All compatible deadhead arcs are then added to complete the network. The cost of waiting arcs is equal to the time of the layover, and the cost of deadhead arcs is equal to the time of the deadhead, plus a fixed "deadhead penalty”. This penalty models the fact that given a choice between a layover or deadhead, it is better to have the vehicle wait because this does not require a driver.

In addition, TMS uses a small, specially computed, cost on waiting arcs that doesn’t affect the total layover time or the number of blocks, but favorably biases the solution as follows: given a choice between an optimal set of layover times, this special cost causes the set of times that are most equitable in duration to be selected. This avoids solutions with widely varying layover unless necessary to minimize the number of vehicle blocks.

The network solver optimally "hooks” the trip nodes to each other or to a "source” which represents the depot. The algorithm proceeds through a series of "pivots” where trips are initially hooked together in a "greedy fashion”, but the solver has the ability to correct sub-optimum choices that are made early in the process. This ensures that the solver converges on the true global, lowest-cost solution. The TMS network solver was developed especially for this application, and has been specially tuned for the Windows-PC architecture. The optimal blocker can create over 300 blocks in under 2 minutes on a low-end P-III, while considering all combinations of trips, wait times, and deadheads simultaneously. This technique also allows the optimizer to solve around a specified number of minimum pullouts (to ensure that a minimum number of blocks are created) or a maximum number of pullouts (at the expense of missing trips at a specified penalty cost).

TMS also provides a mechanism to connect trips together by choosing the next connecting trip with the least waiting time. Although this process may lead to more vehicle blocks than the optimal blocker, it does lead to a solution where vehicles collecting at a transfer point are guaranteed arrive and leave in a "first in, first out” (FIFO) sequence. This is sometimes necessary in cases where there are streetcars or tight transfer points where vehicles must leave in the same order they arrive.

Runcutting

Runcutting is a much more complex problem than vehicle assignment and still does not yet have a totally satisfactory and robust algorithmic solution. The first problem with runcutting is to accurately describe and represent the cost structure of the valid runs.

Run Types:

TMS is unique in its ability to allow users to specify extremely complex cost structures completely by point-and-click from dialog boxes - no custom programming or configuration is required. It has extensive features to define multi-piece runs (up to ten pieces) and many "premiums” (a service performed or condition experienced by the operator that needs to be paid for). The names of run classifications are completely user defined, for example, a "straight” run can consist of any number of pieces, with mandatory meal breaks if desired. Of course, limits on the spread of duties and the lengths of breaks can be modeled¹⁰. SMI has yet to encounter a property at which we cannot model the runs definition rules accurately within the system.

Additionally, runcutting requires the specification of "relief points”. Relief points are specified points on routes where a driver can start work, end work, be relieved by another driver, or leave the current vehicle to perform work on another vehicle. In TMS, relief points are specified at the System Node level, and different relief point codes can be in effect at different times of the day. Additionally, schedulers can specify comments associated with relief points, and those comments can appear on any report.

Runcut Algorithms:

TMS’ runcutting philosophy is to combine the best of algorithmic and heuristic techniques with the addition of user expertise. Additionally, the time to get a feasible runcut is extremely important to adding real business value. A runcut solver that takes 24 hours to finish is not acceptable as a tool to evaluate special events or proposals during union negotiations.

Two-Piece Technique:

The runcut techniques actually used in TMS depend on the "type” of run required. For example, consider "straight” runs with meal breaks. In this case, TMS uses the technique first used in the HOT II system (Hoffstadt (1981)¹¹, Daduna / Mojsilovic (1988)¹², Mojsilovic (1983)¹³). This technique first uses heuristics to determine the sets of pieces which are themselves efficient and provide good chains of meal breaks. Additionally, the piece creation is steered through parameters that give minimum and maximum limits to the length of pieces and also specify a desired length.

After a good set of pieces has been heuristically determined, a "matching problem” is constructed. Each piece or a run is then considered a "node” in another network, and each node is connected to all other legal pieces. A legal connection is one which respects minimum/maximum break time, work time, spread time, etc. The cost of a connection is the cost of the run consisting of the two pieces, including all premiums and potential overtime.

Then an optimization process is used to "match” each piece to exactly one other piece so that the total minimum cost is achieved in addition to maximizing the number of matched pairs. This is done with the "non-bipartite min-cost Hungarian matching algorithm”. A global solution is achieved because this technique considers all the pair and cost combinations simultaneously. It is our experience that this method creates excellent runs within a few seconds, even for large data sets (greater than 300 runs).

An important feature of the runcutting solution is the "run analyzer” user interface. The run analyzer takes a run specified by the scheduler and determines its classification and cost. If the run is not legal, than it shows exactly which rule the run is violating. This ability also allows the scheduler to undo the offending run, or change the run definition rules and then get an instant reclassification and recosting of all the existing runs. This feature is a great help for running quick policy scenarios to measure the impact of proposed changes on the existing driver schedules without recutting all the runs.

Combination Techniques:

Of course, TMS can cut "straight” runs without meal breaks as well as split and multi-piece runs. The method used is a combination of heuristic and algorithmic techniques. It is well known that while an optimal solution contains mostly efficient duties, a few inefficient duties are needed to complete the puzzle that constitutes an optimal crew scheduling solution¹⁴. If the number of each run type is known beforehand, it is much easier to use a heuristic to cut the runs. In the previous example, all runs had to be 2-piece straights with meal breaks, and these were the only run types that were cut. Most properties allow a combination of run types including straights, splits, and trippers that can compose the runcut. Often union agreements specify that there must be a minimum percentage of runs of a certain type (usually straight runs).

For example, the HASTUS¹⁵ system uses a Linear Programming (LP) "relaxation” to determine the distribution of run types likely to be optimal. This relaxation starts by modeling the required work by "rounding” all the relief point times to the nearest 15, 30, or 60 minutes. It then constructs all the possible combinations of runs possible which correspond to the work in the "time buckets”, including potential overtime. An LP is then solved to determine the minimum cost number and type of each run required for this rounded times problem. The decision to use 15, 30 or 60-minute time buckets depends on the problem size. Sixty minute buckets must sometimes be used to make the LP problem small enough to be solved (with a great sacrifice to time accuracy). Once this profile is obtained, it is used to guide a heuristic that actually cuts the blocks, always following the ideal profile as closely as possible. Essentially, the heuristic tries to apply the "rounded” solution as best as possible to the "real” relief times, and its success depends on how well the ideal run types match the real data. After the heuristic is finished, there is a set of undesirable work that is handled by trippers.

It is our experience that solving an LP relaxation is not necessary to determine the optimal run type set. Most properties have a work profile that looks like a "two-humped camel”, where the two humps represent the morning and evening peak activity. The process for determining the run type profile is "cut AM and PM straight runs as much as possible to even out the peaks, cut straight runs from the middle of the day to leave two separated humps, cut as many two-piece runs from the humps, and do as best as you can with the rest”. TMS uses this technique in addition to user parameterization to arrive at an optimal runcut. Straight runs are cut using heuristics, two-piece runs are cut using the matching technique described earlier, and greater-than-two piece runs are combined last.

The advantage of this technique over the HASTUS approach is that the runs are always derived from real data, not from an approximate relaxation. Secondly, the long solve time and large memory requirement of the LP solver is avoided. The TMS technique allows a full runcut to be produced in a matter of minutes if desired. Thirdly, the experience of the scheduler is efficiently leveraged by allowing him/her to tune and control the progress of runcut interactively while it is occurring. This can dramatically save time during a negotiation situation where there is some latitude in the runcut rules that may be extremely difficult to determine ahead of time. Of course, the scheduler can always cut runs manually from a point-and-click user interface.

Finally, the TMS heuristics closely imitate the actions normally done by the scheduler, but much, much faster. They do not require advanced mathematical experience to understand or use. This allows schedulers to spend their time actually scheduling, not trying to figure out why the mathematical solver takes so long, has gone unfeasible, or will not converge.

An emerging technique for solving the runcutting problem called "column generation” has been implemented in at least one commercial product¹⁶. Column generation promises to solve runcutting to a provable global optimum without any intervention from the scheduler. However, this technique does not terminate for more than a modest numbers of runs, it requires a very large and expensive computer, and it can have solution times greater than 24 hours even for modest property sizes¹⁷. Although we will continue to follow this and every new technique in transit scheduling, we feel that the current column generation methods do not provide enough business value to justify their use.

Conclusion

TMS delivers sophisticated state-of-the-art solver functionality. It uses robust algorithmic solution methods where available, and provides a blend of heuristic and algorithmic techniques when necessary. Its data modeling and trip generation techniques ensure that the scheduler is always solving a realistic problem based on accurate data. Its point-and-click user interface always leaves the scheduler in control of all system parameters and costs. The expertise of the scheduler is always leveraged, as he/she can manually create blocks and runs at any time and then have the solvers work around those decisions. The impressive speed of the solvers allows multiple scenarios to be evaluated fast for time critical special event planning and during union negotiation. This total approach to functionality and usability has enabled TMS to keep delivering exceptional return on investment.

Footnotes

¹ Orloff, C.S. (1976): Route constraint fleet scheduling. in: Transportation Science 10, 149-168

² Mojsilovic, M. (1983): Verfrahren für die Bildung von Fahzeugumläufen, Dinstplänen und Dienstreihenfolgenplänen in Verkehr und Transport. in: HEUREKA ‘83 - Optimeirung in Transport und Verkehr, Karlsruhe, 178-191

³ Gavish, B. / Schweitzer, P. / Shilfer, E. (1978): Assigning buses to schedules in a metropolitan area. in: Computers and Operations Research 5, 129-138

⁴ Gavish, B. / Shilfer, E. (1978): An approach for solving a class of transportation scheduling problems. in: European Journal of Operational Research 3, 122-134

⁵ Carraresi, P. / Gallo, G. (1984): Network Models for Vehicle and Crew Scheduling. in: European Journal of Operational Research 16, 139-151

⁶ Luedtke, L.K. (1985): RUCUS II: A review of system capabilities. in: Rousseau J.-M. (ed.), 61-115

⁷ Paixão, J. / Branco, I. (1987): A quasi-assignment algorithm for bus scheduling. in: Networks 17, 249-269

⁸ Paixão, J. / Branco, I. (1988): Bus scheduling with a fixed number of vehicles. in: Daduna, J.R. / Wren, A. (1988), 28-40

⁹ Bertossi, A. / Carraresi, P. / Gallo, G. (1987): On some matching problems arising in vehicle scheduling. in: Networks 17, 271-281

¹⁰ TMS User Manual (1995)

¹¹ Hoffstadt, J. (1981): Computerised vehicle and driver scheduling for the Hamburger Hochbahn Aktiengsellschaft. 35-52

¹² Daduna, J.R. / Mojsilovic, M. (1988): Computer aided vehicle and duty scheduling using the HOT programme system. 133-146

¹³ Mojsilovic, M. (1983): Verfaren für de Bildung von Fahrzeugumläufen, Dienstplänen und Dienstreihenfolfen, in: Heureka '93. Optimierung in Verkehr und Transport. (Forschungsgesellschaft für Straßen-und Verkehrswesen) Köln, 174-191

¹⁴ Rousseau, J.M. / Desrosiers, J. (1993): Results obtained with Crew-Opt: a column generation method for transit crew scheduling. in: Computer-Aided Transit Scheduling Proceedings, Springer-Verlag, 1995

¹⁵ Wren, A. / Rousseau, J. M. (1993): Bus Driver Scheduling: An Overview. in: Computer-Aided Transit Scheduling Proceedings, Springer-Verlag, 178-179.

¹⁶ Rousseau, J.M. / Desrosiers, J. (1993): Results obtained with Crew-Opt: a column generation method for transit crew scheduling. in: Computer-Aided Transit Scheduling Proceedings, Springer-Verlag, 1995

¹⁷ IBID. p357