Nel seguito verranno descritti i file di input/output necessari per definire il problema da risolvere, la cui comprensione approfondita richiede che il lettore conosca le problematiche di base della formazione turni e la relativa terminologia (tempo di nastro, lavoro, ecc.). I principali termini utilizzati sono i seguenti.

Per fermata (o punto di cambio) si intende una località in cui può avvenire il cambio di autista, tipicamente un capolinea per le applicazioni nel trasporto su gomma o una stazione per le applicazioni ferroviarie. È compito dell’utente definire quali sono le località che permettono il cambio di autista, scegliendole in base alla realtà ed alla consuetudine aziendale.

Per corsa si intende un segmento lavorativo indivisibile da coprire con un autista, ed è caratterizzato da un istante ed una fermata di partenza e di arrivo. Per definizione il cambio di autista non può dunque avvenire in un punto intermedio di una corsa, ma solo (eventualmente) prima del suo inizio o dopo la sua fine. Nel caso in cui si ritenga utile prevedere la possibilità di cambi "in corsa" sarà necessario spezzare il segmento lavorativo in due o più corse consecutive.

Per turno (di servizio) si intende una sequenza di corse coperte una dopo l’altra da uno stesso autista. Il turno deve soddisfare numerosi vincoli normativi e aziendali. Come regola generale, un turno deve iniziare e terminare in una stessa fermata detta convenzionalmente deposito (che a volte, ma non sempre, coincide con il "deposito aziendale", inteso come luogo di ricovero degli autobus). Inoltre, ogni corsa deve terminare nella stessa fermata da cui parte la corsa successiva nel turno, ed il tempo che intercorre fra l’arrivo e la partenza deve essere sufficiente a permettere una connessione affidabile (tempo di cuscinetto). In alcuni casi il turno dovrà dunque contenere opportune corse a vuoto (o trasferimenti come passeggero) necessarie per il trasferimento dell’autista fra due fermate.

Ogni fase di lavoro inizia e termina con i cosiddetti tempi di PRE e di POST, che rappresentano tempi di lavoro riconosciuti all’autista in modo forfetario per le operazioni che precedono/seguono la guida. Due fasi di lavoro consecutive sono separate da una sosta, la cui durata minima (al netto dei tempi di PRE/POST) è specificata dalla normativa nazionale e/o aziendale (tipicamente, 31 minuti). Si noti che il tempo di attesa fra le prime due corse in figura (e quello fra le ultime due corse) non è sufficiente a produrre una sosta e quindi viene riconosciuto all’autista come tempo di lavoro.

Il tempo di lavoro associato ad un turno viene calcolato sommando la durata delle singole fasi di lavoro, più eventuali tempi forfetari aggiuntivi. Il tempo di nastro associato ad un turno rappresenta invece il tempo di disponibilità dell’autista dall’inizio alla fine del servizio. Sia il tempo di lavoro che di nastro sono soggetti a limiti massimi stabiliti dalla normativa nazionale/locale e dalle consuetudini aziendali.

L’ammissibilità di un turno prevede inoltre la presenza di opportune soste per consumare il pasto, la possibilità di effettuare eventuali cambi di autobus, l’interruzione dell’attività di guida continuativa dopo certi limiti, ecc.

Per soluzione si intende un insieme di turni ammissibili che copra le corse assegnate. In alcuni casi è permesso che una singola corsa venga coperta da due o più turni, nel qual caso gli autisti eccedenti si intendono trasportati come passeggeri. Inoltre, può essere consentito che i turni in soluzione contengano corse a vuoto generate automaticamente in base alle distanze specificate fra le fermate.

L’ammissibilità della soluzione complessiva richiede che vengano rispettati opportuni limiti massimi per le medie dei tempi di lavoro e di nastro, per la percentuale di turni con nastri di lavoro particolarmente lunghi o comunque disagiati, ecc. Inoltre si dovrà tener conto del fatto che ciascun turno afferisce ad un certo gruppo di residenza per gli autisti, per ciascuno dei quali vengono specificati limiti specifici per quanto riguarda il numero di turni del gruppo, la massima media del tempo di lavoro nel gruppo, ecc.

Il programma TI (Turni Interface) permette di creare e/o modificare in ambiente Windows 95/98 ed NT tutti i file di input richiesti dal software TURNI. In particolare sono gestiti i file relativi a: Corse, Gruppi, Controlli, Parametri, Forzature, Linee e Fermate, descritti più dettagliatamente nel seguito.

