Workload Equity in Vehicle Routing Problems: A Survey and Analysis

1. Introduction.

• Balancing vehicle capacity utilization can free bottleneck resources, while equitable workloads can improve plan acceptance, driver morale, and customer-service quality.These benefits are cited as reasons workload equity has gained attention.Source: §1 · p. 2
• Equity objectives have been proposed without clear guidance on which measures suit which contexts, and their consequences remain largely unclear.The choice is often made ad hoc despite the broad variety of applications.Source: §1 · p. 2
• Prior reports of “artificial equity” (Jozefowiez, Semet, and Talbi 2002, Halvorsen-Weare and Savelsbergh 2016) remain unexplained in the general case.The introduction identifies this as a paradox requiring explanation.Source: §1 · p. 2
• Earlier single-objective comparisons have limited scope for bi-objective settings and do not establish how worst-case results relate to intermediate trade-offs.Practical interest ultimately lies in compromise solutions rather than any single-objective optimum.Source: §1 · p. 2
• The paper categorizes equitable-VRP literature, compares six measures axiomatically, links measure properties to Pareto sets, and studies these implications numerically.The numerical study estimates the extent of selected connections and examines other aspects relevant to choosing an equity measure.Source: §1 · p. 2

2. Models and Methods for Equity in Vehicle Routing.

• The survey groups equitable VRPs into five streams: route balancing, time-window variants, min-max models, complex VRP variants, and application studies.Source: §2 · p. 3
• Equity metrics identify the workload being balanced, such as tour length or demand served, while equity functions calculate an index such as the range.Source: §2 · p. 3

2.1. The VRP with Route Balancing.

• The VRPRB extends the capacitated VRP with a second objective that measures equity as the range of tour lengths.The surveyed literature describes it as a standard bi-objective model.Source: §2.1 · p. 3
• The only exact algorithm identified for a bi-objective equity VRP uses maximum tour length rather than the VRPRB range, and higher-equity solutions require considerably more computation.A separate general min-max model is solved to optimality with column generation.Source: §2.1 · p. 5

2.2. Time Window Extensions to the VRPRB.

• With time windows, length-based and load-based range objectives yield noticeably different solutions, and optimizing equity can add unnecessary waiting to tours.Source: §2.2 · pp. 5–6
• Time-window methods include a hybrid heuristic that outperforms NSGA-II and a prior reimplementation, and scatter search that approximates small-instance Pareto fronts and outperforms NSGA-II on larger instances.Source: §2.2 · pp. 5–6

2.3. The Min-Max VRP.

• In min-max applications, the best min-max solution can have significantly higher total cost than the best min-sum solution, while a newspaper-delivery heuristic solution was proved optimal.Source: §2.3 · p. 6
• Min-max research also extends to multi-depot routing, including ant colony optimization combined with equitable region partitioning to solve single-depot problems.Source: §2.3 · p. 6
• Min-max VRP studies extend the model to multiple regions, demand types, heterogeneous fleets, split deliveries, technician skills, and selective routing.Yakıcı and Karasakal (2013) study multiple regions, demand types, heterogeneous vehicles, and split deliveries; Schwarze and Voß (2013) use a min-max objective to balance technician skill utilization, while Valle et al. (2011) describe min-max selective VRP.Source: §2.3 · pp. 6–7
• The min-max literature raises the question of how the chosen single-objective function affects optimal-solution properties and structure.Campbell, Vandenbussche, and Hermann (2008), Huang, Smilowitz, and Balcik (2012), and Bertazzi, Golden, and Wang (2015) study this question; the survey reviews them in Section 3.Source: §2.3 · p. 7

2.4. Other VRPs with Equity Aspects.

• Periodic VRP studies measure workload by customers per tour, daily workload range, or total demand served; equity can be addressed through a maximum-allowable constraint or as the primary objective.Source: §2.4 · p. 7
• In capacitated arc routing, Mei, Tang, and Yao (2011) report significant solution-quality improvements over competing approaches, at the expense of longer computation times.Their decomposition-based memetic algorithm is compared with Lacomme, Prins, and Sevaux (2006) and standard NSGA-II.Source: §2.4 · p. 8
• Other routing studies optimize equity through route-cost range in the mixed capacitated general routing problem or compare four equity functions on small instances.Mandal et al. (2015) extend NSGA-II with Pareto-based local search, with experiments indicating some crossover operators work better for balance; Halvorsen-Weare and Savelsbergh (2016) solve small instances exactly.Source: §2.4 · p. 8

