On balancing fairness and efficiency in routing cooperative vehicle fleets

The presentation is the introduction of myself and the project Agrobots, this includes the objectives, methodology, and perspective of the work.

1. On balancing fairness and efficiency
in routing of cooperative vehicle fleets
Aitor L´opez S´anchez
Rey Juan Carlos University
May 25, 2022
Aitor L´opez S´anchez (URJC) AGROBOTS May 25, 2022

2. Index
1
Myself
2
Motivation
3
First approach to the problem
4
Mathematical formulation and first results
5
Conclusions
Aitor L´opez S´anchez (URJC) AGROBOTS May 25, 2022

3. Myself
Index
1
Myself
2
Motivation
3
First approach to the problem
4
Mathematical formulation and first results
5
Conclusions
Aitor L´opez S´anchez (URJC) AGROBOTS May 25, 2022

4. Myself
Myself
Name:Aitor L´opez S´anchez
Studies:
University of Murcia, Spain
■Doble Degree Program in
Mathematics and Computer
Science
Polytechnic University of Madrid,
Spain
■Master’s Artificial
Intelligence
Aitor L´opez S´anchez (URJC) AGROBOTS May 25, 2022

5. Motivation
Index
1
Myself
2
Motivation
3
First approach to the problem
4
Mathematical formulation and first results
5
Conclusions
Aitor L´opez S´anchez (URJC) AGROBOTS May 25, 2022

6. Motivation
Motivation
■Collaborative routing.
■Decrease the cost.
■Sustainable and fair economy.
■Coordination of large and heterogeneous vehicle fleets.
Cooperative last-mile delivery
Aitor L´opez S´anchez (URJC) AGROBOTS May 25, 2022

7. Motivation
Techniques
Solutions:
■Optimisation techniques.
Vehicle routing problem (VRP).
Fairness.
■Multi agent systems.
Dynamic.
Decentralised.
Objective:
■How can distributed coordination improve the efficiency and
autonomy of vehicle fleets while decreasing their cost and dependence
on humans?
Aitor L´opez S´anchez (URJC) AGROBOTS May 25, 2022

8. First approach to the problem
Index
1
Myself
2
Motivation
3
First approach to the problem
4
Mathematical formulation and first results
5
Conclusions
Aitor L´opez S´anchez (URJC) AGROBOTS May 25, 2022

9. First approach to the problem
First approach
Vehicle Routing Problem
VRP is a combinatorial optimisation problem that tries to obtain the
routes of a fleet of vehicles that minimise the total cost of the trips.
Image from [1].
Aitor L´opez S´anchez (URJC) AGROBOTS May 25, 2022

10. First approach to the problem
Fairness
The success of the cooperative will depend on the balance between
fairness and efficiency in the shared fleet.
Resource:Cost, Travel time, Total time or Num. of Tasks.
Social Welfare:
■Utilitarian
min
r∈routes
X
v∈vehicles
cv(r)
■Egalitarian
min
r∈routes
max
v∈vehicles
{cv(r)}
■Elitist
min
r∈routes
min
v∈vehicles
{cv(r)}
Aitor L´opez S´anchez (URJC) AGROBOTS May 25, 2022

11. First approach to the problem
Systematic social welfare
Systematic social welfare: Each vehicle is the result of applying social
welfare.
Egalitarian social welfareSystematic egalitarian social welfare
Aitor L´opez S´anchez (URJC) AGROBOTS May 25, 2022

12. Mathematical formulation and first results
Index
1
Myself
2
Motivation
3
First approach to the problem
4
Mathematical formulation and first results
5
Conclusions
Aitor L´opez S´anchez (URJC) AGROBOTS May 25, 2022

13. Mathematical formulation and first results
VRP Formulation
Elements of the formal VRP.
Sets Description
N Set of nodesi,j∈ N.
Nc Set of tasks,Nc=N \ {1}.
{1} Depot.
A Set of edges (i,j)∈ A.
V Set of vehiclesv∈ V.
Variable Description
xijv xijv= 1 if the vehiclev∈ Vgoes from nodei∈ Nto nodej∈ N.
ui
Auxiliar variable. If a vehicle drives from nodei∈ Ncto nodej∈ Nc,
the valueuiof has to be bigger than the value ofuj.
Parameters Description
cij Euclidean cost going from nodei∈ Nto nodej∈ N.
Aitor L´opez S´anchez (URJC) AGROBOTS May 25, 2022

14. Mathematical formulation and first results
VRP Formulation
minfo(x) (1)
s. t.xiiv= 0 ∀v∈ V,∀i∈ N, (2)
X
v∈V
X
i∈N
xijv= 1 ∀j∈ Nc, (3)
X
i∈N
xijv=
X
i∈N
xjiv ∀j∈ N,∀v∈ V, (4)
X
j∈Nc
x1jv= 1 ∀v∈ V (5)
uj−ui≥1−(N−V)(1−
X
v∈V
xijv) ∀i,j∈ Nc:i̸=j, (6)
1≤ui≤N−V i ∈ Nc, (7)
xijv∈ {0,1}, i,j∈ N,∀v∈ V, (8)
Aitor L´opez S´anchez (URJC) AGROBOTS May 25, 2022

15. Mathematical formulation and first results
Fairness Functions I
Utilitarian socaial welfare:Minimise the total cost of the routes.
min
X
v∈V
X
i∈N
X
j∈N
cijxijv
s. t.
(2)−(8)
Aitor L´opez S´anchez (URJC) AGROBOTS May 25, 2022

16. Mathematical formulation and first results
Fairness Functions II
Egalitarian welfare:Minimise the most costly route.
minz
s. t.
(2)−(8)
X
i∈N
X
j∈N
cijxijv≤z∀v∈ V,
z≥0.
Aitor L´opez S´anchez (URJC) AGROBOTS May 25, 2022

17. Mathematical formulation and first results
Fairness Functions III
Elitist social welfare:Minimise the minimum cost of the routes.
minz
s. t.
(2)−(8)
X
i∈N
X
j∈N
cijxijv−z≤Myv,∀v∈ V
X
v∈V
yv=V−1,
M=∞,
yv∈ {0,1}, ∀v∈ V,
z≥0.
Conclusion:We obtain very different solutions between the three different
fairness functions.
Aitor L´opez S´anchez (URJC) AGROBOTS May 25, 2022

18. Conclusions
Index
1
Myself
2
Motivation
3
First approach to the problem
4
Mathematical formulation and first results
5
Conclusions
Aitor L´opez S´anchez (URJC) AGROBOTS May 25, 2022

19. Conclusions
Conclusions
■First approach of the fair cooperative vehicle routing problem.
■First mathematical model of FC-VRP.
Homogeneous vehicles.
One deposit.
No capacity.
Minimise cost.
No time per task.
■Fist definitions of fairness in collaborative environments.
Aitor L´opez S´anchez (URJC) AGROBOTS May 25, 2022

20. Conclusions
References
[1]
edge weighting-based optimization of vehicle routing problems.
Processes, 8(11), 2020.
[2]
decentralised and dynamic problem.AI Communications, 34(1):55–71,
2021.
Aitor L´opez S´anchez (URJC) AGROBOTS May 25, 2022

21. Conclusions
Final
Thank you very much for your attention
Aitor L´opez S´anchez (URJC) AGROBOTS May 25, 2022