Mathematical Programming Approaches to Home Healthcare Nurse Routing Problem and Truckload Transportation Procurement via Combinatorial Auctions

Open Access
Chi, Cheng
Graduate Program:
Industrial Engineering
Doctor of Philosophy
Document Type:
Date of Defense:
February 20, 2015
Committee Members:
  • Dr Paul Griffin, Dissertation Advisor
  • M Jeya Chandra, Committee Member
  • Vittaldas V Prabhu, Committee Member
  • Robert Alexander Novack, Committee Member
  • David Arthur Nembhard, Committee Member
  • Mathematical Programming
  • Home Healthcare
  • Nurse Routing Problem
  • Truckload
  • Transportation Procurement
  • Combinatorial Auctions
Mathematical programming (MP) models are among the most widely used tools in operations research and management science. In this dissertation, we use MP approaches, mainly relying on mixed-integer programming (MIP) modeling, to solve logistics problems in the following two areas: home healthcare (HHC) and truckload transportation procurement. HHC is health or supportive care provided in the patient’s home by healthcare professionals. Approximately 12 million individuals currently receive HHC services from more than 33,000 providers with over 1 million staff members. However, 65% of home care and hospice agencies are facing nurse staff vacancies and 84% of nurse staff worked overtime during last week at the interview time. To help improve efficiency of the HHC workforce and improve patient outcomes, we develop an operational dispatching (routing) model that assigns care workers to patients and determines the optimal visiting sequences and start times. An appointment scheduling decision support system is developed to handle the clients’ appointment requests dynamically. The model allows the use of time windows and time-dependent travel speeds. We develop and compare heuristic approaches for solving this problem and conduct numerical experiments on different sized instances. According to the results, a hybrid algorithm based on genetic algorithm and particle swarm optimization is further proposed. In freight transportation service procurement, shippers sell service contracts to carriers based on negotiated transportation rates and service level by utilizing a competitive auction process. Recently, several large shippers and third-party-logistics (3PL) providers have turned to combinatorial auction mechanisms to reduce their transportation costs, where the bidding carriers can quote prices on packages in combination of individual lanes. We address the problem of truckload transportation procurement via combinatorial auctions from two perspectives. i) a carrier perspective, where the goal is to develop an optimal bidding strategy based on the operation cost analysis (called bid generation), and ii) a shipper perspective, where the goal is to determine the allocation of lanes to carriers give a set of bids (called the winner determination problem). In the first case, we incorporate the bid generation model with vehicle routing methods and stochastic optimization to determine an optimal bidding strategy for carriers. In the second case, we develop a multi-round combinatorial auction of transportation procurement by MIP. A real application to an agriculture and construction equipment company is also provided. Computational results show that a significant savings can be achieved.