The multi-vehicle stochastic-dynamic inventory routing problem for bike sharing systems

We consider a BSS with stations \(n_i \in N, i>0\) and a depot \(n_0\). Every station n has an initial fill level \(f^n_0\), i.e., a specific number of bikes, and a maximum capacity \(c^n\). Over a time horizon T, users rent and return bikes altering the fill level of the stations spontaneously. At a non-empty station, rental demand can be served. At a non-full station, return demand can be served. If a demand is served, the station’s fill level is decreased, or increased, respectively. If demand fails, a penalty occurs and the user approaches an adjacent station.

Failed demand can be avoided by providing sufficient bikes and free bike racks at every station and every time. To this end, the dispatcher dynamically routes a fleet of transport vehicles \(V = \left\{ v_1,\dots ,v_{\text {max}}\right\}\). We assume the number of vehicles is determined by the tactical management and the drivers are already paid. Every vehicle starts at the depot, is initially empty, and has a capacity of \(c^v\). The travel time between two stations is given by function \(\tau (\cdot ,\cdot )\). The service time for relocation is \(\tau _r\) per bike.

Over the course of the day, the vehicles are subsequently sent from station to station to pick up or load bikes. Decision making therefore comprises a combination of routing to a station and loading operation at a station. Since new demand information reveals during travel, the loading operation is to be reconsidered, once a vehicle arrives at a station. The service provider aims on maximizing the users’ satisfaction based on the limited resources accessible. Therefore, the goal is to minimize the expected failed demand per day.

In the following, we model the problem as an MDP. An MDP is a framework for stochastic-dynamic optimization problems (Puterman 2014). We extend the single-vehicle Markov decision process of Brinkmann et al. (2019). Equation (1) depicts the components of an MDP:In an MDP, a sequence of decision states \(s_k\) occurs over time. In a decision state, a decision x is selected leading to a post-decision state \(s^x_k\). Based on post-decision state \(s^x_k\), a transition \(\omega\) leads to a new decision state \(s_{k+1}\). In the following, we define the MDP components for the SDIRP. The notation is given in Table 1.

In Fig. 1, we give an example of the MDP. On the left-hand side, decision state \(s_k\) is depicted. The center shows post-decision state \(s^x_k\). The following decision state \(s_{k+1}\) is depicted on the right-hand side. The system has four stations \(n_1\), \(n_2\), \(n_3\), and \(n_4\). The depot is neglected. Two vehicles \(v_1,v_2\) are given. For the stations and vehicles, light boxes represent empty bike racks, dark boxes represent bike racks filled with a bike. Stations \(n_1\) and \(n_2\) have a capacity of five racks, station \(n_3\) of three, and station \(n_4\) of four racks. The vehicle capacities are four.

Decision point k is induced due to vehicle \(v_1\)’s arrival at station \(n_1\) in time \(t_k = 12\). In the associated decision state \(s_k\), stations \(n_1\) and \(n_4\) contain \(f^{n_1}_k=f^{n_4}_k=4\) bikes, \(n_3\) contains \(f^{n_3}_k=2\) bikes, and \(n_2\) is empty, \(f^{n_2}_k=0\). Vehicle \(v_1\) is located at \(n^{v_1}_k=n_1\). It just arrived at this station. Thus, the arrival time is \(\alpha ^{v_1}_k=t_k=12\). The current fill level of vehicle \(v_1\) is \(f^{v_1}_k=1\). Vehicle \(v_2\) travels to station \(n_4\) and arrives in nine time units. It has loaded one bike. Thus, the vector for vehicle \(v_2\) reads \((n_4,21,1)\).

The inventory decision is made about how many bikes to pick up at or to deliver to station \(n_1\) by vehicle \(v_1\). The routing decision is made about which station to serve next, or idling at the current station. Here, the applied decision is \(x=(-2,n_2)\): picking up two bikes and travel to \(n_2\). Assuming \(\tau _r = 2\) units, two pick ups consume four time units. Furthermore, assuming travel time of \(\tau (n_1,n_2) = 20\), the decision consumes 24 time units in total. Finally, vehicle \(v_1\) arrives at station \(n_2\) in \(t_k + |\text {-}2| \cdot \tau _r + \tau (n_1,n_2) = 12 + 4 + 20 = 36\). The updated vector is \((n_2,36,3)\).

