In this research, we investigate and propose new operators to improve Genetic Algorithm’s performance to solve the multi-stop routing problem. In a multi-stop route, a user starts at point x, visits all destinations exactly once, and then return to the same starting point. In this thesis, we are interested in two types of this problem. The first type is when the distance among destinations is fixed. In this case, it is called static traveling salesman problem. The second type is when the cost among destinations is affected by traffic congestion. Thus, the time among destinations changes during the day. In this case, it is called time-dependent traveling salesman problem. This research proposes new improvements on genetic algorithm to solve each of these two optimization problems. First, the Travelling Salesman Problem (TSP) is one of the most important and attractive combinatorial optimization problems. There are many meta-heuristic algorithms that can solve this problem. In this paper, we use a Genetic Algorithm (GA) to solve it. GA uses different operators: selection, crossover, and mutation. Sequential Constructive Crossover (SCX) and Bidirectional Circular Constructive Crossover (BCSCX) are efficient to solve TSP. Here, we propose a modification to these crossovers. The experimental results show that our proposed adjustment is superior to SCX and BCSCX as well as to other conventional crossovers (e.g. Order Crossover (OX), Cycle Crossover (CX), and Partially Mapped Crossover (PMX)) in term of solution quality and convergence speed. Furthermore, the GA solver, that is improved by applying inexpensive local search operators, can produce solutions that have much better quality within reasonable computational time. Second, the Time-Dependent Traveling Salesman Problem (TDTSP) is an interesting problem and has an impact on real-life applications such as a delivery system. In this problem, time among destinations fluctuates during the day due to traffic, weather, accidents, or other events. Thus, it is important to recommend a tour that can save driver’s time and resources. In this research, we propose a Multi-Population Genetic Algorithm (MGA) where each population has different crossovers. We compare the proposed MG against Single-Population Genetic Algorithm (SGA) in terms of tour time solution quality. Our finding is that MGA outperforms SGA. Our method is tested against real-world traffic data [1] where there are 200 different instances with different numbers of destinations. For all tested instances, MGA is superior on average by at least 10% (for instances with size less than 50) and 20% (for instances of size 50) better tour time solution compared to SGA with OX and SGA with PMX operators, and at least 4% better tour time compared toga with SCX operator.

abstract: Short-notice disasters such as hurricanes involve uncertainties in many facets, from the time of its occurrence to its impacts’ magnitude. Failure to incorporate these uncertainties can affect the effectiveness of the emergency responses. In the case of a hurricane event, uncertainties and corresponding impacts during a storm event can quickly cascade. Over the past decades, various storm forecast models have been developed to predict the storm uncertainties; however, access to the usage of these models is limited. Hence, as the first part of this research, a data-driven simulation model is developed with aim to generate spatial-temporal storm predicted hazards for each possible hurricane track modeled. The simulation model identifies a means to represent uncertainty in storm’s movement and its associated potential hazards in the form of probabilistic scenarios tree where each branch is associated with scenario-level storm track and weather profile. Storm hazards, such as strong winds, torrential rain, and storm surges, can inflict significant damage on the road network and affect the population’s ability to move during the storm event. A cascading network failure algorithm is introduced in the second part of the research. The algorithm takes the scenario-level storm hazards to predict uncertainties in mobility states over the storm event. In the third part of the research, a methodology is proposed to generate a sequence of actions that simultaneously solve the evacuation flow scheduling and suggested routes which minimize the total flow time, or the makespan, for the evacuation process from origins to destinations in the resulting stochastic time-dependent network. The methodology is implemented for the 2017 Hurricane Irma case study to recommend an evacuation policy for Manatee County, FL. The results are compared with evacuation plans for assumed scenarios; the research suggests that evacuation recommendations that are based on single scenarios reduce the effectiveness of the evacuation procedure. The overall contributions of the research presented here are new methodologies to: (1) predict and visualize the spatial-temporal impacts of an oncoming storm event, (2) predict uncertainties in the impacts to transportation infrastructure and mobility, and (3) determine the quickest evacuation schedule and routes under the uncertainties within the resulting stochastic transportation networks. / Dissertation/Thesis / Doctoral Dissertation Industrial Engineering 2020