\documentstyle[11pt,psfig,lslide]{article}
%\documentstyle[12pt,amssymbols,lslide]{article}
        % <- if amssymbols.sty is available
%\documentstyle[12pt,amstex,amssymb,lslide]{article}
        % <- if you use AmSLaTeX

\pagestyle{myheadings}

\makeatletter
\def\@oddhead{\vbox{\hbox to\hsize{\sl \rightmark \hfill \sl \today }}}
\def\@oddfoot{\vbox{\vspace{-20pt} \footmsg \hfill \rm \thepage}}
\makeatother

\def\rightmark{Genetic Algorithms for Transportation Problems}
\def\footmsg{H. T. Ozdemir}

\def\slidetitle{Analysis}
\def\author{Hasan Timucin OZDEMIR}
\def\authorAddr{Department of Electrical Engineering and Computer Science \\
Syracuse University, Syracuse, NY, 13244 }
\def\authorEmail{ {\em Email : htozdemi@top.cis.syr.edu } }

\landscape
        % <- if your driver can rotate 90 degrees.
        % e.x. in emTeX derivers:
        %  hp filename /tr2
        % \portrait is default. 1 


% Adjust page dimensions here if necessary. For example:
%\addtolength{\textwidth}{-.3in}
%\addtolength{\textheight}{.5in}
%\addtolength{\topmargin}{.02in}
%\addtolength{\oddsidemargin}{-.03in}
%\addtolength{\evensidemargin}{-.03in}

%\verttop
        % compare it with \vertcenter that is the default

%\ovalframe
\doubleboxframe

%\doubleboxframe % or \ovalframe
        % compare them with \shadowframe that is the default

%\boxsecframe
%\boxsecframe
        % compare it with \shadowsecframe that is the default

\input{psfig}
\include{psfig}
\title{ {\bf Genetic Algorithms for Transportation Problems } \\
\vspace{1cm} \author \\
\vspace{1cm} \authorAddr \\
\vspace{1cm} \authorEmail}

\begin{document}

\begin{slide}

\titlepage

\begin{center}
\fbox{{\bf Outline }} 
\end{center}

\begin{enumerate}
\item Airline Crew Scheduling
\item Constraints
\item Cost Related Items
\item Models
\item Modeling based on Directed Graph 
\item Genetic Algorithm (GA) on Directed Graph Model
\item GA for Column Generation 
\item GA for Set Cover Problem 
\item Comparisons
\item Results
\item Future Work
\end{enumerate}

\pagebreak

\begin{center}
\fbox{{\bf Airline Crew Scheduling }} 
\end{center}

\begin{itemize}
\item
Crew scheduling is the assignment of the flight and training activities
schedule for some period of time to each crew member.

\item
Crew utilization has significant revenue return in the airline companies
as crew costs constitute the largest direct operating cost of airlines 
next to fuel costs.

\begin{itemize}
\item  Northwest Airlines (1989) reported \$1.05 billion for crew expenses
\item  United Airlines (1993) spent \$0.6 billion just on pilots
\end{itemize}

Therefore, relatively small improvements in efficiency leverage into
large cost savings.

\item Marketing department produces timetable by trying to match the
      expectations of the marketing department with the available fleets
      and with constraints on the network.

\item Aircraft rotations are built (Fleet Assignment, Through Flight
      Assignment, Aircraft Maintenance Assignment).

\item Pairings are constructed for an unspecified crew member starting and 
      ending at the same crew base ({\em domicile}) and respecting FAA and 
      company regulations.

\item Crew Assignment (Bidline/Rostering) phase assigns
      individuals to the pairings. 

\end{itemize}

\pagebreak

\begin{center}
\fbox{{\bf Constraints }} 
\end{center}

\begin{itemize}

\item Each flight must be covered once and only once.

\item A duty period is usually restricted to 8 hours of flying and
      12-13 hours of total duty time.

\item The minimum rest period between duty periods is typically 10 hours.
      If more than 8 hours flying are scheduled in a 24 hours period, then 
      the minimum rest period is typically 12 hours.

\item Crew assignments must consider the number of crews available at
      the various crew bases ({\em crew balance}).

\item Layover time cannot exceed a maximum amount (typically 36 hours).

\end{itemize}

\pagebreak

\begin{center}
\fbox{{\bf Cost Related Items }} 
\end{center}

