How to achieve fair and efficient cooperative vehicle routing?

Abstract

A cooperative is a business entity with the primary objective of providing benefits, services, and goods to its members, who both own and exercise democratic control over it. In the context of a cooperative, a fleet typically consists of vehicles owned by self-concerned individually rational owners who prioritize their own efficiency and the fairness of the system. This fairness refers to how their individual gain aligns with the gain of others. In this paper, we focus on the routing of such cooperative fleets. Considering only the fleet’s efficiency in terms of minimising its overall cost, the studied problem corresponds to the multiple Traveling Salesman Problem (mTSP). However, our interest lies in finding both efficient and fair solutions, so we propose two new variants of this problem that integrate and maximise the fleet’s egalitarian and elitist social welfare. Additionally, to enhance the balance between fleet efficiency and fairness, we propose the systematic elitist and systematic egalitarian social welfare optimisation algorithm. Through simulation results, we observe a wide diversity of routes depending on the approach considered. Therefore, a cooperative may choose a model that best balances its fleet’s efficiency and fairness based on its specific requirements.

Keywords

Vehicle Routing Problem multiple traveling salesman problem collaborative routing intelligent vehicles fair and efficient routing

1. Introduction

Cooperatives are business entities where ownership and democratic control are entrusted to their member-owners. Diverging from the conventional business model, each member possesses the right to actively participate in the decision-making process governing the operation of the cooperative (see, e.g., [31]). The provision of services or goods by the cooperative is designed to serve the collective interests of all member-owners.

Cooperatives are prevalent within the agriculture industry, as they embody the concept of a shared economy, which plays a pivotal role in enhancing resource utilization efficiency and effectiveness. In this domain, cooperatives serve as collective platforms where farmers can consolidate their resources for various purposes, including land cultivation, as well as offering, aggregating, marketing, and processing services. However, resource-sharing in this context presents significant computational challenges, primarily due to the involvement of heterogeneous fleets comprising tractors, agricultural mobile robots (AMR), and associated machinery specifically designed for farm sensing and actuation.

A cooperative fleet consists of a collection of vehicles and equipment that are usually owned by self-interested individuals, which include member-owners and rental companies. The primary focus of these individuals in engaging in vehicle sharing is to maximise their own benefits while minimising the costs associated with the vehicles’ operations. Additionally, they emphasize the importance of fairness within the system, ensuring that their gains are equitable related to the gains of other participants. To be part of a cooperative fleet, vehicle owners must make individually rational decisions based on their self-interest. They willingly share their vehicles and participate in the fleet only if it is advantageous for them on an individual level. This implies that their involvement in the fleet should yield personal benefits, aligning with their own goals and objectives.

Considering efficiency in terms of the minimisation of the overall fleet costs, in this paper, we study fairness in cooperative routing of a fleet of homogeneous vehicles. Since vehicles can join and leave a cooperative fleet based on their owners’ individual interests, the cooperative fleet aims to satisfy a given demand and minimise the fleet’s overall workload cost while considering fairness in its distribution among the fleet’s vehicles.

Cooperatives are usually large enterprises whose fleets may be of substantial size. By increasing the number of vehicles in the fleet, the number of possible combinations of allocating vehicles to the tasks also increases, which, in its turn, allows for decreasing the overall fleet’s costs. optimising economic efficiency of allocation of customers to visit (tasks to perform) to the vehicles in the fleet in terms of maximising the overall profit and/or minimising the overall cost of the fleet is often a conflicting objective with maximising fairness. Fairness may be considered as the quality of treating individuals equally or in a way that is right or reasonable. Within the scope of this paper, we consider fairness in terms of distributive justice, which is concerned with the equitable distribution of burdens and benefits that arise from social cooperation among vehicle agents, who possess competing objectives and requirements. This approach studies how task allocation to vehicle routes comes about and is not concerned about the impact on the overall cost of the entire fleet (see, e.g., [14]).

Finding a good efficiency-fairness balance is essential for the survival and growth of a cooperative fleet over time. Insufficient fairness can deter potential members from joining a cooperative, despite the potential cost reduction compared to individual competition. Even more, an insufficiently fair cooperative may be a reason for cooperative members to abandon the system and join a fairer one, thus putting in jeopardy its survival. Thus, cooperative vehicle routing mechanisms that are both efficient globally for the fleet as a whole and fair individually for each vehicle in the fleet are essential for cooperative fleet prosperity.

In this paper, we study economic welfare to tackle this issue in the context of cooperative vehicle routing. Broadly, economic welfare is the level of prosperity or well-being that individuals or groups experience as a result of their activities and conditions. In the field of economics, it specifically refers to utility gained through the achievement of material goods and services. A utilitarian welfare function sums the utility of each individual in order to obtain society’s overall welfare. Generally, the optimisation of utilitarian social 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. The egalitarian welfare, on the other hand, defends the position that equality is central to justice. It postulates that the best social policy is the one which ensures equality of cost/benefit distribution among all the members of a system. Contrarily, elitism revolves around the belief that only a small fraction of members truly changes a system since they have an intrinsic quality and are more likely to be constructive to society as a whole, and therefore deserve influence or authority greater than that of others.

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), both without any concern for other agents.

The aim of this study is to develop a methodology for equitable distribution of routes among vehicles in a cooperative fleet in order to achieve both fairness and cost efficiency. This is done by incorporating the concepts of utilitarian, egalitarian, and elitist social welfare into the mathematical model of the uncapacitated Vehicle Routing Problem (VRP). In contrast to the capacitated VRP, the uncapacitated VRP is a variant of the VRP where vehicles have unlimited carrying capacities (see, e.g., [3]). The studied problem corresponds to the multiple Traveling Salesman problem (mTSP) that considers a set of customers (destinations or tasks) to visit in a region of interest by a set of vehicles starting and ending their routes in a depot. Each customer has to be visited exactly once and by only one vehicle. The objective of the conventional mTSP is to minimise the overall cost associated with the movements of the vehicles.

Moreover, note that neither the egalitarian social welfare nor the elitist social welfare consider the distribution of the costs or benefits among all the agents in the system. They only consider the worst-off and the best-off agent, respectively. To resolve this issue, in this paper, we also present the systematic egalitarian social welfare optimisation algorithm and the systematic elitist social welfare optimisation algorithm that not only minimise the cost of the worst-off and the best-off vehicle, respectively, but also consider finding efficient and fair routes for all the other vehicles in the fleet.

The rest of the paper is organised as follows. In Section 2, we resume the most relevant works on balancing fairness and efficiency in collaborative vehicle routing. In Section 3, we describe the problem and present the starting mathematical model for conventional mTSP. In Section 4, the mTSP model is modified for the three welfare measures and we present algorithms for the systematic egalitarian social welfare and systematic elitist social welfare optimisation. Section 5 analyses and compares the results of the proposed approaches in a set of experiments in structured as well as randomly created transportation networks. We analyse fairness and efficiency measures of the proposed algorithms as well as their computational complexity considering the execution times. Finally, Section 6 closes the article giving an overview of the proposed models and algorithms and the achieved results with indications about future work.

2. Related work

The VRP was first introduced in 1959 by Dantzig and Ramser [5], and is a generalisation of the famous travelling salesman problem (TSP) [8]. 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 ${CO}_{2}$ emissions, and share costs in large vehicle fleets [4,9,10]. [9,10] review the state of the art related to horizontal collaborations between companies, i.e., sharing of customers and routes between companies with the same characteristics to reduce travel costs. In [4], 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 vehicles’ trips 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 many cases are in conflict with the cost reduction (e.g. [6,19–22,32]). 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 [16]. 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 [13,16]. A formulation for the two-objective version, minimising the cost and the difference in distance travelled by the vehicles can be found in [28]. Due to the added complexity of solving more than one objective and analysing the various non-dominated solutions (Pareto optimal [15]), the solution process involves using various techniques such as transforming the bi-objective problem into a single objective problem [25], column generation techniques [7,11] or the use of different metaheuristics [12,27,30,34].

When different vehicles in a fleet are owned by different actors (agents), it is no longer important to consider only the balance between vehicle routes. It is also necessary to introduce other metrics representing fairness, equality, and equity in the generated routes. In [24], 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 for each agent. Some examples of functions are the rank function, maximum, standard deviation or the Gini coefficient. In [35], Wu et al. 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 $l_{p}$ norms since they have (non-negative, symmetry, monotonic, quasi-convexity) properties that benefit the convergence of the model [2].

When applying the concept of fairness to large fleets of vehicles belonging to multiple 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 their owners are balanced. The method proposed by [17] 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 [29] 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.

An Agriculture Fleet Vehicle Routing Problem (AF-VRP) described in [22] not only involves the creation of an optimal route for each vehicle in the fleet, but it also considers fairness and justice concepts for each of the mutually collaborating owners of the vehicles, since an individual owner does not want their vehicles to accumulate a too high cost or a too low profit in relation to the others.