L’interfaccia TI è inoltre in grado di visualizzare e stampare i risultati delle ottimizzazioni sia in modo testo che in forma grafica mediante diagrammi temporali "di Gantt" e mediante diagrammi spazio-temporali "per linea", con vari livelli di dettaglio.

L’unica operazione di configurazione necessaria per il corretto funzionamento del programma TI consiste nell’indicare la posizione del file eseguibile dell’ottimizzatore attraverso il menu "Opzioni® Percorso dell’ottimizzatore…".

Questo file solitamente si chiama TURNI.EXE e si trova nella stessa directory in cui viene installata l’interfaccia, tipicamente C:\Turni\Bin. Mediante lo stesso menù di Opzioni è inoltre necessario impostare il nome del file delle FERMATE e del file che contiene le DISTANZE A VUOTO (se richiesto).

 Dopo l’installazione sarà necessario creare la maschera di OTTIMIZZAZIONE relativa alla nuova simulazione che si vuole effettuare, utilizzando il menù "File® Nuovo® Ottimizzazione" (oppure il primo pulsante in alto a sinistra, subito sotto il menù "File").

Al fine di evitare confusioni fra i dati, si consiglia di utilizzare la seguente organizzazione in directory dei dati di input/output:

• c:\Turni\Bin: contiene tutti gli eseguibili, i file di configurazione ed le utility distribuite;
• c:\Turni\Globali: contiene tutti i dati globali (file fermate e distanze)
• c:\Turni\NOME1: contiene i dati di input /output relativi alla simulazione con nome-base NOME1
• c:\Turni\NOME2, c:\Turni\NOME3, ….: contengono i dati relativi alle simulazioni NOME2, NOME3 ecc.

Durante il caricamento, l’interfaccia TI visualizza una finestra con informazioni sulla versione del programma e sullo stato del caricamento stesso.

Viene quindi presentata una finestra principale che comprende un menu, una barra di pulsanti (parte alta) e una riga di stato per eventuali avvisi e/o errori (parte bassa). È possibile aprire uno o più documenti, anche contemporaneamente, ciascuno in una finestra separata ed indipendente. L’aspetto (vista) con cui viene presentato un documento dipende dal suo tipo. Nel caso di nuovi documenti, il tipo viene specificato dall’utente, altrimenti viene dedotto dall’estensione del file corrispondente. Quando si salva un documento, al nome base per il file digitato dall’utente viene aggiunta automaticamente l’estensione corrispondente.

I tipi supportati sono elencati nella tabella seguente:

La vista di un documento può essere di tipo Tabella o Maschera: nel primo caso i dati sono organizzati in una tabella molto simile a quella di Access e/o Excel di Microsoft; nel secondo caso i dati sono organizzati in una tabella i cui campi sono modificabili dall’utente.

Tutti i tipi (eccezion fatta per i tipi Ottimizzazione, Parametri Aziendali e Output log) derivano direttamente dai file di input richiesti dal software TURNI, il cui significato verrà descritto in modo dettagliato nel seguito.

Il tipo Ottimizzazione permette di gestire l’avvio di una nuova ottimizzazione. Un documento di questo tipo specifica la directory di lavoro per l’ottimizzatore, da quali file caricare i dati di input e il nome da usare per i file con risultati. Dalla maschera di Ottimizzazione è inoltre possibile avviare l’ottimizzatore e richiedere l’apertura e visualizzazione sia dei file di commento sia dei risultati generati dall’ottimizzatore (Log e Soluzione).

I tipi Parametri Aziendali e Output Log non sono direttamente supportati da TI ma vengono aperti ed editati attraverso programmi di editing esterni forniti con Windows, come indicato nella precedente tabella.

Per le viste di tipo Maschera si è cercato di rispettare lo stile delle finestre di dialogo di Windows e quindi per tutte le maschere si avrà:

• Barra di titolo con pulsante di chiusura in alto (ed eventuali pulsanti di ingrandimento/riduzione).
• Passaggio al campo successivo/precedente con tasti Tab e Shift-Tab (di norma è consentito anche Enter/Invio per il passaggio al campo successivo).
• Pulsanti per spostarsi al record precedente/successivo e per inserire/cancellare record (limitatamente alle maschere relative a file con più record).
• Nella maschera di Parametri, è possibile spostarsi al parametro precedente o successivo anche con i tasti cursore Su/Giù.
• Nella barra di stato che compare nella parte bassa della maschera viene indicato il numero di record corrente (se appropriato) ed eventuali suggerimenti sul formato da usare per i dati introdotti.