\begin{itemize}

\item Crews may be paid an overtime rate whenever they fly more than
      five hours consecutively.

\item Crews are paid per diem whenever they have a rest period not at
      their home base. Their hotel expenses are also paid by the 
      company.

\item Crews are paid a bonus if their total time away from base exceeds
      a specified amount.

\item Crews are paid extra if they have rotations containing two flight 
      segments that do not have enough break time (90 minutes) between them.

\item Union contracts specify that flight crews will be guaranteed pay 
      for some number of hours each day or each trip.

\item {\em Deadhead flight} crews get paid for 50\% or more of the
      flying time of the leg.

\end{itemize}

\pagebreak

\begin{center}
\fbox{{\bf Models }} 
\end{center}

\begin{itemize}

\item Linear Programming (LP) can be applied but the problem has a large
      number of integer variables. The large number of variables makes
      this problem harder for Integer Linear Programming (ILP) model.

\item Because of the problems with LP and ILP, there have been many attempts 
      to solve it with branch-and-cut,  branch-and-bound, and algorithms 
      based on enumeration techniques.

\item Set Partitioning Problem (SPP) model can also be applied after generating
      {\em good} columns. Unfortunately, there is no way to solve this
      size problem with SPP or Set Cover Problem (SCP) solution techniques. 

\end{itemize}

\pagebreak

\begin{center}
\fbox{{\bf Models (Cont.) }} 
\end{center}

\begin{itemize}

\item Iterative approaches such as TRIP are still in use. Iterative
      approaches start with a solution (such as schedule of the previous 
      period) and apply several heuristics to the small portion of the 
      problem to improve the quality of the general solution.
      {\em This idea assumes that optimally solved small pieces will lead to
      a better solution in the global optimization process.}
      Therefore, heuristic, enumeration, SCP, SPP, LP, or ILP solution 
      techniques are applicable for these small size problems. 

\item Levine and Chu appllied a GA to a similar problem. Both of them
      used SPP model, bit representation, and used pre-produced columns as
      an input to their algorithms. Both their results are unfortunately 
      discouraging. 

\end{itemize}

\pagebreak

\begin{center}
\fbox{{\bf Modeling based on Directed Graph }} 
\end{center}

\begin{itemize}

\item I propose a new graph representation,  which is easy to use and 
      can take care of several constraints for the problem.

\item In the proposed representation, each node represents a 
      flight (work, assignment) and directed edge ($a \rightarrow b$) 
      represents that flight $a$ can be followed by flight $b$.

\item Proposed graph expresses time, minimum time between flight legs
      and city constraints. 

\item Each directed path starting from a base city and returning to 
      the same base city can be a candidate for the solution provided that
      it also respects the duty-period and minimum rest-time constraints.

\end{itemize}

\pagebreak

\begin{center}
\fbox{{\bf Modeling Based on Directed Graph }} 
\end{center}

%\begin{figure}[htbp]
%\centerline{\psfig{file=schedule.ps,height=3in,width=3in}
%            \psfig{file=graph.ps,height=3in,width=3in} }
%\caption{Example schedule and Directed Graph representation }
%\label{fig:schedule}
%\end{figure} 

%\begin{figure}[htbp]
%\centerline{\psfig{file=graph.ps,height=2in,width=2in}}
%\caption{Directed Graph representation for given schedule}
%\label{fig:graph}
%\end{figure}

%\begin{figure}[htbp]
%\centerline{\psfig{file=NumOfMatch.ps,height=3in,width=3in}}
%\caption{Fuzzy Classes for the Number of matches measure}
%%\label{fig:layers}
%\end{figure} 

\pagebreak

\begin{center}
\fbox{{\bf Genetic Algorithm (GA) on Directed Graph Model }} 
\end{center}

\begin{itemize}

\item It accepts flight schedules and produces pairings for crews.

\item Each chromosome contains a set of pairings.

\item Each pairing corresponds to a directed path in the graph.

\item Mutation operator takes two pairings and applies 1PX provided that
      this operation is applicable between these two pairings.

\item Several new recombination operators are proposed:

      \begin{itemize}
      \item Set Based
      \item Time Based
      \item Distance Preserving
      \end{itemize}

\item Mutation operator tries to build a new pairing while crossover
      operator reorganizes them while trying to minimize the number of 
      pairings (number of crews).