Zibaei et al. [36] propose a cooperative vehicle routing problem for (capacitated) multi-depot VRP where each depot with only one vehicle in it (both owned by a single owner) has its own customers and can also serve the customers of partners. Each customer is visited by exactly one vehicle. The routing problem is solved for an individual vehicle/depot with its own customers and for any coalition (combination) of vehicles considering customer sharing. When the routing cost for any coalition is smaller than the accumulated cost of its vehicles considered individually, the owners (considered players of a cooperative game) have the incentive to coordinate with each other. The key mechanisms of the game are presented for this setting including its Shapley value, game core, τ value and the equal cost saving method that provides a stable and uniform allocation of vehicles’ routes. Based on the results obtained from the cost saving allocation, the owners can decide about joining the coalitions that bring them more profit. How to achieve that is not the topic of the paper. Moreover, solving the problem for any coalition structure is computationally expensive and intractable.

To the best of our knowledge, the state of the art on balancing fairness and efficiency in a cooperative fleet vehicle routing problem is scarce or missing. While [22] provided qualitative discussions on this topic, it did not include mathematical modeling formalizations or algorithmic solution approaches. The present work is an extended version of [18]. The aim is to provide the formalization of the problem through proposed mathematical models as well as to propose computationally efficient routing algorithms that balance the fairness and efficiency of a cooperative fleet. The key distinctions between this work and [18] lie in the introduction of the systematic egalitarian social welfare optimisation algorithm (SEGSW) and the systematic elitist social welfare optimisation algorithm (SELSW) for the optimisation of egalitarian and elitist social welfare concepts introduced in [18], as well as the inclusion of extended functional experiments presented in Section 5.

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 VRP context described before, there exist multiple routing solutions that consider different social welfare measures and may impact differently the individual performance of vehicles or the overall performance of the fleet.

In Fig. 1, we present an example of this problem where we deal with a transportation network modelled as a complete digraph composed of 9 vertices and a fleet of 3 vehicles.1

¹
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. Only the task vertices are presented in the graph, and the transit vertex are implicit in the arcs. 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 tasks will be performed once and only once by a single vehicle of the fleet.

The vehicles that are initially positioned at the depot located at vertex 1 must visit all the other vertices collaboratively where one and only one vehicle must visit each vertex and, in the end, return to the depot. The vehicles’ itineraries are represented by red-dotted, green-broken, and blue-full lines. The circuit cost is the sum of the costs of individual arcs passed by a vehicle. Here, the cost of the arcs is the Euclidean distance between the nodes. The blue-full and green-broken lines correspond to the worst-off and best-off vehicle.

The three different routing solutions correspond to optimal solutions under the consideration of different social welfare measures. Figure 1a represents a routing solution considering the optimisation of the utilitarian social welfare of the fleet (minimise the overall cost). Figure 1b gives us a egalitarian social welfare solution (minimise the worst-off cost), while Fig. 1c provides a elitist social welfare solution (minimise the best-off cost). The differences in the routing of the vehicles are obvious and in the following subsection, we will describe the used welfare measures in more detail.

Fig. 1.

Examples of routing approaches focusing on different social welfare measures impacting distinctly individual vehicles’ and the overall fleet’s cost. The colours of the vehicles are the same in all three figures.

3.2. Social welfare measures

Utilitarian social welfare (USW) considers the overall cost or profit of the system as a whole. Maximising the utilitarian social welfare in the routing of fleets composed of homogeneous vehicles 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 overall cost obtained by maximising utilitarian social welfare represents a lower bound of the overall routes’ cost for the whole vehicle fleet.

Egalitarian social welfare (EGSW) is a concept that increases fairness in terms of equality Here, the cost/profit of the worst-off agent in the system is minimised/maximised. 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 value of the routing solution that optimises egalitarian social welfare will be an upper bound for the maximum cost that each vehicle’s route can assume; any solution that involves a vehicle travelling more than that distance could be considered less fair from the egalitarian point of view.

Elitist social welfare (ELSW) has 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 police) where any of the vehicles in a fleet needs to reach an incident location as soon as possible. Opposite to 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.

As we have commented, optimal egalitarian or elitist solutions only consider the worst-off or best-off vehicle, but do not constrain the routes chosen for the other vehicles. We can obtain different solutions with equal egalitarian or elitist social welfare optimum value but with less or more efficient route distributions for the rest of the vehicles. As an alternative, in this paper, we present the Systematic egalitarian social welfare optimisation (SEGSW) and the Systematic elitist social welfare optimisation (SELSW) as methods that calculate optimal solutions for egalitarian or elitist social welfare, but also consider the distribution of the routes for all vehicles in a fleet.

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 an iteration, we ignore the worst-off/best-off vehicle and the vertices that it visits in the next iteration, where we calculate a solution for the remaining vertices and vehicles. This process is repeated until there are no more remaining vertices to visit or vehicles without an assigned route. In this way, the two systematic approaches do not focus only on the worst-off/best-off vehicle but they also consider all the other vehicles in the fleet.

Fig. 2.

Differences between egalitarian social welfare and systematic egalitarian social welfare.

An example of the differences in the routes that can be obtained by applying egalitarian social welfare versus systematic egalitarian social welfare (in this case for 3 vehicles) is presented in Figs 2a and 2b, respectively. Both sets of routes minimise the cost of the worst-off vehicle, coloured in green. However, the cost of the blue and red circuits in Fig. 2a is higher than the cost of the routes in Fig. 2b. By applying the systematic egalitarian social welfare approach, we obtain a more efficient solution from an (utilitarian) point of view. That is, we reduce the overall cost.

It is interesting to analyse another criterion in Fig. 2: fairness. If we consider a fair solution as one where the cost differences between the vehicle routes are small, that is, that the cost range between the best and the worst vehicle route is small, the solution of Fig. 2a is fairer than the one of Fig. 2b. However, it is clear that this solution unnecessarily increases the cost of two of the three vehicles by assigning them both a more costly route. This indicates that fairness by itself (defined in this way) is not an appropriate measure. In fact, from a purely individual utilitarian point of view, none of the vehicles/agents would be better of with the solution provided in Fig. 2a and thus, from a rational perspective should prefer the less costly route over the “fairer” but more costly distribution. The former type of solution is exactly what we aim to achieve with the systematic egalitarian and systematic elitist welfare algorithm that we propose in this paper.

3.3. Problem formulation

Let us consider a complete arc-weighted digraph $(N, A)$ composed of a set N of vertices of size $| N |$ , and a set A of arcs $(i, j)$ with $i \neq j$ representing a transportation network. The cost of travel for each arc $(i, j) \in A$ is given by parameter $c_{i j} ⩾ 0$ . We study a generic case where $c_{i j}$ is not necessarily equal to $c_{j i}$ . We assume that vertex $d \in N$ is the depot and $N_{c} = N ∖ {d}$ is the set of the vertices to visit (called customers, destinations, demands or tasks). 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 set V representing a fleet of vehicles, where $| V |$ is the cardinality of the set. Vehicles $v \in V$ that are initially positioned in vertex d must visit all vertices in $N_{c}$ and return back to vertex d such that each of the vertices in $N_{c}$ is visited by a single vehicle. We use a 3-index binary decision variable $x_{i j v}$ , whose value is 1 if the route of vehicle v visits consecutively vertices i and j, and 0 otherwise. The sets, indices, and parameters of the studied problem are presented in Table 1.

Table 1
Elements of the studied problem

Sets Description

N Set of vertices $i, j \in N$ .

d Depot.

$N_{c}$ Set of destinations, $N_{c} = N ∖ {d}$ .

A Set of arcs $(i, j) \in A$ .

V Set of vehicle agents $v \in V$ .

Variable Description

$x_{i j v}$ $x_{i j v} = 1$ if vehicle $v \in V$ goes from vertex $i \in N$ to vertex $j \in N$ and 0 otherwise.

$u_{i}$ Auxiliary subcircuit avoidance variable where $u_{i} ⩾ 0$ .

Parameters Description

$c_{i j}$ Cost of travelling from vertex $i \in N$ to vertex $j \in N$ .

Sets	Description
N	Set of vertices $i, j \in N$ .
d	Depot.
$N_{c}$	Set of destinations, $N_{c} = N ∖ {d}$ .
A	Set of arcs $(i, j) \in A$ .
V	Set of vehicle agents $v \in V$ .
Variable	Description
$x_{i j v}$	$x_{i j v} = 1$ if vehicle $v \in V$ goes from vertex $i \in N$ to vertex $j \in N$ and 0 otherwise.
$u_{i}$	Auxiliary subcircuit avoidance variable where $u_{i} ⩾ 0$ .
Parameters	Description
$c_{i j}$	Cost of travelling from vertex $i \in N$ to vertex $j \in N$ .