The resulting post-decision state \(s^x_k\), including the decisions made, is depicted in the center of Fig. 1. The next decision point \(k+1\) occurs at \(t_{k+1}=21\) because vehicle \(v_2\) arrives at station \(n_4\): \(\alpha _{k+1}^{v_2} = t_{k+1} = 21\).

Before the associated decision state \(s_{k+1}\) occurs, the transition \(\omega\) reveals new fill levels and a realization of the penalty function. New fill levels are revealed at \(n_1\) and \(n_3\) due to successful requests. At \(n_1\), the fill level has increased by one. At \(n_3\), the fill level has decreased by one. Station \(n_3\) remains empty and station \(n_4\) remains full. For the purpose of presentation, the customer trips are not depicted in Fig. 1. We assume that one rental demand failed at \(n_2\) and one return demand failed at \(n_4\) resulting in a realized penalty of \(p(s_k,x,\omega ) = 2\). The resulting new decision state \(s_{k+1}\) is shown on the right-hand side of Fig. 1.

An optimal policy as defined in the objective function (2) relies on the Bellman equation (3). It minimizes the penalties over the current and all future decision points:Applying the Bellman equation in decision point k results in evaluating future decision points \(k+1 , \dots , k_{\text {max}}\) and the associated decisions \(x \in X\). This results in evaluating almost every potential decision state \(s \in S\) and is usually computationally intractable even for smaller problem instances. In the following, we demonstrate the state space dimensionality of the SDIRP by investigating an upper bound of the state space’s size |S|:The resulting upper bound reads as follow:The upper bound ignores the interdependencies between the fill levels of stations (and vehicles) due to the given number of bikes in the system. However, it indicates that calculating optimal policies by means of dynamic programming is computationally intractable even for smaller systems. To this end, we draw on a heuristic in the next section.

The SDIRP is dynamic because of the spontaneity in user demand. A suitable method is required to coordinate the fleet of vehicles effectively, reacting to current demand and anticipating potential future demand.

Coordination manifests in the routing decision of the MDP. In the routing decision, the potential movement of the other vehicles needs to be considered. To highlight the importance of coordination, we show a (simplified) example in Fig. 2. The figure consists of three parts depicting different routing decisions for the same situation. Two empty vehicles and two full stations are given. We assume the travel time of vehicle \(v_1\) to station \(n_1\) is 12 min, to station \(n_2\), the travel time is 10 min. The travel times for vehicle \(v_2\) are 25 min to station \(n_1\) and 15 min to station \(n_2\).

In the situation, we need to route \(v_1\). We assume that \(v_2\) will require a routing decision a very short time later. A potentially good decision is depicted in Fig. 2a, sending \(v_1\) to \(n_1\) and \(v_2\) to \(n_2\). The decision leads to relatively short travel times and the vehicles arrive early to balance the stations and to avoid unmet demand.

Without coordination, we observe different decisions. The first (most obvious) decision is depicted in Fig. 2b. If we only focus on the current vehicle and ignoring the other vehicles in the decision process, both vehicles may eventually approach the same station. We first send \(v_1\) to \(n_2\) (ignoring \(v_2\)) and a short time later, we send \(v_2\) to the same station (ignoring \(v_1\)).

However, coordination should not be restricted to avoiding vehicles approaching the same station, as shown in Fig. 2c. In this decision, \(v_1\) is sent to its individual “best” station and a short time later, \(v_2\) is sent a long way to the remaining “best” station. As the example shows, this procedure may be inferior because other vehicles may travel unnecessarily long distances within the city.

Coordinating the fleet allows to effectively assign vehicles to stations avoiding unnecessary long travel. To achieve coordinated routing decisions, our method determines the potential for every vehicle to avoid failed demand for every station. Based on the estimation, it then determines the assignment for vehicles to stations and selects the routing decision accordingly. The method only implements the assignment only for the vehicle under consideration. The assignments for the other vehicles can be reevaluated later in the process based on new observations.

To estimate the potential for a vehicle to avoid unsatisfied demand at the current station and all other stations, anticipation of future demand is necessary. Anticipation indicates stations which are likely to run out of bikes or congests.

In the following, we present the details of the algorithm. We first describe how we estimate the future failed demand for the stations. We then present the procedures to determine inventory and routing decisions.

Our policy requires a measure to calculate the expected failed demand for stations. To this end, we use historical trip data to successively update the fill levels of stations. The updates may lead to accumulations of failed demand for each station. The failed demand measured can then be used in the decision making of our policy. As previous research has shown, there is benefit to limit the horizon (Brinkmann et al. 2019) because it balances the urgency of near-future demand with longer term demand. Thus, we limit the horizon in state \(s_k\) to \(\delta\) minutes.