La vista di tipo Tabella ricalca la struttura delle tabelle in Excel ed è costituita da una griglia con:

• Nomi dei campi (prima riga).
• Dati presentati con una riga per record.
• Eventuali barre di scorrimento a destra e sotto la griglia.
• Eventuali selettori di record a sinistra (per selezionare un record, fare click sul relativo selettore con il tasto sinistro del mouse; per aggiungere record alla selezione, tenere premuto il tasto Ctrl finché si effettua il click con il mouse; per cancellare i record selezionati premere Canc).
• Ultima riga vuota (eventualmente contrassegnata con un asterisco) utilizzata per aggiungere nuovi record.

I tasti cursore permettono di spostarsi da una cella all’altra. Se ci si porta su di una cella e si inizia a scrivere, il contenuto della cella sarà sostituito da ciò che viene digitato; se si vuole modificare il contenuto senza sovrascriverlo, è necessario digitare preventivamente F2.

Durante la modifica di una cella, il tasto Esc riporta il contenuto della cella al valore che aveva prima della modifica del record, il tasto Enter/Invio conferma il nuovo valore e termina l’editazione, i tasti Su e Giù terminano la modifica del record e spostano al record precedente/successivo.

Nella stessa finestra della tabella possono essere presenti alcuni pulsanti che permettono di inserire record in posizioni diverse dall’ultima riga, cancellare il record corrente e altre funzioni aggiuntive (ricerca codici fermate, visualizzazione a maschera, ecc.).

Il menu File comprende i comandi classici per creare, aprire, salvare e stampare i documenti, e memorizza una lista degli ultimi 10 documenti significativi aperti.

 La voce Nuovo presenta una lista con i vari tipi di documenti e permette di creare un nuovo documento, inizialmente vuoto.

Salva memorizza le modifiche apportate ad un documento aggiornando il file da cui era stato inizialmente caricato; Salva con nome… permette invece di specificare il file di destinazione prima di procedere.

La voce Stampa è abilitata solo per i documenti di tipo Soluzione e permette stampe sia di testo (dalla Vista "Testo") che di grafici.

Esci chiude tutti i documenti aperti e termina l’applicazione.

Comprende 4 voci:

• Barra degli strumenti: abilita o disabilita la barra degli strumenti (che si trova in fondo al menu).
• File fermate…: permette di selezionare il file delle fermate da utilizzare.
• File distanze…: permette di selezione il file distanze da utilizzare o disabilitare l’uso del file distanze (se non si immette nessun nome).
• Percorso dell’ottimizzatore…: specifica l’eseguibile da lanciare (tipicamente TURNI.PIF o TURNI.EXE) quando si avvia un’ottimizzazione, e costituisce un’informazione indispensabile affinché TI possa funzionare correttamente; si suggerisce di controllare che il pulsante della finestra MS-DOS relativo all’opzione "In background, sospendi sempre" (il secondo da destra) appaia "premuto" come in figura, in modo da consentire l’esecuzione in backgroud del programma TURNI.EXE.

Permette di disporre automaticamente tutte le finestre aperte o di attivare e portare in primo piano una finestra in particolare.

La voce Manuale richiama il file di documentazione TI.RTF. La voce Informazioni su Turni riporta invece informazioni sul Copyright e sulla versione di TI in uso.

La barra degli strumenti comprende tre pulsanti che costituiscono una scorciatoia per i seguenti comandi (da sinistra verso destra): "File® Nuovo® Ottimizzazione", "File® Apri" e "File® Salva".

I pulsanti sono visualizzati solo quando i rispettivi comandi sono abilitati.

La maschera di Ottimizzazione rappresenta il punto di partenza di ogni nuova ottimizzazione, e permette di definire i file di input e di output necessari. La maschera è divisa in 3 sezioni.

La prima sezione riguarda l’Output e specifica il Percorso e il Nome base utilizzati dall’ottimizzatore per i file generati (soluzioni e log). Il Nome base è limitato ad una lunghezza massima di 6 caratteri per compatibilità con DOS e Windows3.11 e per consentire l’aggiunta di un numero progressivo al nome.

