Optimization models for selecting bus stops for accessibility improvements for people with disabilities

Bus stops are key links in the journeys of transit patrons with disabilities. Inaccessible bus stops prevent people with disabilities from using fixed-route bus services, thus limiting their mobility. The Americans with Disabilities Act (ADA) of 1990 prescribes the minimum requirements for bus stop accessibility by riders with disabilities. Due to limited budgets, transit agencies can only select a limited number of bus stop locations for ADA improvements annually. These locations should preferably be selected such that they maximize the overall benefits to patrons with disabilities. In addition, transit agencies may also choose to implement the universal design paradigm, which involves higher design standards than current ADA requirements and can provide amenities that are useful for all riders, like shelters and lighting. Many factors can affect the decision to improve a bus stop, including rider-based aspects like the number of riders with disabilities, total ridership, customer complaints, accidents, deployment costs, as well as locational aspects like the location of employment centers, schools, shopping areas, and so on. These interlacing factors make it difficult to identify optimum improvement locations without the aid of an optimization model. This dissertation proposes two integer programming models to help identify a priority list of bus stops for accessibility improvements. The first is a binary integer programming model designed to identify bus stops that need improvements to meet the minimum ADA requirements. The second involves a multi-objective nonlinear mixed integer programming model that attempts to achieve an optimal compromise among the two accessibility design standards. Geographic Information System (GIS) techniques were used extensively to both prepare the model input and examine the model output. An analytic hierarchy process (AHP) was applied to combine all of the factors affecting the benefits to patrons with disabilities. An extensive sensitivity analysis was performed to assess the reasonableness of the model outputs in response to changes in model constraints. Based on a case study using data from Broward County Transit (BCT) in Florida, the models were found to produce a list of bus stops that upon close examination were determined to be highly logical. Compared to traditional approaches using staff experience, requests from elected officials, customer complaints, etc., these optimization models offer a more objective and efficient platform on which to make bus stop improvement suggestions.

The order selection and lot sizing problem in the make-to-order environment

This research is motivated by the need for considering lot sizing while accepting customer orders in a make-to-order (MTO) environment, in which each customer order must be delivered by its due date. Job shop is the typical operation model used in an MTO operation, where the production planner must make three concurrent decisions; they are order selection, lot size, and job schedule. These decisions are usually treated separately in the literature and are mostly led to heuristic solutions. The first phase of the study is focused on a formal definition of the problem. Mathematical programming techniques are applied to modeling this problem in terms of its objective, decision variables, and constraints. A commercial solver, CPLEX is applied to solve the resulting mixed-integer linear programming model with small instances to validate the mathematical formulation. The computational result shows it is not practical for solving problems of industrial size, using a commercial solver. The second phase of this study is focused on development of an effective solution approach to this problem of large scale. The proposed solution approach is an iterative process involving three sequential decision steps of order selection, lot sizing, and lot scheduling. A range of simple sequencing rules are identified for each of the three subproblems. Using computer simulation as the tool, an experiment is designed to evaluate their performance against a set of system parameters. For order selection, the proposed weighted most profit rule performs the best. The shifting bottleneck and the earliest operation finish time both are the best scheduling rules. For lot sizing, the proposed minimum cost increase heuristic, based on the Dixon-Silver method performs the best, when the demand-to-capacity ratio at the bottleneck machine is high. The proposed minimum cost heuristic, based on the Wagner-Whitin algorithm is the best lot-sizing heuristic for shops of a low demand-to-capacity ratio. The proposed heuristic is applied to an industrial case to further evaluate its performance. The result shows it can improve an average of total profit by 16.62%. This research contributes to the production planning research community with a complete mathematical definition of the problem and an effective solution approach to solving the problem of industry scale.

Algorithms for scheduling parallel batch processing machines with non-identical job ready times

This research is motivated by a practical application observed at a printed circuit board (PCB) manufacturing facility. After assembly, the PCBs (or jobs) are tested in environmental stress screening (ESS) chambers (or batch processing machines) to detect early failures. Several PCBs can be simultaneously tested as long as the total size of all the PCBs in the batch does not violate the chamber capacity. PCBs from different production lines arrive dynamically to a queue in front of a set of identical ESS chambers, where they are grouped into batches for testing. Each line delivers PCBs that vary in size and require different testing (or processing) times. Once a batch is formed, its processing time is the longest processing time among the PCBs in the batch, and its ready time is given by the PCB arriving last to the batch. ESS chambers are expensive and a bottleneck. Consequently, its makespan has to be minimized. ^ A mixed-integer formulation is proposed for the problem under study and compared to a formulation recently published. The proposed formulation is better in terms of the number of decision variables, linear constraints and run time. A procedure to compute the lower bound is proposed. For sparse problems (i.e. when job ready times are dispersed widely), the lower bounds are close to optimum. ^ The problem under study is NP-hard. Consequently, five heuristics, two metaheuristics (i.e. simulated annealing (SA) and greedy randomized adaptive search procedure (GRASP)), and a decomposition approach (i.e. column generation) are proposed—especially to solve problem instances which require prohibitively long run times when a commercial solver is used. Extensive experimental study was conducted to evaluate the different solution approaches based on the solution quality and run time. ^ The decomposition approach improved the lower bounds (or linear relaxation solution) of the mixed-integer formulation. At least one of the proposed heuristic outperforms the Modified Delay heuristic from the literature. For sparse problems, almost all the heuristics report a solution close to optimum. GRASP outperforms SA at a higher computational cost. The proposed approaches are viable to implement as the run time is very short. ^