\item First studies tried to conduct search only through feasible
      strings. It was successful for 74-102 flight data sets, but it could not
      show the same success for the larger problems (133-217 flight data
      set).

\end{itemize}

\pagebreak

\begin{center}
\fbox{{\bf GA on Directed Graph Model (Cont.) }} 
\end{center}

\begin{itemize}

\item Current algorithm applies recombination after each application of
      genetic operators. 
      
\item After operator is applied, offsprings and parents are
      placed into a set and two individuals are selected from this set and
      replaced with parents.
      Note that if the parent is the best in the current
      population, it cannot be replaced.

\item Fitness scaling is applied and their selection probability
      obtained by mapping fitness value to the range [ 0.5, 1.0 ]. 
      This scaling allows GA to
      introduce some degraded individuals for exploring the search space.

\end{itemize}

\pagebreak

\begin{center}
\fbox{{\bf GA on Directed Graph Model (Cont.) }} 
\end{center}

\begin{itemize}

\item The algorithm tries to repair the solution with the following steps:

      \begin{enumerate}
      \item Obtain a reduced graph by removing already covered nodes
	    and edges incident to those nodes.
      \item Search for directed path on this graph which respects all
            constraints.
      \item Apply backtracking, 
           \begin{enumerate}
	   \item  remove a node from the current graph,
           \item  update the graph with new uncovered nodes, and 
	   \item apply step 2. 
           \end{enumerate}
      \item Allow deadheadings and apply step 2.
      \item Cover all uncovered nodes with one edge assignment.
      \end{enumerate}

\item The algorithm uses the cost with a multiplicative penalty term to express
      fitness value of a chromosome.

\end{itemize}

\pagebreak

\begin{center}
\fbox{{\bf GA for Column Generation }} 
\end{center}

\begin{itemize}

\item Column generation is to produce solutions for smaller size problems
      which are obtained from the actual problem. The basic blind enumeration
      technique produces all possible combinations and evaluates them
      according to their cost value.

\item SCP or SPP model is used to select a group of columns to produce
      a better schedule. SPP model is much more harder than SCP.

\item The purpose of producing columns with GA is to keep the size of
      column set small while producing columns in such a way that
      they are cost efficient as well as compatible with each other.
      This general approach can be applied to many different problems
      reducible to SCP or SPP. Since SCP and SPP solvers can be efficiently 
      used with small size problems, this approach might be very useful.

\end{itemize}

\pagebreak

\begin{center}
\fbox{{\bf GA for Set Cover Problem }} 
\end{center}

\begin{itemize}

\item A typical algorithm based on random or greedy choice can be
      summarized as follows:

      \begin{itemize}
      \item while ( there is an uncovered node ($r$) )
           \begin{itemize}
           \item pick a column ($c$) covering $r$ according to random or
	         greedy choice.
           \item add column $c$ to the solution set
           \item update cover
           \end{itemize}
      \end{itemize} 

\item Chavatal's heuristic selects the minimum cost column to cover the
      uncovered row. 

\item Back's heuristic calculates the cost ratio of the column based on its 
      cost and how many uncovered nodes it can cover. 

\item A third, new heuristic multiplies the cost calculated by
      Back's heuristic with the number of overlap between the already covered
      nodes and the current column.

\item Mutation operators: 

      \begin{itemize}
      \item delete a column randomly
      \item restore the solution with random choice or greedy choice
            (Chavatal, Back, Greedy3).
      \end{itemize}

\end{itemize}

\pagebreak

\begin{center}
\fbox{{\bf GA for Set Cover Problem (Cont.) }} 
\end{center}

\begin{itemize}

\item Crossover operators are defined as

      \begin{itemize}
      \item place common columns into offspring
      \item cover uncovered nodes with one of the following
            approaches:

           \begin{itemize}
           \item pick randomly by using probabilities defined according
	         to their cost values.
           \item restore the solution with greedy choice (Chavatal,
	         Back, Greedy3).
           \item according to DPX, restore the solution with random
		 choice or greedy choice (Chavatal, Back, Greedy3).
           \end{itemize}

      \end{itemize}

\end{itemize}

\pagebreak

\begin{center}
\fbox{{\bf Comparisons }} 
\end{center}

\begin{itemize}

\item To be able to compare results of different approaches, algorithms 
      converting the output of SCP solver to a crew schedule are developed.

