Manpower and Transportation Planning

This thesis studies three routing and scheduling problems arising in manpower and transportation planning. These problems are rooted in real applications, and carry interesting characteristics. By exploiting the structures of the problems, this thesis provides effective mathematical models and algorithms for solving the problems practically. Managerial insights are developed via extensive computational tests and sensitivity analyses.

Effective scheduling of staff can generate considerable saving where unnecessary costs due to misallocation of staff to the demand are reduced. The second chapter of this thesis studies the Shift Rostering Problem—the assignment of staff to shifts over a planning horizon such that work rules are observed. In view of the special structure of the work-rule constraints, we model work rules in terms of prohibited meta-sequences and resource constraints. A novel graph-based formulation is proposed where the formulation size depends on the structure of the work-rule constraints and is independent of the number of staff. This is particularly beneficial when the work rules possess sufficient structure that results in a small formulation. For some cases when the canonical formulation could not solve in a reasonable time, our approach can find optimal solutions in a few minutes.

Vehicle routing problems occur frequently in the delivery and collection of items between a central depot and a number of customer locations. Motivated from the distribution of beer and malt beverages in China, the third chapter of this thesis studies a time-constrained heterogeneous vehicle routing problem on a multigraph. Parallel arcs represent Pareto-optimal paths between two locations, with various travel times and costs. We provide a mixed-integer linear programming formulation of the problem and propose a tabu search heuristic for its solution. The tabu search is designed to address the parallel arc structure on the network, which necessitates modifications of the basic search operations such as insertion. Our numerical experiments demonstrate the effectiveness of the proposed tabu search heuristic and provide further managerial insights through sensitivity analysis. The numerical experiments suggest considerable transportation cost savings attributable to the utilization of alternative route structure and provide some insights to aid distributors on their vehicle dispatch policies.

Most transportation planning models are deterministic and do not consider uncertainties in operations. Therefore, disruptions on the planned daily schedule often occurs in the daily operations due to unexpected traffic conditions, vehicle breakdowns, accidents, special events, etc. When delays due to these uncertainties accumulate and propagate in the execution and operation of the planned schedule, poor service and high operational cost result. The fourth chapter of this thesis addresses a real-time tram scheduling problem arising in a public transit company in Hong Kong. Motormen and trams are scheduled simultaneously to provide passenger transportation service in some commercial routes. To mitigate unexpected overtime and meal-break delays due to the uncertainties in operations, planned schedules are revised dynamically using real-time information under a rolling-horizon framework. Furthermore, route frequencies are maximized simultaneously for improved passenger transportation service. We provide a number of mathematical models for revising the schedules in real-time. A general event-driven simulation model is developed to evaluate the efficiency and the effectiveness of the models with real-world data.