2.5. Applications.

• For a rural school-bus routing problem in Spain viewed socially, computational tests of a min-max VRP minimizing longest transit time significantly improved service over standard min-sum and reduced costs versus manual plans.Source: §2.5 · p. 8
• Parragh et al. (2009) formulate patient transportation as a biobjective problem minimizing average transit time and total cost alongside a maximum-transit-time constraint.Source: §2.5 · p. 9
• Goodson (2014) compares equity based on attorneys’ assigned polling stations with equity based on route duration, reflecting the importance of fair workloads for volunteers.Source: §2.5 · p. 10
• Applications also impose workload bounds: Gro¨er, Golden, and Wasil (2009) constrain meter-route distance and stops per route, while library delivery studies bound stops and vehicle loads.Source: §2.5 · p. 10
• Kim, Kim, and Sahoo (2006) and Mendoza, Medaglia, and Velasco (2009) address balance indirectly through cluster-based routing, with the latter finding cluster-first allocation better balances workloads.Source: §2.5 · pp. 10–11
• Other applications use tailored measures, including mean square deviation of working hours, average relative imbalance, cargo deviation from median load, and differences from minimum tour duration.These measures appear in sales-representative scheduling, baked-goods distribution, the classic VRPTW, and Lee and Ueng’s duration-equity formulation.Source: §2.5 · p. 11

3. Theoretical Analysis.

• The analysis approaches equity-function choice axiomatically, examines six classical measures, and derives implications of their properties for Pareto-optimal sets.The section positions biobjective analysis as useful for understanding intermediate trade-offs beyond extreme single-objective optima.Source: §3 · p. 13

3.1. Model Assumptions.

• In the model, each driver receives one tour and workload is minimized; an inequality function is needed to rank workload allocations beyond total workload.In the VRPRB, tour workload is measured by distance, and an equity measure reduces the dimensionality of allocations into a stricter ordering.Source: §3.1 · p. 13

3.2. Desirable Properties of Inequality Measures.

• The axiomatic approach treats an inequality measure as minimized and expects equal outcomes to receive zero (or another fixed value), unequal outcomes to be positive, and rankings to be transitive.Scale invariance means the index is unchanged when every outcome is multiplied by a constant, so the inequality assessment does not depend on units such as kilometres or miles.Source: §3.2 · p. 14
• Measures affected by the number of outcomes cannot directly compare distributions of different sizes; replicating populations to equal size is one workaround.Population-independent measures do not require this transformation.Source: §3.2 · p. 14
• Anonymity makes equity independent of outcome order, but may be inappropriate for entities with different needs, rights, or preferences unless reference targets are used.With differing targets, equity depends on deviations from each entity’s target, so a perfectly equal outcome distribution need not be optimal.Source: §3.2 · pp. 14–15
• Monotonicity requires inequality not to improve when workloads rise, keeping the measure consistent with Pareto-optimal distributions.The axiom requires weak monotonicity in every outcome.Source: §3.2 · p. 15
• The Pigou-Dalton principle favors progressive, mean-preserving workload transfers, but applies only when allocations have the same number and sum of outcomes.Its weak form permits equality in the inequality index after progressive transfers; its strong form requires a strict decrease.Source: §3.2 · p. 15

3.3. Commonly Used Inequality Measures.

• The six measures examined are min-max, its lexicographic extension, range, mean absolute deviation, standard deviation, and the Gini coefficient.Min-max ignores differences among distributions with the same worst outcome and may prefer a distribution that is less equitable across the remaining workloads.Source: §3.3 · pp. 15–16
• The lexicographic extension successively minimizes workloads from worst to best and satisfies the strong transfer principle, but its ranking does not quantify equity differences.It distinguishes distributions sharing the same worst outcome, unlike min-max.Source: §3.3 · p. 16
• Range captures the gap between best and worst outcomes but ignores absolute workload levels, while mean absolute deviation reflects every outcome but not all progressive transfers.MAD is unaffected by transfers between outcomes on the same side of the mean, though fewer transfers leave it unchanged than leave the range unchanged.Source: §3.3 · p. 17
• Standard deviation satisfies the strong transfer principle but can be computationally complex and less intuitive; lower Gini values indicate lower inequality on a 0-to-1 scale.Dividing standard deviation by the mean yields the coefficient of variation.Source: §3.3 · p. 17
• The Gini coefficient satisfies strong Pigou-Dalton, but its complexity is a main disadvantage in optimization, despite linear formulations in special cases.The linear special case holds when both the average outcome and the number of outcomes are constant.Source: §3.3 · p. 17