We start with the VRP formulation of the Multiple Travelling Salesman Problem (mTSP) in [1]. To eliminate the subcircuits that may occur in the routing of the vehicles in the graph, we consider the Miller-Tucker-Zemlin formulation [23,26] since it grows linearly with the size of the problem, unlike other formulations that show exponential growth. To avoid subcircuits, it uses auxiliary decision variables $u_{i} ⩾ 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. $\begin{aligned} (1) & minimise & \sum_{v \in V} \sum_{i \in N} \sum_{j \in N} c_{i j} x_{i j v} \\ (2) & s. t. & \sum_{v \in V} \sum_{i \in N} x_{i j v} = 1 \forall j \in N_{c}, \\ (3) & \sum_{i \in N} x_{i j v} = \sum_{k \in N} x_{j k v} \forall j \in N, \forall v \in V, \\ (4) & \sum_{j \in N_{c}} x_{d j v} = 1 \forall v \in V, \\ (5) & u_{j} - u_{i} ⩾ 1 - (| N | - | V |) (1 - \sum_{v \in V} x_{i j v}) \forall i, j \in N_{c} : i \neq j, \\ (6) & 1 ⩽ u_{i} ⩽ | N | - | V | i \in N_{c}, \\ (7) & x_{i j v} \in {0, 1} i, j \in N, \forall v \in V . \end{aligned}$ 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; 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: if a vehicle travels from vertex $i \in N_{c}$ to vertex $j \in N_{c}$ , the value of $u_{j}$ must be higher than the value of $u_{i}$ . 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 [ 1 ], but with lower bounds on the auxiliary variables $u_{i}$ for all $i \in N_{c}$ .

Proof.

In the original formulation in [1], for each destination $i \in N_{c}$ , $u_{i}$ is upper bounded by $| N |$ . In mTSP, it is mandatory for all the vehicles to leave the depot, constraints (4). Therefore, let $N_{c}^{f}$ be a set of vertices that are visited first when vehicles leave the depot. Then, the minimum value of $u_{i}$ is 1 for $i \in N_{c}^{f}$ , and $| N_{c}^{f} | = | V |$ . 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 $(| N | - | V | - 1)$ vertices. This vehicle, thus, visits in total $| N | - | V |$ vertices. For the last vertex $l \in N_{c}$ it visits, it sets the value of its auxiliary variable $u_{l} = | N | - | V |$ . This value is exactly the number of vertices in its path up to vertex l considering the deposit vertex. Here, we can observe that for $| N | ⩽ | V |$ , the problem has no solution because the constraints (4) are not satisfied. Therefore, the necessary assumption is that $| N | > | V |$ . Then, $| N | - | V |$ is a better upper bound of $u_{i}$ than $| N |$ for each destination $i \in N_{c}$ . Furthermore, thanks to this new upper bound of $u_{i}$ , for all vehicles $v \in V$ and mutually different vertices $i, j \in N_{c}$ (with $i \neq j$ ), the following is always satisfied: $\begin{matrix} u_{j} - u_{i} \overset{| N | - | V | ⩾ u_{i}}{⩾} u_{j} - (| N | - | V |) \overset{u_{j} ⩾ 1}{⩾} 1 - (| N | - | V |) > 1 - | N | . \end{matrix}$ Therefore, constraints (5) are more restrictive than constraints (38) in [1]. The notations above the inequalities (⩾) indicate the property used in each case. □

4. Solution approach

In this section, we modify the mTSP formulation (Equations (1)–(7)) to balance efficiency and fairness in a fleet. We adapt the concepts of utilitarian, egalitarian, and elitist social welfare for the mTSP context and describe the aforementioned systematic approaches for the latter two.

4.1. Utilitarian Social Welfare (USW) model

A utilitarian social welfare function sums the utility of each vehicle to obtain the overall fleet’s welfare. Translated into costs, it minimises the overall fleet’s cost (over all vehicles’ 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 vehicle routes’ costs. $\begin{aligned} (1) & minimise & \sum_{v \in V} \sum_{i \in N} \sum_{j \in N} c_{i j} x_{i j v} \\ s. t. & (2)–( 7) \end{aligned}$

4.2. Egalitarian Social Welfare (EGSW) model

As mentioned before, the utilitarian model (1)–(7) only focuses on the overall performance of the fleet as a whole. 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 takes into account these differences by minimising the maximum cost of the vehicle with the worst-off (the most costly) route applying the constraints of the mTSP. Formally: $\begin{aligned} (8) & minimise & z \\ s. t. & (2)–( 7) and \\ (9) & \sum_{i \in N} \sum_{j \in N} c_{i j} x_{i j v} ⩽ z, \forall v \in V, \\ (10) & z ⩾ 0 . \end{aligned}$

This model fixes the maximum cost for each vehicle of the fleet to the value of z and the objective is to minimise this value. As mentioned in Section 3.2, this approach considers only the worst-off route.

4.3. Systematic Egalitarian Social Welfare (SEGSW) algorithm

Systematic Egalitarian Social Welfare (SEGSW) Algorithm) (Algorithm 1) finds the routes of the fleet’s vehicles optimising the fleet’s egalitarian social welfare systematically.

Algorithm 1:

Systematic Egalitarian Social Welfare (SEGSW) algorithm

To do so, the Algorithm performs $| V |$ optimisation iterations where in each iteration, a vehicle with the route of the worst cost (highest cost) is found by solving (8)–(10). 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.

In each iteration, $N_{r}$ are the (remaining unassigned) destination vertices that have not been visited yet by the vehicles with assigned routes. The remaining unassigned arcs $A_{r}$ are the arcs connecting the remaining unassigned vertices, while the remaining unassigned vehicles $V_{r}$ are the unassigned vehicles in each iteration.

Feasible solution $S$ represents a set of routes in a feasible solution of (8)–(10). Moreover, o is the accumulated cost of the current solution $R$ . Function $getsEgalitarianRoutes (d, N_{r}, A_{r}, V_{r}, c_{i j}, S)$ solves the egalitarian model (8)–(10) returning the value z that represents the cost of the worst-off vehicle route and the values $x_{i j v}$ described in Table 1. A feasible solution may be given to the model to find a solution quicker. In each iteration, the vehicle route $P_{v}$ obtained is stored in $S$ , $R_{v}$ is the route with the highest cost within the found routes in $S$ and it is added to the solution set $R$ .

4.4. Elitist Social Welfare (ELSW) model

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 w whose value is the best-off vehicle route’s cost. Furthermore, we introduce $| V |$ binary auxiliary variables $y_{v}$ , and a constant M, which takes an arbitrary large value. Then, the model is defined as follows: $\begin{aligned} (11) & minimise & w \\ s. t. & (2)–( 7) and \\ (12) & \sum_{v \in V} y_{v} = | V | - 1, \\ (13) & \sum_{i \in N} \sum_{j \in N} c_{i j} x_{i j v} - w ⩽ M y_{v}, \forall v \in V, \\ (14) & y_{v} \in {0, 1}, \forall v \in V, \\ (15) & w ⩾ 0 . \end{aligned}$

Constraint (12) fixes the value of only one variable $y_{v}$ to 0, while all the others are equal to 1. Constraints (13) limit the lowest value of the assigned routes’ cost to w. Thus, we minimise the value of w, which is the cost of the route with minimum cost assigned to any of the vehicle agents.

4.5. Systematic Elitist Social Welfare (SELSW) algorithm

In order to find a systematically optimised elitist welfare solution, Systematic Elitist Social Welfare (SELSW) Algorithm (Algorithm 2) finds the routes of the fleet’s vehicles iteratively optimising the fleet’s elitist social welfare. It uses an optimisation approach similar to the SEGSW Algorithm (Algorithm 1), through $| V |$ successive iterations of the elitist model (11)–(15) but this time, in each iteration, the lowest cost route and its related vehicle are assigned to the solution $R$ .

Algorithm 2:

Systematic Elitist Social Welfare (SELSW) algorithm

It can be noted that the way we model the systematic elitist social welfare reduces to finding the first $V - 1$ shortest loops ( $1 \to i \to 1$ ), where $i \in N_{c}$ , and to assign them to the first $| V | - 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 $| N | - | V | + 1$ vertices.

5. Functional experiments

In this Section, we analyse the performance of the proposed models and algorithms and present the results of the performed simulation experiments. We describe the experiment setup in random and graphs with grid, rectangular, and line structure and present the key performance indicators of the analysis. We finish the Section with the discussion of the results.

5.1. Setup of simulation experiments

The simulation experiments were run on an Intel Xeon Gold 6226R2

²
https://www.intel.es/content/www/es/es/products/sku/199347/intel-xeon-gold-6226r-processor-22m-cache-2-90-ghz/specifications.html

virtualised cluster with 16 CPUs, 32 GB of RAM and clock frequency 2.9 GHz. The whole process was run in Gurobi solver with gurobipy Python library.

We test the proposed models and algorithms considering two types of transportation networks and related graph topology: random (e.g., as seen in Fig. 3) and graphs with grid, rectangular, and line structure (Fig. 4). In the experiments, we consider complete graphs in a 2D plane where the cost between any two vertices $n_{1} = (x_{1}, y_{1})$ and $n_{2} = (x_{2}, y_{2})$ is defined by the Euclidean distance (we use a scale of kilometres): $\begin{matrix} c_{12} = c (n_{1}, n_{2}) = d ((x_{1}, y_{1}), (x_{2}, y_{2})) = \sqrt{{(x_{1} - x_{2})}^{2} + {(y_{1} - y_{2})}^{2}} . \end{matrix}$

Fig. 3.

Examples of experimented random complete graphs. Arcs are excluded for visibility.

Fig. 4.

Examples of a 17-vertex complete graph with a grid, rectangular, and line structure. Arcs are excluded for visibility.