We calculate the average difference of rented and returned bikes per minute \(\varDelta ^n_t \in {\mathbb {R}}\) for each station n and minute t. These values can be precomputed based on historical data and allow instant decision making in a real-time decision state. A negative value of \(\varDelta ^n_t\) indicates that in minute t at station n more bikes are rented than returned. A positive value indicates that more bikes are returned than rented. For a station n at time \(t_k\) with fill level \(f^n_{t_k}\), we can then calculate the fill level development over time as follows:The fill levels are altered minute by minute with respect to the average difference in demand per minute. The fill levels always stay in the range between zero and the maximum capacity. Based on this development, we calculate the cumulated amounts of failed return demand \(\gamma ^+(n)\) and of failed rental demand \(\gamma ^-(n)\) for station n. Value \(\gamma ^+(n)\) is calculated as follows:In minute t, a failed return demand occurs if the sum of current fill level and return demand exceeds the station’s capacity. Analogously, the failed rental demand can be calculated:The values can now be used in our inventory decision \(\iota\) and routing decision \(\rho\) of our MDP.

In the first step, the CLA determines the inventory decision \(\iota\). We reduce the set of inventory decisions to evaluate because the set of potential fill levels is very large and the runtime is limited. Here, we draw on the percentages \(\mu _1=25\%\) (low), \(\mu _2=50\%\) (medium), and \(\mu _3=75\%\) (high) leading to the target fill levels \(\mu _1 \cdot c^{n^v_k}\), \(\mu _2 \cdot c^{n^v_k}\), and \(\mu _3 \cdot c^{n^v_k}\). With respect to the vehicle’s capacity \(c^v\) and load \(f_k^v\), we may not be able to realize the target fill levels as described. If necessary, we modify the target fill levels and derive the corresponding relocations \(\iota _1\), \(\iota _2\), and \(\iota _3\) according to Eq. (8):The first case occurs when bikes need to be delivered to the station. Then, we limit the number of bikes to the vehicle’s load. In the second case, bikes need to be picked up. Here, the equation ensures that the number of loaded bikes does not exceed the vehicle’s capacity. The third case occurs if the station’s fill level is equal to the predetermined target fill level and therefore no relocations need to be done.

As an example, we consider a station \(n^v_k\) with capacity \(c^{n^v_k}=20\) bikes. The current fill level is \(f_k^{n^v_k}=10\) bikes. The vehicle v has currently loaded \(f_k^v=2\) and a capacity of \(c^v=20\) bikes. The three relocation decisions aim on fill levels of \(25\% \cdot 20=5\), \(50\% \cdot 20=10\), and \(75\% \cdot 20=15\) bikes. The first fill level can be achieved by removing 5 bikes from the station, \(\iota _1 = -5\). The second fill level can be achieved by maintaining the fill level, \(\iota _2=0\). The third fill level cannot be achieved, because only \(f_k^{n^v_k}+f_k^v=12\) bikes are available. Thus, with respect to Eq. (8), the third relocation decision is \(\iota _3 = 2\).

For each inventory decision \(\iota _i\), we now can determine the expected failed demand at that station as described above. Because the failed demand depends on decision \(\iota _i\), we denote the values \(\gamma ^-(\iota _i,n^v_k)\) and \(\gamma ^+(\iota _i,n^v_k)\). Based on the cumulated values of \(\gamma ^-(\iota _i,n^v_k)\) and \(\gamma ^+(\iota _i,n^v_k)\) for \(\iota _i \in \{\iota _1,\iota _2,\iota _3\}\), we select \(\iota ^\star\) minimizing the sum of failed demand:

In the second step, the CLA determines the routing decision \(\rho\) for the current vehicle in coordination with the other vehicles. In the following, we anticipate the prevented failed demand for pairs of stations and vehicles. We then describe how we coordinate the routing based on these values.