3.4. Implications for Choosing an Equity Objective.

• None of the examined measures satisfies every axiom or dominates all others; absolute and relative measures each include at least one measure satisfying strong Pigou-Dalton.Absolute measures are min-max and lexicographic min-max; the remaining four are relative measures.Source: §3.4 · p. 18
• Because tour lengths are variable-sum outcomes, the Pigou-Dalton principle is not expected to noticeably affect efficient sets in the standard VRPRB.More generally, the principle does not in general affect preferences between solutions when the equity metric is variable-sum.Source: §3.4 · p. 18
• Monotonic equity measures guarantee that every Pareto-optimal VRPRB solution uses TSP-optimal tours and is workload-consistent; nonmonotonic measures guarantee neither property.The paper states that nonmonotonic measures can produce solutions that are both non-TSP-optimal and inconsistent.Source: §3.4 · pp. 18–20
• Nonmonotonic equity measures can make Pareto-optimal solutions include non-TSP-optimal tours, because worsening a workload can improve the inequality index.Adding total cost as an objective does not resolve this possibility: an improvement in equity alone can suffice for Pareto-optimality.Source: §3.4 · pp. 19–20
• Workload inconsistency means a solution has no shorter workload for any tour than another solution, yet has a worse equity value; TSP-optimal tours alone do not prevent it.Lower-bound constraints on workload can also lead to inconsistency, regardless of the equity function.Source: §3.4 · p. 19

4. Numerical Analysis.

• The study enumerated Pareto sets for 60 instances with 14 customers, drawn from 10 disjoint customer subsets, because larger instances could not be enumerated within reasonable time for all parameter combinations.Instances were derived from CMT5, and feasible tours and combinations of tours were examined to obtain optimal Pareto sets.Source: §4 · p. 20

4.1. General Observations.

• Cost-optimal solutions were poorly balanced on average, with the longest tour about twice as long as the shortest.Source: §4.1 · p. 21
• Selecting the second-best-cost TSP-optimal and consistent solution reduced the longest–shortest tour-length difference by around 40% on average for a total-cost increase of around 2%.About 37% of efficient solutions had total costs within 10% of the cost optimum.Source: §4.1 · p. 21
• Only around 14% of solutions were identified by all examined measures, while about a quarter were unique to no more than two, underscoring that measure choice matters.Agreement was slightly over 80% between min-max and its lexicographic extension, and ranged from around 50% between range and mean absolute deviation to around 80% between standard deviation and Gini coefficient.Source: §4.1 · p. 21, Figure 1 · p. 21

4.2. Conventional Optimization.

• Non-monotonic measures generated around 10 times as many optimal Pareto solutions; only 11%–14% were consistent, compared with 100% for monotonic measures.Their Pareto fronts averaged around 30 to 40 solutions, unexpectedly large considering the size of the instances.Source: §4.2 · p. 22
• In the representative instance, lexicographic min-max yielded additional trade-off solutions beyond standard min-max, while relative-measure fronts were larger than absolute-measure fronts and generally did not subsume one another.The relative measures could typically be reduced to nearly 0.Source: §4.2 · p. 24
• Inconsistent solutions appeared only with non-monotonic measures and mainly at the low-inequality ends of fronts; many were non-TSP-optimal, although some low-cost solutions were also inconsistent.TSP-optimal solutions appeared at both the lower-cost and lower-inequality ends of all fronts.Source: §4.2 · p. 24
• Without a TSP-optimality constraint, non-monotonic measures produced Pareto solutions with non-TSP-optimal tours and TSP-optimal but workload-inconsistent solutions.Solutions with minimal range, including solution 11, were found only with such measures.Source: §4.2 · pp. 24–26
• A customer move from the medium-length tour to the shortest improved range but not min-max; range could also be improved by breaking a tour’s TSP-optimality.In the illustrated example, solution 3 lengthened the shortest tour, while later range improvements included non-TSP-optimal solutions.Source: §4.2 · pp. 25–26

