An Agent-Based Fleet Management Model for
First- and Last-Mile Services

The data used in this study is from the Bengaluru city metro transit network that consists of 40 stations on the East-West corridor (Purple Line) and the North-South corridor (Green Line). The East-West corridor extends from Baiyappanahalli in the East to Mysore Road terminal in the West, while the North-South corridor extends from Nagasandra in the North to Yelachenahalli in the South as shown in Figure 1. The data includes train start times at these four reference stations and headway that varies by the time of the day. Using this information and the time taken for a train to travel from one station to the next, we estimate the train arrival times at every station. During peak hours, the frequency of metro trains is in the range of 3–6 minutes, while the off-peak frequency is 15–30 minutes. The average ridership per day is approximately 726,000 (pre-COVID).

The transit demand data consists of monthly count of passengers entering and exiting these 40 stations for different hours of the day, from 5 AM to 11 PM. We first compute the number of passengers alighting at a station from each train by dividing the demand data by the number of days in the month. We assume that 10% of this demand equals the mean value of the last-mile passenger count. The actual number of last-mile passengers arriving at different stations is simulated according to a Poisson distribution. For the first-mile scenario, we use 10% of the hourly count of passengers entering the metro stations (as obtained from historical data) and generate their departure times within each hour using a uniform distribution. For passenger origins and destinations, we use census data of Bengaluru consisting of enumeration blocks (EBs) and their population. The centroids of these EBs serve as proxies for locations of first- and last-mile trips, respectively. The probability of choosing a location (centroid) is assumed to be proportional to the population of the EB to which it belongs. Currently, there are no centralised FLM providers, and hence we did not have data on the exact percentage of riders who might be interested in such services. We also could not simulate different trip types (e.g., work-based, recreational), which produce different patterns for FLM demand and their origin/destination locations. In the future, this kind of data could be sourced from surveys to get more realistic estimates.

Only those EBs in Voronoi regions within a radius of 500 m to 5 km from the metro stations are considered. The Voronoi polygon of a particular station contains points closest to it (measured using the haversine distance) compared to any other station. If the roadway network is sparse, the shortest path lengths along the network could be used instead of haversine distances while constructing the Voronoi regions. For distances less than 500 m, we assume that passengers prefer walking, and for locations farther than 5 km, passengers are assumed to use other direct modes of travel. FLM vehicles assigned to a metro station are only assumed to serve locations in the corresponding Voronoi polygon.

We extract the metro network, i.e., the two transit lines and 40 metro stations, using the Overpass API of OpenStreetMap, and convert it into GeoJSON and shapefiles. Figure 1 shows a QGIS snapshot of the Bengaluru metro transit network and the Voronoi regions along the Purple and Green Line. The enumeration blocks are shown in grey colour. The outer boundary on the map indicates the city planning limits. The Nagasandra station, located at the end of the North-South corridor, can serve more demand from the city’s suburbs, but the EB data was available only within the city limits.

Figure 2 shows a screenshot of the AnyLogic simulator. The FLM vehicles are routed using the shortest paths from the OSM server. The travel times on the road network are assumed constant based on the average speed of vehicles in Bengaluru and the length of the links.

We currently do not assume time-of-day variations in network travel times. The waiting time calculation begins when a passenger makes an FLM request until a vehicle is available for boarding. Walking time to the parking lot is ignored. However, extending the simulator to capture these features using more realistic data is straightforward.

This section describes the model components of the proposed simulator. We use a combination of agent-based and discrete-event modelling paradigms. Agent-based modelling involves multiple decentralised entities (called agents) who interact with each other within a simulation environment (Crooks and Heppenstall, 2012). These agents represent real-world entities and can either be fixed in position (such as metro stations) or exhibit movement (such as people and vehicles). Agent behaviour is modelled using statecharts where each state represents a situation during the life cycle of an agent (Greenlaw and Liang, 2003). When an agent is in a specific state, it can perform a certain action(s) or wait for an event or timeout. The properties of agents can be specified using parameters and variables. Any action agents take within a state can be modelled using functions. A state change occurs at the onset of a certain event or when a certain condition holds and is modelled using transitions. Transitions can be triggered by a timeout, rate, message, agent arrival, or when a certain user-defined condition is true. Communication between agents is modelled using messages. The message object and destination agent to whom the message is to be sent must be provided while designing the state chart. As soon as the destination agent receives the message, a set of necessary actions can also be specified. Additional details specific to AnyLogic are provided in Appendix A.

