=Paper=
{{Paper
|id=Vol-3173/paper5
|storemode=property
|title=On Balancing Fairness and Efficiency in Routing of Cooperative Vehicle Fleets
|pdfUrl=https://ceur-ws.org/Vol-3173/5.pdf
|volume=Vol-3173
|authors=Aitor Lopez Sanchez,Marin Lujak,Frederic Semet,Holger Billhardt
|dblpUrl=https://dblp.org/rec/conf/ijcai/SanchezLSB22
}}
==On Balancing Fairness and Efficiency in Routing of Cooperative Vehicle Fleets==
https://ceur-ws.org/Vol-3173/5.pdf
On balancing fairness and efficiency in routing of
cooperative vehicle fleets
Aitor López Sánchez1 , Marin Lujak∗1 , Frederic Semet2 and Holger Billhardt1
1
Centre for Intelligent Information Technologies (CETINIA), University Rey Juan Carlos, 28933 Madrid, Spain
2
Centrale Lille, Univ. Lille, CNRS, Inria, UMR 9189 CRIStAL, F-59000 Lille, France
Abstract
Shared economy takes an ever increasing part of our everyday activities. Generally, resource sharing is a
key to more efficient and effective 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 efficiency and effectiveness, 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 efficiency 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
difference in performance between the worst-off and the best-off 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 efficiency of
the fleet. Moreover, we give examples of how the proposed models influence routes of a fleet’s vehicles in
small but sufficiently 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 efficiency and fairness requirements of a fleet at hand.
Keywords
Vehicle Routing Problem, multiple traveling salesman problem, intelligent vehicles, collaborative routing,
fair and efficient routing.
1. Introduction
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 self-
concerned 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
∗
Corresponding author.
ATT’22: Workshop Agents in Traffic and Transportation, July 25, 2022, Vienna, Austria
$ aitor.lopez@urjc.es (A. L. Sánchez); marin.lujak@urjc.es (M. Lujak); frederic.semet@centralelille.fr (F. Semet);
holger.billhardtd@urjc.es (H. Billhardt)
0000-0002-8556-2701 (A. L. Sánchez); 0000-0001-8565-9194 (M. Lujak); 0000-0002-1334-5417 (F. Semet);
0000-0001-8298-4178 (H. Billhardt)
© 2021 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
CEUR
Workshop
Proceedings
http://ceur-ws.org
ISSN 1613-0073
CEUR Workshop Proceedings (CEUR-WS.org)
of the benefit among the fleet’s vehicles. Thus, it is not enough only to minimise the costs of the
fleet as a whole, but it is also necessary to find vehicles’ itineraries that will be both efficient 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 efficient 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-off 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-off 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 efficiency. 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
fleet’s vehicles and the efficiency 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 efficiency
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 different 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.
2. Related 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 traffic
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 efficiency 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 difference 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 different metaheuristics [18, 19, 20, 21].
When different vehicles in the system are owned by different 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 different 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 different 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 coefficient. 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 coefficient
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.
3. Problem description
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.
3.1. Motivation
In the context of the VRP we have described before, there might exist multiple solutions with
different 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 different results in
terms of costs of the vehicle routes when considering different social welfare measures. In the
following subsection, we will analyse the welfare measures we use in more detail.
3.2. Social welfare measures
Utilitarian social welfare is related with the overall cost or benefit of all individuals compos-
ing 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-off actor is minimised/maximised, respectively. In particular,
maximising egalitarian social welfare in m-TSP translates into minimising the route cost of
the worst-off 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-off 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 differences 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
(a) Utilitarian s. welfare (b) Systematic egalitarian (c) Systematic elitist s. wel-
s. welfare fare
Figure 1: Examples of routing approaches focusing on different social welfare measures impacting
distinctly individual vehicle and overall fleet cost.
police) where any of the vehicles in a fleet needs to reach an incident location as soon as possible.
Note that the solution will depend on additional constraints on the vehicles’ routes. Opposite to
the egalitarian social welfare, elitist social welfare only looks at the cost of the best-off vehicle,
with no regard for other vehicles. The minimum cost of the routes found by using elitist social
welfare represents a lower bound on any vehicle route’s cost.
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-off and the best-off vehicle, respectively,
without considering the distribution of the costs of the other vehicles’ routes. Thus, we can
obtain different solutions with equal egalitarian or elitist social welfare optimum value but with
inefficient 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-off
vehicle and then, in an iterative way, repeats the same with every other vehicle in a non-
increasing preference order based on the vehicles routes’ costs up to the best-off vehicle with
the least costly route. The systematic elitist social welfare approach, similarly, applies elitist
social welfare maximisation iteratively, starting from the best-off and ending with the worst-off
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-off/best-off 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-off/best-off vehicle but they also consider all the other vehicles in the fleet.
An example of the differences 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
Figure 2: Differences between egalitarian social welfare and systematic egalitarian social welfare.
in Figures 2a and 2b, respectively. Both sets of the routes minimise the cost of the worst-off
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.
3.3. Problem formulation
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 Miller-
Tucker-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 𝑐𝑖𝑗 𝑥𝑖𝑗𝑣 (1)
𝑣∈𝒱 𝑖∈𝒩 𝑗∈𝒩
Table 1
Elements of mTSP
Sets Description
𝒩 Set of vertices 𝑖, 𝑗 ∈ 𝒩 .
𝒩𝑐 Set of destinations, 𝒩𝑐 = 𝒩 ∖ {1}.
{1} Depot.
𝒜 Set of arcs (𝑖, 𝑗) ∈ 𝒜.
𝒱 Set of vehicles 𝑣 ∈ 𝒱.
Variable Description
𝑥𝑖𝑗𝑣 𝑥𝑖𝑗𝑣 = 1 if vehicle 𝑣 ∈ 𝒱 goes from vertex 𝑖 ∈ 𝒩 to vertex 𝑗 ∈ 𝒩 and 0 otherwise.
𝑢𝑖 ≥ 0. Auxiliary subcircuit avoidance variable. If a vehicle goes from vertex 𝑖 ∈ 𝒩𝑐
𝑢𝑖
to vertex 𝑗 ∈ 𝒩𝑐 , the value of 𝑢𝑗 has to be higher than the value of 𝑢𝑖 .
Parameters Description
𝑐𝑖𝑗 Cost of going from vertex 𝑖 ∈ 𝒩 to vertex 𝑗 ∈ 𝒩 .
∑︁ ∑︁
s. t. 𝑥𝑖𝑗𝑣 = 1 ∀𝑗 ∈ 𝒩𝑐 , (2)
𝑣∈𝒱 𝑖∈𝒩
∑︁ ∑︁
𝑥𝑖𝑗𝑣 = 𝑥𝑗𝑘𝑣 ∀𝑗 ∈ 𝒩 , ∀𝑣 ∈ 𝒱, (3)
𝑖∈𝒩 𝑘∈𝒩
∑︁
𝑥1𝑗𝑣 = 1 ∀𝑣 ∈ 𝒱 (4)
𝑗∈𝒩𝑐
∑︁
𝑢𝑗 − 𝑢𝑖 ≥ 1 − (𝑁 − 𝑉 )(1 − 𝑥𝑖𝑗𝑣 ) ∀𝑖, 𝑗 ∈ 𝒩𝑐 : 𝑖 ̸= 𝑗, (5)
𝑣∈𝒱
1 ≤ 𝑢𝑖 ≤ 𝑁 − 𝑉 𝑖 ∈ 𝒩𝑐 , (6)
𝑥𝑖𝑗𝑣 ∈ {0, 1} 𝑖, 𝑗 ∈ 𝒩 , ∀𝑣 ∈ 𝒱, (7)
where constraints (2) state that each vertex should be visited exactly once; constraints (3)
are the flow conservation constraints that state that if a vehicle visits a vertex, it should leave
the same vertex; constraints (4) force each vehicle to leave the depot; constraints (5) are used
to avoid subcircuits and determine the order in which the vertices are transited. The last two
constraints (6) and (7) define the range of the decision variables.
Claim. Model (1)-(7) is equivalent to model (35)-(39) in [27], but with lower bounds on the
auxiliary variables 𝑢𝑖 for all 𝑖 ∈ 𝒩𝑐 .
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 (4). Therefore, let
𝒩𝑐𝑓 be a set of vertices that are visited first when vehicles leave the depot. Then, the minimum
value of 𝑢𝑖 is 1 for 𝑖 ∈ 𝒩𝑐𝑓 , and |𝒩𝑐𝑓 | = 𝑉 . In the worst case, all vehicles except one return to
the depot from the first visited vertex and this last vehicle visits the rest of the (𝑁 − 𝑉 − 1)
vertices. This vehicle, thus, visits in total 𝑁 − 𝑉 vertices. For the last vertex 𝑙 ∈ 𝒩𝑐 it visits,
it sets the value of its auxiliary variable 𝑢𝑙 = 𝑁 − 𝑉 . This value is exactly the number of
vertices in its path up to vertex 𝑙 considering deposit vertex. Here, we can observe that for
𝑁 ≤ 𝑉 , the problem has no solution because the constraints (4) are not satisfied. Therefore,
the necessary assumption is that 𝑁 > 𝑉 . Then, 𝑁 − 𝑉 is a better upper bound of 𝑢𝑖 than 𝑁
for each destination 𝑖 ∈ 𝒩𝑐 . Furthermore, thanks to this new upper bound of 𝑢𝑖 , for all vehicles
𝑣 ∈ 𝒱 and mutually different vertices 𝑖, 𝑗 ∈ 𝒩𝑐 (with 𝑖 ̸= 𝑗), the following is always satisfied:
𝑁 −𝑉 ≥𝑢𝑖 𝑢𝑗 ≥1
𝑢𝑗 − 𝑢𝑖 ≥ 𝑢𝑗 − (𝑁 − 𝑉 ) ≥ 1 − (𝑁 − 𝑉 ) > 1 − 𝑁.
Therefore, constraints (5) are more restrictive than constraints (38) in [27].
4. Solution approach
In this section, we modify the mTSP formulation (Equations (1)–(7)) to balance efficiency and
fairness in a fleet. We study utilitarian, egalitarian, and elitist social welfare and describe the
aforementioned systematic approaches for the latter two.
4.1. Utilitarian social welfare model
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 𝑐𝑖𝑗 𝑥𝑖𝑗𝑣 (8)
𝑣∈𝒱 𝑖∈𝒩 𝑗∈𝒩
s. t. (2) − (7) (9)
4.2. Egalitarian and systematic egalitarian social welfare model
As mentioned before, the utilitarian model in Equations (8)–(9) only focuses on the overall
performance of the fleet. By doing so, the found solution may be unfair as, in general, there may
be no limit on the differences between the costs of the routes assigned to individual vehicles.
The egalitarian social welfare model does take into account these differences by minimising the
maximum cost of the worst-off vehicle applying the constraints of the mTSP. Formally:
minimise 𝑧 (10)
s. t. (2) − (7) and
∑︁ ∑︁
𝑐𝑖𝑗 𝑥𝑖𝑗𝑣 ≤ 𝑧, ∀𝑣 ∈ 𝒱, (11)
𝑖∈𝒩 𝑗∈𝒩
𝑧 ≥ 0. (12)
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-off 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 (10)–(12). This vehicle, together with the vertices assigned to its route, is ignored in
the following iterations. The solution process runs until there are no more unassigned vehicles.
4.3. Elitist and systematic elitist social welfare
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-off vehicle route cost. To achieve it, we introduce 𝑉 binary auxiliary
variables 𝑦𝑣 , and a constant 𝑀 , which takes an arbitrary large value. Formally:
minimise 𝑧 (13)
s. t. (2) − (7) and
∑︁
𝑦𝑣 = 𝑉 − 1, (14)
𝑣∈𝒱
∑︁ ∑︁
𝑐𝑖𝑗 𝑥𝑖𝑗𝑣 − 𝑧 ≤ 𝑀 𝑦𝑣 , ∀𝑣 ∈ 𝒱, (15)
𝑖∈𝒩 𝑗∈𝒩
𝑦𝑣 ∈ {0, 1}, ∀𝑣 ∈ 𝒱, (16)
𝑧 ≥ 0. (17)
Constraint (14) fixes the value of only one variable 𝑦𝑣 to 0, while all the others will be equal
to 1. Constraints (15) limit the lowest assigned route cost to 𝑧. Thus, we minimise the value of
𝑧, which is the cost of the route with minimum cost assigned to any of the agents.
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 (13)– (17)
where, in each iteration, the assigned route of the lowest cost and its related vehicle and vertices
are ignored in all subsequent iterations. However, note that the way we model the systematic
elitist social welfare reduces to finding the first 𝑉 − 1 shortest loops (1 → 𝑖 → 1), where 𝑖 ∈ 𝒩𝑐 ,
and to assigning them to the first 𝑉 − 1 vehicles. As the result, the last vehicle passes through
all the remaining vertices of the graph; its route is obtained by solving the travelling salesman
problem over 𝑁 − 𝑉 + 1 vertices.
5. Functional experiments
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 efficiency and
fairness of the proposed solutions.
(a) Irregular graph (b) Regular grid graph
Figure 3: Coordinates of the 9 vertices of the two example complete graphs (each vertex is connected
with every other vertex).
Experiment 1 is carried out in the example graph shown in Figure 3a. We can see the different
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 difference between the best and the worst-off
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 differences between the worst-off and the
best-off 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 different 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
(a) Utilitarian s. welfare (b) Systematic egalitarian (c) Systematic elitist s. wel-
s. welfare fare
Figure 4: Solution obtained in experiment 2 on a complete regular grid graph with 3 vehicles initially
positioned in the depot located at left down corner vertex number 1.
(a) Utilitarian s. welfare (b) Systematic egalitarian (c) Systematic elitist s. wel-
s. welfare fare
Figure 5: Solution obtained in experiment 3 on a complete regular grid graph with 3 vehicles initially
positioned in the depot located at the centre vertex number 5.
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.
6. Conclusions
In this paper, we studied the vehicle routing problem where a fleet composed of vehicles belong-
ing to different 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
efficient 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 different fairness and efficiency criteria of the routes: utilitarian
social welfare considers the overall vehicles routes’ cost, egalitarian social welfare gets an upper-
Table 2
Distances travelled by each vehicle and global measure obtained with the different social welfare
functions in the different experiments.
V1 V2 V3 O. cost Av. Max. Min. Range
Util 2.61 6 1.2 9.81 3.27 6 1.2 4.8
Exp. 1 Egal 3.61 3.61 3.41 10.63 3.55 3.61 3.41 0.2
Elit 1.2 2 7.24 10.41 3.47 7.24 1.2 6.04
Util 8.82 2 2 12.82 4.27 8.82 2 6.82
Exp. 2 Egal 5.24 5.24 5.65 16.13 5.37 5.65 5.24 0.41
Elit 2 2 8.82 12.82 4.27 8.82 2 6.82
Util 3.41 5.41 3.41 12.23 4.07 5.41 3.41 2
Exp. 3 Egal 4.82 4 3.41 12.23 4.07 4.82 3.41 1.41
Elit 2 2 8.82 12.82 4.27 8.82 2 6.82
bound 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-off and the best-off vehicle,
respectively, we proposed the systematic egalitarian/elitist welfare solution approaches that
not only minimise the costs of the worst-off/best-off 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-off vehicle and in
other cases, it may be unfair, introducing big differences 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 efficient 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.
References
[1] G. B. Dantzig, J. H. Ramser, The truck dispatching problem, Management science 6 (1959)
80–91.
[2] M. M. Flood, The traveling-salesman problem, Operations research 4 (1956) 61–75.
[3] M. Gansterer, R. F. Hartl, Collaborative vehicle routing: A survey, European Journal of
Operational Research 268 (2018) 1–12.
[4] M. Gansterer, R. F. Hartl, Shared resources in collaborative vehicle routing, Top 28 (2020)
1–20.
[5] C. Cleophas, C. Cottrill, J. F. Ehmke, K. Tierney, Collaborative urban transportation: Recent
advances in theory and practice, European Journal of Operational Research 273 (2019)
801–816.
[6] M. Lujak, S. Giordani, A. Omicini, S. Ossowski, Decentralizing coordination in open vehicle
fleets for scalable and dynamic task allocation, Complexity 2020 (2020).
[7] M. Lujak, E. Sklar, F. Semet, Agriculture fleet vehicle routing: A decentralised and dynamic
problem, AI Communications 34 (2021) 55–71.
[8] M. Lujak, S. Giordani, S. Ossowski, Fair route guidance: Bridging system and user opti-
mization, in: 17th International IEEE Conference on Intelligent Transportation Systems
(ITSC), IEEE, 2014, pp. 1415–1422.
[9] T. Vidal, G. Laporte, P. Matl, A concise guide to existing and emerging vehicle routing
problem variants, European Journal of Operational Research 286 (2020) 401–416.
[10] A. Daoud, H. Alqasir, Y. Mualla, A. Najjar, G. Picard, F. Balbo, Towards explainable
recommendations of resource allocation mechanisms in on-demand transport fleets, in:
International Workshop on Explainable, Transparent Autonomous Agents and Multi-Agent
Systems, Springer, 2021, pp. 97–115.
[11] N. Jozefowiez, F. Semet, E.-G. Talbi, An evolutionary algorithm for the vehicle routing
problem with route balancing, European Journal of Operational Research 195 (2009)
761–769.
[12] E. E. Halvorsen-Weare, M. W. Savelsbergh, The bi-objective mixed capacitated general
routing problem with different route balance criteria, European Journal of Operational
Research 251 (2016) 451–465.
[13] J. Oyola, A. Løkketangen, Grasp-asp: An algorithm for the cvrp with route balancing,
Journal of Heuristics 20 (2014) 361–382.
[14] N. Jozefowiez, F. Semet, E.-G. Talbi, Target aiming pareto search and its application to the
vehicle routing problem with route balancing, Journal of Heuristics 13 (2007) 455–469.
[15] P. Matl, R. F. Hartl, T. Vidal, Leveraging single-objective heuristics to solve bi-objective
problems: Heuristic box splitting and its application to vehicle routing, Networks 73 (2019)
382–400.
[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-and-
enumeration 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 meta-
heuristic 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, Bi-
objective 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.