To ensure manageable computational times and standardized solutions, the costs of vehicles’ routes are rounded to the third decimal point, which corresponds to meters. Additionally, each model’s instance run in the solver is constrained to a standardized one-hour time limit, a common practice in the state of the art allowing for practical and consistent solutions to be obtained. We only consider the optimal solutions of the studied models, so that instances whose runs take more than one hour to reach an optimal solution are not considered.

Random graphs. We perform the experiments on random graphs with the following number of vertices: 10, 12, 15, 17 and 20. We consider two scenarios of the fixed position of the deposit vertex, one in the left lower corner and the other one in the centre of the graph. For each number of vertices and each position of the deposit, we generate 10 random instances in a 2D square environment ${[0, 20]}^{2}$ , using a uniform distribution, giving a total of 100 different instances. Three examples of random graphs with different numbers of vertices are presented in Fig. 3.

Graphs with a regular structure. In certain large cities, such as in New York (Manhattan) and Barcelona (L’Eixample), or in agriculture fields for precision farming, the transportation network usually has a regular structure. Here, we consider the structures presented in Fig. 4: a grid structure with equidistant neighbour vertices to visit (Fig. 4a), a rectangular structure with vertices to visit concentrated on four sides of a rectangle (Fig. 4b), and the line structure in Fig. 4c, where all the vertices to visit are on the same line. To add variance, we generate 5 instances for each structured graph type where the position of each vertex is randomly generated following a uniform distribution on the circle of unitary radius centred at the initial position of the vertex. For the deposit, we consider the two same positions as before, one in the left lower corner and the other in the centre of the graph.

For each generated graph, we examine the scenarios with 2, 3 and 5 vehicles. This makes a total of 390 different problem instances (scenarios); 300 on the random and 90 on the regular graph structures.

5.2. Key performance indicators

In the analysis of the results, we are interested in different key performance indicators (KPIs) related with cost efficiency and fairness. We consider the overall vehicles’ cost, which aggregates the costs of individual vehicles’ routes, the individual maximum vehicles’ cost, which gives the cost of a vehicle’s route with the highest cost, and the individual minimum vehicles’ cost, which represents the minimum cost of the vehicles’ routes.

The USW model (1)–(7) minimises the overall vehicles’ cost. The EGSW model (8)–(10) minimises the individual maximum vehicles’ cost, while the SEGSW Algorithm 1 systematically minimises the maximum vehicles’ cost. On the other hand, the ELSW model (11)–(15) minimises the individual minimum vehicles’ cost, while the SELSW Algorithm 2 systematically minimises the minimum vehicles’ cost. In addition, we consider three statistical measures of dispersion of the routes’ costs to analyse fairness: range, standard deviation, and Gini coefficient (see, e.g., [24]).

Range measures the difference between the maximum and the minimum cost of the vehicles’ routes. Let $c_{v}$ represent the cost of vehicle v’s route, where $v \in V$ . Then, it can be expressed as follows: $\begin{matrix} range = max_{v \in V} c_{v} - min_{v \in V} c_{v} . \end{matrix}$ Range can be seen as a measure of fairness since it gives an idea of how concentrated the costs of the vehicles’ routes are. A smaller range implies a fairer solution. However, the value of the range does not contain information about the distribution of the routes’ costs in between the two values, nor does it deal with the overall cost (efficiency) of the fleet. By optimising (minimising) this performance indicator alone, we obtain range zero as an optimal solution. This implies the same cost for all vehicles’ routes, but without any insight on the overall vehicles’ cost and the related fleet’s efficiency.

Standard Deviation measures how dispersed the route costs are in relation to the mean. A high standard deviation shows that the routes’ costs are widely spread (less fairness) and a low standard deviation shows that the costs are clustered closely around the mean (a higher fairness). Similar to the range, values close to zero imply the highest fairness.

Let $\hat{C}$ be the mean value of the fleet’s costs. Then, the mathematical expression for the standard deviation of routes’ costs is: $\begin{matrix} SD = \sqrt{\frac{1}{| V |} \sum_{v \in V} {(c_{v} - \bar{C})}^{2}} . \end{matrix}$

Gini coeficient is a dispersion measure that is used in economics to reflect the inequality within a social group and is formulated as follows. $\begin{matrix} GC = \frac{\sum_{v \in V} \sum_{w \in V} | c_{v} - c_{w} |}{2 | V |^{2} \bar{C}} . \end{matrix}$ The Gini coefficient’s values are expressed in the range $[0, 1]$ , with 0 representing perfect equality, in which all of the vehicles’ route costs are the same, and the values close to 1 representing perfect inequality, in which only one vehicle assumes all of the route costs and the others share a cost as low as possible. A Gini coeficient of 0.5 could mean that half the vehicles share all of the costs while the other half suffer no cost.

5.3. Simulation results

In the experiments, we tested the three presented social welfare models for mTSP (USW, EGSW, ELSW) and the two Algorithms (SEGSW and SELSW) on the 390 generated problem instances. Tables 2 and 3 present the results obtained for the experiments on random graphs and Table 4 on regular graphs. The results correspond to the average values obtained on the 300 instances for random and 90 instances for regular graph structures. These include 20 and 10 instances for the two deposit locations for random and regular structures, respectively.

Besides the performance indicators mentioned previously, we also include a study of the execution times of the proposed mathematical models and algorithms to check their scalability. In the tables, ♯Vert. is the number of vertices and ♯Veh. number of vehicles. Social welfare is the social welfare model used to solve the instances. Moreover, Max represents the maximum vehicles’ cost, Min the minimum vehicles’ cost, and O. cost the overall vehicle fleet cost. Additionally, Range is the cost range value, while GC is the Gini coefficient. SD represents the standard deviation and Time the execution time of the model. Rows marked with a star (*) in the ♯Veh field mean that not all of the instances have been solved to optimality in the one hour limit. In this case, the best solution found within one hour is taken.

Table 2
Key performance indicators for instances in random structure graphs

♯ Vert. ♯ Veh. Social welfare Max cost Min cost Overall cost Range Gini coef. SD Time [sec]

10 2 USW 55.97 11.66 67.63 44.31 0.323 22.156 0.1

EGSW 41.65 39.99 81.64 1.66 0.012 0.831 0.2

SEGSW 41.65 39.42 81.07 2.23 0.016 1.116 0.2

ELSW 96.57 8.73 105.30 87.84 0.421 43.920 0.1

SELSW 59.87 8.73 68.60 51.14 0.375 25.571 0.1

3 USW 49.41 10.39 79.33 39.02 0.323 16.884 0.1

EGSW 36.48 32.23 104.17 4.26 0.027 1.869 0.3

SEGSW 36.48 31.95 102.07 4.53 0.030 1.980 0.4

ELSW 67.47 8.73 114.55 58.74 0.344 25.026 0.1

SELSW 58.77 8.73 81.59 50.04 0.415 22.506 0.1

5 USW 41.25 8.73 110.49 32.52 0.273 11.674 0.1

EGSW 34.38 21.27 142.76 13.11 0.092 5.006 0.3

SEGSW 34.38 24.95 145.34 9.43 0.066 3.425 0.5

ELSW 53.17 8.73 147.74 44.44 0.291 15.890 0.1

SELSW 54.79 8.73 116.03 46.06 0.351 16.495 0.1

12 2 USW 62.06 10.87 72.92 51.19 0.352 25.596 0.1

EGSW 45.50 44.44 89.94 1.06 0.007 0.529 1.2

SEGSW 45.50 44.19 89.69 1.31 0.009 0.653 1.2

ELSW 123.45 8.24 131.69 115.20 0.437 57.602 0.1

SELSW 65.49 8.24 73.73 57.25 0.390 28.625 0.1

3 USW 56.27 8.88 82.71 47.40 0.383 21.198 0.1

EGSW 40.36 38.07 117.80 2.28 0.014 1.007 3.8

SEGSW 40.36 37.09 116.06 3.27 0.019 1.430 4.1

ELSW 89.54 8.24 144.67 81.30 0.374 34.743 0.1

SELSW 64.37 8.24 84.09 56.13 0.449 25.772 0.1

5 USW 48.53 8.41 113.73 40.12 0.328 14.701 0.1

EGSW 37.51 25.07 164.95 12.45 0.067 4.726 4.7

SEGSW 37.51 29.71 166.36 7.80 0.045 2.863 6.5

ELSW 73.01 8.24 173.56 64.77 0.363 24.117 0.1

SELSW 62.10 8.24 117.86 53.86 0.398 19.881 0.1

15 2 USW 70.18 11.38 81.56 58.79 0.355 29.396 0.2

EGSW 48.44 47.50 95.93 0.94 0.005 0.471 7.8

SEGSW 48.44 46.88 95.31 1.56 0.008 0.781 7.8

ELSW 152.05 7.48 159.53 144.57 0.453 72.286 0.1

SELSW 74.51 7.48 81.99 67.03 0.410 33.516 0.2

3 USW 69.11 7.60 89.89 61.51 0.456 28.195 0.3

EGSW 41.20 38.70 120.38 2.50 0.015 1.067 47.0

SEGSW 41.20 38.23 118.55 2.97 0.019 1.302 47.8