Figure 3 shows an overview of the simulation architecture, including the different data sources used and the flow of execution for both first- and last-mile scenarios. Table 1 gives a brief summary of agents used in the proposed model. All agents reside in Main, which can be viewed as the top-level agent. For the last-mile scenario, we define the timestamps at which trains arrive at the reference stations. At each of these timestamps, an event eventTrainArrival is triggered, which creates an instance of the agent type MetroTrain. This event can occur at an absolute model time or a specific date and time, as in our case. Next, an event eventPassengerArrival gets triggered at each subsequent metro station at the specified arrival time. For the first-mile case, the eventPassengerArrival is triggered randomly on an hourly basis.

We now describe the Vehicle and LastMilePassenger agents in detail, along with their statecharts. The statechart for first-mile passengers is modelled similarly.

Vehicle agent: Figure 4 describes the statechart of a Vehicle agent. Initially, all FLM vehicle agents are positioned at the metro stations. We first describe the last-mile scenario. A state transition from AtMetroStation state to MovingToDestination happens when the FLM vehicle agent receives a message of the type LastMileTrip that stores information on the last-mile passenger, including their origin station and destination. After receiving this information, the FLM vehicle agent moves to the corresponding destination along the OSM road network, and the vehicle is in the MovingToDestination state. A transition to the Offboarding state occurs by the transition type agent_arrival, which signifies that the FLM vehicle agent has reached the passenger’s last-mile destination. Following a timeout, the FLM vehicle agent moves back to the station in the MovingToStation state. State transition from MovingToStation to AtMetroStation occurs via agent_arrival transition type.

For the first-mile scenario, state transitions take place from AtMetroStation state to MovingToOrigin when a FLM vehicle receives a message of the type FirstMileTrip. On arriving at the origin of a first-mile passenger, the FLM vehicle goes into the Pickup state. Once the first-mile passenger has been picked up, the FLM vehicle agent transitions to the MovingToStationFull state and then back to the AtMetroStation state.

Passenger agent: Last-mile passengers alighting at metro stations are modelled as LastMilePassenger agents. Their behaviour is captured using the passenger statechart shown in Figure 5. After alighting from the train, each last-mile passenger requests an FLM vehicle in the GenerateVehicleRequest state, and the associated timestamp is recorded. We also maintain a station-wise FIFO queue of passengers containing those who request an FLM service. A decision branch checks the availability of FLM vehicles at the metro station.

If a vehicle is available, the passenger enters the TripRequestAccepted state. In this state, the passenger is removed from the request queue, and the event eventTrip gets triggered. eventTrip creates an instance of a LastMileTrip agent, assigns vehicles to passengers in a FIFO manner, and sends a message containing the passenger origin station and destination information to the Vehicle agent. The Vehicle agent receives this message through its connections, and the message is then forwarded to its statechart. The passenger then goes into the Travelling state until their destination is reached.

If an FLM vehicle is unavailable, the passenger goes into the WaitForAssignment state. If the total waiting time exceeds a threshold parameter maxWaitingTime, it is marked as lost demand, and the passenger is removed from the request queue. Otherwise, they retry requesting a vehicle and go to the GenerateVehicleRequest state again, and the process is repeated.

The scenario described thus far where rides are not shared is considered the base case. Additionally, we model and simulate situations where passenger requests can be pooled together, and an FLM vehicle can serve multiple passengers in a single trip. The following subsections describe these scenarios in detail.

