Title

Graph based evolutionary algorithms for transportation problems

Date of Award

2001

Degree Type

Dissertation

Degree Name

Doctor of Philosophy (PhD)

Department

Electrical Engineering and Computer Science

Advisor(s)

Chilukuri K. Mohan

Keywords

Evolutionary algorithms, Transportation, Graph representations, Airline scheduling

Subject Categories

Computer Sciences | Physical Sciences and Mathematics

Abstract

A large number of optimization problems need to be solved in the field of transportation, and have consirable industrial and practical significance. The majority of these problems are multi-objective, highly constrained (due to regulations and physical limitations) and NP-complete. In general, even very little improvement in the solution (1%) produces substantial profit as well as satisfaction of customers and employees. Traditional Operations Research (OR) techniques are generally applied to solve these problems, with recent interest in Tabu Search and Evolutionary Algorithms. Sophisticated modeling and transformation techniques have been proposed and studied. This dissertation proposes a new approach to solve transportation problems, hybridizing with previously known algorithms when appropriate. We propose a new graph representation and operations to be applied on this representation, using evolutionary algorithms. We applied these ideas on the Airline Crew Scheduling (ACS) and Vehicle Routing with Time Windows (VRPTW) problems. We applied the new algorithms to many problem sets and demonstrate that the evolutionary algorithms with the new proposed representation are able to produce competitive solutions for these multi-objective, highly constrained, and NP-hard problems.

Access

Surface provides description only. Full text is available to ProQuest subscribers. Ask your Librarian for assistance.

http://libezproxy.syr.edu/login?url=http://proquest.umi.com/pqdweb?did=725906631&sid=1&Fmt=2&clientId=3739&RQT=309&VName=PQD

Link to Full Text

Share

COinS