ELSW 119.84 7.48 175.85 112.36 0.426 48.379 0.1

SELSW 73.28 7.48 90.67 65.80 0.488 30.471 0.1

5 USW 58.49 7.48 114.59 51.01 0.413 19.311 0.3

EGSW 37.39 31.20 174.37 6.19 0.034 2.286 169.7

SEGSW 37.39 31.18 169.24 6.21 0.034 2.267 189.9

ELSW 83.99 7.48 207.04 76.51 0.352 27.300 0.1

SELSW 69.88 7.48 117.60 62.40 0.457 23.495 0.2

♯ Vert.	♯ Veh.	Social welfare	Max cost	Min cost	Overall cost	Range	Gini coef.	SD	Time [sec]
10	2	USW	55.97	11.66	67.63	44.31	0.323	22.156	0.1
EGSW	41.65	39.99	81.64	1.66	0.012	0.831	0.2
SEGSW	41.65	39.42	81.07	2.23	0.016	1.116	0.2
ELSW	96.57	8.73	105.30	87.84	0.421	43.920	0.1
SELSW	59.87	8.73	68.60	51.14	0.375	25.571	0.1
3	USW	49.41	10.39	79.33	39.02	0.323	16.884	0.1
EGSW	36.48	32.23	104.17	4.26	0.027	1.869	0.3
SEGSW	36.48	31.95	102.07	4.53	0.030	1.980	0.4
ELSW	67.47	8.73	114.55	58.74	0.344	25.026	0.1
SELSW	58.77	8.73	81.59	50.04	0.415	22.506	0.1
5	USW	41.25	8.73	110.49	32.52	0.273	11.674	0.1
EGSW	34.38	21.27	142.76	13.11	0.092	5.006	0.3
SEGSW	34.38	24.95	145.34	9.43	0.066	3.425	0.5
ELSW	53.17	8.73	147.74	44.44	0.291	15.890	0.1
SELSW	54.79	8.73	116.03	46.06	0.351	16.495	0.1
12	2	USW	62.06	10.87	72.92	51.19	0.352	25.596	0.1
EGSW	45.50	44.44	89.94	1.06	0.007	0.529	1.2
SEGSW	45.50	44.19	89.69	1.31	0.009	0.653	1.2
ELSW	123.45	8.24	131.69	115.20	0.437	57.602	0.1
SELSW	65.49	8.24	73.73	57.25	0.390	28.625	0.1
3	USW	56.27	8.88	82.71	47.40	0.383	21.198	0.1
EGSW	40.36	38.07	117.80	2.28	0.014	1.007	3.8
SEGSW	40.36	37.09	116.06	3.27	0.019	1.430	4.1
ELSW	89.54	8.24	144.67	81.30	0.374	34.743	0.1
SELSW	64.37	8.24	84.09	56.13	0.449	25.772	0.1
5	USW	48.53	8.41	113.73	40.12	0.328	14.701	0.1
EGSW	37.51	25.07	164.95	12.45	0.067	4.726	4.7
SEGSW	37.51	29.71	166.36	7.80	0.045	2.863	6.5
ELSW	73.01	8.24	173.56	64.77	0.363	24.117	0.1
SELSW	62.10	8.24	117.86	53.86	0.398	19.881	0.1
15	2	USW	70.18	11.38	81.56	58.79	0.355	29.396	0.2
EGSW	48.44	47.50	95.93	0.94	0.005	0.471	7.8
SEGSW	48.44	46.88	95.31	1.56	0.008	0.781	7.8
ELSW	152.05	7.48	159.53	144.57	0.453	72.286	0.1
SELSW	74.51	7.48	81.99	67.03	0.410	33.516	0.2
3	USW	69.11	7.60	89.89	61.51	0.456	28.195	0.3
EGSW	41.20	38.70	120.38	2.50	0.015	1.067	47.0
SEGSW	41.20	38.23	118.55	2.97	0.019	1.302	47.8
ELSW	119.84	7.48	175.85	112.36	0.426	48.379	0.1
SELSW	73.28	7.48	90.67	65.80	0.488	30.471	0.1
5	USW	58.49	7.48	114.59	51.01	0.413	19.311	0.3
EGSW	37.39	31.20	174.37	6.19	0.034	2.286	169.7
SEGSW	37.39	31.18	169.24	6.21	0.034	2.267	189.9
ELSW	83.99	7.48	207.04	76.51	0.352	27.300	0.1
SELSW	69.88	7.48	117.60	62.40	0.457	23.495	0.2

Table 3

Key performance indicators for instances in random structure graphs (continue)

♯ Vert.	♯ Veh.	Social welfare	Max cost	Min cost	Overall cost	Range	Gini coef.	SD	Time [sec]
17	2	USW	71.69	10.79	82.48	60.90	0.369	30.449	0.3
		EGSW	49.30	48.42	97.73	0.88	0.005	0.441	76.4
		SEGSW	49.30	47.99	97.29	1.32	0.007	0.658	76.5
		ELSW	162.95	7.47	170.42	155.48	0.456	77.742	0.1
		SELSW	75.50	7.47	82.97	68.03	0.412	34.016	0.2
	3	USW	66.83	8.63	92.81	58.20	0.418	26.173	0.2
		EGSW	42.02	40.84	124.39	1.18	0.007	0.514	532.2
		SEGSW	42.02	40.27	123.56	1.75	0.011	0.763	540.3
		ELSW	137.75	7.47	189.68	130.28	0.458	56.477	0.1
		SELSW	74.71	7.47	93.90	67.24	0.483	30.778	0.2
	5	USW	60.38	7.51	120.41	52.87	0.392	19.406	0.3
		EGSW	33.41	28.71	159.10	4.70	0.031	1.813	447.0^∗
		SEGSW	33.41	28.97	155.53	4.44	0.030	1.624	566.8^∗
		ELSW	92.99	7.47	218.81	85.52	0.368	30.323	0.1
		SELSW	71.37	7.47	122.39	63.91	0.445	23.810	0.2
20	2	USW	82.54	6.23	88.78	76.31	0.432	38.153	0.8
		EGSW	51.72	51.24	102.96	0.47	0.003	0.237	607.5^∗
		SEGSW	51.72	50.88	102.60	0.84	0.004	0.418	606.7^∗
		ELSW	210.11	6.23	216.35	203.88	0.471	101.939	0.1
		SELSW	82.54	6.23	88.78	76.31	0.432	38.153	0.3
	3	USW	74.21	6.23	97.36	67.98	0.468	30.464	3.2
		EGSW	38.53	37.32	113.97	1.21	0.008	0.519	437.7^∗
		SEGSW	38.53	36.91	113.15	1.62	0.010	0.707	438.9^∗
		ELSW	148.65	6.23	213.76	142.41	0.447	61.489	0.1
		SELSW	81.75	6.23	97.91	75.51	0.520	34.774	0.5
	5	USW	67.05	6.23	121.74	60.82	0.452	22.784	0.7
		EGSW	29.72	25.31	139.81	4.41	0.031	1.614	1026.3^∗
		SEGSW	29.72	25.01	135.76	4.70	0.033	1.695	1476.9^∗
		ELSW	100.86	6.23	244.95	94.63	0.385	34.493	0.1
		SELSW	79.12	6.23	123.06	72.88	0.503	27.479	0.4

Table 4

Key performance indicators for instances in regular structure graphs

Structure	♯ Vert.	♯ Veh.	Social welfare	Max cost	Min cost	Overall cost	Range	Gini coef.	SD	Time [sec]
Grid	17	2	USW	14.69	1.54	16.22	13.15	0.407	6.575	0.1
			EGSW	9.29	9.13	18.42	0.16	0.004	0.082	20.1
			SEGSW	9.29	9.12	18.42	0.17	0.004	0.083	20.1
			ELSW	32.70	0.72	33.42	31.97	0.478	15.986	0.0
			SELSW	15.51	0.72	16.24	14.79	0.456	7.394	0.1
		3	USW	14.76	0.72	17.15	14.04	0.545	6.414	0.1
			EGSW	7.91	7.37	22.84	0.54	0.017	0.246	369.7
			SEGSW	7.91	7.42	22.90	0.49	0.016	0.220	369.9
			ELSW	24.67	0.72	36.86	23.95	0.439	10.241	0.1
			SELSW	14.87	0.72	17.22	14.14	0.547	6.471	0.1
		5	USW	14.52	0.72	20.79	13.79	0.540	5.213	0.1
			EGSW	6.37	5.57	30.27	0.80	0.024	0.305	608.0^∗
			SEGSW	6.37	5.59	29.68	0.78	0.022	0.291	647.4^∗
			ELSW	18.13	0.72	38.16	17.41	0.415	6.240	0.1
			SELSW	14.52	0.72	20.79	13.79	0.540	5.213	0.2