We develop an optimisation model for the no-sharing case using the Custom Experiment functionality in AnyLogic and implement it using its Java API and the OptQuest optimisation engine. Custom Experiment offers flexibility for setting up model parameters, seed value, solver run time, and simulation run properties such as start and stop time. During a simulation-based optimisation experiment, multiple simulation runs are carried out by varying the values of decision variables while respecting the specified constraints. For reproducible model runs, it is necessary to reset the seed to a fixed value at the beginning of every iteration.

The objective in our model was to minimise the total expected lost demand $l_{s}$ as shown in Equation (1). Here, $S$ denotes the set of metro stations, and $s$ represents the index of a station. The decision variables are the number of FLM vehicles assigned to each station, represented by $x_{s}$. We assume a fixed fleet size, and hence the total number of FLM vehicles cannot exceed $a^{total}$ as shown in (2). Equation (3) specifies the upper and lower bounds on the number of vehicles positioned at individual stations, denoted by $a_{s}^{min}$ and $a_{s}^{max}$, respectively. Such bounds could be imposed for reasons associated with parking and equity.

We observed that the time taken by OptQuest to complete a single iteration increases substantially in the last-mile and joint shareability case due to function calls to OR-Tools for solving the CVRP. However, note that the objective function can be decomposed by stations, and only Constraint (2) binds the decision variables. It is expected that as the number of FLM vehicles assigned to a station increases, the lost demand will decrease. Thus, this relationship is likely to be decreasing (and in most cases convex, with diminishing returns for every extra vehicle).

At each station, we interpolate the expected lost demand using simulation runs performed at uniformly discretised supply values (or break points) as shown in Figure 8. With such lost demand curves for each station as problem input, we propose a piecewise linear cost approximation for the objective and formulate it as an Integer Linear Program (ILP), which is solved using CPLEX. The ILP model uses auxiliary variables and has an objective that is separable with respect to the supply at stations.

Let the piecewise linear function of station $s$ be described using function values $l_{s}(a_{is})$, where $a_{is}$ is the $i^{th}$ break point at which the simulation is performed. Let the number of pieces in the lost demand curve for station $s$ be $k_{s}-1$. Define $\lambda_{is}$ as the weight placed on the break point $a_{is}$. Let $y_{is}$ be one if the optimal solution for station $s$ lies in piece $i$.

The number of FLM vehicles assigned to a station $s$ is represented as $\sum_{i=1}^{k_{s}}\lambda_{is}a_{is}$ and hence Constraint (6) ensures that the total supply is not exceeded. The optimal supply for a station $s$ must lie in one of the pieces, which is enforced by (7). The actual supply value is determined by a convex combination of the $\lambda$s using (8). If the $y$ variable is 1, only the $\lambda$s associated with its endpoints must take non-negative values. This constraint is enforced by (9)–(11). Finally, (12) and (13) impose bounds and integrality constraints. We do not require constraints to model (3) in this formulation because they are implicitly set by $a_{1s}$ and $a_{k_{s},s}$.

The proposed ILP can be solved reasonably quickly using off-the-shelf solvers. However, the major bottleneck is in estimating the lost demand at the break points using simulation. This problem can be addressed by starting with a coarse set of break points and iteratively generating new ones. To illustrate this idea, consider the example in Figure 9. Suppose that for a station $s$, the lost demand was estimated at two break points $a_{1s}$ and $a_{6s}$. We approximate the lost demand curve as shown by the thick line segments in the left panel. Suppose the resulting optimal ILP solution lies in the interval $[a_{3s},a_{4s}]$. Additional simulations are then run to estimate the lost demand at the endpoints $a_{3s}$ and $a_{4s}$, and the lost demand curve is updated with more pieces as shown in the right panel. If both endpoints of the optimal solution are already explored, we stop. If not, we perform new simulations at new break points, update lost demand curves, and repeat. If the ILP solution coincides with the break point, say $a_{3s}$, we explore its neighbours $a_{2s}$ and $a_{4s}$. This adaptive procedure was found to reduce the number of break points and simulations by nearly 50%.