Il pulsante Crea si attiva automaticamente se il percorso introdotto non esiste e permette di creare la directory corrispondente, copiandovi eventualmente i file di input specificati. Il pulsante MS-DOS apre una finestra MS-DOS nel direttorio di output specificato. Il pulsante ZIP lancia un’utility di compressione descritta più in dettaglio nel seguito) per l’archiviazione dei dati di input specificati nella maschera. Il pulsante UTIL lancia un file batch UTIL.BAT (eventualmente definito dall’utente) presente nella directory dell’ottimizzatore.

La seconda sezione è relativa all’Input, e permette di associare un file (esistente) a ciascuno degli input richiesti dall’ottimizzatore. Per ogni tipo di file è presente un pulsante per la selezione del file ([…] ) e un pulsante per aprire il file selezionato ([Apri]).

I file delle Fermate e delle Distanze sono considerati di tipo globale e possono essere impostati esclusivamente dal menu Opzioni.

Sia per la sezione di Output che per quella di Input, i dati inseriti vengono visualizzati con sfondo dello stesso colore della maschera quando contengono dati non validi (file non presente, file di tipo errato, ecc.) e, in questo caso, nella riga di stato viene visualizzata una descrizione dell’errore.

L’ultima parte della maschera comprende tre pulsanti di comando: quando tutti i dati necessari sono corretti si attiva il pulsante Avvia Ottimizzazione che lancia l’elaborazione; gli altri due pulsanti, Apri Log e Apri Soluzione, permettono di visualizzare i risultati ottenuti.

Come già accennato, nella maschera di ottimizzazione è presente un pulsante ZIP per creare un archivio compresso contenente tutti i file specificati nella maschera. Agendo sul file di configurazione TURNI.DEF è inoltre possibile includere altri file nell’archivio, ed in particolare i file delle distanze, delle fermate e delle soluzioni. Premendo il pulsante ZIP viene mandato in esecuzione un file batch MS-DOS, ZIPL.BAT, presente nella directory che contiene l’ottimizzatore, passandogli come parametri il nome del file compresso e la lista dei file da archiviare

Selezionando un file con estensione .FER dal menù Apri

(oppure creando un nuovo file di Fermate) si attiva la maschera di modifica del file delle Fermate.

I documenti relativi ai Gruppi sono visualizzati con una maschera che comprende due sotto-tabelle: la prima contiene una lista di attributi per ogni gruppo; la seconda riporta l’elenco delle fermate afferenti al gruppo.

Ad ogni fermata afferente ad un gruppo viene associato un flag che indica se la fermata è un Deposito (fermata dal quale possono partire/arrivare i turni del gruppo) oppure se essa deve essere solo considerata "in residenza" per il gruppo. Il valore del flag può essere invertito indifferentemente facendo un doppio click sulla fermata, oppure selezionando con il mouse la casella Deposito.

Un documento di tipo Corse viene normalmente visualizzato in forma di tabella; è comunque possibile richiamare una vista di tipo maschera (dettaglio su un singolo record) premendo il pulsante Scheda.

La vista a maschera comprende anche una sotto-tabella che contiene eventuali campi aggiuntivi specifici per ciascuna Azienda: nella vista a tabella tali campi sono associati ad altrettante colonne.  

Per quanto riguarda il campo "Vincoli sui gruppi / Gruppi male assegnati" presente alla fine di ciascuna corsa, la lista dei flag V (Vietato), N (Non male assegnato), ed F (Forzato) deve essere descritta specificando una sequenza di intervalli di gruppi separati da virgole, ciascuno dei quali specifica un insieme di gruppi ed il flag corrispondente (si vede la descrizione del file INPUT.COR per il significato dei flag).

Per esempio, volendo specificare che una corsa risulta "male assegnata" per i gruppi 2, 3, 4 e 7 e non assegnabile ai gruppi 10,11 e 12 sarà sufficiente specificare "2-4, 7, 10-12V" ", interpretato come "la corsa risulta male assegnata per i gruppi 2-4 e per il gruppo 7, e risulta vietata per i gruppi 10-12". Alternativamente, è possibile specificare "2-7, 5-6N, 10-12V" intendendo "la corsa risulta male assegnata per i gruppi 2-7 ma non per i gruppi 5 e 6, e risulta vietata per i gruppi 10-12". I gruppi che non vengono specificati si intendono di tipo N (Non male assegnati). In caso di dati errati, sull’ultima riga della schermata compare un breve messaggio che specifica i valori leciti per i flag (V,F, bianco ed N).

