Size of Solvable Instances

Recall that the DSBRCP is solved every time a service vehicle arrives at a new station. For effective utilization of operational resources, rapid decision support is required. Hence, we definereasonable timeto solve the DSBRCP as less than 60 seconds, the estimated aver-age time it takes for a service vehicle to park.

To get an initial idea of the limit in size of solvable instances, the model was run with three varying subproblem parameters; number of stations, number of vehicles and number of customer arrival scenarios. Further, the computational time sensitivity for each of the

parameters were examined. These analyses are helpful to explore the applicability of the model to real-world operations, by addressing the maximum BSS size to which the model can assist. Each configuration was run ten times. The average results for each config-uration is presented in Table 8.7. The grey colored cells mark configconfig-urations where the average computational time was higher than the defined reasonable time. The branching factor was fixed to five for the first branching step, and three for the second branching step.

The time horizon used as planning period in the subproblems is discussed by Fosen and Haldorsen (2019) and set to 25 minutes. In their work, this value proved to demonstrate the best balance between having a long planning period and maintaining a high marginal activity level.

From Table 8.7, we observe a clear trend of increased computational times by increased number of vehicles, holding all other parameters constant. The same trend is seen for the number of scenarios. Notably, the table also indicate low impact on the computational time when increasing the number of stations. This can be explained by the fact that the full set of stations in the BSS is only considered in the master problem of the heuristic, which is only solved once. In some cases, the computational time even decreases slightly when increasing the number of stations due to natural variance in the initialization. Further, the table shows that most grey cells, i.e. configurations with a higher average computational time than the reasonable time, occur when the number of scenarios and vehicles are close to the maximum tested value.

From the findings elaborated above, we construct a hypothesis that the computational time of the heuristic is heavily dependent on the number of created columns, i.e. the number of subproblems that is solved in the heuristic. Recall from Section 5.6 that a subproblem is solved for a specific vehicle, scenario, route, and pattern. Counting the total number of subproblems solved by the heuristic does however impose a challenge, as the cardinality of P^v, the number of patterns created for service vehiclev, may vary depending on the vehicle and start station inventories. Additionally, the cardinality ofR^v, the number of routes created for service vehiclev, depends on the number of stations that can be added to a route before reaching a total driving time larger than the planning horizon of 25 min-utes, i. e. the number of branching steps.

An upper bound for the number of subproblems solved by the heuristic may however be estimated by Equation (8.3). | V |and| F |are simply the number of vehicles and the number of subproblem scenarios that the heuristic is solved for. The constantB1represents the branching factor at the first branching point, whileB2denotes the branching factor at the second branching point. Later branching steps apply a branching factor equal to one.

Further,P is the number of extreme patterns in a route. Recall from Subsection 5.5.4 that the upper bound for this value when solving the DSBRCP is 45 patterns. When testing the

Table 8.7: Overview of average DSBRCP computational time in seconds for varying number of stations, number of vehicles, and number of subproblem scenarios. Combinations with average computational time higher than the defined reasonable time are marked in grey. The branching factor was fixed toB1= 7,B2= 3 andBn= 1for alln 3.

solution time, we made sure that all the instances reached this number of patterns through a careful choice of initial values. The presented values in Table 8.7 thus represent an upper bound for the computational time of the problem. Note that the number of stations in the instance,| S |is not included in the equation.

| V |⇥| F |⇥B1⇥B2⇥P (8.3) Equation (8.3) is used to estimate the number of subproblems solved by the heuristic for all instance configurations listed in 8.7. Figure 8.1 shows a plot of the computational time of each configuration by the estimated number of subproblems. From the plot, we observe a clear trend in increased computational time with higher estimated number of subprob-lems. Further, there seems to be a greater variance among the computational times for higher estimated numbers of subproblems. This may be due to differences in how the computational time of the master problem is affected by changes in| V |and| F |.

Figure 8.1: Computational time by estimated number of subproblems solved for the test instances presented in Table 8.7. The red line indicates the defined reasonable time.

Regarding computational time, it is important to note that the subproblems are indepen-dent of each other. Consequently, computations of the subproblems may be parallellized.

Parallellizing of the subproblems can improve the computational time of the heuristic sig-nificantly, without compromising the solution quality. Even though some of the computa-tional times in Table 8.7 exceed the defined reasonable time, we may therefore conclude that the DSBRCP heuristic has potential to assist in even larger sized BSS environments in terms of computational time than tested.