The SmartPref™ Optimization Approach

SmartPref™ works in your favor. It uses an optimistic greedy algorithm, it tries to satisfy a given request the best way it can without consideration to the final open time. It does require the line to be within the user defined limits (min/max) of utilization and choices will be reordered to achieve this. During the process and as the solutions are displayed, two conditions are often present; these are: ‘short’ lines (lines below minimum) and excessive open time on certain days. Optimization techniques are then used to redistribute the open time by forcing assignment on certain days and achieving the required utilization. Nevertheless the process is keenly aware of the fact that certain bidders are now being denied some of their most wanted choices and, as it incrementally works back up the seniority list, it ensures that seniority violations do not occur by evaluating all the possible choices within a specified time frame. SmartPref™ will examine hundreds of thousands alternatives in a matter of a few seconds and redisplay the current schedule.

Determining the best solution: Heuristic vs. LP

The goal of the Crewing Solutions’ SmartPref™ Preferential Bidding System is to develop crew rosters that satisfy individual crew preferences as well as global utilization constraints as much as possible. In order to model the rostering problem so that it may be solved with linear and integer optimization methods, we need to first define the choice set of scheduling objects from which the optimum solution may be extracted

Unfortunately, the choice sets of rosters are typically huge: potentially on the order of billions. In a recent test, we estimated for 1100 trips, there were well over 5 billion possible anonymous schedules from which to chose 275 full lines. And this is not a particularly large problem!

Column Generation arose in response to the problem of applying LP methods to huge numbers of variables. However, if one attempts to reduce the size of the choice set in some intelligent manner to some small and manageable subset, one runs the risk of throwing the baby out with the bathwater: unless that subset contains an optimal solution to the larger choice set, its solution will obviously be suboptimal. There is no straightforward way to decide the most efficient order to add scheduling objects to the choice set; obviously if the wrong ones are added, there will be little or no improvement to the solution, and this could occur over and over until the choice set is too big to solve with LP methods.

Since the order of generating columns and adding them to the choice set is heuristic in nature, it is worth exploring alternative heuristics which solve the rostering problem by operating upon smaller choice sets of simpler scheduling objects, i.e. trips. Crewing Solutions has developed such heuristics and has exploited other aspects of the preferential bidding process to create a PBS which is able to solve very large rostering problems in an extremely short period of time. We patented this process.