In entrambe le viste, posizionandosi su uno dei due campi Codice Fermata Partenza o Codice Fermata Arrivo, si attiva il pulsante Cerca Fermata che richiama una lista di fermate: selezionandone una viene aggiornato automaticamente sia il campo codice da cui si è richiamata la lista, sia la relativa descrizione. 

Un documento Parametri (a sinistra nella figura) comprende una sequenza di parametri con la relativa descrizione. Per selezionare un parametro da modificare si possono utilizzare i tasti cursore Su/Giù o Enter/Invio oppure fare click con il mouse direttamente sulla lista.

Si noti che i valori decimali devono essere inseriti utilizzando il punto (e non la virgola) decimale, scrivendo p.e. 10.1 invece di 10,1.

Un documento Controlli (a destra nella figura) prevede un insieme di indicatori (flag) da attivare/disattivare, ed alcuni valori numerici che determinano le condizioni di esecuzione del programma.

Aprendo un file Soluzione viene inizialmente visualizzata una finestra di Testo che mostra le statistiche globali della soluzione elaborata ed eventuali note/messaggi di errore relativi a singoli turni.

Utilizzando il menu Vista (che appare solo quando è attivo un documento Soluzione) si può passare alla vista grafica oppure alla visualizzazione completa, in forma di testo, delle informazioni sulla soluzione.

Il Grafico di Gantt rappresenta le corse assegnate a ciascun gruppo con barre colorate in base al tipo della corse, alternando (se richiesto) colori diversi per gruppi di turni diversi. Posizionando il puntatore del mouse su di una corsa, questa viene evidenziata e nella barra di stato nella parte bassa dello schermo vengono visualizzate alcune informazioni sulla corsa (orari e fermate di partenza e di arrivo, ecc.). Posizionando il puntatore sull’etichetta di un turno (o tenendo premuto il pulsante sinistro del mouse su di una corsa) vengono invece visualizzate alcune informazioni sul turno (tempo di lavoro, nastro, ecc.). È possibile visualizzare i turni di ciascun gruppo secondo la sequenza ottimale legata alla rotazione settimanale preliminare determinata automaticamente dal programma, oppure per istanti di inizio crescenti. È inoltre possibile ridefinire il colore delle corse in base al tipo, agendo sul file di configurazione TURNI.DEF.

È possibile ingrandire o ridurre il grafico mediane i pulsanti [+] e [-] nell’angolo in alto a sinistra, nonché spostare la visualizzazione mediante le barre di scorrimento ed i tasti cursore. Usando il pulsante sulla destra è inoltre possibile "allargare" le barre visualizzate, in modo da evidenziare informazioni relative alle corse quali codice della corsa, turno manuale assegnato, oppure (come in figura) in base alla tipologia Piccolo, Medio, Grande, … di autobus.

Per visualizzare il Grafico a Linee è necessario definire preventivamente la sequenza di fermate che costituirà l’asse spaziale (verticale) del grafico. Ad ogni lista di fermate si può associare una Descrizione e tutte le liste create vengono salvate su file (con lo stesso nome del file Fermate attivo ma con estensione LST) in modo da poter essere riutilizzate in seguito.

Nella finestra di definizione delle liste si trovano pulsanti atti ad aggiungere o togliere fermate dalla lista selezionata (pulsanti [+] e [-]) ed a modificarne l’ordine (pulsanti [­ ] e [¯ ]).

Una volta completata la definizione della lista, viene visualizzato il grafico che rappresenta le corse afferenti alle fermate selezionate con linee di colore diverso per turni diversi. Facendo click con il mouse su di una corsa vengono evidenziati sia la corsa stessa che il turno corrispondente, e vengono visualizzate le relative informazioni sulla barra di stato. È inoltre possibile ingrandire, ridurre e spostare l’area visualizzata mediante gli appositi controlli.

I colori con cui vengono rappresentati i vari elementi delle rappresentazioni grafiche (barre/titoli/linee) sono definiti nel file TURNI.DEF presente nella directory contenente il programma TI.EXE, e possono essere modificati da un utente esperto mediante un editor di testi (p.e. Notepad) come descritto all’interno dello stesso file. Si consiglia in ogni caso di effettuare una copia di backup del file originale.

L’ultima voce del menu vista, File completo, lancia l’applicazione Write (editor di testo) sul file soluzione aperto, che viene quindi visualizzato in modo testo.

