Decomposition approaches for prioritised collaborative vehicle routing and scheduling problems
Creators: name: Nuraiman, Dian
Publisher: name: RMIT University
Year: 2024
Subjects: classificationCode: 490108
subject: Operations research

description: This thesis focuses on prioritised collaborative vehicle routing and scheduling problems (PCVRSPs) in which vehicles with various capabilities are deployed to deliver services to customers with synchronous visit requirements. The main characteristic of the problems considered is that the available vehicles may not be enough to serve all the demands. Thus, a prioritisation scheme is applied by assigning a score to each customer indicating the priority of being serviced. The objective is then to maximise total collected scores from serviced customers. In this thesis, three PCVRSPs are considered; the asset protection problem (APP) under deterministic and stochastic circumstances, and the prioritised home health care routing and scheduling problem (PHHCRSP). To solve the problems efficiently, decomposition approaches are proposed utilising a mathematical programming solver. Proposed solution methods all use spatial decomposition strategies which decompose large-scale PCVRSP into smaller and more manageable sub-problems. Computational tests on realistically large benchmark instances show that the proposed methods provide high quality solutions within times suitable for practical purposes.

The asset protection problem (APP) involves deploying firefighting resources of various capabilities to service as many community assets as possible within time windows determined by an advancing wildfire. A new spatial decomposition based matheuristic (SDM) approach is proposed. The heuristic exploits the property that time windows are geographically correlated as fire spreads across a landscape. Thus an appropriate division of the landscape allows the problem to be decomposed into smaller more tractable sub-problems. A common situation arising during an escaped wildfire is a wind change. Forecasts of changes in wind velocity (i.e. direction and speed) are reasonably accurate but there is some uncertainty around the time of a wind change. The timing has implications for which areas, and hence which assets, will be impacted by the wildfires. The SDM approach originally developed for the deterministic APP is extended for the stochastic APP. This is achieved by regarding the deterministic and stochastic components as a coupled system. A two-stage stochastic programming (TSSP) model is thus only used for a smaller sub-problem around the uncertainty. 

The third PCVRSP addressed in this thesis is a prioritised home health care routing and scheduling problem (PHHCRSP). This problem arises in situations when the HHC provider has insufficient number of caregivers available and/or faces higher than usual demand over a period of time. Determining the routes and schedules of available limited caregivers to match prioritised patients is, therefore, a highly critical task for many HHC providers. The patients that potentially cannot be serviced at their homes, can be offered a phone-call service or a time slot out of their requested time windows. A Mixed Integer Programming (MIP) model is formulated to allow for various types of caregivers and synchronised visits. A new spatial-temporal decomposition with patient filtering (STDPF) approach is proposed. This method combines multi-dimensional temporal and spatial decomposition approaches together with a filtering scheme considering the care requirements and priorities. A daily temporal decomposition approach of the STDPF is capable of handling any visit cancellations and/or new patients, changes in caregivers' availability or any unexpected/unplanned disruptions to the plans like failing to visit a patient. All these changes can easily be incorporated at the end of the day for creating the plans for the following day without impacting the performance of the approach.