Line	17	2	USW	24.44	8.04	32.48	16.40	0.251	8.201	57.0
			EGSW	24.44	20.76	45.20	3.68	0.036	1.839	160.2
			SEGSW	24.44	8.04	32.48	16.40	0.251	8.201	160.5
			ELSW	91.03	0.94	91.97	90.09	0.490	45.043	0.1
			SELSW	32.34	0.94	33.29	31.40	0.472	15.699	13.3
		3	USW	24.44	0.94	34.37	23.50	0.454	10.791	30.9
			EGSW	24.44	17.53	62.57	6.91	0.069	2.988	432.2
			SEGSW	24.44	6.99	40.42	17.45	0.327	7.969	453.3
			ELSW	80.25	0.94	107.06	79.30	0.486	34.683	0.1
			SELSW	32.34	0.94	35.47	31.40	0.591	14.522	8.0
		5	USW	24.44	0.94	42.20	23.50	0.522	9.303	41.2
			EGSW	24.44	10.21	96.15	14.23	0.139	5.466	880.8
			SEGSW	24.44	2.90	54.59	21.54	0.385	8.006	1439.6
			ELSW	59.18	0.94	125.35	58.24	0.441	21.143	0.1
			SELSW	32.34	0.94	44.55	31.40	0.591	11.817	1.7
Square	17	2	USW	14.38	4.55	18.93	9.82	0.291	4.912	0.0
			EGSW	12.43	11.96	24.39	0.48	0.009	0.238	38.8
			SEGSW	12.43	11.60	24.03	0.84	0.017	0.418	38.8
			ELSW	47.33	2.00	49.34	45.33	0.459	22.666	0.0
			SELSW	17.28	2.00	19.28	15.28	0.411	7.638	0.1
		3	USW	13.51	3.29	21.36	10.23	0.360	4.557	0.1
			EGSW	10.74	9.78	30.96	0.95	0.022	0.408	205.2
			SEGSW	10.74	9.78	30.81	0.95	0.021	0.403	205.5
			ELSW	35.68	2.00	54.20	33.68	0.415	14.497	0.0
			SELSW	17.22	2.00	22.09	15.22	0.483	6.989	0.1
		5	USW	12.24	2.05	27.69	10.19	0.353	3.680	0.1
			EGSW	8.62	6.97	40.46	1.65	0.039	0.624	754.0^∗
			SEGSW	8.62	7.16	39.69	1.46	0.032	0.501	776.0^∗
			ELSW	25.22	2.00	58.73	23.22	0.381	8.483	0.0
			SELSW	17.15	2.00	29.10	15.15	0.454	5.736	0.2

Execution time analysis. The execution times of the optimisation runs depend mainly on the social welfare optimisation model used. In more than 96.5 % of the experimented optimisation runs (1448 out of the total of 1500) for the random structures, we achieved the optimal solution within one hour.

In general, the EGSW model and the SEGSW Algorithm take much more execution time than the USW and ELSW models or the SELSW algorithm. Also, the SEGSW Algorithm takes more execution time than the EGSW model since it repeats the execution of the EGSW model for each number of vehicles going from |V| to 1.

In our experiments, the USW model, the ELSW model and the SELSW Algorithm obtain an exact solution in all the runs in less than one hour. However, the EGSW model and the SEGSW Algorithm do not. Also, the number of vertices and vehicles strongly influence the total execution time; the instances with less than 17 vertices and 5 vehicles are solved exactly to optimum in all the social welfare models. However, in 5 out of 20 runs with 17 vertices and 5 vehicles, and in some runs with 20 vertices and any number of vehicles, the EGSW model and the SEGSW Algorithm were unable to find an optimal solution within the one-hour time limit, obtaining gaps of the best found incumbent of up to 5%.

Tables 2 and 3 demonstrate that when the model successfully finds an optimal solution for the instances, the computation times are considerably shorter compared to the one-hour limit. Notably, the EGSW model and the SEGSW Algorithm exhibit longer computation times in scenarios involving a greater number of vehicles and vertices.

Regarding the regular structures, Table 4 demonstrates that 91,6 % (412 out of the total of 450) of the optimisation runs achieve the optimal solution within one hour. Most of the instances for which the solver does not achieve an optimal solution in one hour belong to the linear structure instances with the deposit in the left corner. This is because these instances present a symmetric combinatorial problem structure with possibly numerous solutions having the same cost. The mathematical model requires considering each one of them. Thus, although the solver may find the optimal solution within the time limit, it cannot mathematically prove its optimality. To ensure optimality for the solutions provided within the one-hour range, symmetry-breaking techniques are employed to reduce the search space. An additional constraint is added, giving preference to solutions that visit more vertices in case of equal cost [33]. By utilizing this method, 98,2 % (442 cases) are solved exactly to optimality (as seen in Table 4).

Comparison of the EGSW model and the SEGSW algorithm (Algorithm 1 ). With the EGSW Model and the related SEGSW Algorithm, we obtain that in 54 % of the instances, the systematic approach is better in at least one of the KPI values and equal in the others. In Tables 2 and 3, the SEGSW Algorithm strictly dominates the EGSW Model solution in both efficiency and fairness in instances with 5 vehicles. Comparing fairness measures, in case of range or the Gini coefficient, the SEGSW Algorithm dominates the EGSW Model in 7 % of the tested instances, but if we consider the standard deviation, this number increases to 10%. In particular, in Fig. 5, we can see the solution routes of the instance with 12 vertices and 5 vehicles where the SD values are better for the SEGSW Algorithm and the range is better for the EGSW Model solution. For example, for this specific instance, the SEGSW Algorithm obtains an overall vehicles’ cost of 227.27, a range of 14.51, and the SD value of 4.822. On the other hand, the EGSW Model reaches a higher overall vehicles’ cost of 248.96, a lower range of 13.81 and a higher SD value of 5.133.

Fig. 5.

Solution obtained with the 5 social welfare models in a random graph with 12 vertices and 5 vehicles initially located in the depot in the lower left corner.

Comparison of the ELSW model and the SELSW algorithm (Algorithm 2 ). In terms of efficiency, the SELSW Algorithm always achieves a lower overall vehicles’ cost than the ELSW Model, but the results on fairness measures are different. Considering the range and the standard deviation as fairness measures, in 88% of the cases, the SELSW Algorithm dominates the ELSW Model. If we consider the Gini coefficient, this only occurs in 46 % of the instances. This is due to the fact that the SELSW Algorithm minimises the costs of the routes of all the vehicles and achieves the best route combination for all the vehicles except for the last one that has to visit the rest of the vertices. In other words, this behaviour is the unfair economic interpretation of the Gini coefficient. As an example, in Fig. 6e we see the solution of the SELSW Algorithm where 4 vehicles obtain the minimum costs possible and the last one visits all the remaining vertices, achieving a Gini coefficient of 0.536, a range of 16 and an SD of 5.65. On the other hand, in Fig. 6c, the ELSW Model routes are shown where only one vehicle achieves the minimum vehicles’ cost possible and the others share the rest of the vertices achieving a Gini coefficient of 0.477, a range of 26.44 and an SD value of 9.68. The Gini coefficient is the only fairness measure that is better in the ELSW Model at the cost of decreased cost efficiency (overall vehicles’ cost).

Fig. 6.

Solution obtained by the 5 social welfare models in a graph with rectangular structure with 16 vertices and 5 vehicles initially located in a centrally positioned depot. The colors of the vehicles are the same as in Fig. 5.

Balancing cost efficiency and fairness. Next, we evaluate how many of the solutions obtained by the USW Model, the SEGSW and SELSW Algorithms achieve the best possible trade-off between efficiency and fairness. In the ideal case, the overall vehicles’ cost of the routes obtained by the SEGSW Algorithm would be the same as the overall cost obtained by the USW Model. This happens in 8% of the cases. An example of an instance where both approaches achieve the same overall vehicles’ cost is shown in Fig. 6. Even though this cost is the same in the USW Model and the SEGSW Algorithm, the 3 fairness KPIs (range/SD/Gini) are better (lower) in the SEGSW Algorithm. On the other hand, if we consider the vehicles clients’ point of view, the best balance occurs with the SELSW Algorithm and the USW Model that have the same overall vehicles’ cost. Referring to the experiments, in 54 % of the instances, both models return the same solution; i.e., when it is necessary to visit the vertices in order of priority, in more than half of the cases, the solution is efficient. An instance where both approaches achieve the same solution can be seen in Fig. 5.

Efficiency-fairness balance according to graph structure. In terms of efficiency, the USW Model obtains the set of routes that achieve the minimum overall cost while the SEGSW Algorithm achieves the fairest solution. Comparing the type of structure of the instances for which we obtain at the same time the minimum overall cost and the minimum maximum cost and their relation with cost efficiency and fairness, 83 % of the instances follow a regular structure and the other 27 % follow a random structure. The instances with the regular structure are divided in two, the ones with the depot in the left corner that have been executed on the graphs with linear structure and the rest of them with the depot in the centre and with the grid, square and line structure. All the random graph instances have the deposit in the centre of the graph. We believe that this happens because regular instances have more symmetries and therefore allow vehicles to follow similar routes while having the lowest possible cost. In addition, if we compare each of the instances according to the position of the depot, the overall cost obtained by the SEGSW Algorithm is closer in absolute terms to the USW Model’s solution cost in 93% of the instances. This result means that when the depot is located in the centre of the graph, the solutions obtained by the USW Model and the SEGSW Algorithm are similar in terms of overall cost but the latter provides better performance in terms of fairness.