Minimizing makespan for hybrid flowshops with batch, discrete processing machines and arbitrary job sizes

This research aims at a study of the hybrid flow shop problem which has parallel batch-processing machines in one stage and discrete-processing machines in other stages to process jobs of arbitrary sizes. The objective is to minimize the makespan for a set of jobs. The problem is denoted as: FF: batch1,sj:Cmax. The problem is formulated as a mixed-integer linear program. The commercial solver, AMPL/CPLEX, is used to solve problem instances to their optimality. Experimental results show that AMPL/CPLEX requires considerable time to find the optimal solution for even a small size problem, i.e., a 6-job instance requires 2 hours in average. A bottleneck-first-decomposition heuristic (BFD) is proposed in this study to overcome the computational (time) problem encountered while using the commercial solver. The proposed BFD heuristic is inspired by the shifting bottleneck heuristic. It decomposes the entire problem into three sub-problems, and schedules the sub-problems one by one. The proposed BFD heuristic consists of four major steps: formulating sub-problems, prioritizing sub-problems, solving sub-problems and re-scheduling. For solving the sub-problems, two heuristic algorithms are proposed; one for scheduling a hybrid flow shop with discrete processing machines, and the other for scheduling parallel batching machines (single stage). Both consider job arrival and delivery times. An experiment design is conducted to evaluate the effectiveness of the proposed BFD, which is further evaluated against a set of common heuristics including a randomized greedy heuristic and five dispatching rules. The results show that the proposed BFD heuristic outperforms all these algorithms. To evaluate the quality of the heuristic solution, a procedure is developed to calculate a lower bound of makespan for the problem under study. The lower bound obtained is tighter than other bounds developed for related problems in literature. A meta-search approach based on the Genetic Algorithm concept is developed to evaluate the significance of further improving the solution obtained from the proposed BFD heuristic. The experiment indicates that it reduces the makespan by 1.93 % in average within a negligible time when problem size is less than 50 jobs.

Capacity planning methodology for concurrent engineer -to -order operations

This research focuses on developing a capacity planning methodology for the emerging concurrent engineer-to-order (ETO) operations. The primary focus is placed on the capacity planning at sales stage. This study examines the characteristics of capacity planning in a concurrent ETO operation environment, models the problem analytically, and proposes a practical capacity planning methodology for concurrent ETO operations in the industry. A computer program that mimics a concurrent ETO operation environment was written to validate the proposed methodology and test a set of rules that affect the performance of a concurrent ETO operation. ^ This study takes a systems engineering approach to the problem and employs systems engineering concepts and tools for the modeling and analysis of the problem, as well as for developing a practical solution to this problem. This study depicts a concurrent ETO environment in which capacity is planned. The capacity planning problem is modeled into a mixed integer program and then solved for smaller-sized applications to evaluate its validity and solution complexity. The objective is to select the best set of available jobs to maximize the profit, while having sufficient capacity to meet each due date expectation. ^ The nature of capacity planning for concurrent ETO operations is different from other operation modes. The search for an effective solution to this problem has been an emerging research field. This study characterizes the problem of capacity planning and proposes a solution approach to the problem. This mathematical model relates work requirements to capacity over the planning horizon. The methodology is proposed for solving industry-scale problems. Along with the capacity planning methodology, a set of heuristic rules was evaluated for improving concurrent ETO planning. ^

Branch and price solution approach for order acceptance and capacity planning in make -to -order operations