We benchmark our proposed method for fleet allocation by comparing it with two baseline strategies and the OptQuest solver.

Baseline Strategies: Two simple strategies that could be used by an operator in the absence of an optimisation model were simulated. In the first strategy (proportional to demand), we try to achieve a supply allocation proportional to the total first- and last-mile demand. However, since the number of vehicles allowed at each station is capped at 60, vehicles in excess of this value are again redistributed among the remaining stations, proportional to their corresponding demand and the process is repeated until all 1200 vehicles are assigned. In the second case (equal supply), we simply allocate an equal number of FLM vehicles (i.e., 1200/40 = 30) at each metro station. The results for all four shareability scenarios are shown in the first two columns of Table 2. The values in brackets show percentage benefit compared with the proportional to demand strategy. Assigning an equal number of vehicles across stations resulted in higher lost demand in all shareability scenarios.

OptQuest: The optimal fleet allocation problem was also solved using AnyLogic’s in-built OptQuest solver with a time budget of 24 hours. The solver was initialised with 30 vehicles at each station. For the no sharing case, a total of 1235 iterations were simulated, but the best-found solution’s objective was 17,854, which was 19.4% worse compared to the proportional to demand case. The quality of solutions discovered for the shareability scenarios was also poorer compared with the proportional to demand case, mainly because each of these iterations runs slower when sharing is involved. Hence, only a limited portion of the feasible region is explored.

ILP Model: As described in Section 3.4, we discretised the feasible region and ran simulations by varying the number of vehicles at each station from 5 to 60 in increments of 5 and estimated the expected lost demand. For the adaptive piecewise approximation method, only 247 out of 480 simulations (40 stations with 12 break points at each station) were needed to find the optimum supply values. Figure 10 compares the lost demand for different shareability scenarios for one of the metro stations – Indiranagar. The joint FLM shareability case results in significantly lower lost demand for all supply values. Similar trends were observed at other stations. The average number of simulated first- and last-mile passengers in this scenario was 36,664 and 36,994, respectively.

These curves were used as input to the ILP formulation (5)–(13), which was solved using CPLEX. The optimal decision variables, i.e., the number of FLM vehicles at every station, were passed to the AnyLogic simulation, the results of which are shown in the last column of Table 2. The CPLEX runtimes in all four shareability scenarios were less than a minute. The estimated lost demand for the baseline strategies and ILP model are average values from five simulation runs.

Overall, the ILP model solution consistently resulted in lower lost demand and outperformed the other allocation methods for all shareability scenarios. Specifically, for the joint FLM shareability case, improvements of 65% and 26% were observed over the baseline strategies, showcasing the potential of our work in improving FLM connectivity. The rest of this section analyses the solutions from the proposed ILP method for the joint FLM shareability scenario in greater detail.