Fig. 7.

Results achieved depending on the number of vehicles. The left axis presents the efficiency (overall vehicles’ cost) in red, where a lower value is better. The right axis shows the transformed value of the three fairness measures: range, standard deviation and the Gini coefficient, where, a higher value is better.

Behavior of efficiency-fairness balance with increasing fleet size. In Fig. 7, we examine the data when the number of vehicles increases. For each number of vehicles, we analyze the overall cost and various fairness measures for each social welfare model. The overall cost of the vehicles is displayed on the left vertical axis, while the values of fairness in terms of range, standard deviation, and Gini coefficient values are presented on the right vertical axis. The five studied algorithms and models are listed on the horizontal axis.

The fairness values are normalized on a scale between 0 and 1, where 1 represents the highest level of fairness and 0 corresponds to the highest level of unfairness. This normalization is necessary since the Key Performance Indicator values have the opposite interpretation, where a lower value implies greater fairness. They are transformed using the following formulas: $\begin{aligned} (16) & fair_Range (n, v, s) = 1 - \frac{Range [n, v, s]}{{max}_{x \in SW} {Max [n, v, x]}} \\ (17) & fair_SD (n, v, s) = 1 - \frac{SD [n, v, s]}{{max}_{x \in SW} {O . cost [n, v, x] / v}} \\ (18) & fair_GC (n, v, s) = 1 - GC \frac{SD [n, v, s]}{{max}_{x \in SW} {O . cost [n, v, x] / v}} \end{aligned}$ where $SW = {USW, EGSW, ELSW, SEGSW, SELSW}$ is the set of the social welfare models. For the normalised range $fair_Range (n, v, s)$ of an instance with n vertices, v vehicles and using the s social welfare model, the actual range value $Range [n, v, s]$ is divided by the maximum possible range for the instance. The maximum range is determined by the maximum cost of the vehicles in the instance while changing the social welfare model and maintaining the values of n and v. For the normalised standard deviation $fair_SD (n, v, s)$ , we compute the actual standard deviation value $SD [n, v, s]$ and divide it by the maximum average cost of instances with the same number of vehicles and vertices.

Figure 7 illustrates the relationship between the overall vehicles’ cost and the standard deviation as the number of vehicles increases. It can be observed that the overall cost of vehicles increases, while the standard deviation decreases with the increasing number of vehicles. Additionally, it can be noted that both the SEGSW algorithm and the EGSW model consistently achieve the fairest values for all three fairness measures.

In more detail, Fig. 7a with 2 vehicles shows the three measures of fairness that are almost the same since with two vehicles they have a similar meaning, i.e., if the cost of the vehicles is similar or not. The tendency, in this case, is that the SEGSW Algorithm and the EGSW Model obtain the fairest results at the very low cost of efficiency. Here, the differences between the USW Model and the SEGSW Algorithm’s normalised measures are 0.22 for the overall vehicles’ cost, −0.23 for the range, −0.29 for SD and −0.35 for the Gini coefficient. For 3 vehicles (Fig. 7b), we can observe how the different fairness measures start to differ, but the overall tendency is the same as before, the difference between overall vehicles’ costs is less compared to the different fairness values, the values are 0.42 for the overall vehicles’ cost, −0.32 for the range, −0.21 for SD and −0.40 for the Gini coefficient. Finally, with 5 vehicles (Fig. 7c), the pattern changes for the standard deviation. It is similar among the different social welfare models and lowers compared to the previous results, The Range and the Gini coefficient remain similar to the results with fewer vehicles. The differences with 5 vehicles are 0.74 for the overall vehicles’ cost, −0.29 for the range, −0.1 for SD and −0.30 for the Gini coefficient. Based on the obtained results, we can see that the behaviour of the USW Model and the SEGSW Algorithm is adequate. However, when the number of vehicles increases, the relative overall cost of the EGSW Model increases compared to the USW Model (0.22, 0.42 and 0.74). Nevertheless, the fairness values for range and the Gini coefficient do not vary significantly and, the standard deviation value even decreases. These values indicate tendency of increasing overall vehicles’ costs as we move from the USW Model to the SEGSW Algorithm and the EGSW Model. However, the higher the costs, the larger the gain in fairness. Lastly, this tendency does not translate also to the ELSW Model that shows both high overall vehicles’ costs and low fairness measures’ values.

6. Conclusions and future work

In this paper, we studied the uncapacitated vehicle routing problem where a fleet composed of homogeneous vehicles, each one belonging to a different owner, collaborate to visit a set of locations distributed in an area of interest. Our aim was not only to find an optimal solution in terms of the overall fleet’s cost (as is the case in the conventional VRP). Instead, we searched for routes that represent a balance between fleet’s efficiency in terms of the overall vehicles’ cost and fairness or how the cost of one vehicle relates to the costs of the others. In this context, we mathematically modelled utilitarian, egalitarian, and elitist social welfare and adapted them for the Multiple Traveling Salesman Problem (mTSP).

The proposed models quantify various fairness and efficiency criteria of the routes: Utilitarian social welfare minimises the overall vehicles routes’ cost, egalitarian social welfare gives an upper-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 without any consideration of the rest of the vehicles, we proposed the Systematic Egalitarian Social Welfare (SEGSW) Algorithm and the Systematic Elitist Social Welfare (SELSW) Algorithm that not only minimise the costs of the worst-off and the best-off vehicle, respectively, but also minimise the costs of the routes in the rest of the fleet. This leads to a significantly improved balance between efficiency and fairness, as shown in the performed simulation experiments.

In the experiments, we analysed the balance between the fleet’s efficiency and fairness by using three well-known statistical measures of dispersion: range, standard deviation, and the Gini coefficient. Depending on the number of vehicles, we noted that the conventional mTSP (equivalent to the utilitarian social welfare model) can be unfair as it may introduce large differences among the routes assigned to vehicles. However, by increasing the number of vehicles in the fleet, it can reach fairer solutions as vehicle costs are reduced on average due to the combinatorial structure of the problem.

In our experiments, the proposed egalitarian social welfare model and the SEGSW Algorithm always achieve the best fairness values and good efficiency in terms of the overall vehicles’ cost. The utilitarian social welfare model is the protagonist of efficiency optimisation. However, the SELSW Algorithm showed a surprisingly close performance both in efficiency and fairness compared to the utilitarian social welfare model. The egalitarian social welfare model which does not take into account all the vehicles in the fleet is dominated by the SEGSW Algorithm and, similarly, the elitist social welfare model is strongly dominated by the SELSW Algorithm.

We found that the proposed SEGSW and the SELSW Algorithm obtain better results in balancing effectiveness and fairness than their non-systematic variants. Proposed (non-systematic) models are never better than their related systematic approaches at both fairness (Range/SD/Gini coefficient) and efficiency (overall vehicles’ cost).

For a good balance of efficiency and fairness, the intrinsic structure of the transport network at hand represented by a graph is also important. This is because the positioning of the tasks to be performed by the vehicles in relation to the depot has a great influence; fairer and more efficient solutions are obtained if the depot is located in central positions of the graph. Thus, the results show that if fairness is of concern, such concepts should be explicitly included or taken into account when finding the routes for the fleet’s vehicles. This is critical in cooperative fleets, as individual owners not only aim at improving their own utility (e.g., by sharing resources), but also require fair treatment.

The proposed centralized and exact mathematical programming solution approach has certain limitations that should be taken into account. The primary limitation lies in the computational complexity associated with the mathematical models employed, which rely on exact methods to achieve an optimal solution in a given timeframe. Indeed, in case the optimal solution is not found, the solver provides the best-found incumbent with quality-of-solution guarantees, which is a strong advantage in respect to ad-hoc heuristic and metaheuristic approaches.

In our experiments, the solver successfully obtained optimal solutions within the one-hour time limit for the most of the tested instances of the proposed models and algorithms. However, for the largest instances, the computational complexity of the models already imposes a considerable challenge for efficient exact computation, providing a best incumbent solution with quality of solution guarantees. Exact methods are generally unsuitable for large-scale, computationally complex vehicle routing problems due to their substantial computational requirements.

To overcome this challenge, in future work, we intend to explore decomposition techniques like Lagrange relaxation, column generation, and Dantzig-Wolfe decomposition. These techniques aim to decompose a large centralized model into smaller, more computationally efficient models that may parallelize the computation and through mutual interaction, efficiently resolve large-sized problems maintaining the quality-of-solution guarantees. Moreover, such approaches may be used to distribute decision-making in a multi-agent system composed of vehicle agents and further improve computation, which is anticipated to substantially reduce computation time. Ad-hoc heuristics algorithms may be used to solve computationally costly parts of such decomposed problems.

In future work, we will also investigate how to keep sensitive individual vehicle information private while finding the fleet’s routes. To this end, we will explore decomposition techniques to decompose the proposed models into interconnected decision making sub-problems, one per vehicle (agent), where each vehicle has its own private local parameters and variables and shares the global ones when needed. We also plan to consider strategic agents that can lie with the aim to maximize their own benefit and minimize cost. In this aspect, we will study mechanisms and incentives to obtain strategy-proof individual vehicle behavior alligned with the fleet’s objectives.