Il file prevede una stampa dei singoli turni, divisi per gruppo di residenza e sequenziati in modo da agevolarne la successiva vestizione. Per ciascun turno vengono evidenziate le caratteristiche principali (tempo di lavoro, nastro, ecc.), nonché l’efficienza percentuale del turno calcolata dividendo il tempo di lavoro per la somma delle durate delle corse di copertura richiesta o suggerita. Eventuali trasferimenti tecnici o vuoti generati dal programma vengono riportati come corse contrassegnate dalla dicitura "VUOTO+" (il segno + indica che la corsa non era presente nel file INPUT.COR ma è stata generata in base al tempo di trasferimento ricavato dal file delle DISTANZE). Una riga separa le varie fasi di lavoro: la riga doppia "==========" segnala una sosta in residenza, mentre una riga semplice "----------------" individua una sosta fuori residenza. Prima di ogni corsa viene riportato il tempo di attesa T-ATT rispetto alla corsa precedente; in caso di sosta, invece, viene riportato il tempo di sosta (al netto dei tempi di pre e di post) intercorso prima dell’inizio della corsa.

Per ciascuna delle viste descritte è possibile richiedere la stampa dal menu File; la stampa del file in formato dettagliato (testo) deve essere attivata dalla vista "Testo", dato che la vista "File Completo" passa il controllo all’editor WordPad.

La finestra di stampa permette di impostare la stampante da utilizzare (una qualunque stampante definita in ambiente Windows) e l’orientamento della pagina (portrait o landscape). Per i grafici è possibile inoltre specificare (i) quante ore stampare per ogni pagina; (ii) la richiesta di stampare turni di gruppi diversi su pagine separate; (iii) la richiesta di stampare una pagina aggiuntiva con le statistiche sui turni della soluzione. Per la modalità testo è possibile troncare le righe troppo lunghe (senza spezzarle andando a capo).

I restanti documenti (Linee e Forzature) non presentano particolarità di rilievo.

Il programma TURNI può essere eseguito direttamente, come applicazione MS-DOS, oppure mediante l’interfaccia grafica TI descritta nella sezione successiva attivando il pulsante "Avvia Ottimizzazione" della maschera di ottimizzazione.

Per eseguire direttamente TURNI direttamente da ambiente (o finestra) MS-DOS è invece sufficiente eseguire il comando

nella directory di lavoro (quella che contiene il programma).

L’elaborazione effettuata dal programma TURNI è articolata in Passate, in ciascuna delle quali si tenta di migliorare la soluzione correntemente disponibile.

• Passata n. –1: è la primissima Passata, che ha lo scopo di determinare un primo insieme di turni che coprano tutte le corse assegnate;
• Passata n. 0: questa passata, opzionale, determina le prime soluzioni efficienti del problema allo studio; a differenza delle passate successive, la Passata n. 0 è progettata per ottenere al più presto una buona soluzione, ed utilizza una strategia aggressiva di risoluzione;
• Passate n. 1, 2, …: tentano di migliorare le soluzioni individuate in precedenza, utilizzando una strategia più accurata (e quindi più lenta) rispetto alla Passata n. 0.

Tipicamente le soluzioni ottimali vengono determinate durante le primissime passate, ma in alcuni casi particolarmente difficili anche le passate successive possono individuare soluzioni via via migliori.

Durante ciascuna passata si alternano ciclicamente due distinte fasi di elaborazione: la fase di generazione dei turni (in cui viene generato un insieme di turni "candidati") e la fase di selezione (in cui vengono selezionati i turni che definiscono la soluzione). Se richiesto, durante la fase di generazione dei turni vengono anche generate opportune corse a vuoto. Entrambe le fasi utilizzano internamente algoritmi di ottimizzazione (proprietari) particolarmente efficienti, basati su opportuni modelli matematici che permettono di quantificare in modo molto preciso l’utilità di possibili nuovi turni in base alle caratteristiche della soluzione corrente. Tipicamente, durante la fase di generazione vengono implicitamente valutati milioni di turni possibili, e durante la fase di selezione vengono considerate e valutate decine di migliaia di soluzioni alternative.

Durante una stessa passata, le due fasi di generazione e selezione vengono applicate per un certo numero di iterazioni, aggiornando di volta in volta la miglior soluzione individuata dal programma. Viene quindi attivata una opportuna procedura di fissaggio che sceglie alcuni turni ritenuti particolarmente "efficienti" e decide di fissarli come facenti parte della soluzione definitiva. Il procedimento viene quindi ripetuto sulle corse non coperte dai turni fissati: si alternano nuovamente le fasi di generazione e di selezione, si fissano nuovi turni, ecc.

