T U R N I
The Crew Scheduling Optimizer
Short User’s Manual
Software TURNI has been developed by Double-Click (Padova – Italy). It is an innovative tool capable of dealing with the complexity and specificity of the problems found in real-world crew scheduling.
The algorithm makes use of the most recent methodological developments in the field of Optimization and Operations Research, and improves substantially the performance of previous techniques used e.g. by some major airline companies. Strong points of the program are its flexibility, execution speed, and above all, its ability to generate optimized solutions for very large instances and under many constraints.
Program TURNI is commercialized in a base version that satisfies typical user’s requirements. Possible extensions and updates can be provided upon request. The Windows® version of the program requires a standard Personal Computer; other platforms can be supported upon request.
Typical execution times for problems with 2,000-3,000 trips are in the order of 10 minutes without dead-heading automatic generation, and of about 30 minutes/one hour enabling it. Recent experiments showed that TURNI is capable of dealing with instances involving more than 8,000 trips within 4-5 hours.
The heart of the program is constituted by a central "engine", TURNI.EXE, that defines the optimal crew schedules. This engine communicates with the outside through text files that contain input and output data, whose format can be easily adapted during the customization of the program. A graphical interface, TI.EXE, is also provided for the input and output with PC with Windows® operating system.
Program TURNI lets you:
THE WINDOWS GRAPHICAL INTERFACE
Program TI (Turni Interface) lets you create and/or edit all the input files used by software TURNI in a Windows® 9x/NT environment. Supported files are of type Trips, Groups, Controls, Parameters, Forcings, Lines and Relief Points, as described in the sequel. Program TI can also display and print the results of the elaboration either in textual form or in graphical form as Gantt charts or Line graphs, with different detail levels.
For a detailed description of input data required by the program TURNI, files structure and fields format, the reader is referred to the complete user's manual.
Installation and configuration
For the program TI to work correctly you only need to specify where the optimizer executable file can be found. You can do this by choosing Options® Optimizer path… from the main menu.
The default filename for the optimizer is TURNI.EXE and it is placed in the same directory where the interface has been installed (usually C:\Turni\Bin). Through the Options menu you should also specify which Relief Points file and (if necessary) Distances file are to be loaded.
After the installation, you can launch program TI from the Windows® "Start" menu (or by clicking the desktop shortcut, if any) and open a new OPTIMIZATION form for the simulation to be executed by choosing File® New® Optimization from the main menu (or clicking the leftmost icon on the toolbar just beneath the File menu).
To avoid any confusion, we suggest the following directory hierarchy for TURNI files:
Upon start-up, the interface TI shows the following window with information about the program version and the loading status.
After that, the main window is displayed together with the main menu and an optional toolbar at the top, and a status bar where possible warnings/errors are reported at the bottom. It is possible to open one or more documents at the same time, each in a separate and independent child window. The view through which the document is displayed depends on the type of the document. When a new document is created, the user must specify its type; in all other cases the type is inferred from the filename extension. Whenever a document is saved to disk, the filename extension for its type is automatically appended to its base name.
The supported types are listed in the following table:
The view of a document can be either a Table or a Form: a table shows data organized in a grid much like an Access or Excel grid; a form displays data through an input dialog that details a single item at a time.
All types (except for Optimization, Company Par. and Output log) correspond to the TURNI input/output files, whose format will be exhaustively explained in a later chapter.
The Optimization type is used to launch new optimizations. A document of this type specifies the working directory for the optimizer, which input files to load and where to store the results. From the Optimization dialog you can also launch the optimizer and open and browse both the comments and results created by the optimizer (Log and Solution files).
The Company Parameters and Output Log types are not natively supported by TI but can be opened and edited through external application (that are part of the Windows® standard installation) as specified in the previous table.
For the Form views, we tried to comply with the style of Windows® dialog windows, so in every form you will find:
The Table view is similar to Excel® tables and is made of a grid with:
You can move from cell to cell by using the cursor keys. If you move over a cell and start typing, the content of the cell is replaced by the entered text; if you wish to edit the content of the cell without overwriting it, you should press F2 before typing.
While you are editing a cell, the Esc key restores the previous content; the Enter key confirms the new value and terminates the editing; Up and Down keys terminate the editing and move to next/previous record.
In the same window that contains the grid you may find some buttons that let you insert new records in an intermediate position, delete the current record and perform other special functions such as looking up relief point codes, switch to Form view, etc..
The File menu contains the standard menu items to create, open, save and print documents; it also keeps the history of the last ten OPTIMIZATION and SOLUTION documents opened.
If you choose File® New, you will be presented a new sub-menu listing all document types that can be created. After you select the type, the new (empty) document is created and its default name will be "Unnamed" followed by a progressive number.
Save saves the changes applied to a document and updates the file from which it was initially loaded; Save as… also saves the changes but asks for the name of the destination file.
The item Print is enabled only for documents of type Solution and can produce printed documents with both text and graphics.
Exit closes all documents and quits the application.
This menu has four items:
This menu lets you arrange on the screen all opened windows.
Help (?) Menu
The first item, Manual, opens the user-dependent documentation file TI.RTF (if any) in a new window. The second item, About, reports Copyright and release information about program TI.EXE.
The toolbar contains three buttons that are a shortcut for the following commands (left to right): "File® New® Optimization", "File® Open", and "File® Save".
These buttons are only visible when the associated command is enabled.
The Optimization form is the starting point for every new optimization and lets you define all the required input and output files. The form is divided into three sections.
The first section corresponds to the Output and specifies the Path and Base name to be used by the optimizer for the output files that it generates (solutions and logs). The Base name is limited to at most six characters for compatibility reasons with MS-DOS® and Windows® 3.11 and to reserve some space for appending a progressive number to the name.
The button Create is enabled automatically when the path that has been typed does not exist and lets you create the corresponding directory and (possibly) copy some input files into it. The button MS-DOS opens an MS-DOS session in a separate window with the output path as the current directory. The button ZIP starts the compression program (better described later on) to archive all files related to the optimization. The button UTIL launches a batch file, UTIL.BAT, that the user can create/edit in the optimizer directory.
The second section corresponds to the Input and lets you specify the input files to be used by the optimizer. For each file type there is a button to select the file by browsing the directory tree ([…]), and a button to open the file ([Open]).
The files for Relief points and Distances are considered to be global so they can be set only from the Options menu.
For both the Output and the Input sections, an error message is reported in the status bar in case the typed name is invalid (non-existing file, wrong file type, etc.) .
The last section of the form contains three buttons: the Start Optimization button is enabled when all requested data are correct and it lets you launch the optimizer; the other two buttons, Open Log and Open Solution let you view the results generated.
As already mentioned, the ZIP button lets you create a compressed archive containing all the files listed in the form. Editing the configuration file TURNI.DEF it is also possible to include other files in the archive. When you click the ZIP button, the program launches a batch file named ZIPL.BAT from the optimizer directory (c:\Tuni\Bin) and passes as arguments the name for the compressed archive and the list of the files to be archived. The batch commands in the ZIPL.BAT depends on the underlying compression utility. The standard distribution of TI.EXE includes a ZIPL.BAT for the Zip.exe program by Info-Zip, therefore the compression MS-DOS command is:
ZIP –j %1 -@ < %2
The compression utilities released by Info-Zip (Zip, UnZip, etc.) are free and can be downloaded both in binary or source form the Internet site http://www.cdrom.com/pub/infozip; the format used by these utilities is compatible with other commercial tools such as PKZIP® and WinZip®.
Relief points documents
A Relief points document is opened whenever you choose a file with the .FER extension from the Open dialog
or create a new document for Relief points through the File® New menu.
This document type uses the standard table view.
The documents associated with Groups are organized in a form containing two sub-tables: the first one with a list of attributes for each group, and the second with the list of associated relief points.
A flag is associated with each relief point, indicating whether it has to be considered as a "depot" from which the duties of that group can be originated, or just as an "in-residence" location. The flag can be switched by double-clicking it, or by (un)checking the Depot check-button.
A Trips document is initially displayed as a table, but you can also request a single-record detailed form by clicking the Card button on the bottom.
The form view contains a sub-table with the fields, specific to some Company, possibly added; in the table view these fields correspond to a distinct column each.
The field "Constraints on groups" contains an optional sequence of flags (blank: badly assigned, V: forbidden, N: Not badly assigned, F: Forced) that specify if the trip can be assigned to each group. The format for these flags is a sequence of ranges of groups, comma separated and followed by the flag for the range (see the description of the trip file INPUT.COR for a detailed explanation of the flags).
For example, if a trip is "badly assigned" for groups 2, 3, 4 and 7 and forbidden for groups 10, 11 and 12, the field "Constraints on groups" should read "2-4, 7, 10-12V". This means that the trip would be badly assigned to groups from 2 to 4, badly assigned to group 7, and forbidden for groups from 10 to 12. Since in case of overlapping ranges the rightmost has the precedence, you can also type "2-7, 5-6N, 10-12V". Groups not covered by any range are considered of type N (Not badly assigned). If invalid data is entered, a short message with correct syntax is displayed on the status bar at the bottom of the window.
In both views, when one of the two fields Departure Point or Arrival Point is active, you can click the Seek relief pt. button for browsing the list of relief points: choosing one of these, both the code and the description fields for the relief point are updated.
Parameters and Controls documents
A Parameters document (the leftmost window in the following figure) contains a list of parameters with a description of their meaning and current value. To select a parameter and change its value, you can click on it or scroll up and down with the cursor keys.
A Controls document (the rightmost window) contains some flags (displayed as check-buttons) and some numerical values to control the execution and behavior of the optimizer.
When a Solution file is opened, it is initially viewed as a Text document reporting some global statistics about the solution.
From the View menu (displayed only when a solution document is active) you can select a graphical view or a text-format view of the solution file.
The Gantt chart shows the trips assigned to each group as solid bars whose color depends on the type of the trip and on the corresponding group. Moving the mouse pointer over a trip, the trip is highlighted and some information about the trip is displayed on the status bar (departure and arrival times/relief points, etc.). Moving the pointer over the label of a duty (or by right-clicking a trip) you will see information about the duty itself—working time, spread time, etc. The duties of each group can be sorted either in the roster-related optimal sequence determined by the program, or according to increasing starting times. All colors are defined in the configuration file TURNI.DEF and can be customized.
The chart can be enlarged or reduced by using the [+] e [-] buttons (or keys), and scrolled by using the scroll bars or cursor keys. The leftmost button enables or disables the display of additional information for each trip as in the figure below.
Before displaying a Line chart you need to define the sequence of relief points that will define the spatial (vertical) axis of the chart. To every such sequence so you can associate a Description and all the defined sequences are saved in a file (with the same name of the active Relief points file but with extension .LST).
The dialog window for the sequence definition contains two buttons ([+] e [-]) for adding/removing relief points to the current sequence, and two buttons ([ ] e [¯ ]) to move the relief points up or down within the sequence.
When a sequence has been defined and selected, the chart can be displayed. Every trip from/to the selected relief points is displayed as a line starting and ending at the corresponding times. Colors for the lines are cycled from a set of colors defined in TURNI.DEF. Clicking a trip, the trip itself and the corresponding duty are highlighted and information about the trip is shown on the status bar. The chart can be zoomed and scrolled in the same way as for the Gantt chart.
As already mentioned, all colors used in the charts are defined in the configuration file TURNI.DEF, stored in the same directory of TI.EXE, and can be modified by advanced users using a text editor (e.g. Notepad). It is recommended to make a backup copy of the original file before trying any changes.
The last item of the View menu, Source file, launches a Write (WordPad in Windows® 9x) session with the text solution file .SOL opened. Duty errors and violated constraints, if any, are labeled as "ERROR" and "VIOLATED CONSTRAINT", respectively, so they can be found easily by exploiting the Search/Find editor command. Single and double lines correspond to in-residence and out-of-residence breaks, respectively. Some duty statistics are printed after each duty, while overall statistics are given in the last part of the file.
For variant-duties, the .SOL text solution file reports, for each duty D, the name of duty of the reference solution which is most similar to D, chosen among the duties of the same group as D (it is possible for two duties to be considered variants of the same reference duty), along with the associated per-cent variation; for more explanations, see the section about variants of the parameter file INPUT.PAR.
Each of the views just described can be printed by choosing File® Print; note that printing from the Text view will print the whole text .SOL solution file and not just the summary shown on screen.
The print dialog lets you choose the destination printer (any Windows® printer) and page orientation (portrait or landscape). For the charts you can choose (i) how many hours to print per page; (ii) whether to print duties of different groups on the same page or in distinct pages; (iii) whether to print an additional page with duty statistics. For the text view you can choose either to chop long lines, or to wrap them in multiple lines.
The remaining document types (Lines and Forcing) use the standard table view without any particularities; the reader is referred to Section 5 (INPUT.LIN and INPUT.FOR) for a detailed description of the parameters.
Program TURNI can be launched directly from the command line, as an MS-DOS application, or through the graphical interface TI (described in the previous section) by clicking the Start Optimization button from the Optimization form.
To launch TURNI directly from the MS-DOS environment (or MS-DOS prompt window), type the following command:
from the working directory C:\Turni\Bin (where the program has been installed).
The TURNI algorithm executes a sequence of Passes, in each of which it tries to improve the best solution currently available according to the following scheme:
Typically the optimal solutions are determined during the very early passes but, in some hard cases, also later passes can find improved solutions.
During each pass, two elaboration phases alternate cyclically: the duties generation phase (during which a set of candidate duties is generated), and the selection phase (during which the duties defining the actual solution are chosen). If requested, during the duties generation some suitable dead-heading trips are also generated.
Both phases use special purpose optimization algorithms that are very efficient. The algorithms are based on specific mathematical models that make it possible to quantify very precisely the usefulness of new eligible duties, taking into account the characteristics of the current solution. Typically, millions of possible duties are implicitly evaluated during the generation phase, and tens of thousands of alternative solutions are considered and evaluated during the selection phase.
For every pass, the generation and selection phases are applied for a certain number of iterations, updating the best solution found. Thereafter a fixing procedure is activated to select some duties that appear to be particularly efficient and to fix them as belonging to the final solution. The overall process is then repeated on the trips not covered by the fixed duties: generation and selection phases are reiterated for a while, new duties are fixed, etc.
In this way, better and better solutions are typically found, up to a point where the current solution cannot be improved any further due to the performed fixings. In this situation the program ends the current pass, applies a refinement procedure to hopefully improve the best solution by means of trip exchanges among duties, and begins a new pass: the pass counter is incremented, some/all fixed duties are freed, and the program is reapplied on uncovered trips.
Elaboration continues until some stopping conditions (time limit, maximum number of passes etc.) are met.
The user can interrupt the execution of the program at any time (typing Ctrl-C or clicking the [X] button on the top-right corner of the MS-DOS window) if he/she finds the current solution satisfactory. Anyway, it is not advisable to stop the program before the end of Pass n. 1, i.e. before the displayed pass counter has reached value 2.
The above elaboration scheme has the advantage of finding quickly very good solutions for the problem at hand (already after the first fixings, the solutions are typically comparable to the best manual ones), while using the remaining processing time for improving them by exploring different fixing patterns.
At any time, the best solution found is stored in the output file TURNI.SOL, where TURNI represents the base solution name as specified by the user. The program also saves in the output files TURNI-nn.SOL the K best solutions found, where the number K of solutions to be saved is a user-defined parameter.
Moreover, the program saves in the output file TURNI-X.SOL the generated (possibly infeasible) solution that uses the minimum number of duties and, in case of ties, the one with minimum cost. The analysis of this solution, that typically violates some of the constraints of the problem, can be useful to get an indication of the most stringent constraints.
E.g., if K=3 and the base solution name is Prova, the program stores the 3 best solutions found in the output files Prova-1.sol, Prova-2.sol, and Prova-3.sol. Moreover, if the best solution uses (say) 59 duties, then the program will also save in files Prova-59.sol, Prova-60.sol, and Prova-61.sol the best solutions with 59, 60, and 61 duties, respectively. The best (possibly infeasible) solutions with less than 59 duties, if any, would be
saved in Prova-58.sol, Prova-57.sol etc. Finally, the (possibly infeasible) solution with a minimum number of duties is stored in Prova-X.sol.
In some customized versions of the program, the solutions are saved also in files TURNI.OUT and TURNI-nn.OUT with the customized format requested by the client.
The program TURNI can also evaluate the quality and feasibility of a manual solution provided on input. The program automatically evaluates the manual solution, showing possible errors (or duties that cannot be associated with any depot) in the file TURNI-E.SOL and printing the duties and the corresponding characteristics in the files TURNI-V.SOL and TURNI-M.SOL. The file TURNI-V.SOL reports exactly the manual duties provided, whereas within the file TURNI-M.SOL possible useless parts of the duties are removed, and the duty sequence in each group is redefined according to a preliminary weekly roster. After having evaluated the manual solution, the program saves internally the input duties that are feasible with respect to the specified parameters, and starts the optimization for improving the manual solution.
It is also possible to save in a file with extension .CRS each solution found by the program and saved to a corresponding .SOL file. Files with extension .CRS have the same format as the trip input files, but contain the trips in the sequence corresponding to the duties in the solution. In this way it is possible to begin a new elaboration that starts from the solution saved in any .CRS file, by just defining that file as the initial "manual solution" to analyze and improve.
The program generates automatically a very large number of duties (up to about 150,000, chosen among the most efficient ones) and of dead-headings (up to about 5,000). These duties/dead-headings can be saved into appropriate files and used, together with the best solutions found, as a starting point for later runs.
During the elaboration, an MS-DOS window displays a summary chart corresponding to the best solution found so far.
It is important to check that the MS-DOS window (the one with a black background shown in the previous figure) does NOT suspend the program execution when it is not run in foreground. To this end it is sufficient to check that the second rightmost button at the top of the window is depressed (as in the figure).
For safety’s sake, during the first installation it is advisable to click (with the mouse) the rightmost button of the MS-DOS window (the one marked with an A), choose the Misc tab and check that the Always suspend and Allow screen saver are NOT active, as in the figure below.
The summary chart reports also:
Possible violated constraints are marked with the label "<---- violated constraint". If appropriate, the chart also reports the cost and number of duties of the (typically infeasible) solution currently saved in file TURNI-X.SOL.
The output text file TURNI.LOG contains a short summary of the input data and of the main weights/parameters read, and reports possible errors or inconsistencies found while reading the input files. Errors and warnings are marked by "ERROR" and "WARNING", respectively, so they can be found easily within the file by using the Find/Search editor command. Moreover, file TURNI.LOG contains statistics on the run, including the time where the current best solution has been updated (Time), the corresponding pass (Pass), the number of fixed duties (Fix, R stands for refinement), the solution fitness (Fitness) and number of duties (Dut), the optimistic estimate of the final cost before any fixing (GlobalEstimate), and the percentage of the total time spent within the duty-generation module (T.GenD).
Finally, file TURNI-S.LOG contains an indication of the "degree of difficulty" of the constraints (average working time, requirement of covering the trips etc.), and can be of help in locating bottleneck constraints affecting the quality of the overall solution.
This section outlines the input data files required by program TURNI; see the complete user’s manual for detailed information.
Program TURNI communicates with the outside through ASCII text files, organized in rows (records) with fixed column widths. These file can be constructed/modified by using any text editor (e.g., Notepad or WordPad), or by means of the Windows® interface TI.EXE described in a previous section. In this latter case, decimal values must be specified by using dots as decimal separators (commas are not accepted by TI.EXE).
The input files required for the elaboration are described in the sequel. The reader is assumed to have some knowledge about the structure of a generic crew scheduling problem. Here is an outline of the main notation we use.
Notation ands basic oncepts
A relief point is a location where a driver-change can take place, typically a main station for railway applications or a line terminus for bus applications. It is up to the user to define which stations/termini along the transportation network define valid relief points for driver change.
A trip is an indivisible time-tabled increment of work to be covered by a driver, and is characterized by the starting and ending times and associated relief points. By definition, no driver change can take place in any middle point of a trip—for this to become possible it is required to split the original piece of work into two or more consecutive trips.
A duty is a sequence of trips to be performed consecutively by the same driver, which satisfies a number of feasibility requirements laid down by the union contract and company regulations. As a general rule, every duty has to start and end at the same relief point defining the home depot for the duty. Moreover, each trip in the sequence must end at the same relief point from which the next trip starts, and the interleaving time between arrival/departure must be wide enough to allow for a safe connection (pad time). Sometimes the duty contains time-tabled dead-heading trips needed to transfer the driver between two distinct arrival/departure relief points.
Each duty is split into 1 or more work phases (also called blocks). Each work phase starts and ends with the so-called PRE and POST times, representing flat-rate working times paid to the driver for the operations that precede/follow each driving block, respectively. Between any two consecutive work phases a break takes place, whose minimum duration (net of PRE/POST times) is specified by the union contract and company regulations; e.g., 31 minutes. Notice that the idle time between the first two trips (as well as the one between the last two trips) in the figure is too short to lead to a valid break.
The working time associated with a duty is computed as the sum of the duration of each work phase, plus possible flat-rate additional times. The spread time associated with a duty is the total driver availability, and is computes as the difference between the duty end and start time (including both PRE and POST times). Both working and spread times in a feasible duty must not exceed given bounds.
Duty feasibility also requires the presence of meal breaks within certain time windows, the possibility of performing suitable vehicle changes and vehicle clean-up operations, the interruption of continuous driving after some maximum amount of time, etc.
A crew scheduling solution is a set of feasible duties covering all the prescribed trips. In some cases it is allowed that a single trip is covered by two or more duties, a situation implying that one or more drivers actually act as passengers for the over-covered trip. Moreover, the automatic generation of time-tabled dead-heading trips may be allowed under some circumstances.
The feasibility of the crew scheduling solution as a whole requires that the average working and spread times, as well as some percentages of duties with "bad" characteristics (computed with respect to all the duties in the solution) meet pre-defined limits. Moreover, it has to be taken into account that the duties typically originate from different groups of depots, each of which has its own limits e.g. on the average working time and on the number of duties with a long spread time.
File INPUT.COR (Trips)
This file contains the trips to be covered, each of which is identified by the relief points and times of departure and arrival, and by additional information corresponding to particular constraints. Every row of the files corresponds to a trip.
File RELIEF.FER (Relief Points)
This file contains the codes and identifiers of the relief points where driver changes can take place. The file also lets you associate with each relief point a certain "reference" relief point.
File DISTANCES.INP (Distances)
This file contains the dead-heading distances between the relief points that are required in order to automatically generate dead-heading trips and technical transfers. Each row corresponds to the distance between two relief points.
The correct working of the program requires that the supplied distances are consistent and correspond to the shortest path between each pair of relief points. This condition is technically defined "distance triangularity" as it requires that, for each triplet A, B and C of relief points, the distance A-C is not greater than the sum of the distances A-B and B-C.
Program TURNI is accompanied by the DISTANZE.EXE utility, described in detail in the section about "UTILITY PROGRAMS", that automatically updates the distance file by computing the shortest distances between all the relief points so as to fulfill the triangularity property. Obviously, the distances that have been forced are not altered.
File INPUT.FOR (Forcing)
Each row of this (optional) file contains a forced connection between two trips.
File INPUT.CON (Controls)
This file contains values that control the desired type of execution. Each row begins with a numerical parameter, possibly followed by a comment (not elaborated). For parameters corresponding to yes/no conditions, value 1 represents a "yes" and value 0 a "no" answer. Blank lines are ignored. The file contains the following data.
Analyze and use input duties
This 0/1 parameter lets you analyze a manual solution and proceed with the elaboration in the attempt of improving it. As already mentioned, the manual solution is printed into the output files TURNI-M.SOL and TURNI-V.SOL, whereas possible duties that contain some errors or cannot be associated to any group are printed into file TURNI-E.SOL.
Generate dead-heading trips
This 0/1 parameter lets you enable/disable the automatic generation of dead-heading trips (technical trasfers within a same zone are always active, instead).
Warning: when the dead-heading trip generation is disabled, the program is prevented from shifting possible dead-heading trips provided in input in the attempt of minimizing idle times.
This 0/1 parameter lets you forbid/allow the covering of a trip by two or more drivers (all but one acting as a passenger).
In case passengers are not allowed but the dead-heading generation is enabled, every possible passenger transfer is considered a dead-heading to all extents. On the other hand, if passengers are allowed, every passenger transfer is penalized according to the parameter "Penalty for each passenger transfer" specified in section Weights of file INPUT.PAR.
Apply Pass n. 0 (suggested)
If set to 1 (recommended choice), the Pass n.0 is activated to find a good initial solution for the problem by using a more aggressive solution strategy.
Generate new duties,
Erase previous duties/d-heads/sol.s
As already mentioned, program TURNI cyclically alternates two elaboration phases: the duty generation one (where a set of candidate duties is generated) and the selection one (where some duties are selected to become part of the solution). If required, suitable dead-heading trips can also be generated.
The program internally handles a very large number of duties (about 150,000 chosen from the most efficient ones) and of dead-heading trips (up to about 5,000). If requested, all generated duties and dead-headings can be saved into files TURNI.TUR and TURNI.VUO, respectively, and the best current solutions to file TURNI.SLZ, where TURNI is the base solution name for the current run. This can be useful because one can start at a later time a new elaboration by reading these duty/dead-heading/solution files, thus hopefully reducing the overall computing time. Of course, all stored duties are re-evaluated and discarded if they do not satisfy the constraints for the current elaboration.
The three parameters under consideration let you, respectively:
Program TURNI has been designed for the situation where the duties and dead-heading trips are not either read or stored, but generated at every execution. Therefore we recommend the use of the following values for the three parameters:
Warning: disabling the generation of new duties (first parameter set to 0) can prevent the program from finding good solutions for the problem under consideration, so this option should be selected only when it is certain that the stored duties can yield a satisfactory solution.
Setting this parameter to 1, an audio hint (beep) is emitted whenever a new feasible solution, better than the last stored one, is found.
Pause on warnings
If set to 1 (recommended choice), the program stops and waits for pressing the <Enter> key whenever a warning message about input data ambiguities is displayed.
Store solutions in format .CRS also
Specifying value 1 for this parameter (recommended choice), every solution saved in a file with extension .SOL is also saved to another file with the same name but extension .CRS.
This file has the same format as the input trip files (e.g., INPUT.COR), but the trips appear according to the sequence associated with the duties in the solution so as they can be viewed as "manual solutions". To this end, in Field 111-117 giving the "manual duty identifier" each trip reports the name of the corresponding duty in the solution, whereas possible uncovered trips are associated to the fictitious duty name "TRIPPER". Possible passenger transfers are marked with an asterisk (‘*’) in field 87 (unused by the program), and their covering type is set to ‘P’ (covering allowed).
Files with extension .CRS files can therefore play the role of input trip files for a later elaboration (to avoid ambiguities it is suggested to rename this file with a .COR or .RIF extension). Thus it is possible to launch a new elaboration starting from the solution stored, for example, in TURNI.SOL: to do that, simply copy the solution file TURNI.CRS to file INPUT.COR, and activate the analysis of the "manual solution" therein stored (setting to 1 the first control parameter).
Skip input d-head.s of cover-type ‘P’
Setting this parameter to 1 (NOT recommended), all dead-heading trips with covering type ‘P’ (allowed) possibly found in the input trip file INPUT.COR are disabled so as to force the program to generate immediately new dead-heading trips. This mode slows down the execution but can lead to alternative solutions, hopefully requiring fewer dead-headings.
We suggest to set this parameter to 0 for the first runs, and possibly try to set it to 1 only in later runs when looking for alternative solutions.
Penalize errors in the reference solution
Before every elaboration, the program can read a reference solution (if specified) from a file, whose duties are stored internally. Each reference duty is automatically checked to see whether it covers some trips which are not part of the current elaboration, in which case the duty is skipped—two trips being considered the same if and only if their trip code is the same (it is therefore required that the trip codes of the current elaboration are the same as those used when generating the reference solution).
In case this parameter is set to 0, it is supposed that the non-skipped duties loaded from the reference have been verified by the user, hence they are allowed to contain errors (e.g.: too long spread or working time). When setting the parameter to 1, instead, any possible error is penalized so to favor the generation of feasible variants.
Maximum execution time,
Minimum n. of passes,
Maximum n. of passes
These three numerical parameters define the stop conditions for the execution of the program, on the basis of the execution time and/or number of passes.
For example, in case they are set to:
180 = Maximum execution time, in minutes
3 = Minimum n. of passes
20 = Maximum n. of passes
the execution will stop as soon as (at least) one of the following conditions is met:
The recommended choice is not to set any limit (setting every value to 999999) and to interrupt manually the execution by pressing the Ctrl-C key combination to abort the current run. In any case, it is inadvisable to set the Minimum n. of passes to values smaller than 3.
Number of solution to store
This parameter defines the number k of solutions to be saved to files TURNI-*.SOL. This value must be within the range 1 to 99. In order to avoid excessive slowdowns due to the large number of file I/O operations, we suggest to choose for k less or equal to 3 problems with 2,000 trips or more.
File INPUT.PAR (Parameters)
This file contains the parameters that define the regulation and company constraint, and a set of weights that lets the program define a cost for each duty and then for the overall solution.
Each row (free format, blank rows skipped) defines a different parameter possibly followed by a comment.
WORKING AND SPREAD TIMES
Maximum average working time (default)
Maximum working time (default)
Maximum working time for a non-long duty
Start of the optimal working-time window
End of the optimal working-time window
Maximum spread time (default)
Maximum spread time for a non-long duty (default)
Maximum average spread-time (global)
Max. n. of duties (or exact required number, if negative)
Starting time of spread-time window n. 1
Starting time of spread-time window n. 2
Starting time of spread-time window n. 3
Starting time of spread-time window n. 4
Starting time of spread-time window n. 5
Starting time of spread-time window n. 6
Starting time of spread-time window n. 7
Starting time of spread-time window n. 8
Starting time of spread-time window n. 9
Starting time of spread-time window n. 10
Maximum percentage of duties with long spread time
Maximum percentage of duties with long spread t. in every group
Maximum percentage of duties with several breaks
Maximum percentage of duties with meal bonus
Maximum percentage of duties with long working time
Maximum percentage of bad duties
Maximum percentage of duties without vehicle clean up
Maximum percentage of missing pads
CONNECTION TIMES, PADS AND BREAKS
Minimum connection time for normal-type trips (in min.s)
Minimum connection time for d-heading trips (in min.s)
Minimum connection time for dummy-type trips (in min.s)
Maximum number of missing pads in a duty
Maximum number of breaks in a duty
Number of duty breaks considered inconveniently large
Limit beyond which the idle time yields a duty break (in min.s)
MINIMUM WORKING TIMES AND PART-TIME DUTIES
Minimum working time for a full-time duty
Minimum working time paid to a full-time duty
Minimum working time for a part-time duty
Maximum number of part-time duties
OUT-OF-RESIDENCE BREAKS AND BAD DUTIES
Maximum out-of-residence idle time
Maximum idle time for a non-long out-of-residence break
Maximum out-of-residence idle time with reduced rate
Percentage paid for out-of-residence idle time
Percentage paid for in-residence idle time
Minimum number of breaks in a bad duty
Minimum average spread-time in a bad duty
CONSTRAINTS PERTAINING THE VARIOUS WORK PHASES
Minimum starting time for a duty
Minimum working time for a work phase
Minimum working time for the first work phase
Minimum working time for a first phase starting before 6:00 a.m.
VEHICLE CHANGES AND BADLY-ASSIGNED TRIPS
Maximum number of badly-assigned trips in a duty
Maximum number of changes of vehicle type in a duty
Minimum vehicle change time (in minutes)
Maximum duration implicit vehicle-change dead-heading (=-1 no zone)
PRE / POST TIMES AND ADDITIONAL TIMES
Standard PRE time (in min.s)
Standard POST time (in min.s)
Extra PRE time at the beginning of the duty (in min.s)
Extra POST time at the end of the duty (in min.s)
Extra flat-rate working time (in min.s)
Extra flat-rate working time for break n. 1 (in min.s)
Extra flat-rate working time for break n. 2 (in min.s)
Extra flat-rate working time for break n. 3 (in min.s)
Extra flat-rate working time for break n. 4 (in min.s)
Extra flat-rate working time for break n. 5 and next (min.s)
Extra working time paid for 0-time connections (in min.s)
Art. 21 amplifying factor for reduced bonus application (=0 no)
Starting time for lunch-break window
Ending time for lunch-break window
Starting time for dinner-break window
Ending time for dinner-break window
Meal duration for bonus application (in min.s)
Minimum meal duration as a constraint (in min.s)
Minimum working time for rostering
Maximum working time for rostering
Minimum rest time for rostering
Starting time for vehicle clean-up window
Ending time for vehicle clean-up window
Minimum vehicle clean-up duration (in min.s)
Extra flat-rate working time for missing clean-up (in min.s)
CONTINUOUS DRIVING TIMES AND MISCELLANY
Maximum continuous driving time
1-stop length sufficient to break driving (in min.s)
2-stop length sufficient to break driving (in min.s)
3-stop length sufficient to break driving (in min.s)
PRE/POST times contribute to driving time (=1 yes, =0 no)
Dead-heading vehicle speed (Km/h)
Relief points within a same zone are coincident (=1 yes, =0 no)
Percentage threshold for too-large a variation
Starting time for the overnight-work window
Ending time for the overnight-work window
WEIGHTS (DEFINE THE OVERALL SOLUTION COST)
Cost of a full-time duty
Cost of a part-time duty
Cost of a minute of work
Cost of a minute of dead-heading
Extra-cost for a long-spread minute
Cost of a meal bonus
Extra-cost for each uncovered Suggested trip
Extra-cost for each covered Inadvisable trip
Extra-cost for each duty with no vehicle clean-up
Extra-cost for each additional vehicle
Extra-cost for each long-work minute
Extra-cost for each work minute below minimum paid work time
Extra-cost for each visit of a different oper. unit
Extra-cost for each vehicle-type change
Fixed cost for each duty covering a vehicle-type A trip
Extra-cost for each missing pad in a duty
Extra-cost for each bad duty
Extra-cost for working time difference w.r.t. optimal window
Extra-cost for each minute in an out-of-residence break
Penalty for each passenger transfer
Penalty factor F1 for missing rostering rest (integer 0-1000)
Penalty factor F2 for rostering aver.work. time (integer 0-1000
Fixed extra-cost for spread-time window n. 1
Fixed extra-cost for spread-time window n. 2
Fixed extra-cost for spread-time window n. 3
Fixed extra-cost for spread-time window n. 4
Fixed extra-cost for spread-time window n. 5
Fixed extra-cost for spread-time window n. 6
Fixed extra-cost for spread-time window n. 7
Fixed extra-cost for spread-time window n. 8
Fixed extra-cost for spread-time window n. 9
Fixed extra-cost for spread-time window n. 10
Fixed extra-cost for duties with 0 breaks
Fixed extra-cost for duties with 1 break
Fixed extra-cost for duties with 2 breaks
Fixed extra-cost for duties with 3 breaks
Fixed extra-cost for duties with 4 breaks
Fixed extra-cost for duties with 5 breaks
Fixed extra-cost for duties with 6 breaks
Fixed extra-cost for duties with 7 breaks
Fixed extra-cost for duties with 8 breaks
Fixed extra-cost for duties with 9 or more breaks
Extra-cost for each overnight working minute
Extra-cost for each number-plate change in a duty
Extra-cost for each badly assigned trip in a duty
Penalty for each over-covered piece
Extra-cost for each variant duty w.r.t. reference solution
Extra-cost for percentage changes in a duty w.r.t. refer. sol.
Extra-cost for a too-large-variation duty w.r.t. reference sol.
COMPANY COSTS (FOR STATISTICS ON THE COMPANY COST)
Company cost for each full-time duty
Company cost for each part-time duty
Company cost for each minute of work
Company cost for each minute of long-work
Company cost for each minute of dead-heading
The meaning and valid values of the parameters are described in the full user’s manual.
Program TURNI is distributed together with the following utilities.
This is an MS-DOS executable that calculates the minimum distance between every pair of relief points, on the basis of the network-link distances and possibly of a trip file containing some "sample" connections.
To launch the program, type the following command in an MS-DOS window:
The input files have fixed names: the user shall copy input data to the required files FERMATE.INP (relief points), DISTANZE.INP (distances) and CORSE.INP (trips); this strategy avoids that important data get accidentally overwritten. The output file DISTANZE.MIN (containing the minimum distances) is overwritten at every execution.
The program starts by asking for the dead-heading vehicle speed (e.g., 60.0 Km/hr) and for the maximum limit beyond which distances should be considered too large and hence are not to be reported in the output (e.g., 999 minutes).
The program then reads the relief-point file FERMATE.INP (if present). This optional file is only used to set to zero all distances between the relief points belonging to a same zone, hence it must NOT be created (or must be deleted) whenever the distances between relief points within the same zone have to be defined by the program as for all other distances.
The (optional) distance file DISTANZE.INP file is then loaded, which contains the distances associated with the main direct links of the transportation network.
Finally, the (optional) trip file CORSE.INP is loaded, which contains some trips whose duration is used to infer the distance between some relief-point pairs.
At this point, the program has read a number of "basic" distances between some relief-point pairs; in case any such distance has been defined more than once, the one leading to the minimum travel time is preferred (for forced distances, instead, the last occurrence has the precedence).
Computation of the shortest path distances is then performed between each pair of relief points, and the resulting distances and travel time are saved to the output file DISTANZE.MIN. Distances/travel times that are marked as forced (Field 11 set to ‘F’ or ‘f’) are not changed. Afterwards, the user can provide pairs of relief points A and B and ask the code to print (on the screen and a echo text file, CAMMINI.TXT) the sequence of relief points visited by the shortest path between A and B.
Some log information about the input data and possibly missing distances is finally reported in the DISTANZE.LOG file. Moreover, an auxiliary ASCII output file DISTANZE.TXT is constructed, which contains the "basic network distances" extracted from DISTANZE.MIN—those from which all other distances can be re-constructed by re-applying the short path computation.
This program updates an old parameter file to the format of the current TURNI version. To launch the application, type the following command from an MS-DOS window:
During the execution, the program asks for the pathname of the file to be updated, e.g. C:\Turni\Data\EXAMPLE.PAR. If no errors are detected, EXAMPLE.PAR is saved as EXAMPLE.PA~ and a new EXAMPLE.PAR is created with the correct format (i.e. with the new parameters inserted in the correct positions). After that, the user can open the updated file by using a text editor or the graphical interface TI.EXE, and possibly change the default values set for the new parameters.
If no parameter file is specified (i.e., the <Enter> key is pressed immediately), the program looks for the TURNI.CFG file in the working directory, and reads automatically the name of the parameter file therein specified. This is useful in case AGGPAR.EXE is copied to the TURNI-executable directory, C:\Turni\Bin, and the user-defined batch file C:\Turni\Bin\UTIL.BAT is edited to contain the single line:
In this way, an automatic parameter-file updating can be obtained by simply pressing the UTIL button in the Optimization mask of the graphical interface TI.EXE : program AGGPAR is launched from UTIL.BAT, the user simply presses the <Enter> key, and the parameter file specified in the current mask is updated.
For more information, please contact us at
Optimization Software and Consultancy
Via PARUTA 8 - 35126 PADOVA - ITALY