Footnotes

Acknowledgements

This work was partially funded by project “AGROBOTS” of the Rey Juan Carlos University funded by Community of Madrid, Spain and by project “InEDGEMobility” (RTI2018-095390-B-C33 MCIU/AEI/FEDER, UE) funded by Spanish Ministry MINECO and by project “COSASS” (PID2021-123673OB-C32) and by project VAE (TED2021-131295B-C33), both funded by Spanish Ministry MCIU.

References

Bektas, The multiple traveling salesman problem: An overview of formulations and solution procedures, Omega34(3) (2006), 209–219. doi:10.1016/j.omega.2004.10.004.

Bektaş and

A.N.

Letchford, Using

l^{p}

-norms for fairness in combinatorial optimisation, Computers & Operations Research120 (2020), 104975. doi:10.1016/j.cor.2020.104975.

Braekers,

Ramaekers and

Van Nieuwenhuyse, The vehicle routing problem: State of the art classification and review, Computers & industrial engineering99 (2016), 300–313. doi:10.1016/j.cie.2015.12.007.

Cleophas,

Cottrill,

J.F.

Ehmke and

Tierney, Collaborative urban transportation: Recent advances in theory and practice, European Journal of Operational Research273(3) (2019), 801–816. doi:10.1016/j.ejor.2018.04.037.

G.B.

Dantzig and

J.H.

Ramser, The truck dispatching problem, Management science6(1) (1959), 80–91. doi:10.1287/mnsc.6.1.80.

Daoud,

Alqasir,

Mualla,

Najjar,

Picard and

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. doi:10.1007/978-3-030-82017-6_7.

Dupin,

Parize and

E.G.

Talbi, Matheuristics and column generation for a basic technician routing problem, Algorithms14(11) (2021), 313. doi:10.3390/a14110313.

M.M.

Flood, The traveling-salesman problem, Operations research4(1) (1956), 61–75. doi:10.1287/opre.4.1.61.

Gansterer and

R.F.

Hartl, Collaborative vehicle routing: A survey, European Journal of Operational Research268(1) (2018), 1–12. doi:10.1016/j.ejor.2017.10.023.

10.

Gansterer and

R.F.

Hartl, Shared resources in collaborative vehicle routing, Top28(1) (2020), 1–20. doi:10.1007/s11750-020-00541-6.

11.

Glize,

Jozefowiez and

S.U.

Ngueveu, An ε-constraint column generation-and-enumeration algorithm for bi-objective vehicle routing problems, Computers & Operations Research138 (2022), 105570. doi:10.1016/j.cor.2021.105570.

12.

Goel and

Maini, Improved multi-ant-colony algorithm for solving multi-objective vehicle routing problems, Scientia Iranica28(6) (2021), 3412–3428.

13.

E.E.

Halvorsen-Weare and

M.W.

Savelsbergh, The bi-objective mixed capacitated general routing problem with different route balance criteria, European Journal of Operational Research251(2) (2016), 451–465. doi:10.1016/j.ejor.2015.11.024.

14.

Jasso,

K.Y.

Törnblom and

Sabbagh, Distributive justice, in: Handbook of Social Justice Theory and Research, Springer, 2016, pp. 201–218. doi:10.1007/978-1-4939-3216-0_11.

15.

Jozefowiez,

Semet and

E.G.

Talbi, Target aiming Pareto search and its application to the vehicle routing problem with route balancing, Journal of Heuristics13(5) (2007), 455–469. doi:10.1007/s10732-007-9022-6.

16.

Jozefowiez,

Semet and

E.G.

Talbi, An evolutionary algorithm for the vehicle routing problem with route balancing, European Journal of Operational Research195(3) (2009), 761–769. doi:10.1016/j.ejor.2007.06.065.

17.

Liu and

L.G.

Papageorgiou, Fair profit distribution in multi-echelon supply chains via transfer prices, Omega80 (2018), 77–94. doi:10.1016/j.omega.2017.08.010.

18.

López Sánchez,

Lujak,

Semet and

Billhardt, On balancing fairness and efficiency in routing of cooperative vehicle fleets, in: CEUR Workshop Proc. ATT 2022 – Agents in Traffic and Transportation, Vol. 3173, 2022, pp. 62–76. Available online athttp://ceur-ws.org/.

19.

Lujak,

Giordani,

Omicini and

Ossowski, Decentralizing coordination in open vehicle fleets for scalable and dynamic task allocation, Complexity2020 (2020).

20.

Lujak,

Giordani and

Ossowski, Fair route guidance: Bridging system and user optimization, in: 17th International IEEE Conference on Intelligent Transportation Systems (ITSC), IEEE, 2014, pp. 1415–1422. doi:10.1109/ITSC.2014.6957885.

21.

Lujak,

Giordani and

Ossowski, Route guidance: Bridging system and user optimization in traffic assignment, Neurocomputing151 (2015), 449–460. doi:10.1016/j.neucom.2014.08.071.

22.

Lujak,

Sklar and

Semet, Agriculture fleet vehicle routing: A decentralised and dynamic problem, AI Communications34(1) (2021), 55–71. doi:10.3233/AIC-201581.

23.

Marcotte,

Savard and

Semet, A bilevel programming approach to the travelling salesman problem, Operations Research Letters32(3) (2004), 240–248. doi:10.1016/j.orl.2003.08.005.

24.

Matl,

R.F.

Hartl and

Vidal, Workload equity in vehicle routing problems: A survey and analysis, Transportation Science52(2) (2018), 239–260. doi:10.1287/trsc.2017.0744.

25.

Matl,

R.F.

Hartl and

Vidal, Leveraging single-objective heuristics to solve bi-objective problems: Heuristic box splitting and its application to vehicle routing, Networks73 (2019), 382–400. doi:10.1002/net.21876.

26.

C.E.

Miller,

A.W.

Tucker and

R.A.

Zemlin, Integer programming formulation of traveling salesman problems, J. ACM7(4) (1960), 326–329, https://doi.org/10.1145/321043.321046. doi:10.1145/321043.321046.

27.

Nunes,

Moura and

Santos, Solving the multi-objective bike routing problem by meta-heuristic algorithms, International Transactions in Operational Research (2022).

28.

Oyola and

Løkketangen, Grasp-asp: An algorithm for the cvrp with route balancing, Journal of Heuristics20(4) (2014), 361–382. doi:10.1007/s10732-014-9251-4.

29.

C.L.

Quintero-Araujo,

Gruler,

A.A.

Juan and

Faulin, Using horizontal cooperation concepts in integrated routing and facility-location decisions, International Transactions in Operational Research26(2) (2019), 551–576. doi:10.1111/itor.12479.

30.

Vahedi-Nouri,

Arbabi,

Jolai,

Tavakkoli-Moghaddam and

Bozorgi-Amiri, Bi-objective collaborative electric vehicle routing problem: Mathematical modeling and matheuristic approach, Journal of Ambient Intelligence and Humanized Computing (2022), 1–21.

31.

Van Dijk,

Sergaki and

Baourakis, The Cooperative Enterprise: Practical Evidence for a Theory of Cooperative Entrepreneurship, Springer, 2019.

32.

Vidal,

Laporte and

Matl, A concise guide to existing and emerging vehicle routing problem variants, European Journal of Operational Research286(2) (2020), 401–416. doi:10.1016/j.ejor.2019.10.010.

33.

Walsh, General symmetry breaking constraints, in: Principles and Practice of Constraint Programming-CP 2006: 12th International Conference, CP 2006, Nantes, France, September 25–29, 2006, Proceedings, Vol. 12, Springer, pp. 650–664. doi:10.1007/11889205_46.

34.

Wang,

Zhao,

Savelsbergh and

Wu, Multi-period workload balancing in last-mile urban delivery, Transportation Sci (2022).

35.

Wu,

Pan,

Li,

Chen and

Dong, Peer-induced fairness capacitated vehicle routing scheduling using a hybrid optimization aco–vns algorithm, Soft Computing24(3) (2020), 2201–2213. doi:10.1007/s00500-019-04053-9.

36.

Zibaei,

Hafezalkotob and

S.S.

Ghashami, Cooperative vehicle routing problem: An opportunity for cost saving, Journal of Industrial Engineering International12(3) (2016), 271–286. doi:10.1007/s40092-016-0142-1.

How to achieve fair and efficient cooperative vehicle routing?

Abstract

Keywords

1. Introduction

2. Related work

3. Problem description

3.1. Motivation

4.1. Utilitarian Social Welfare (USW) model

4.2. Egalitarian Social Welfare (EGSW) model

4.3. Systematic Egalitarian Social Welfare (SEGSW) algorithm

4.5. Systematic Elitist Social Welfare (SELSW) algorithm

5.1. Setup of simulation experiments

2 https://www.intel.es/content/www/es/es/products/sku/199347/intel-xeon-gold-6226r-processor-22m-cache-2-90-ghz/specifications.html

5.3. Simulation results

Footnotes

Acknowledgements

References

²
https://www.intel.es/content/www/es/es/products/sku/199347/intel-xeon-gold-6226r-processor-22m-cache-2-90-ghz/specifications.html