In questo modo si individuano tipicamente soluzioni sempre migliori, fino ad arrivare ad un punto in cui la soluzione corrente non risulta ulteriormente migliorabile. In questa situazione il programma termina la Passata corrente, e procede con la Passata successiva: il contatore delle Passate viene incrementato di 1, vengono "liberati" i turni fissati, ed il programma viene riapplicato sulle corse scoperte.

La successione di Passate continua finché non viene raggiunto il tempo di esecuzione massimo specificato dall’utente.

L’utente può interrompere in qualsiasi momento l’esecuzione del programma (mediante la combinazione di tasti Ctrl-C, oppure con il controllo [X] in alto a destra della maschera MS-DOS) se ritiene soddisfacente la soluzione corrente. In ogni caso, è sconsigliabile interrompere il programma prima che sia terminata la Passata n. 1, cioè prima che il contatore delle Passate che compare sul video non abbia raggiunto il valore 2.

Questo schema di elaborazione ha il vantaggio di individuare rapidamente soluzioni molto buone del problema (tipicamente già dopo i primi fissaggi le soluzioni sono paragonabili a quelle manuali), e di migliorarle man mano che l’elaborazione procede.

La migliore soluzione individuata è in ogni caso disponibile nel file di output TURNI.SOL, ove TURNI rappresenta il nome base per le soluzioni specificato dall’utente. Il programma memorizza inoltre le migliori K soluzioni individuate, scrivendole nei file di output TURNI-*.SOL (il numero K di soluzioni da memorizzare è definibile da parte dell’utente).

Viene inoltre riportata nel file TURNI-X.SOL la soluzione, fra quelle costruite dal programma, che utilizza il minimo numero di turni (anche in presenza di vincoli violati). L’analisi di questa soluzione, che viola tipicamente alcuni dei vincoli del problema, può risultare utile per avere un’indicazione di quali siano i vincoli più stringenti del problema allo studio.

Per esempio, se K=3 ed il nome base per le soluzioni è Prova, il programma memorizzerà le 3 migliori soluzioni individuate nei file di output Prova-1.sol, Prova-2.sol e Prova-3.sol. Inoltre, se la miglior soluzione utilizza p.e. 59 turni, il programma memorizzerà nei file Prova-59.sol, Prova-60.sol e Prova-61.sol le migliori soluzioni con 59, 60 e 61 turni, rispettivamente. Eventuali soluzioni (anche se non ammissibili) con meno di 59 turni sarebbero memorizzate nei file Prova-58.sol, Prova-57.sol ecc. Infine, la soluzione con il numero minimo di turni (anche se non ammissibile) verrà memorizzata in Prova-X.sol.

In alcune versioni personalizzate del programma, le soluzioni vengono memorizzate anche nei file TURNI.OUT, e TURNI-*.OUT secondo il formato personalizzato richiesto dall’Azienda.

Inoltre, il programma memorizza internamente un numero molto elevato di turni (circa 150.000, scelti fra quelli più efficienti) e di corse a vuoto (fino ad alcune migliaia). Questi turni/vuoti possono essere memorizzati ed utilizzati, insieme alla miglior soluzione ottenuta, come base di partenza per una successiva elaborazione.

Il programma TURNI è inoltre in grado di valutare la bontà e l’ammissibilità di una eventuale soluzione "manuale" fornita in input. Il programma valuta automaticamente la soluzione "manuale", evidenziando nel file TURNI-E.SOL eventuali errori (o turni incongruenti in quanto non associabili ai depositi) e stampando nel file TURNI-V.SOL e TURNI-M.SOL i turni letti e le relative competenze. Il file TURNI-V.SOL riporta esattamente i turni manuali forniti, mentre nel file TURNI-M.SOL vengono eliminati eventuali spezzoni di turno inutili e la sequenza dei turni stessi viene ridefinita calcolandone una rotazione settimanale indicativa. Dopo aver valutato la soluzione manuale, il programma memorizza internamente i turni manuali che risultino ammissibili in base ai parametri specificati, ed avvia il modulo di ottimizzazione nel tentativo di individuare nuovi turni che migliorino la soluzione manuale.

È altresì possibile memorizzare in un file con estensione .CRS ogni soluzione individuata dal programma e salvata in un file con estensione .SOL. I file con estensione .CRS hanno il medesimo formato dei file di input delle corse, ma contengono le corse nella sequenza corrispondente ai turni in soluzione. In questo modo è possibile iniziare una nuova elaborazione partendo dalla soluzione memorizzata in un qualunque file .CRS, semplicemente definendola come "soluzione manuale" di partenza.