\item SCP algorithms are applied on the data sets produced by
      blind enumeration. 

\item Their performance is measured according to the following parameters:

      \begin{itemize}
      \item number of required crews
      \item average flying time
      \item standard deviation in flying times
      \item number of deadheadings
      \item total flying time used for assignment
      \item run time
      \item cost
      \end{itemize}

\end{itemize}

\pagebreak

\begin{center}
\fbox{{\bf Results }} 
\end{center}

\begin{itemize}

\item The proposed algorithm seems to provide the following results:

     \begin{itemize}

     \item Produces a better workload between crew members.

     \item Produce  a better crew size.

     \item Produces less number of deadheadings.

     \item Produces less number of assigned flying time for crews with 
           better cost value.

     \item Open for warm start setting.

     \end{itemize}

\item The proposed algorithm has the following drawbacks:

     \begin{itemize}

     \item Demands long run time.

     \item Requires more experiment to prove that it is a better
           solution technique.

     \end{itemize}

\end{itemize}

\pagebreak

\begin{center}
\fbox{{\bf Future Work}}
\end{center}

\begin{enumerate}

\item More experiments with GA for column generation.

\item Detailed study on proposed various operators for SCP.

\item Application of the proposed technique on different problems such
      as Vehicle Scheduling and Bus Driver scheduling problems.

\item Robustness analysis for the obtained shedule and incorporating
      this objective to the search process by using fitness value of 
      a chromosome.

\end{enumerate}

\pagebreak

\begin{center}
\fbox{{\bf 74 Flight}}
\end{center}

%\input{t74}


\pagebreak

\begin{center}
\fbox{{\bf 74 Flight}}
\end{center}

%\begin{figure}[htbp]
%\centerline{\psfig{file=74_p20_g1000_f1.ps,height=3in,width=4in}
%            \psfig{file=74_p20_g1000_f2.ps,height=3in,width=4in}
%	   }
%\caption{74 Flight Problem. (Weekly)}
%\label{fig:f74}
%\end{figure} 

\pagebreak

\begin{center}
\fbox{{\bf 102 Flight}}
\end{center}

%\input{t102}

\pagebreak

\begin{center}
\fbox{{\bf 102 Flight PS=20, G=1000}}
\end{center}

%\begin{figure}[htbp]
%\centerline{\psfig{file=102_p20_g1000_f1.ps,height=3in,width=4in}
%            \psfig{file=102_p20_g1000_f2.ps,height=3in,width=4in}
%	   }
%\caption{102 Flight Problem with 20 population size and 1000 generations}
%\label{fig:f102}
%\end{figure} 

\pagebreak

\begin{center}
\fbox{{\bf 102 Flight PS=20, G=2500}}
\end{center}

%\begin{figure}[htbp]
%\centerline{\psfig{file=102_p20_g2500_f1.ps,height=3in,width=4in}
%            \psfig{file=102_p20_g2500_f2.ps,height=3in,width=4in}
%	   }
%\caption{102 Flight Problem with 20 population size and 2500 generations}
%\label{fig:f102b}
%\end{figure} 

\pagebreak

\begin{center}
\fbox{{\bf 133 Flight}}
\end{center}

%\input{t133}

\pagebreak

\begin{center}
\fbox{{\bf 133 Flight PS=20, G=1000}}
\end{center}

%\begin{figure}[htbp]
%\centerline{\psfig{file=133_p20_g1000_f1.ps,height=3in,width=4in}
%            \psfig{file=133_p20_g1000_f2.ps,height=3in,width=4in}
%	   }
%\caption{133 Flight Problem with 20 population size and 1000 generations}
%\label{fig:f133}
%\end{figure} 

\pagebreak

\begin{center}
\fbox{{\bf 217 Flight}}
\end{center}

%\input{t217}

\pagebreak

\begin{center}
\fbox{{\bf 217 Flight PS=20, G=600}}
\end{center}

%\begin{figure}[htbp]
%\centerline{\psfig{file=217_p20_g600_f1.ps,height=3in,width=4in}
%            \psfig{file=217_p20_g600_f2.ps,height=3in,width=4in}
%	   }
%\caption{217 Flight Problem with 20 population size and 600 generations}
%\label{fig:f217}
%\end{figure} 

%\pagebreak

%\slidecontents

%\sectioncontent



\end{slide}
\end{document}