4.3. Optimization with TSP Constraints.

• With the constraint, Pareto-front cardinality was approximately halved, while about 60% of each new front comprised previously unidentified TSP-optimal solutions, reaching 90% in some instances.The larger-instance results were qualitatively similar.Source: §4.3 · pp. 26, 28, Table 5 · p. 26
• Around 70% of solutions found with a TSP-optimality constraint remained inconsistent, and inconsistent solutions could dominate TSP-optimal solutions.Tour-length minimization therefore cannot eliminate inconsistent solutions from Pareto-optimal sets.Source: §4.3 · p. 28
• With the TSP constraint, inconsistent solutions were most common in the high-cost, low-inequality region after the lexicographic minimum; consistent solutions beyond it were rare but existed with up to five vehicles.For two vehicles, all solutions with cost above the lexicographic minimum are inconsistent.Source: §4.3 · p. 28
• Even when every tour is TSP-optimal, customer allocations can lengthen tours and let non-monotonic measures improve their inequality index, so tour-length minimization does not resolve the problem.The study indicates this is a common feature of Pareto-optimal solutions, not merely a special case.Source: §4.3 · p. 28

Analytical Results

• No examined measure satisfies every desirable axiom or is best in all aspects; the authors recommend monotonic min-max measures for variable-sum workloads.This recommendation also applies to weighted aggregations when at least one component metric is variable-sum.Source: §5 · pp. 29–30

Empirical Observations

• Cost-optimal solutions had longest tours about twice as long as shortest tours, while nearly 40% of efficient solutions cost less than 10% above optimal.These findings indicate that improving equity often has a low marginal cost and that reasonable compromise solutions can exist.Source: §5 · p. 29
• For conventional optimization of VRPRB instances, non-monotonic measures yielded Pareto sets with high non-TSP-optimality and inconsistency; on average, less than 20% of Pareto-optimal solutions were TSP-optimal.Source: §5 · p. 29
• With a TSP constraint, around 50% of identified Pareto-optimal solutions were TSP-optimal, but fewer than 5% of these new solutions were consistent.Thus, tour-length minimization procedures were insufficient in theory and practice to overcome problems caused by non-monotonic inequality measures.Source: §5 · p. 30

Proposed Guidelines

• Lexicographic min-max yields about 20% more unique trade-off solutions, often on low-cost fronts, but its complexity makes standard min-max more practical.Lexicographic optimization is harder to implement and interpret, while Pareto-set size tends to grow exponentially.Source: §5 · p. 30

Open Research Directions

• Future work should address equity when anonymity does not hold and extend models to multiple periods, where workloads may balance over a horizon despite period-level inequity.The authors note that this requires considering how balanced workloads interact with customer and driver consistency.Source: §5 · pp. 30–31
• Some equitable solutions lack credibility because simple customer relocations or exchanges can improve workloads even when every tour is TSP-optimal.Local-optimality constraints using relocate or exchange neighborhoods are proposed as a possible way to improve credibility; the authors note that Pareto-set local optima have not been studied.Source: §5 · p. 31
• Further research should broaden workload definitions beyond tour length to reflect other relevant factors, such as stops, load, demand, or service time.The theoretical literature surveyed focuses almost exclusively on tour length, while application papers also treat other factors as important.Source: §5 · p. 31

• For constant-sum metrics, every change in one outcome is offset by the reverse change in another, making the PD transfer principle more important because every solution pair is connected by mean-preserving transfers.Source: §5 · p. 31
• Range-like measures may generate richer Pareto sets for constant-sum metrics without the shortcomings identified in this study, and comparing equity measures for this metric class is a promising research direction.Source: §5 · p. 31

• The generated instances and detailed computational results are available upon request from the authors and in the paper’s online version.Source: Electronic Companion · p. 32

Appendix

• For n = 2, any solution y other than lexicographically minimal x with C(y) > C(x) is either inconsistent or dominated by x.Source: Appendix · p. 32
• The proof sorts outcomes in non-increasing order and uses lexicographic minimality to establish x1 ≤ y1.Source: Appendix · p. 32
• When x2 ≤ y2, y is inconsistent; when x2 > y2, its equity value is no better than x’s, making y dominated.Source: Appendix · p. 32