Shared Car Repositioning Problem

In this study, a two-stage stochastic programming model for the shared car dynamic staff relocation problem in a free-floating environment was formulated. A mixed-integer linear programming model similar to the multi-period transportation problem was formulated first. The model decides the inventory levels of cars and staff in each zone at the beginning of each period, relocation and staff movement between each zone, and the amount of unsatisfied demand to minimize total cost including relocation and opportunity costs. An exact method and an approximate clustering method to solve this model stochastically were developed. In the exact method, all the variables and constraints related to staff movement from the model were removed and a simplified MILP to use in a two-stage stochastic programming formulation was obtained. The simplified model was solved by relaxing its second-stage variables in a deterministic equivalent (extensive form) of two-stage stochastic programming to obtain values of first-stage variables that is car inventory levels at the beginning of each period. Then, these first stage-variable values were fed into a new MILP model that is the same model with the main model except decision variables of inventory levels are parameters in the new model. After feeding the inventory levels, this model was run for each scenario separately to obtain the expected cost of the second-stage decisions. This exact method is effective in solving instances up to 20 zones and 18 time periods. To solve larger instances, a clustering-based approximate method was developed. This approximate clustering method can solve instances up to 40 zones and 36 time periods.