Shared economy takes an ever increasing part of our everyday activities. Generally, resource sharing is a key to more eficient and efective smart cities and transportation, with the most known applications in car sharing and cooperative hot meal delivery (Uber, Deliveroo, Uber Eats, Glovo, etc.). These fleets are generally composed of self-concerned individually rational agents (drivers) whose interest, in general, is their own eficiency and efectiveness, but also the fairness of the system as a whole; in other words, how their individual gain relates to the gain of the others. Most of the AI state-of-the-art fleet coordination approaches focus only on the eficiency of the fleet as a whole and result in generally unfair solutions without guarantees of the distribution of the workload, cost, or profit or without guarantees on the diference in performance between the worst-of and the best-of vehicle in the fleet. In this light, in this paper, we study the multiple Traveling Salesman problem (mTSP) and propose its two new variations that maximise utilitarian, egalitarian, and elitist social welfare and balance workload and eficiency of the fleet. Moreover, we give examples of how the proposed models influence routes of a fleet's vehicles in small but suficiently representative problem instances. The computational results show a great diversity of routes depending on the social welfare approach considered. Thanks to the latter, we can balance solutions based on the eficiency and fairness requirements of a fleet at hand.
The number of commercial companies using resource sharing has been growing in recent years. More and more companies are demanding transportation services for goods such as food, packages and electronics or even for people using shared mobility in cars or cabs.
Shared economy applied to collaborative open fleets composed of individually rational selfconcerned vehicle owners allows individual vehicles to improve their performance. Vehicles can join or leave such a fleet based on individual interest. The aim of the fleet is at responding to a given demand and getting the highest benefit for all while considering also the distribution of the benefit among the fleet’s vehicles. Thus, it is not enough only to minimise the costs of the lfeet as a whole, but it is also necessary to find vehicles’ itineraries that will be both eficient and satisfactory for all the vehicles. This requirement is essential to maintain the fleet stably over time. Otherwise, some members might not agree to cooperate even though the cooperation reduces costs in respect to competition and may leave the fleet, thus putting in jeopardy the survival of the fleet.
With the aim to obtain a fair and eficient routing solution for such fleets, in this paper, we introduce and analyse utilitarian, egalitarian, and elitist social welfare concepts from welfare economics. Generally, the optimisation of the utilitarian welfare concentrates on maximising the benefit and/or minimising the cost for the whole system independently of how the costs are distributed among its components. Concentrating on the optimisation of the system’s egalitarian social welfare without other concerns will generally result in the solution that will minimise the cost of the worst-of agent (an agent with the highest cost or the lowest benefit), while optimising the elitist social welfare will give us the solution that will minimise the cost of the best-of agent (the one with the lowest cost or the highest benefit). Note that both the egalitarian and elitist social welfare do not consider the distribution of the costs or benefits within the rest of the system. In this context, we study the uncapacitated Vehicle Routing Problem (VRP) for cooperative open fleets and investigate how to balance routes among the vehicles in terms of fairness and eficiency. We analyse the three welfare concepts mentioned before and propose three vehicle routing models that use them for that aim. The studied problem corresponds to the multiple Traveling Salesman problem - mTSP) that considers a set of customers to visit in a region of interest by a set of vehicles. Each customer has to be visited exactly once and by only one of the vehicles and all the customers must be visited.
This paper presents a new cooperative vehicle routing problem balancing fairness among the lfeet’s vehicles and the eficiency of the fleet as a whole. The rest of the paper is organised as follows. In Section 2, we resume the most relevant works on balancing fairness and eficiency in vehicle routing of collaborative fleets. In section 3, we describe the problem and the studied social welfare measures, and we present its general mathematical problem formulation. In section 4, the general model is instantiated for the diferent welfare measures. Section 5 describes and analyses some functional examples in two small artificially generated environments. Finally, section 6 gives an overview of the work done looking also at future work.
The VRP was first introduced in 1959 by Dantzig and Ramser [ 1], and is a generalisation of the famous travelling salesman problem (TSP) [2]. The objective of VRP is to minimise the total travel cost through a given set of locations to be visited by a given set of vehicles. This problem has been widely studied since its inception and is currently of increasing interest due to the need to save fuel, reduce 2 emissions, and share costs within large fleets of vehicles [ 3, 4, 5]. [3, 4] review the state of the art of studies related to horizontal collaborations between companies, i.e., sharing of customers and routes between companies with the same characteristics to reduce travel costs. In [5], the collaboration focuses on urban routes, where problems with trafic congestion, space in the city, and emissions are accentuated.
However, the reduction of the total cost of the trip made by vehicles is no longer the only objective to be taken into account. Others, such as, profitability, quality of service, consistency, fairness and equality in the workload or simplicity and eficiency of individual routes are also valued by the industry and public administration and in most cases conflict with the cost reduction (e.g. [6, 7, 8, 9, 10]). In this context, a new problem called vehicle routing problem with route balance (VRPRB) arises, which proposes to balance the workload performed by each vehicle [11]. To find this balance in workloads, multi-objective techniques are proposed, where each objective considers one of the above aspects to balance the workload of each vehicle [11, 12]. A formulation for the two-objective version, minimising the cost and the diference in distance travelled by the vehicles can be found in [13]. Due to the added complexity of solving more than one objective and analysing the various non-dominated solutions (Pareto optimal [14]), the resolution involves using various techniques such as transforming the bi-objective problem into a single objective problem [15], column generation techniques [16, 17] or the use of diferent metaheuristics [18, 19, 20, 21].
When diferent vehicles in the system are owned by diferent actors (agents), it is no longer important to consider only the level of balance between vehicle routes. It is necessary to introduce other metrics representing fairness, equality and equity in the generated routes. In [22], an axiomatic analysis is performed on diferent fairness metrics and fairness measures applied to VRP problems. In this study, the authors distinguish between the resources to be balanced such as distance, delivery time, amount of load, and the diferent functions that measure how unfair a solution is depending on each agent. Some examples of functions are the rank function, maximum, standard deviation or the Gini coeficient. In [ 23], the authors introduce another type of fairness measure when goods are delivered to people in emergency relief distribution. For this purpose, they include in the objective function a fairness coeficient that weights the cost of the trip by the number of people receiving assistance by the service divided by the time spent on a direct trip without taking into account other destinations. Finally, other authors have considered as justice functions the norms since they have properties (non-negative, symmetry, monotonic, quasi-convexity) that benefit the convergence of the model [24].
When applying the concept of fairness to large fleets of vehicles belonging to several owners, the fairness measure must be adapted. It is necessary that not only the vehicles perform the routes in a balanced way, but also that the profits of the owners are balanced. The method proposed by [25] is based on multi-objective optimisation and with a max-min objective function, which tries to maximise the minimum satisfaction of the owners. Finally, in [26] the assumptions of competition, mutual aid and total cooperation between fleet owners are compared, concluding that, if they choose to cooperate, the range of benefits they can mutually obtain is expanded.
In this Section, we first qualitatively describe the problem that we tackle in this paper. Then, we describe the analysed social welfare measures in more detail and finally, we present a formal description of the problem.
In the context of the VRP we have described before, there might exist multiple solutions with diferent impact on individual vehicles from the social welfare point of view. In Figure 1, we present some examples. Here, we deal with a transportation network modelled as a complete digraph composed of 9 vertices and a fleet of 3 vehicles whose itineraries are circuits coloured in green, blue, and red, start from the depot located at vertex 1. The vehicles need to visit all the other vertices collaboratively where one and only one vehicle must visit each vertex and, at the end, return to the depot. The circuit cost is the sum of all the distances represented as the costs of individual arcs passed by a vehicle.
Note that a complete digraph may be seen as an abstraction of a transportation network where routes from each vertex to every other vertex are precomputed and their costs are considered as the costs of the arcs in the complete digraph. This implies that, when the solution found in the complete graph is applied to the transportation network, a vertex in the transportation network may be visited more than once as it may serve as a transit vertex, but the task assigned to that vertex will be performed once and only once by a single vehicle of the fleet.
By approaching a solution for the described problem, we may obtain diferent results in terms of costs of the vehicle routes when considering diferent social welfare measures. In the following subsection, we will analyse the welfare measures we use in more detail.
Utilitarian social welfare is related with the overall cost or benefit of all individuals composing a system. Maximising utilitarian social welfare in vehicle fleets translates into minimising the overall fleet’s cost obtained as a sum of the costs of all vehicles’ routes, without taking into account the distribution of these costs among the vehicles. The value obtained by maximising utilitarian social welfare alone represents a lower bound of the overall routes’ cost for the whole vehicle fleet.
Egalitarian social welfare is a concept that intents to increase fairness in the sense that the cost/benefit of the worst-of actor is minimised/maximised, respectively. In particular, maximising egalitarian social welfare in m-TSP translates into minimising the route cost of the worst-of vehicle. Note that this approach only focuses on the vehicle(s) with the highest route’s cost and it does not consider the routes taken by other vehicles (the ones that do not match that cost). The maximised egalitarian social welfare solution will be an upper bound for the maximum cost that each vehicle can assume within the route; any solution that involves a vehicle travelling more than that distance could be considered unfair from the egalitarian point of view.
Elitist social welfare has as the objective to minimise the cost of the best-of vehicle (the vehicle with the route of the minimum cost). In terms of fairness looking from the fleet’s perspective, this can be seen as an unfair solution, since it increases the diferences in costs (or benefits) among the fleet’s vehicles. However, from the fleet’s clients’ point of view, elitist welfare may be applied, e.g., in emergency cases (emergency medical assistance, firemen, or
Systematic egalitarian/elitist social welfare resolves the previously mentioned issues that occur with the optimisation of egalitarian or elitist social welfare alone. The latter is only focused on minimising the cost of the worst-of and the best-of vehicle, respectively, without considering the distribution of the costs of the other vehicles’ routes. Thus, we can obtain diferent solutions with equal egalitarian or elitist social welfare optimum value but with ineficient route costs for the rest of the vehicles. Such a solution is not desirable in a system that also seeks to minimise the overall cost of the fleet’s routes.
To deal with this problem and to minimise the overall fleet’s costs while considering egalitarian and elitist welfare, we propose in this paper the systematic egalitarian and systematic elitist social welfare approach. The solution process in both cases is done iteratively. The systematic egalitarian social welfare approach first minimises the cost of the itinerary of the worst-of vehicle and then, in an iterative way, repeats the same with every other vehicle in a nonincreasing preference order based on the vehicles routes’ costs up to the best-of vehicle with the least costly route. The systematic elitist social welfare approach, similarly, applies elitist social welfare maximisation iteratively, starting from the best-of and ending with the worst-of vehicle in the preference order based on the non-decreasing vehicles routes’ costs.
In both cases, once a solution is found in each iteration, in further iterations, we ignore the worst-of/best-of vehicle and the vertices that it visits. Then we recompute the solution for the remaining vertices and vehicles in subsequent iterations. This process is repeated until there are no more remaining vertices to visit or vehicles without an assigned route. In this way, the two newly proposed systematic social welfare approaches do not focus only on the worst-of/best-of vehicle but they also consider all the other vehicles in the fleet.
An example of the diferences in the routes that can be obtained by applying egalitarian social welfare and systematic egalitarian social welfare is presented by 3 vehicles’ circuits on a digraph (a) Egalitarian (b) Systematic Egalitarian in Figures 2a and 2b, respectively. Both sets of the routes minimise the cost of the worst-of vehicle circuit, coloured in blue. However, the cost of the green circuit in Figure 2a is higher than the one in Figure 2b. By applying the systematic egalitarian social welfare approach, we also maximise egalitarian social welfare for all the remaining vehicles’ circuits (red and green vehicle) and reduce the overall cost.
Let us consider a complete arc-weighted digraph ( , ) composed of a set of vertices ∈ {1, . . . , }, and a set of arcs (, ) with ̸= representing a transportation network. The cost of travel for each arc (, ) ∈ is given by parameter ≥ 0. We study a generic case where is not necessarily equal to . We assume that vertex 1 is the depot and = ∖ {1} is the set of the vertices to visit (destinations). Note that a complete digraph is a directed graph in which every pair of distinct vertices is connected by a pair of unique arcs (one in each direction).
Given is a fleet of vehicles ∈ = {1, . . . , } initially positioned in vertex 1 that should visit all vertices in and return back to vertex 1. Each of these vertices should be visited by a single vehicle. We use a 3-index binary variable , whose value is 1 if the route of vehicle visits consecutively vertices and , and 0 otherwise.
With the aim to introduce the fairness measure into the problem, we start with the VRP formulation of the Multiple Travelling Salesman Problem (mTSP) in [27]. To eliminate the subcircuits that may occur in the routing of the vehicles in the graph, we consider the MillerTucker-Zemlin formulation [28] since it grows linearly with the size of the problem unlike other formulations with the exponential growth. To avoid subcircuits, it uses auxiliary decision variables ≥ 0, that determine the order in which the vertices are to be visited.
The original objective of mTSP is to minimise the overall cost of the routes. In the following, we give its mathematical formulation.
minimise
∈ ∈ ∈
(
Claim. Model (
Proof. In the original formulation in [27], for each destination ∈ , is upper bounded by
. In mTSP, it is mandatory for all the vehicles to leave the depot, constraints (
Therefore, constraints (
In this section, we modify the mTSP formulation (Equations (
A utilitarian welfare function sums the utility of each vehicle to obtain the fleet’s overall welfare. Translated into costs, it minimises the overall fleet’s cost (over all vehicle routes). The mathematical model for utilitarian social welfare is just the formulation of the mTSP as defined before, with the objective function being the sum of the vehicles routes’ costs. minimise
As mentioned before, the utilitarian model in Equations (
∀ ∈ ,
This model fixes the maximum cost for each vehicle of the fleet to the value of and the
objective is to minimise this value. As mentioned in Section 3.2, this approach considers only
the worst-of route. In order to obtain the systematic egalitarian social welfare, we perform
optimisation iterations where in each iteration, a vehicle with the route of the worst cost is
found by (
Elitist social welfare is of relevance in cases where a fleet needs to reach some location as soon as possible. The objective here is to minimise the cost (arrival time) of the vehicle with a minimum route cost. With this aim, we introduce a new continuous decision variable that is going to define the best-of vehicle route cost. To achieve it, we introduce binary auxiliary variables , and a constant , which takes an arbitrary large value. Formally: ∑︁ ∑︁ − ≤ , ∈ ∈ ∈ {0, 1}, ≥ 0.
Constraint (
In order to achieve a systematic elitist welfare solution, we use an optimisation approach
similar to the systematic egalitarian social welfare through successive iterations of (
In this section, we analyse and compare the behaviour of the utilitarian welfare model, the (systematic) egalitarian welfare model and the (systematic) elitist model in 2 example scenarios with 9 vertices and 3 vehicles. The graphs representing the example scenarios are presented in Figure 3, both located in a 2D square environment [− 1, 1]2. They represent a transportation network (graph) with 9 vertices, the first one in Figure 3a of irregular form and the second one in Figure 3b of a regular grid structure with distance of 1 between any two adjacent vertices. We consider that both graphs are complete and the cost between any two vertices is defined by the Euclidean distance, i.d., for any two vertices 1 = (1, 1) and 2 = (2, 2) the cost is defined by: 12 = (1, 2) = 2((1, 1), (2, 2)) = √︀(1 − 2)2 + (1 − 2)2.
For each proposed model, we obtain the costs associated with each vehicle, the overall fleet’s cost, the average, the maximum and the minimum routes’ costs and the range between the maximum and minimum cost of each solution. They are used to evaluate the eficiency and fairness of the proposed solutions.
(a) Irregular graph (b) Regular grid graph
Experiment 1 is carried out in the example graph shown in Figure 3a. We can see the diferent routes resulting from the application of the utilitarian social welfare, systematic egalitarian social welfare and systematic elitist social welfare in Figure 1a, 1b and 1c, respectively. The evaluation metrics obtained in this case can be seen in Table 2. The overall routes’ cost associated with the optimisation of the utilitarian social welfare is 9.81, with systematic egalitarian welfare it is 10.63 and for systematic elitist welfare 10.41. The best solution in terms of overall cost is achieved with utilitarian social welfare and the best balanced solution is achieved with systematic egalitarian social welfare where the diference between the best and the worst-of vehicle is only 0.2. With the systematic elitist solution, we obtain that the minimum route cost is 1.2 and we obtain an unbalanced solution with the diferences between the worst-of and the best-of vehicle reaching the highest value of 6.04.
Experiment 2 is carried out on the graph presented in Figure 3b. The 3 vehicles are initially positioned at the depot at the left down corner at vertex 1. The resulting routes of the application of the utilitarian social welfare, systematic egalitarian social welfare and systematic elitist social welfare are found in Figures 4a, 4b and 4c, respectively. The overall routes’ cost associated with the optimisation of the utilitarian and the systematic elitist welfare coincides and is 12.82, while with the systematic egalitarian welfare optimisation, it equals 16.13. This result is interesting because the utilitarian social welfare and the systematic elitist social welfare solutions have the same value and both achieve the lowest overall cost, but they are unbalanced in terms of the cost distribution. On the opposite, systematic egalitarian social welfare obtains a higher cost but with a more balanced solution. The individual values of the routes are shown in Table 2. Experiment 3 is carried out on the graph given in Figure 3b, but in this case the 3 vehicles are initially positioned in the depot located at the centre, vertex 5. At a first glance, the routes’ results presented in Figure 5 show three diferent solutions, utilitarian social welfare in Figure 5a, systematic egalitarian social welfare in Figure 5b and systematic elitist social welfare in Figure 5c. But, as we can observe in Table 2, the overall cost achieved is the same with utilitarian and systematic egalitarian social welfare value in both cases, 12.23, and the range in systematic egalitarian social welfare solution is 1.41 less than 2, achieved with the utilitarian social welfare approach. This means that, in this example, we get the optimal overall cost and the best balanced solution for each vehicle by applying egalitarian social welfare.
In this paper, we studied the vehicle routing problem where a fleet composed of vehicles belonging to diferent owners collaborate to visit a set of locations that are distributed geographically in some area of interest. We did not just look for an optimal solution in terms of the overall routes’ cost (as is the case in the conventional VRP), but we searched for the routes that are both eficient and fair. We were interested in measuring social welfare and the distribution of the costs of assigned routes among the individual vehicles. In this context, we studied utilitarian, egalitarian, and elitist social welfare and integrated them in the classical vehicle routing problem.
The proposed models quantify diferent fairness and eficiency criteria of the routes: utilitarian social welfare considers the overall vehicles routes’ cost, egalitarian social welfare gets an upperbound on the cost value for the vehicle whose route is of the highest cost and the elitist social welfare gives a lower bound on the route’s cost of the vehicle that assumes the least cost. Furthermore, since the latter two models consider only the worst-of and the best-of vehicle, respectively, we proposed the systematic egalitarian/elitist welfare solution approaches that not only minimise the costs of the worst-of/best-of vehicle, but also consider the rest of the vehicles in the fleet.
We analysed the results obtained by the proposed models in small functional examples, showing an interesting fact: in general, depending on the cost structure, the utilitarian social welfare model may be fair in the sense of reducing the cost of the worst-of vehicle and in other cases, it may be unfair, introducing big diferences among the assigned routes to the vehicles. Thus, if fairness is of concern, such concepts should be explicitly included or taken into account when distributing the workload among vehicles. This is essential in collaborative vehicle fleets, where individuals do not only search to improve their individual benefit (e.g., through the sharing of resources or capacities), but also want to be considered in a fair way.
In future work, we plan to analyse the proposed models in larger instances and to study the ways of distributing and decentralising of decision making in finding fair and eficient routes in collaborative fleets. To do so, we will study decomposition techniques to break down the proposed models into interconnected decision-making subproblems, one per each agent, where agents will have their own private, local, parameters and variables and will share the global ones. We plan to apply multi-agent system modelling considering trust and strategic agents that may lie to improve their individual benefit or cost. With that scope, we will apply mechanism design and incentives such that the optimal individual strategy being the one that minimises the cost of an individual agent, at the same time minimises also the cost of the system as a whole. The system optimum here may be defined according to utilitarian or systematic egalitarian social welfare.
Acknowledgements. This work has been partially funded by AGROBOTS Project of the Rey Juan Carlos University funded by Community of Madrid, Spain and project "InEDGEMobility" (RTI2018-095390-B-C33 MCIU/AEI/FEDER, UE) funded by Spanish Ministry MINECO. [16] N. Dupin, R. Parize, E.-G. Talbi, Matheuristics and column generation for a basic technician routing problem, Algorithms 14 (2021) 313. [17] E. Glize, N. Jozefowiez, S. U. Ngueveu, An -constraint column generation-andenumeration algorithm for bi-objective vehicle routing problems, Computers & Operations Research 138 (2022) 105570. [18] P. Nunes, A. Moura, J. Santos, Solving the multi-objective bike routing problem by metaheuristic algorithms, International Transactions in Operational Research (2022). [19] R. Goel, R. Maini, Improved multi-ant-colony algorithm for solving multi-objective vehicle routing problems, Scientia Iranica 28 (2021) 3412–3428. [20] Y. Wang, L. Zhao, M. Savelsbergh, S. Wu, Multi-period workload balancing in last-mile urban delivery, Transportation Sci (2022). [21] B. Vahedi-Nouri, H. Arbabi, F. Jolai, R. Tavakkoli-Moghaddam, A. Bozorgi-Amiri, Biobjective collaborative electric vehicle routing problem: mathematical modeling and matheuristic approach, Journal of Ambient Intelligence and Humanized Computing (2022) 1–21. [22] P. Matl, R. F. Hartl, T. Vidal, Workload equity in vehicle routing problems: A survey and analysis, Transportation Science 52 (2018) 239–260. [23] Y. Wu, F. Pan, S. Li, Z. Chen, M. Dong, Peer-induced fairness capacitated vehicle routing scheduling using a hybrid optimization aco–vns algorithm, Soft Computing 24 (2020) 2201–2213. [24] T. Bektaş, A. N. Letchford, Using -norms for fairness in combinatorial optimisation,
Computers & Operations Research 120 (2020) 104975. [25] S. Liu, L. G. Papageorgiou, Fair profit distribution in multi-echelon supply chains via transfer prices, Omega 80 (2018) 77–94. [26] C. L. Quintero-Araujo, A. Gruler, A. A. Juan, J. Faulin, Using horizontal cooperation concepts in integrated routing and facility-location decisions, International Transactions in Operational Research 26 (2019) 551–576. [27] T. Bektas, The multiple traveling salesman problem: an overview of formulations and solution procedures, Omega 34 (2006) 209–219. [28] C. E. Miller, A. W. Tucker, R. A. Zemlin, Integer programming formulation of traveling salesman problems, J. ACM 7 (1960) 326–329. URL: https://doi.org/10.1145/321043.321046. doi:10.1145/321043.321046.