The optimal number of vehicles at each station and the lost demand percentage, calculated with respect to the total demand on an hourly and station-wise basis, are shown in Figure 11. The bar plots on the top and right indicate the cumulative lost demand percentages for each hour and each station, respectively. Lost demand is highest in the time window 7 PM–8 PM, followed by 9 AM–10 AM. As expected, the off-peak morning hours 5 AM–8 AM record the lowest lost demand percentage. For most metro stations, the percentage of lost demand is less than 5%. Three out of four ends of the metro lines are assigned the maximum number of FLM vehicles allowed because of their large Voronoi regions. Among them, Baiyyappanahalli (label #17), one of the endpoints on the East-West line, has the highest lost demand (see Figure 12, which shows the locations of the lost demand). As mentioned earlier, Nagasandra station in the North also has a sizeable Voronoi region, but the complete EB data was unavailable. The lost demand at the other two terminal stations – Mysore Road and Yelachenahalli – is relatively much lower because the passenger demand at these stations is nearly half that at Baiyyappanahalli. The overall difference between the number of last- and first-mile lost demand across all stations for this instance was found to be 413.

Table 3 shows the top five metro stations with the highest lost demand, their LM and FM demand, the number of FLM vehicles in the optimal solution, and LM and FM lost demand. Their rank based on the total lost demand is also indicated in Figure 12. Despite having a significant share of lost demand, the stations Majestic and Dr. BR Ambedkar Station (labels # 8 and #10) are not assigned more FLM vehicles because the marginal effect of adding an extra vehicle at these stations was found to be very low. The number of unserved first-mile requests in the case of Baiyyappanahalli is higher because the detour times are longer compared with other stations with a high passenger volume, such as Majestic.

To test the sensitivity of the optimal solution with respect to the total number of vehicles, we ran a few additional scenarios. Specifically, we set the number of vehicles to 800, 1200, and 1600. The percentage of lost demand in these instances was 10.7%, 3.7%, and 3.5%, respectively.

We also compared utilisation statistics of FLM vehicles in the system. The line chart associated with the secondary axis in Figure 13 shows the average unit utilisation of vehicles assigned to different stations. Unit utilisation values indicate the percentage of time the vehicle was busy. The highest (82%) and lowest (44%) utilisation percentages were found to correspond to stations Baiyyappanahalli (label #17) and Mahakavi Kuvempu Road (label #28), respectively, and are correlated with the supply and demand at these stations. Knowing utilisation percentages can help reserve downtime of the vehicle fleet if needed (e.g., for maintenance, refuelling, and recharging/battery swapping in the case of an electric fleet).

Vehicle utilisation statistics are also a measure of the number of idle vehicles that require parking at stations. Figure 13 shows a box plot in which the number of vehicles parked at different stations estimated at a one-minute frequency makes up the data points. As expected, stations with high utilisation, such as Baiyyappanahalli, Majestic, and Yeshwantpura, have low median values. These percentile measures can be used to design appropriate parking infrastructure.

Parking requirements are not usually uniform and mirror the demand distribution. Figure 14 shows temporal variations in the number of idle FLM vehicles for two stations – Indiranagar and Majestic. The parking requirements are lowest during the morning (9 AM–11 AM) and evening peak hours (6 PM–8 PM), but the off-peak requirements can be significantly different across stations, as seen from the figure.

Figure 15 shows the percentage of trips that involve transporting a single passenger and ride-sharing with two or three passengers on board. The superimposed line plot indicates the total number of trips. Recall that in the joint shareability model (see Figure 7), FLM vehicles first serve last-mile demand and switch to picking up first-mile passengers (if available and if waiting/detour time thresholds are met). The FLM vehicle can serve multiple passengers on the last-mile leg but may pick up only one passenger on its way back. Hence, classifying a trip based on the number of passengers served can lead to some ambiguity. We, therefore, do not define trips as segments that start and end at the metro station but count them separately for the first- and last-mile legs. In other words, trips are passenger-serving segments between instances where the FLM vehicles are empty. The average number of trips serving one, two, and three passengers across all stations was found to be 777, 175, and 215, respectively.

FLM vehicles at stations such as Baiyyappanahalli, Majestic, and Indiranagar make a greater fraction of shared trips than the others. These stations have a high demand for boarding and alighting passengers, making it easier to pool rides. On the other hand, stations such as Peenya, Peenya Industry, and Goraguntepalya witness a lower fraction of shared trips because of their elongated Voronoi regions, which makes it difficult to pool rides. Sharing rides leads to lower lost demand, as demonstrated in Table 2. In addition, they also result in fewer vehicle kilometres travelled. Serving the passenger demand met in the joint FLM scenario using only single rides would have resulted in 406,434 vehicle km but allowing sharing reduces this to 295,036 vehicle km, a 27% decrease, which decreases both congestion and emissions.

The simulation framework proposed in this paper can also help analyse different pricing models, such as distance- and trip-based pricing schemes. In the following discussion, we compare revenue, assuming that the demand is captive and insensitive to the fare. The numbers used in this section are representative of auto-rickshaw operations in India. All calculations are estimated on a per-day basis.

Distance-based pricing model: To calculate the revenues, we first add up the fares paid by the set of passengers served at station $i$, $P(i)$. Passenger $p$ is assumed to be charged an amount $D_{ip}$ that depends on the direct distance between their origin/destination and the metro station. Metered auto-rickshaw fares in Bengaluru are of threshold type with a fixed base rate $\alpha$ up to 2 km and a distance-based price $\beta$ for subsequent kilometres travelled. Thus, the revenue from a passenger $p$ can be expressed as $R_{ip}=\alpha+\beta\max(D_{ip}-2,0)$, where $\alpha$ and $\beta$ were set to \rupee30 and \rupee15, respectively (IndianExpress, 2021).

Let $D_{iv}$ be the distance travelled during an entire day by a vehicle $v$ assigned to station $i$. The operating cost is defined as $D_{iv}(\phi/\mu)+C_{f}$, where $\mu$ denotes vehicle mileage and $\phi$ is fuel price, set to 25 km per litre and \rupee100 per litre, respectively. Operators are also assumed to incur a fixed cost $C_{f}$ set to \rupee102 per vehicle per day (GoM, 2022), which includes depreciation and maintenance. For simplicity, $C_{f}$ is kept constant but may, in practice, depend on vehicle utilisation and age. Thus, the overall profit for FLM vehicles at station $i$ can be expressed as $P_{i}=\sum_{p\in P(i)}R_{ip}-\sum_{v=1}^{x_{i}}\left(D_{iv}(\phi/\mu)+C_{f}\right)$.

The top panel in Figure 16 shows the profit per vehicle at different metro stations under this pricing scheme. The average profit across all vehicles was found to be \rupee1623. The line plot corresponding to the secondary axis shows the average distance travelled by the FLM vehicles. Compared to the daily earnings of \rupee800–1200 reported in previous studies on auto-rickshaw drivers in Bengaluru city (Ramachander et al., 2015), we observe that serving metro passengers through a centralised service provider can yield higher profits. The estimated profits per vehicle at metro stations Baiyyappanahalli and Majestic are the highest as expected due to high passenger demand, vehicle utilisation, and degree of ride-sharing. Among all stations, Majestic has the smallest Voronoi region and, consequently, shorter average distances. However, since the pricing scheme has a base fare (independent of distance) for trips shorter than 2 km, the overall profits are considerably higher. On the other hand, Peenya Industry has the lowest profit per vehicle despite serving passengers with longer distances to the metro station. This result is possibly because Peenya Industry has the least passenger demand among all stations and a high share of single-passenger trips (see Figure15).

Trip-based pricing model: We also estimated the profits from a trip-based pricing model where passengers are charged a flat fee of $R_{ip}=$ \rupee30, irrespective of the distance they travel. The operating costs are assumed to be the same as before. As seen from the bottom panel of Figure 16, the profit values are lower compared to the distance-based model. The average profit per vehicle was found to be \rupee766, which is less than half of that in the distance-based case. At a fixed price of \rupee44, the trip-based profits per vehicle become nearly equal to the estimates from the distance-based pricing model. Two metro stations – Jalahalli and Peenya Industry – have negative revenues due to a lower number of trips (see the line plot on the secondary axis). Setting a higher fixed fare for FLM vehicles at such stations could resolve this issue.

Based on the above analysis, the following list summarises a few possible policy implications.

• •

  The marginal benefit of adding FLM vehicles to a station drops beyond a threshold. This threshold is different for each station and depends on the size and demand of the region it serves. Hence, service operators must determine an optimal number based on the trade-off between operating costs and net revenue.

• •

  Since vehicle utilisation rates and profits vary significantly across stations, a policy of rotating vehicle assignments to stations may be required to provide equitable earnings to all drivers.

• •

  There are temporal variations in lost demand, with peak hours witnessing three to four-times higher percentage of lost demand than off-peak hours. Considering the importance of public transit in reducing congestion, especially during peak periods, it is imperative to manage peak-period lost demand more efficiently. Ensuring maximum vehicle availability, augmenting the fleet size, and operating larger vehicles could reduce the demand lost during peak hours.