It is estimated that smart on-demand mobility services can significantly reduce emissions caused by urban transportation, especially when combined with the use of low emission vehicles and ridesharing. While current research on sustainable routing typically focuses on economic sustainability (as cost minimisation), this paper also considers the other pillars of sustainability, i.e., the environmental and social aspects of what we call sustainable and equitable Mobility-On-Demand (MOD). To that end, we apply multiobjective genetic algorithms and generate routing options that balance all three pillars of sustainability. We envisage that a diverse set of routing solutions allows participation of end-users in determining an equitable route (e.g., through voting processes) and strongly supports widespread adoption of sustainable MOD and ridesharing services. This work follows principles of human-centred intelligent systems and provides a foundation for building participatory, dynamic, and explainable MOD systems.
Mobility-On-Demand (MOD) services traditionally aim to reduce the economic and
environmental cost of transportation [
As discussed in related work, e.g., [
Against this background, for the first time in this work, we capture the social and
environmental aspects of sustainable routing in MOD and use genetic algorithms for generating routing
options that consider all three pillars of sustainability. This is the first approach that integrates
these two pillars of sustainability into traditional models of (purely) economic sustainability
and generates routing solutions under six sustainable ridesharing objectives: travelling time,
waiting time, overall/excess distance, travel cost, total emission, and working time balance. The
list of sustainable routing options can be used in a “user participation” phase (e.g., in ridesharing
services), where riders can select their desired route from a list of options. Using our approach,
service providers can generate routing options that balance all the three pillars of economic,
environmental, and social sustainability. In addition, they can provide routing options that
reflect riders’ preferences (e.g., by focusing on the environmental dimension). This is a step
towards integrating equitability and user participation [
The MOD routing problem is to allocate a given set of riders to vehicles with respect to diferent
objectives. Each rider requires a ride from its starting point to its destination, along with a
specified earliest departure time for taking a ride. Each vehicle can take a limited number of
riders aboard at the same time, excluding the driver, which we refer to as its capacity. And
the driving costs and capacity of a vehicle are associated with its type. A solution to the MOD
routing problem is an arrangement that sends vehicles to pick up riders at their starting point,
and then drops them of at their destination. The objectives evaluate the eficiency of a solution.
In the following, we present the mathematical notations used for modelling the MOD problem
1In view of human-centred AI techniques and the need for developing trustworthy human-AI partnerships [
In the MOD routing problem, all the riders post their ride requests at the beginning. Let be the set of posted requests and represent a single request. To locate riders, we adopt a graph structure to model the real-world map, i.e., a map graph is = (, ), where nodes in represent the intersections on a real-world map and edges in that link nodes together represent the roads between intersections. In general, to represent an intersection, a node is in the form of a tuple marking the latitude and longitude of the intersection. Thereby, let (, , ) denote a rider’s request for a ride from node to node along with an earliest time for the rider to leave, .
To model the sustainability of the MOD routing problem from economic, environment and
social aspects, this work considers 3 features of a vehicle as well as its location. Let (, , , , )
denote a vehicle that starts working at node , returns to node at the end of its service with
a physical capacity of , emission level of and a travelling cost per kilometre, , including
the driver wage, vehicle maintenance and fuel costs. Regardless of the diference of vehicle
brands, there is a positive correlation between and . Hence, we assume that = × for
a vehicle and varies according to the type of vehicle. For a pessimistic estimation, we use
= 1 in our experiments. Besides, the emission level of a vehicle is a vector, and the th
element in the vector, , denotes the emission rate of a vehicle when there are riders aboard,
since diferent numbers of riders aboard cause diferent emission rate. Specifically, in this work,
the emission of a vehicle generally includes greenhouse gas (GHG) and air pollution. With
respect to the reports from the UK’s Department for Transport [
The features of a vehicle, such as capacity, emission level and travelling cost, depend on its
type. We consider 3 types of general passenger vehicles according to the vehicle categories
specified on the UK Driving Licence Categories [
Our focus in this work is to demonstrate the impact of emissions of vehicles, and we are
aware of the existence of other types of vehicles, such as motorcycles, and diferent types of
emission calculators [
Our intelligent routing approach is based on genetic algorithms [
To calculate the routes for vehicles there are two factors to satisfy: feasibility and uniqueness.
Feasibility requires that when a vehicle follows a route to pick up and drop of riders, the number
2we exclude minibuses and buses [
First, to capture the meaning of the priority weights in a solution, we use the following two rules when comparing the priority weights of diferent riders: 1. No consideration of dropping of priority for riders who are waiting for pick-up. 2. For riders with equal priority weights, the rider with a lower index number is prioritised, considering that the rider posted its ride request earlier.
Regarding a solution, let () denote the set of riders to whom vehicle ofers a ride, and () = {| = }. The route of is a sequence of nodes, ℎ(), that are either starting points or destinations of riders in (), and the path that a vehicle travels from a node to another is the shortest path calculated by Dijkstra’s algorithm [18]. While a vehicle travels, let (, ) denote the riders that are on the vehicle when it visits node , and (, ) be the riders that are still waiting for the vehicle for a pick-up.
Figure 1 displays our routing algorithm that maps a solution to the routes for a vehicle. 3 The very first node in the route of a vehicle is its starting point, and at that node, the boarding passengers is null and all the riders assigned to it are on hold. Then, the next node in the route of the vehicle depends on the priority weights of the aboard and waiting riders. First, we compare the waiting riders’ weights of picking up priority and get the top one waiting rider, and then compare the aboard riders’ weights of dropping of priority and get the top one aboard rider. If the aboard rider’s weight of dropping of priority is greater than the waiting rider’s weight of picking up priority, the next node in the route of the vehicle is the destination of the aboard rider. Otherwise, we check whether picking up the waiting rider violates the vehicle’s capacity constraint. If not, the vehicle will travel to the starting point of the waiting rider and pick it up. If yes, the vehicle still needs to drop of the aboard rider first. Until there is no rider aboard or waiting, the vehicle will travel to its destination and terminates its route.
This routing algorithm guarantees the feasibility of the travel paths of vehicles generated from a solution and the uniqueness of the generation dynamically. Note that, regardless of the uniqueness, it is still possible that diferent solutions generate the same routes for one or even more vehicles. This is because the diferent weights of either picking up priority or dropping of priority can result in the same ranking of the riders in the algorithm. Note that the potential redundancies are left to be resolved in the genetic algorithm.
Regarding the travel paths of vehicles and their loaded riders, we introduce and minimise 6 objectives from 3 aspects of sustainability: economic, environmental and social. The economic 3For a complete implementation of our routing algorithm, please refer to https://github.com/Miya-Liu/ equitable-ridesharing. aspect evaluates the eficiency of the routes generated from a solution with respect to travelling time, waiting time, travel cost and excess distance. Then, the environmental aspect of sustainability considers the impact of vehicles’ emission and tries to minimise the total emission of rides. Finally, the social aspect concerns the working time of drivers and aims at reducing the diferences among the working time of all drivers.
Economic - Travelling Time (et): This objective measures the total travelling time of individual riders. The measurement of the travelling time for one rider is the time that it takes from the moment the rider gets on a vehicle until the vehicle drops of the rider at her destination. This includes the time that the vehicle travels and waits to pick up and drop of other riders while the rider is on board. The waiting time of a vehicle includes time periods when the vehicle stops at a starting point of a rider to pick her up. Such a waiting takes place when a vehicle arrive (too) early, i.e., when the arriving time of the vehicle is earlier than the earliest leaving time of the rider. Less travelling time means that the riders entails a more eficient trip.
Let (, ) denote the time that a vehicle waits for picking riders up at node along its route. Let (, ) be the shortest distance between node and , and (, ) represent the time that the vehicle arrives at node along its route. Hence, (, 0) = 0, (, 0) = 0, and (, ) = (, − 1) + (, − 1) + (− 1, ) , where = ℎ()[], and is a given average speed. Assume that will pick up riders at , thus, (, ) = max{0, () − (, )}, where () is the greatest earliest leaving time among the riders. Therefore, = ∑︁ (︀ (, ()) − (, ()).
Economic - Waiting Time (EW): This objective is to evaluate the waiting time for all riders before vehicles pick them up with respect to their earliest leaving time.
= ∑︁ max{0, (, ()) − ()}
Economic - Excess Distance (ED): This objective measures the extra distance that a vehicle travels when it needs to pick up and drop of riders compared to the distance of directly driving from its starting point to the destination. Let be the th node in a route, = ∑︁ (︀ | ℎ()|− 1 ∑︁ =0
(, +1) − ((), ()))︀ Economic - Travel Cost (EC): This objective measures the cost of all rides in total. = ∑︁ (︀ () × | ℎ()|− 1 ∑︁ =0 (, +1)︀) Environmental - Emission (SE): This objective is designed to measure the emission of all the vehicles. By minimising this objective, sharing a ride can reduce pollution. Recall that the emission rate of a vehicle is related to the number of passengers on the vehicle. Therefore, the emission of all the vehicles regarding one solution is = ∑︁ | ℎ()|− 1
∑︁ =0
()[(, )] × (, ). where (, ) = |(, )|.
Social - Working Time (SW): The working time is calculated from the moment a vehicle leaves its starting point until it arrives at its destination, which is (, ()). This objective demonstrates the workload of a vehicle. Regarding the social sustainability, this work tries to balance the workload among all drivers and ensure a sustainable MOD service that is fairnessaware. Hence, this objective is defined as the Gini coeficient [ 19] of all vehicles’ working time, = {(1, 1()), (2, 2()), · · · , (, ())} as follow.
= ( ).
With the above-defined multiobjectives, we will later explain our algorithm that generates multiple routing options that balance the six objectives of all three pillars of sustainability. (2) (3) (4) (5) (6) (7)
This work adopts an existing genetic algorithm called Non-dominated Sorting Genetic Algorithm 3 (NSGA3) [20] for dynamic routing in the sustainable MOD problem. Figure 2 shows the workflow of the NSGA3 with modifications for the MOD setting.
NSGA3 requires no configurations of the importance or weights of multiple objectives in the optimisation, but balance them automatically. The optimisation procedure includes: 1. Sampling: It generates an initial sample population. In this step, for each solution in the population, we randomly assign vehicles to serve riders, and assign random values as the weights of the picking up and dropping of priority of riders. 2. Selection: It selects some solutions as parents for generating ofspring in next generation.
NSGA3 uses a reference points [21] based selection operator. As we applying this genetic algorithm for multiobjective optimisation, this selection is ideal as it is guided by specifying a set of well-maintain diversity in the population regarding diferent objectives. 3. Crossover: It combines the selected parents to generate ofspring. We define the crossover as two parent solutions generating one ofspring. The pattern to generate an ofspring for each pair of parents is to use the first half chromosomes from a parent and the second half chromosomes from the other parent to generate an ofspring solution. Note that our implementation supports splitting both parents into any number of slices and then selecting the same number of slices to generate an ofspring. However, the eficiency evaluation of crossover patterns is out of the scope of this work. 4. Mutation: It mutates ofspring to increase the diversity of the current population. The modified mutation is: for each ofspring, we select half riders and change the value of its corresponding chromosomes by (1) changing the vehicle assigned to a rider; (2) increasing its weight of picking up priority by a positive number; (3) increasing its weight of dropping of priority by a random positive number. 5. Elimination: It deletes duplicate solutions. And if the size of the current population after elimination is smaller than the initial population, the crossover process is repeated until the desired number of ofspring is fulfilled.
We set the threshold of the number of generations as the condition to terminate the optimisation.
This approach will automatically generate multiple routing solutions when we set the size of population greater than 1. In addition, the routing solutions are feasible and balance the economic, environmental and social sustainability, while the algorithm optimise the six objectives. Note that we did not consider the objectives when calculating the shortest path among all nodes of a map graph. This is because the objectives are defined and calculated based on the paths of all the vehicles that they will drive, pick up, and drop of riders. For instance, we cannot get the override distance just for the edge between two nodes.
The main goal of this work is to demonstrate the impact of sustainable objectives in MOD routing and the eficiency of our GA-based routing approach. We present 4 groups of instances with various numbers of riders, vehicles, objectives and generations to illustrate the performance of our approach. This section evaluates the performance with respect to the standard metrics in the field of vehicle routing [ 22, 23] and includes social and environmental metrics such as the waiting time of a rider to start a ride.
We use the Cargo benchmark dataset [24], which takes data from the MOD ridesharing company Didi. The instances have maximum 65,500 riders and 50,000 vehicles over a long time horizon and a scale of 876km2 area. Since we focus on one-shot routing, we take slices from the dataset for our evaluation. Note that in practice, new routes can be calculated as more requests come in. • Road Map: We use the road map of Manhattan from Cargo [24]. It has 12,320 nodes, 15,722 edges in an area of 59km2. • Instances: We design 4 groups of instances as detailed in Table 2. The highlighted cell in each row is the parameter that we vary in each group. Regarding the extracted instances with the same number of vehicles and riders, we vary the capacity and type of vehicles by setting all vehicles to be one same type from Table 1. • Objectives: With the 6 above-mentioned objectives from 3 aspects of sustainability, we optimise routes for setting up experiments either based on one aspect and then considering all of the 3 aspects, as the instances in group 4 represent.
The implementation of the GA algorithm in the Python programming language (using pymoo4) allows configuring the population size, number of generations, the ofspring rate, and muting/enabling diferent objectives. To present a first evaluation of our approach, we set the population size and ofspring size to 10 and 5, respectively.
For each solution (that assigns riders to be picked up by a vehicle), we calculate the waiting time per rider. Figure 3 presents the waiting time per rider according to the generated solutions for 2 instances in group 1. When the number of riders increase from 10 to 30, the median waiting times per rider only increase from [160, 220] to [190, 290]. The increase ratio is less than the ratio of riders, which indicates the capability of our routing approach for handling larger populations of riders. Besides, Figure 3b has fewer outliers than Figure 3a, but a wide range of waiting time per rider. This is because when the number of riders increases (without any increase in the number of vehicles), more riders need to wait longer. And when there are fewer riders, the location of vehicles has a greater efect on riders’ waiting time. Note that having more riders implies that vehicles travel around more frequently, hence, it is more probable to get close to the starting point of riders.
(a) Instance 1 with 10 riders (b) Instance 2 with 30 riders
To understand the balancedness and diversity of GA-based routing solutions with respect to the economic, environmental and social aspects of sustainability, we focused on instance group 2 (in Table 2) and plotted the results in 4 sampling generations. Figure 4 presents the evolution of the populations at generations 0, 10, 40 and 80. The solutions in each population have diverse efectiveness against the three aspects of sustainability. In general, as the optimisation proceeds, the social inequality decreases. The initial generation (in blue) has greater social inequality than other generations while the 80th generation has the lowest inequality. However, from the perspective of economics and environment, the costs and emissions do not improve for all solutions. However, it is observable that we have a more diverse set of solutions. For instance, solution (in the 80th generation) has a low economic cost and social inequality which compensates for its high environmental emission level. The other notable solution is labelled with a boxed which performs well against all the three dimensions. We argue that such a diverse set of solutions provides an ideal voting pool for what we call participatory route selection (see Section 5).
We further evaluate the efectiveness and diversity of our routing approach in optimising individual objectives with group 4 instances. Figure 5 presents the radar plots of the efectiveness of the 10 generated solutions with respect to the 6 objectives. The smaller number of an objective implies a better performance of a solution on that objective. Among these 10 solutions, the efectiveness regarding social sustainability varies greater than the others. This is because the changes in allocating riders from a vehicle to another directly afects the working time of the vehicles. The population ofers diverse solutions that improve social inequality between 0.1 to 0.3. We expect to take advantage of populations’ diversity in the next phase of our work on sustainable mobility and allow riders to vote on routes with respect to their concerns, such as economic costs, environment emissions, or social inequality.
In this work, we presented a multiobjective evolutionary approach based on GA algorithm for
generating routing options in sustainable MOD. Although there are well-studied multiobjective
optimisation methods [
Explainability for Riders, Drivers, and Operators: In comparison to data-driven techniques with black-box optimisation components, in our approach, stakeholders can be provided with visualisations to see how diferent objectives (e.g., minimising emissions) afect routing solutions. For instance, they can be presented using graphs as in Figure 5 and with explanations on how waiting a bit more (in comparison to using private rides) can benefit the environment or the fairness of the service for drivers.
Participatory Route Selection: Building on this approach, MOD operators can present routing options to riders (or autonomous agents that represent riders) and allow voting among them. This way, users can directly participate in the route selection process and opt for the most collectively equitable route. Our diverse set of GA solutions are not ranked. Thus, a set of riders may prefer one over another and to allow that, we aim to extend our work by adding a preference/vote-based route ranking module in the future.
Dynamic Fine-Tuning: Our approach allows dynamic fine-tuning over time. Users and service operators can inspect routing solutions, evaluate if they are realistic and feasible, and participate in fine-tuning the route generation algorithm and the objective weights to set trade-ofs. One can use focus groups for such a tuning over time—e.g., as a city and its citizens change—to enable dynamic fine-tuning of sustainable MOD services.
We aim to extend our work by integrating a participatory route selection process and allowing users to vote over a diverse set of routing solutions with all the objectives and then also muting one or two objectives to provide solutions that match diversity in users’ preferences. With a better understanding of users’ preferences, we aim to explore other methods for multiobjective optimisation in the context of MOD service. For example, we can define the assignment of a rider to a vehicle as a move and evaluate the move with respect to the multiple objectives, and then adopt reinforcement learning for this problem. Moreover, we plan to test the eficacy of our approach in larger datasets and investigate simulation-based methods to analyse how diferent map structure and spatio-temporal properties of requests afect the optimality and equitability of solutions.
Data access statement. This study was a re-analysis of data that are publicly available from the the Cargo benchmark dataset [24]. Implementations and data derived through the re-analysis undertaken in this study are available from the public GitHub repository at https: //github.com/Miya-Liu/equitable-ridesharing.
Acknowledgements. We thank the anonymous reviewers for their incisive comments that were most useful in revising this paper. This work was supported by the UK Engineering and Physical Sciences Research Council (EPSRC) through a Turing AI Fellowship (EP/V022067/1) on Citizen-Centric AI Systems (https://ccais.ac.uk/) and the platform grant entitled “AutoTrust: Designing a Human-Centred Trusted, Secure, Intelligent and Usable Internet of Vehicles” (EP/R029563/1). For the purpose of open access, the author has applied a creative commons attribution (CC BY) licence to any author accepted manuscript version arising. [18] T. H. Cormen, Section 24.3: Dijkstra’s algorithm, Introduction to algorithms (2001) 595–601. [19] M. T. Catalano, T. L. Leise, T. J. Pfaf, Measuring resource inequality: The gini coeficient.
numeracy 2 (2): Article 4, 2009. [20] H. Jain, K. Deb, An evolutionary many-objective optimization algorithm using referencepoint based nondominated sorting approach, part ii: Handling constraints and extending to an adaptive approach, IEEE Transactions on evolutionary computation 18 (2013) 602–622. [21] J. Blank, K. Deb, P. C. Roy, Investigating the normalization procedure of nsga-iii, in: EMO, 2019, pp. 229–240. [22] G. Laporte, Fifty years of vehicle routing, Transportation Science 43 (2009) 408–416.
doi:10.1287/trsc.1090.0301. [23] S. Ben Cheikh-Graiet, M. Dotoli, S. Hammadi, A tabu search based metaheuristic for dynamic carpooling optimization, Computers & Industrial Engineering 140 (2020) 106217.
URL: https://www.sciencedirect.com/science/article/pii/S0360835219306862. [24] J. J. Pan, G. Li, J. Hu, Ridesharing: simulator, benchmark, and evaluation, Proceedings of the VLDB Endowment 12 (2019) 1085–1098.