To derive the failed demand a vehicle can prevent at a station, we follow the same procedure as discussed in Sect. 4.2. The only difference is that the vehicles have different arrival times at stations and different fill levels. Mathematically, we determine for every station n the failed demand a specific vehicle v can prevent as follows. In time \(t_k\), a vehicle v, which arrives in time \(\alpha ^v_k\) minutes at station \(n^v_k\), can reach station n at earliest at time \(\alpha ^v_k + \tau (n^v_k,n)\). Thus, we consider for v only the failed demand at n in the time interval \({\mathcal {I}}^{n}_v=\left[ \alpha ^v_k + \tau (n^v_k,n) , t_k+\delta \right]\) where \(\delta\) depicts the length of the considered horizon. Let \(\gamma ^-(n,v)\) and \(\gamma ^+(n,v)\) be the failed rental and failed return demand at stations n occurring in this interval \({\mathcal {I}}^{n}_v\). Again, we need to consider the vehicle’s capacity \(c^v\) and load \(f^v_k\). Then, the prevented failed demand if vehicle v is sent to station n can be calculated as follows:Figure 3 provides an example. The lookahead starts at 14:30 h and is limited to \(\delta =360\) min. We successively update the station’s fill level as described and observe the fill level and cumulated failed demand at station n. The fill level is represented by the solid line. We see that the fill level decreases due to rental demand. Just before 16:00 h, the station runs out of bikes. From that time on, the cumulated failed demand, indicated by the dashed line, increases because rental demand cannot be satisfied any more. If vehicles \(v_1\) or \(v_2\) are sent to n, they arrive earliest at 15.00 h, or 15.30 h, respectively. Both vehicles arrive early enough before any demand fails. Vehicle \(v_3\) arrives earliest at 16.30 h. This results in failed demand of about 3.5 rentals between 16:00 and 16:30 h. Given the three vehicles have the same capacity and load, the values for \(v_1\) and \(v_2\) are the same and both are higher than the value for \(v_3\): \(\gamma (n,v_1) = \gamma (n,v_2) > \gamma (n,v_3)\).

Only considering the demand at station n in the example in Fig. 3, it is beneficial to send either \(v_1\) or \(v_2\) to this station. However, looking at the demand at all stations, it might be beneficial to send \(v_3\) to n if \(v_1\) and \(v_2\) can prevent more demand at other stations. To consider these interdependencies, we assign every vehicle to a station. Although we only decide about the routing for the current vehicle, we make a preliminary, tentative decision for every other vehicle as well.

To coordinate the dispatching of the vehicles, we have to solve an assignment problem. The goal is to maximize the prevented failed demand over all stations. The constraint is that every vehicle is assigned to one station and every station is assigned at most to one vehicle. In the following, we formally define the assignment problem.

We define decision variables \(y_{ij} \in \{0,1\} \; \forall n_i \in N,v_j \in V\) to indicate the assignments of stations to vehicles in Eq. (11):Value \(\gamma (n_i,v_j)\) indicates the amount of prevented failed demand at station \(n_i\) if it is assigned to vehicle \(v_j\). Then, the problem can be defined as follows:subject toIn the objective function (12), the amount of prevented failed demands over all stations and vehicles is maximized. In constraints (13) and (14), we ensure that every station is assigned to at most one vehicle, or every vehicle is assigned to one station, respectively.

We apply the heuristic matrix maximum approach to solve the assignment problem: The values of \(\gamma (n,v)\) for all vehicles and stations lead to a matrix \(\varGamma\). Each row indicates a station and each column a vehicle. Let v be the vehicle we need to route in the current decision state. We iteratively search the entry with the maximum in \(\varGamma\). Let \(\gamma (n_i,v_j)\) be this entry. If \(v_j = v\), we stop the procedure and send vehicle v to station \(n_i\): \(\rho ^\star = n_i\). Else, if \(v_j \ne v\), we remove row i and column j of matrix \(\varGamma\). We remove row i to ensure that we do not route our vehicle to \(n_i\) because vehicle \(v_j\) is the best assignment for this station. We remove column j to ensure that \(v_j\) is not sent to another station for the same reason. We repeat the procedure until the maximum \(\gamma (n_i,v_j)\) refers to vehicle v, i.e., \(v = v_j\). Then, we choose \(n_i\) to be vehicle v’s next station: \(\rho ^\star = n_i\).

Notably, even though the approach is greedy, it performs comparably well. Experiments show that solving the deterministic-static assignment problem to optimality even decreases the solution quality of the SDIRP (compare Appendix A.2). As for many dynamic problems, these results confirm the observation that solving static subproblems to optimality in a dynamic context is often not beneficial (Powell et al. 2000; Maggioni and Wallace 2012). One reason is that optimal solutions for static problems usually do not yield any flexibility to react to future information changes, as for the SDIRP, changes in \(\varGamma\).

Eventually, the CLA selects the inventory decision \(\iota ^\star\) of Sect. 4.3 and the routing decision \(\rho ^\star\) of Sect. 4.4.

