Solving transportation scheduling problems : models and algorithms

Given the increasing load on current logistics and transportation systems, it is crucial to improve resource utilization and reduce operational costs. This can be achieved by developing better models and algorithms for transportation planning and scheduling. The main challenges include the mathematical modeling of operational rules, uncertainties in operations, and large-scale problem size. This dissertation addresses crew scheduling in freight railways and vehicle routing problems (VRP) for mail processing and distribution centers (P&DCs). Our goal is to develop models and algorithms that improve efficiency and reduce operating costs. In Chapter 2, we propose an optimization model to support real-time freight railway crew assignment decisions. Due to workload balance requirements and operating regulations, the optimization model is difficult to solve for realistic instances. Hence, we propose model improvements and develop effective solution techniques to find optimal or near-optimal solutions very quickly. Chapter 3 extends the freight rail crew scheduling problem by incorporating uncertainty in train arrival and departure times. We propose a stochastic programming model, but this model is solvable only the number of scenarios is small. As a consequence, we develop heuristics that use an analytical model to calculate the expected total cost of a given choice of crew deadheads. Using this cost evaluator, we develop four local search based heuristic algorithms to sequentially improve crew scheduling decisions under uncertainty. In Chapter 4, we first cluster the pickup and drop off points in mail P&DCs into zones and then minimize the number of vehicles required and the total distance traveled to meet daily transport demand. The clustering is performed with a greedy randomized adaptive search procedure, and two heuristics are developed to find solutions to the VRP, which proved intractable for realistic instances. The heuristics are optimization-based within a rolling horizon framework. An extensive analysis is undertaken to evaluate the relative performance of the two heuristics. The contributions of this dissertation include modeling, algorithmic development, computational testing, and validation using real and randomly generated data.