Master Problem

The problem consists of two sets of nodes. The first set,S⁺, contains all stations in the BSS, including the depot. The second set,S, contains the subset of stations where bike rebalancing and battery swaps can be performed, i.e. not including the depot. Both sets of stations are indexed by i. Further, the setV consists of service vehicles, indexed by v. Each vehiclev has an associated set of possible routes,R^v, and an associated set of possible patterns,P^v. Routes are indexed byrand patterns are indexed byp. Lastly, the setFdefines the set of possible customer arrival scenarios, indexed bys.

There are five types of quantity parameters describing the first stage decision performed by vehiclevdriving routerwith patternp.Q^{F CL}_vrp andQ^CCL_vrp denote the quantities of flat and charged bikes loaded onto the vehicle, respectively. Similarly,Q^{F CU}_vrp andQ^CCU_vrp denote the unloaded quantities of flat and charged bikes.Q^B_vrpstores the number of battery swaps performed by service vehiclevat the start station of routerwith patternp. Note that all routes considered by a vehicle have the same starting station, as the routes are chosen from a vehicle indexed set.

A service vehicle has an inventory consisting ofL^BV_v batteries,L^{F V}_v flat bikes andL^CV_v charged bikes at its origin station. The capacity for bikes at each service vehicle isQ^CV_v . Further, the starting station for vehiclevhas an inventory ofL^{F S}_v flat bikes andL^CS_v upon arrival of vehiclev. Each station has an associated capacityQ^S_v.

Recall that a subproblem, step two of the presented heuristic, is solved for a given combi-nation of route, pattern and scenario. The objective value of the subproblem solution for router, patternpand scenariosis used in the master problem as parameterRrps. This value aims at expressing the benefit of choosing routerand patternpin scenarios. Each scenarioshas probabilityPsof occuring. The binary matrixAirv indicates the first sta-tionifor a vehiclevin a specific router. The matrix is used to determine the next station decision in a given scenario.

The model uses the variables vrps to find the weighted combination of columns that results in the highest total column score, while satisfying the problem constraints. The quantity variables q^B_v,q_v^{F CL}, q^CCL_v ,q_v^{F CU} andq^CCU_v ensure that the first stage quan-tity decisions are uniquely defined for each vehicle. Further, the first stage next station decisions are defined by the binary variablexivsfor each vehicle in each scenario. Non-anticipativity constraints capture the operational decision xiv, making the decision con-sistent between scenarios. The full notation used in the master problem is summarized in Table 5.1.

Table 5.1:Notation used for modelling the master problem Sets

S⁺ Set of stations, including the depot

S Set of stations

V Set of vehicles

R^v Set of possible routes for vehiclev

P^v Set of possible quantity patterns for vehiclev F Set of possible customer arrival scenarios Indices

i Stationsi2S⁺

v Vehiclev2V

r Router2R^v

p Patternp2P^v

s Scenarios2F

Parameters

Aivr 1 if stationiis the start station in routerfor vehiclev, otherwise 0 Rrps Objective value of subproblem for routerwith patternpin scenarios Ps Probability of scenarios

Q^{F CL}_vrp Number of flat bikes loaded to service vehiclev at the start station for router with patternp

Q^CCL_vrp Number of charged bikes loaded to service vehiclevat the start station for route rwith patternp

Q^{F CU}_vrp Number of flat bikes unloaded from service vehiclevat the start station for route rwith patternp

Q^CCU_vrp Number of charged bikes unloaded to service vehiclev at the start station for routerwith patternp

Q^B_vrp Number of battery swaps performed by service vehiclevat the start station for routerwith patternp

Q^CV_v Capacity for bikes at service vehiclev

Q^S_v Station capacity at the origin station for service vehiclev L^{F V}_v Load of flat bikes at service vehiclevat its origin station L^CV_v Load of charged bikes at service vehiclevat its origin station L^BV_v Load of batteries at service vehiclevat its origin station L^{F S}_v Load of flat bikes at its origin station for service vehiclev L^CS_v Load of charged bikes at its origin station for service vehiclev Variables

vrps Weighting variable of the allocation of vehicle v to route r with pattern pin scenarios

xivs 1 if vehiclevtravels directly to stationiin scenarios, 0 otherwise

xiv Non-anticipativity variable forxivs, representing the first stage decision of which station to visit next

q^{F CL}_v First stage decision of flat bikes loaded to vehiclev q^CCL_v First stage decision of charged bikes loaded to vehiclev

q^{F CU}_v First stage decision of flat bikes unloaded from vehiclev q^CCU_v First stage decision of charged bikes unloaded from vehiclev q^B_v First stage decision battery swaps for vehiclev

Objective

The master problem objective finds the combination of columns that has the highest sum of rewards, equal to subproblem objective values. Each scenario is multiplied with the probability that the scenario occurs.

The master problem constraints secure that the first stage decisions are linear combinations of the weighted columns. The decisions must be valid in terms of the current vehicles and stations inventories. Constraints (5.2) - (5.6) capture the quantity variables for each vehicle as a linear function of the pattern quantity parameters in the weighted columns. Further, constraints (5.7) secure that the first stage loading decision is valid for the number of avail-able bike slots at the vehicle. Constraints (5.8) work similarly for the first stage unloading decisions with respect to available locks at the station. The number of battery swaps must be lower than the available flat bikes after rebalancing decisions and lower than the num-ber of charged batteries at the vehicle, secured by (5.9) and (5.10). Constraints (5.11) and (5.12) restrict the number of flat and charged bikes loaded from a station, respectively. The number of unloaded bikes at a station are restricted by Constraints (5.13) and (5.14) in the same manner. Constraints (5.15) capture the next station to visit for a specified vehicle in a specified scenario. These constraints also secure that all columns with nonzero -values in a given scenario must have the same first station. Each vehicle can decide on maximum one station to visit next, secured by (5.16). Further, each station, apart from the depot, may be chosen as the next destination by at most one vehicle. Constraints (5.17) secure this.

Constraints (5.18) are non-anticipativity constraints, and ensure that the first stage next station decision is the same for all scenarios. As an extention to this, Constraints (5.19) ensure that each vehicle chooses a station to visit next. Lastly, constraints (5.20) - (5.22) restrict the feasible values for the decision variables.

X

r2Rv

X

p2Pv

Q^{F CL}_rpv rpvs=q^{F CL}_v v2V, s2F (5.2)

X

xiv =xivs i2S⁺, v2V, s2F (5.18) X

i2S⁺

xiv = 1 v2V (5.19)

0 ^rpvs1 r2R^v, p2P^v, v2V, s2F (5.20)

xivs2{0,1} i2S⁺, v2V, s2F (5.21)

q^{F CL}_v , q^CCL_v , q_v^{F CU}, q^CCU_v , q_v^B 0, integer v2V (5.22)