In the following, we define our benchmark policies. Our CLA draws on two components: anticipation of future developments and coordination of the fleet. We design our benchmark policies with respect to these components.

The first benchmark policy draws on the lookahead as described in Sect. 4 but ignores coordination of the vehicles. We denote this policy CLA-NC for no coordination. This policy ignores information on other vehicles and sends vehicle v to the station where this vehicle can prevent as much demand as possible:The second benchmark ignores anticipation but draws on safety buffers to determine if a station needs to be visited (Brinkmann et al. 2015). We denote this policy as the short-term relocation policy (STR). A threshold percentage \(\beta\) of the stations’ capacity is defined a priori. If a station n has less than \(\beta \cdot c^n\) bikes or free bike racks, the safety buffer is violated and the station is denoted to be imbalanced. The inventory decision \(\iota\) is determined as the difference between the current fill level and the safety buffer. For balanced stations, the inventory decision is \(\iota =0\). Routing decision \(\rho\) selects the nearest imbalanced station. Stations where another vehicle is currently located or approaching are excluded from consideration. The third benchmark policy STR-NC follows the same procedure but ignores coordination. Thus, several vehicles may be sent to the same imbalanced station. Policy STR-NC can be seen as the basis benchmark policy because it neither considers anticipation nor coordination.

We tune the policies as follows. For the CLA and the CLA-NC, we test horizons of \(\delta \in \{60,120,\dots ,720\}\). For STR and STR-NC, we select \(\beta \in \{0.1,0.2,\dots ,0.5\}\). For every instance setting, we run all parametrizations over 1, 000 test days and select the best \(\delta\) and \(\beta\) for our experiments. The parameters can be found in Tables 2 and 3 in Appendix A.2.

In this section, we describe the instances for the SDIRP based on real-world data. We draw on the data of the BSSs in Minneapolis (MN, USA, Nice Ride 2016) and San Francisco (CA, USA, Ford GoBike 2017). The providers frequently publish data sets providing information on trips. Every trip comprises a rental and return station and the corresponding rental and return times. The data sets are preprocessed as proposed by Vogel et al. (2011):

We only draw on week days because the customer demand significantly differs on weekends. We further remove all trips that start and end at the same station and take less than 1 min. In these cases, we assume a user has returned the bike immediately due to some defect and, thus, no real trip takes place. We draw on 88 working days in the summer months from July to October in 2015 for Minneapolis. The preprocessed data set consists of 197,726 trips occurred at 169 stations. The station capacities differ between 15 and 35 bike racks. 2246 trips take place per day on average. Ford GoBike BSS consists of three disjoint subsystems East Bay, San Francisco, and San José. We only draw on the San Francisco subsystem. For San Francisco, we select 89 working days in the summer months July to October in 2014. The data set consists of 100,728 trips after cleaning. The 35 stations have capacities between 15 and 27. 1131 trips take place per day.

We use data sets as foundation for the average differences of rented and returned bikes per station and minute. In our simulation, we discretize one day into \(24 \cdot 60 = 1440\) min. Therefore, time horizon T comprises 1440 individual points in time t. Then, we determine \(\varDelta _t^n, \forall n \in N, t \in T\) as the average differences of rented and returned bikes per minute and station.

Figure 4 depicts the temporal distributions of trips in the course of the day. The solid line refers to the average number of trips in Minneapolis, the dashed line refers to San Francisco. Both BSSs have peaks in the morning, around noon, and in the evening. In Minneapolis, the second and third peak are higher than the previous ones. In San Francisco, the amplitudes of the morning and evening peak are more equal. The noon peak is much lower. In both systems, the morning and evening peaks are likely to represent commuters. In the morning, commuters rent bikes in residential areas and return them in working areas. In the evening, bikes mainly are rented in working areas and returned in residential areas. The noon peak is likely due to leisure and shopping activities. As stated by O’Brien et al. (2014), leisure usage is significant in Minneapolis.

The preprocessed data sets serve as foundation for the actual instances. For each test day, we randomly draw trips with replacement from the associated data sets. We draw 2246 trips for Minneapolis, and 1126 for San Francisco. The combination of real trips from different days lead to new, artificial days. Further, we assume the ratio of bike racks over all stations and bikes within the system to be 2:1 (which is a common ratio in practice, O’Brien et al. 2014). In the beginning of the time horizon, we distribute the bikes randomly over all stations. Here, we use a uniform distribution. For each instance setting, we generate 1000 test days following this procedure. We test every instance setting for every BSS and for fleet sizes between 1 and 4 vehicles. Every vehicle has a capacity of 20 bikes. The vehicles travel on Euclidean distances between the stations with a speed of 15 km/h. This relatively slow speed accounts for potentially longer travel distances due to the road network. We assume a relocation time of 2 min per bike, i.e., \(\tau _r = 2\).