The increasing emphasis on mass customization, shortened product lifecycles, synchronized supply chains, when coupled with advances in information system, is driving most firms towards make-to-order (MTO) operations. Increasing global competition, lower profit margins, and higher customer expectations force the MTO firms to plan its capacity by managing the effective demand. The goal of this research was to maximize the operational profits of a make-to-order operation by selectively accepting incoming customer orders and simultaneously allocating capacity for them at the sales stage. ^ For integrating the two decisions, a Mixed-Integer Linear Program (MILP) was formulated which can aid an operations manager in an MTO environment to select a set of potential customer orders such that all the selected orders are fulfilled by their deadline. The proposed model combines order acceptance/rejection decision with detailed scheduling. Experiments with the formulation indicate that for larger problem sizes, the computational time required to determine an optimal solution is prohibitive. This formulation inherits a block diagonal structure, and can be decomposed into one or more sub-problems (i.e. one sub-problem for each customer order) and a master problem by applying Dantzig-Wolfe’s decomposition principles. To efficiently solve the original MILP, an exact Branch-and-Price algorithm was successfully developed. Various approximation algorithms were developed to further improve the runtime. Experiments conducted unequivocally show the efficiency of these algorithms compared to a commercial optimization solver.^ The existing literature addresses the static order acceptance problem for a single machine environment having regular capacity with an objective to maximize profits and a penalty for tardiness. This dissertation has solved the order acceptance and capacity planning problem for a job shop environment with multiple resources. Both regular and overtime resources is considered. ^ The Branch-and-Price algorithms developed in this dissertation are faster and can be incorporated in a decision support system which can be used on a daily basis to help make intelligent decisions in a MTO operation.^

Branch and Price Solution Approach for Order Acceptance and Capacity Planning in Make-to-Order Operations

The increasing emphasis on mass customization, shortened product lifecycles, synchronized supply chains, when coupled with advances in information system, is driving most firms towards make-to-order (MTO) operations. Increasing global competition, lower profit margins, and higher customer expectations force the MTO firms to plan its capacity by managing the effective demand. The goal of this research was to maximize the operational profits of a make-to-order operation by selectively accepting incoming customer orders and simultaneously allocating capacity for them at the sales stage. For integrating the two decisions, a Mixed-Integer Linear Program (MILP) was formulated which can aid an operations manager in an MTO environment to select a set of potential customer orders such that all the selected orders are fulfilled by their deadline. The proposed model combines order acceptance/rejection decision with detailed scheduling. Experiments with the formulation indicate that for larger problem sizes, the computational time required to determine an optimal solution is prohibitive. This formulation inherits a block diagonal structure, and can be decomposed into one or more sub-problems (i.e. one sub-problem for each customer order) and a master problem by applying Dantzig-Wolfe’s decomposition principles. To efficiently solve the original MILP, an exact Branch-and-Price algorithm was successfully developed. Various approximation algorithms were developed to further improve the runtime. Experiments conducted unequivocally show the efficiency of these algorithms compared to a commercial optimization solver. The existing literature addresses the static order acceptance problem for a single machine environment having regular capacity with an objective to maximize profits and a penalty for tardiness. This dissertation has solved the order acceptance and capacity planning problem for a job shop environment with multiple resources. Both regular and overtime resources is considered. The Branch-and-Price algorithms developed in this dissertation are faster and can be incorporated in a decision support system which can be used on a daily basis to help make intelligent decisions in a MTO operation.

A simulation-based heuristic for fleet assignment

Integer programming, simulation, and rules of thumb have been integrated to develop a simulation-based heuristic for short-term assignment of fleet in the car rental industry. It generates a plan for car movements, and a set of booking limits to produce high revenue for a given planning horizon. Three different scenarios were used to validate the heuristic. The heuristic's mean revenue was significant higher than the historical ones, in all three scenarios. Time to run the heuristic for each experiment was within the time limits of three hours set for the decision making process even though it is not fully automated. These findings demonstrated that the heuristic provides better plans (plans that yield higher profit) for the dynamic allocation of fleet than the historical decision processes. Another contribution of this effort is the integration of IP and rules of thumb to search for better performance under stochastic conditions.

Obesity, cardiovascular disease risk factors and weight loss in a population of adult Mexican Americans

The study of obesity has evolved into one of the most important public health issues in the United States (U.S.), particularly in Hispanic populations. Mexican Americans, the largest Hispanic ethnic subgroup in the U.S., have been significantly impacted by obesity and related cardiovascular diseases. Mexican Americans living in the Lower Rio Grande Valley (the Valley) in the Texas-Mexico border are one of the most disadvantaged and hard-to-reach minority groups. Demographic factors, socioeconomic status, acculturation, and physical activity behavior have been found to be important predictors of health, although research findings are mixed when establishing predictors of obesity in this population. Furthermore, while obesity has long been linked to cardiovascular disease (CVD) risk factors such as hypertension, type 2 diabetes, and dyslipidemia; information on the relationships between obesity and these CVD risk factors have been mostly from non-minority population groups. Overall, research has been mixed in establishing the association between obesity and related CVD risk factors in this population calling attention to the need for further research. Nevertheless, identifying predictors of success for weight loss in this population will be important if health disparities are to be addressed. The overall objective of the findings presented in this dissertation was to attain a more informed profile of obesity and CVD risk factors in this population. In particular, we examined predictors of obesity, measures of obesity and association with cardiovascular disease risk factors in a sample of 975 Mexican Americans participating in a health promotion program in the Valley region. Findings suggest acculturation factors to be one of the most important predictors of obesity in this population. Results also point to the need of identifying other possible risk factors for predicting CVD risk. Finally, initial body mass index is an important predictor of weight loss in this population group. Thus, indicating that this population is not only amenable to change, but that improvements in weight loss are feasible. This finding strengthens the relevance of prevention programs such as Beyond Sabor for Mexican populations at risk, in particular, food bank recipients.

