Multi depot dynamic vehicle routing problem with stochastic road capacity for emergency medical supply delivery in humanitarian logistics

As part of humanitarian logistics research for emergency medical supply delivery during disaster, the modelling and solution of a Multi Depot Dynamic Vehicle Routing Problem with Stochastic Road Capacity (MDDVRPSRC) is presented. Based on the chaotic setting from a disaster event, the model and solution proposed are validated and analysed through a Decision Support System (DSS), MDDVRPSRC DSS. The model proposed is based on Markov Decision Processes (MDP) modelling framework as part of reinforcement learning (RL) solution approach. Through this model, multi objectives, multi depot, multi trip and split delivery among homogeneous fleet of vehicle are addressed. Moreover a stochastic road capacity distribution where its mean deteriorates over time is also depicted in the problem. To solve the proposed model, an Approximate Dynamic Programming (ADP) approach is applied focusing on the lookahead approach. Specifically a PDS - Rollout Algorithm (PDS-RA) is adopted. Five variants of constructive base heuristics, Teach Based Insertion Heuristic (TBIH-1 - TBIH-5) are proposed complementing the PDSRA when dealing with the lookahead rollout involving stochastic road capacity. The computational results obtained are compared with a matheuristic approach. From this novel method, exact CPLEX computation is executed at every rollout decision epoch, based on two proposed reduced 2-stage stochastic programming ILP models (MDVRPSRC-2S1 and MDVRPSRC-2S2). These two models are derived from the Multi Depot Vehicle Routing Problem with Stochastic Road Capacity (MDVRPSRC-2S) which is proposed next to the deterministic model of Multi Depot Vehicle Routing Problem with Road Capacity (D-MDVRPRC) stemming from the preliminary research, prior to the development of MDDVRPSRC model. Results indicate comparable quality of solution from the proposed heuristics to that of CPLEX in random setting of the problem instances. In addition, the proposed heuristics are especially superior in computation time. The contributions of the research are as follows: (1) The MDP model for MDDVRPSRC, deterministic D-MDVRPRC as well as 2 stage stochastic ILP MDVRPSRC-2S models are respectively developed and presented; (2) based on the MDVRPSRC- 2S it is shown how 2-stage stochastic programming model can be applied through CPLEX execution during each of Monte Carlo simulated PDS - RA by proposing another two models as two reduced version (MDVRPSRC-2S1 and MDVRPSRC- 2S2) of the MDVRPSRC-2S; (3) the radial tremor disaster dispersion from a single or multiple epicentres and the corresponding deterioration of road capacity distribution mean and travel time are proposed; (4) the solution algorithm: TBIH-1, and it’s 4 variants (TBIH-2, TBIH-3, TBIH-4 and TBIH-5) are presented; (5) test dataset is developed consists of simulated road networks and the damage unit of each roads due to the earthquake for experimentation and simulation purposes, and finally (6) a decision support system (MDDVRPSRC DSS) for simulating online delivery operation during disaster is designed. All of these could be applied to all types of dynamic vehicle routing problem involving any types of disaster and it’s inherent stochastic road capacity as well as increased delayed travel time.

Text WadiPhdThesisV91_B5_FINAL - IR.pdf Download (3MB)

Actions (login required)

View Item