In Appendix A.1, we go into detail with the user behavior we have implemented in case of failing demand.

Every combination of instance, fleet size, and policy demands a special different tuning. In Appendix A.2, we provide information on the tuning parameters and the achieved failed demand of the solutions.

Here, we compare the solution qualities of the four policies. To this end, we calculate the improvement ratio of a policy \(\pi\) to the basic benchmark STR-NC for every instance setting. Let \({\mathcal {Q}}(\pi )\) denote the average failed demand of policy \(\pi\). The improvement ratio is then calculated as:The improvements of policies STR, CLA-NC, and CLA over STR-NC are shown in Fig. 5. The x-axis shows the policies. The y-axis shows the improvement ratio. The dark bars refer to Minneapolis and the light bars refer to San Francisco. We observe that all three policies significantly improve the solution quality compared to the basic benchmark policy STR-NC. The proposed policy CLA achieves the highest solution quality. Also STR achieves significant improvements against STR-NC. Thus, even without anticipation, coordination is valuable. We further observe very significant improvements for both CLA-NC and CLA up to \(55.0\%\), or \(65.3\%\), respectively. We also see that anticipation is more important for San Francisco while coordination is more important for Minneapolis: the difference between STR and CLA is significantly higher for San Francisco while the difference between CLA-NC and CLA is significantly higher for Minneapolis. We will analyze these observations in more detail in the following.

First, we analyze how anticipation impacts the solution quality. To this end, we calculate the improvement ratio of CLA compared to STR for both BSSs and for fleet sizes of 1–4. Both policies coordinate their fleet. The improvement ratio is shown in Fig. 6. We observe that for every instance setting, an improvement of at least \(20\%\) can be achieved. Further, the improvement is significantly higher in San Francisco. As mentioned before, San Francisco shows a stronger commuter behavior than Minneapolis. Thus, trips are more predictable for San Francisco and anticipation becomes more reliable. This explains the high improvement ratios for San Francisco.

We now analyze the impact of fleet coordination. To this end, we calculate the improvement ratio of CLA compared to CLA-NC. Following the structure of Fig. 6, the results are shown in Fig. 7. We omit the results for tests with a single vehicle because in that case coordination does not effect decision making. In Minneapolis, the coordinated dispatching achieves improvement ratios of \(20.9\%\), \(35.4\%\), and \(44.3\%\) for 2, 3, and 4 vehicles. In San Francisco, the improvement ratios are \(10.7\%\), \(31.3\%\), and \(30.2\%\). As assumed, we observe that coordination becomes more important with increasing number of vehicles. We also observe that for Minneapolis coordination is more important than for San Francisco. The BSS of San Francisco is dominated by commuters: many customers demand rentals and returns at a distinct set of stations at specific times. Thus, the impact of sending vehicles in the same direction without coordination is not as severe compared to Minneapolis where demands are more equally distributed and coordination is crucial.

In our main experiments, we have shown that coordination is essential for successful operational control of the fleet. In the following, we analyze the impact of coordination in more detail. The CLA solves an assignment problem but implements the assignment solution for the current vehicle only. The assignment problem incorporates the potential of all vehicles in the routing decision for the current vehicle. The only partial implementation of the assignment solutions maintains flexibility to react to realized demand later in the process. To show the importance of the assignment problem and the partial implementation, we run experiments with two different coordination degrees:We test the different degrees for both systems and for 2, 3, and 4 vehicles. We benchmark the results with the CLA-NC. The improvements for the different degrees are depicted in Fig. 8. The x-axis depicts the different degrees of coordination. Our CLA as described in Sect. 4.4 is indicated by ’Partial Assignment’. The y-axis shows the improvement over the no coordination policy CLA-NC for the systems of San Francisco and Minneapolis.

We observe that all three coordination methods add significant benefit in comparison to solutions without coordination. CLA with partial assignments outperforms the other coordination degrees. Particularly, committing to the complete assignment decision for all vehicles lead to inferior results. This confirms that the high volatility in customer demand impedes long-term planning for both systems.