Durante l’elaborazione compare sul video una finestra MS-DOS con una "scheda riassuntiva" relativa alla miglior soluzione individuata.

È importante verificare che la finestra MS-DOS (quella a sfondo nero rappresentata in figura) da cui viene eseguito il programma TURNI non ne sospenda l’esecuzione quando la finestra stessa non è in primo piano. A tal fine è sufficiente controllare che il secondo pulsante da destra evidenziato sulla parte alta della finestra (quello a sinistra del pulsante A) appaia "premuto" come in figura.

La schermata MS-DOS riporta, fra l’altro:

• la Passata corrente (Passata n. 1, nell’esempio in figura);
• il numero di corse in input, ed il numero di vuoti e di turni complessivamente generati e memorizzati dal programma;
• il tempo di esecuzione corrente (12 minuti);
• una misura della bontà complessiva (Fitness) della miglior soluzione corrente, calcolata come somma del costo della soluzione, di penalità molto elevate per eventuali vincoli violati, e di piccole penalità per eventuali inefficienze, nonché l’istante in cui la soluzione è stata trovata (9 minuti);
• il costo della miglior soluzione corrente, definito in base ai pesi specificati;
• una stima ottimistica del costo della miglior soluzione ottenibile con i turni attualmente generati, dopo aver fissato un certo numero di turni (4, nell’esempio); tipicamente, questa stima diminuisce rapidamente nelle prime iterazioni per effetto dei turni sempre migliori che vengono generati, ed aumenta man mano che vengono fissati i vari turni; dopo la prima passata, il valore evidenziato con zero turni fissati rappresenta una stima per difetto abbastanza precisa del costo ottimo ottenibile;
• una statistica sulla qualità della miglior soluzione attualmente disponibile (59 turni, 618 minuti di trasferimento a vuoto, tempo medio di lavoro pari a 6:48, ecc.).

Eventuali vincoli violati vengono evidenziati con la dicitura " <---- vincolo violato". In alcuni casi la schermata riporta anche il costo ed il numero di turni della soluzione "non ammissibile" attualmente memorizzata nel file TURNI-X.SOL.

Il file di output TURNI.LOG contiene un breve riassunto dei dati letti, ed in particolare riporta eventuali errori o incongruenze riscontrati durante la lettura dei dati di input, nonché una stampa dei principali pesi/parametri letti. Eventuali errori e commenti vengono evidenziati con la dicitura "ERRORE" o "ATTENZIONE", in modo da poter essere facilmente individuati usando il comando Trova dell’editor utilizzato.

Il programma TURNI legge i dati di input dai file di testo descritti nel seguito (si veda il manuale completo per informazioni dettagliate).

Questo file contiene le corse da coprire, ciascuna delle quali è identificata dalle fermate (capolinea) e dai tempi di partenza e di arrivo, nonché da informazioni aggiuntive relative a vincoli particolari.

Questo file (opzionale) agisce come "filtro" sulle corse e permette di ridefinirne alcune caratteristiche in base al "codice della linea" specificato nel file INPUT.COR.

Questo file contiene i codici e gli identificativi delle fermate dove è possibile effettuare il cambio di autista.

Questo file contiene la descrizione dei gruppi di residenza per gli autisti.

Questo file contiene le distanze "a vuoto" fra le fermate ed è indispensabile se si vogliono generare automaticamente le corse a vuoto ed i trasferimenti tecnici necessari per gli allacciamenti.

Ogni riga di questo file (opzionale) contiene un allacciamento forzato fra due corse (o con i depositi).

Questo file contiene i seguenti valori che controllano il tipo di esecuzione richiesta:

Questo file contiene i parametri che definiscono i vincoli normativi ed aziendali, nonché un insieme di pesi che permettono di quantificate il costo associato a ciascun turno e quindi alla soluzione complessiva.

I parametri gestiti sono descritti nel seguito. Si noti che la maggior parte di questi parametri viene di solito definita in fase di installazione e non viene modificata dall'utente (questi parametri possono essere mascherati in modo da non creare confusione all'utente).

COSTI AZIENDALI (DETERMINANO IL COSTO AZIENDALE DI UNA SOLUZIONE)

Double-Click s.r.l.

e-mail: turni.bus@gmail.com

URL: http://www.turni.it