Obesity, Cardiovascular Risk Factors, and Weight Loss in a Population of Adult Mexican Americans

The study of obesity has evolved into one of the most important public health issues in the United States (U.S.), particularly in Hispanic populations. Mexican Americans, the largest Hispanic ethnic subgroup in the U.S., have been significantly impacted by obesity and related cardiovascular diseases. Mexican Americans living in the Lower Rio Grande Valley (the Valley) in the Texas-Mexico border are one of the most disadvantaged and hard-to-reach minority groups. Demographic factors, socioeconomic status, acculturation, and physical activity behavior have been found to be important predictors of health, although research findings are mixed when establishing predictors of obesity in this population. Furthermore, while obesity has long been linked to cardiovascular disease (CVD) risk factors such as hypertension, type 2 diabetes, and dyslipidemia; information on the relationships between obesity and these CVD risk factors have been mostly from non-minority population groups. Overall, research has been mixed in establishing the association between obesity and related CVD risk factors in this population calling attention to the need for further research. Nevertheless, identifying predictors of success for weight loss in this population will be important if health disparities are to be addressed. The overall objective of the findings presented in this dissertation was to attain a more informed profile of obesity and CVD risk factors in this population. In particular, we examined predictors of obesity, measures of obesity and association with cardiovascular disease risk factors in a sample of 975 Mexican Americans participating in a health promotion program in the Valley region. Findings suggest acculturation factors to be one of the most important predictors of obesity in this population. Results also point to the need of identifying other possible risk factors for predicting CVD risk. Finally, initial body mass index is an important predictor of weight loss in this population group. Thus, indicating that this population is not only amenable to change, but that improvements in weight loss are feasible. This finding strengthens the relevance of prevention programs such as Beyond Sabor for Mexican populations at risk, in particular, food bank recipients.

Lower Aptian Comparative Stratigraphy of the Basco-Cantabrian Region (Spain) and Eastern Cordillera (Colombia): implications for local factors in the depositional record of Oceanic Anoxic Event 1a (OAE-1a)

An important episode of carbon sequestration, Oceanic Anoxic Event 1a (OAE-1a), characterizes the Lower Aptian worldwide, and is mostly known from deeper-water settings. The present work of two Lower Aptian deposits, Madotz (N Spain) and Curití Quarry (Colombia), is a multiproxy study that includes fossil assemblages, microfacies, X-ray diffraction bulk and clay mineralogy, elemental analyses (major, minor, trace elements), Rock-Eval pyrolysis, biomarkers, inorganic and organic carbon content, and stable carbon isotopes. The results provide baseline evidence of the local and global controlling environmental factors influencing OAE-1a in shallow-water settings. The data also improve our general understanding of the conditions under which organic-carbon-rich deposits accumulate. The sequence at Madotz includes four intervals (Unit 1; Subunits 2a, 2b and 2c) that overlap the times prior to, during and after the occurrence of OAE-1a. The Lower Unit 1(3m thick) is essentially siliciclastic, and Subunit 2a (20m) contains Urgonian carbonate facies that document abruptly changing platform conditions prior to OAE-1a. Subunit 2b (24.4 m) is a mixed carbonate-siliciclastic facies with orbitolinid-rich levels that coincides with OAE-1a δ13C stages C4-C6, and is coeval with the upper part of the Deshayesites forbesi ammonite zone. Levels with pyrite and the highest TOC values (0.4-0.97%), interpreted as accumulating under suboxic conditions, and are restricted to δ13C stages C4 and C5. The best development of the suboxic facies is at the level representing the peak of the transgression. Subunit 2c, within δ13C stage C7, shows a return of the Urgonian facies. The 23.35-m section at Curití includes a 6.3-m interval at the base of the Paja Formation dominated by organic-rich marlstones and shales lacking benthic fossils and bioturbation, with TOC values as high as 8.84%. The interval overlies a level containing reworked and phosphatized assemblages of middle Barremian to lowest Aptian ammonites. The range of values and the overall pattern of the δ13Corg (-22.05‰ to -20.47‰) in the 6.3m-interval is comparable with Lower Aptian δ13C stage C7. Thus, conditions of oxygen depletion at this site also occurred after Oceanic Anoxic Event-1a, which developed between carbon isotope stages C3 and C6. Both sites, Madotz and Curití, attest to the importance of terrigenous and nutrient fluxes in increasing OM productivity that led to episodic oxygen deficiency.