Manpower and Transportation Planning

Research output: PhD ThesisPhD Thesis - Research external, graduation externalAcademic

Abstract

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.
LanguageEnglish
QualificationPhD
Awarding Institution
  • The Chinese University of Hong Kong
Supervisors/Advisors
  • Leung, Janny M.Y., Supervisor, External person
Award date1 Dec 2014
Publisher
Print ISBNs9781321821277
StatePublished - 2014

Fingerprint

Tabu search
Planning
Vehicle routing
Scheduling
Costs
Mathematical models
Beer
Beverages
Travel time
Linear programming
Sensitivity analysis
Accidents
Experiments
Uncertainty
Industry

Keywords

  • Integer programming
  • Manpower planning
  • Rostering
  • Scheduling
  • Transportation planning
  • Vehicle routing

Cite this

Lai, S. W. (2014). Manpower and Transportation Planning Proquest UMI Dissertation Publishing
Lai, S.W.. / Manpower and Transportation Planning. Proquest UMI Dissertation Publishing, 2014. 111 p.
@phdthesis{f71027fd25da4d009bbf18d8e78e95af,
title = "Manpower and Transportation Planning",
abstract = "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.",
keywords = "Integer programming, Manpower planning, Rostering, Scheduling, Transportation planning, Vehicle routing",
author = "S.W. Lai",
year = "2014",
language = "English",
isbn = "9781321821277",
publisher = "Proquest UMI Dissertation Publishing",
school = "The Chinese University of Hong Kong",

}

Lai, SW 2014, 'Manpower and Transportation Planning', PhD, The Chinese University of Hong Kong.

Manpower and Transportation Planning. / Lai, S.W.

Proquest UMI Dissertation Publishing, 2014. 111 p.

Research output: PhD ThesisPhD Thesis - Research external, graduation externalAcademic

TY - THES

T1 - Manpower and Transportation Planning

AU - Lai,S.W.

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

KW - Integer programming

KW - Manpower planning

KW - Rostering

KW - Scheduling

KW - Transportation planning

KW - Vehicle routing

UR - https://search.proquest.com/docview/1691074490?accountid=10978

M3 - PhD Thesis - Research external, graduation external

SN - 9781321821277

PB - Proquest UMI Dissertation Publishing

ER -

Lai SW. Manpower and Transportation Planning. Proquest UMI Dissertation Publishing, 2014. 111 p.