Workload equity for a dynamic multi-period routing problem inthe context of medical transportation
M. Agiusa∗ , N. Absia , D. Feilleta and T. Garaixa
a Mines Saint-Etienne, Univ Clermont Auvergne, INP Clermont Auvergne, CNRS, UMR 6158

LIMOS, F - 42023 Saint-Etienne France
maxime.agius@emse.fr, absi@emse.fr, feillet@emse.fr, garaix@emse.fr∗ Corresponding author
Extended abstract submitted for presentation at the 11th Triennial Symposium on
Transportation Analysis conference (TRISTAN XI)
June 19-25, 2022, Mauritius Island

January 13, 2022
Keywords: Medical transportation, dynamic multi-period, workload equity, column generation

1INTRODUCTION

The studied problem concerns the non-emergency transportation of patients. Some disabled orold patients cannot go back and forth to the hospital by their own to get cares. In this context,transport companies are involved to provide medical transportation of patients. In this work,
we consider a single hospital and we assume that a single company is involved with a limited
number of drivers. Transportation requests are daily revealed on a time horizon of several days.
In practice, there exists service provider platforms to help managing the schedule of vehicles
routes and the assignment of routes to drivers. Generally, these platforms use basic algorithms
based on assignment rules (e.g. the FIFO rule "First In First Out"). These rules can be inefficient
for large scale transportation systems or when the demand varies strongly. Another drawbackof these rules is that they create inequities between drivers in terms of route cost (duration ordistance) and/or painfulness of work. In this work we consider the latter.
Equity has gained interest in the VRP literature in the last two decades Matl et al. (2018),Matl et al. (2019). The literature mainly focuses on single period problems. For most papers
where it is considered a larger horizon, the problem is often defined as an extension of the Periodic
Vehicle Routing Problem (PVRP). In this case, the demand is assumed to be completely known
in advance, which is not realistic in many contexts. In multi-period problems, the total workload
can be balanced among periods, delivery points or drivers. The few papers dealing with equity
in a dynamic multi-period context usually consider equity among periods or delivery points anddo not involve individual workloads of drivers Wen et al. (2010), Khorsi et al. (2020).
The originality of our problem is to consider equity for drivers on the “medium” term (typicallyone month), with requests dynamically revealed. Compared to standard models, it gives theopportunity to accept unbalanced routes at some periods (days), as long as equity is preservedon the whole horizon. In this work, we investigate different solution approaches and evaluate
computationally how addressing equity this way allows limiting its impact on routing costs.

2PROBLEM DESCRIPTION

The studied problem is defined on a large horizon T = {1, . . . , T } of T periods. A set M ={m1 , . . . , mK } of K drivers is available. We assume that they work every day with identical
TRISTAN XI Symposium

Original abstract submittal

M. Agius, N. Absi, D. Feillet and T. Garaix

2vehicles of capacity Q. We distinguish two types of requests: inbound and outbound requests.
Inbound requests consist in transporting patients from their home to the hospital, while outboundrequests consist in transporting patients from the hospital to their home. With each request iare associated a release date ri (time at which the patient is available at the pickup location), a
due date di (latest time at which the patient can be dropped off at the delivery location), and aservice time si at the customer location. Service time is also spent at the hospital, when inboundcustomers are dropped-off and when outbound customers are picked-up. In what follows, terms
request, patient and customer will be used indifferently, and the same for terms period and day.
The problem is dynamic in the sense that requests are revealed day by day but requests of a
day t are all known before starting the day. So, even though the problem is dynamic, each daily
routing problem is static. This daily problem is defined as a Multi-Trip Vehicle Routing Problem
with Mixed Pickup and Delivery, and Release and Due dates (MTMPD-RD) Agius et al. (2021).
On a given day, daily routes are first computed and then assigned to the drivers. The objective
is to obtain a good equity between drivers at the end of the horizon, while not deviating too
much from the travel cost that would have been obtained if equity was not considered.

3MEASURE OF EQUITY AND SOLUTION METHOD

In our model, equity is required with regards to request painfulness. We measure the painfulnessof a request i on period t as a value πit defined taking into account the characteristics of patients:
their age, their mobility and the type of residential building where they live. The more a request
is painful, the higher πit is. This metric is said constant-sum as for any feasible solution, the sumof painfulness assigned to drivers remains constant.
PThe total painfulness of period t is denoted Πt = ni=1 πit and painfulness assigned to driver
mk on period t is Πtk . When solving period t, Πtk is unknown while the cumulative painfulness
Pt′
assigned to driver mk up to period t − 1 ( t−1t′ =1 Πk ) is known and can be used.
To deal with the multi-objective nature of our problem, instead of considering two explicit
objectives, we consider cost minimization as the single objective, and equity is ensured by anassignment strategy (we call it RFES for Routing First Equity Second) possibly combined withequity constraints in the daily routing problem. We propose 4 solution approaches. The first
approach consists in using the RFES strategy without introducing any equity constraint in therouting. The three other approaches integrate equity constraints.
The RFES strategy is applied when vehicle routes are known in period t. As drivers aresupposed identical, routes can indifferently be assigned to any driver. We assign the most painfulroute to the driver with the least cumulative painfulness up to period t − 1, the second mostpainful route to the driver with second least cumulative painfulness, and so on to balance thecumulative painfulness up to period t.
The different approaches for the routing problem are briefly described below:
1. Routing First Equity Second (RFES): no equity constraints.
2. Single Period Constant Equity (SPCE): this approach is equivalent to RFES with equity
constraints. For each driver mk in a given period t, we limit the painfulness of the routeassigned to mk . The limit is independent of the driver:Πtk ≤ α ×

Πt, with α > 1K(1)3. Multi-Period Constant Equity (MPCE): This approach is equivalent to RFES with equity
constraints depending on the driver. Again, for each driver mk in a given period t, we limit
the painfulness of the route assigned to mk , but here the limit is driver-dependent. It takes
TRISTAN XI Symposium

Original abstract submittal

M. Agius, N. Absi, D. Feillet and T. Garaix

3

into account the cumulative painfulness assigned to drivers up to period t − 1:tX′Πtk ≤ α ×t′ =1′tX
Πtt′ =1K, with α > 1(2)4. Multi-Period Adapted Equity (MPAE): This approach is similar to MPCE with a decreasing limit on painfulness over the time horizon (αt decreasing uniformly from αs at t = 1 toαe at t = T ).
tXt′ =1′Πtk ≤ αt ×′tX
Πtt′ =1K, αt = αs − (t − 1) ×

αs − αeT −1(3)Parameters α, αt , αs are defined to guarantee a given level of equity. Given a solution(of the multi-period problem), equity can be measured with several indicators, we choose therange as main indicator (difference between the drivers with the most and the least cumulativepainfulness).
For the purpose of evaluation, we also propose another approach that we call Routing First
Equity Second with Perfect Information (RFESPI) which consists in solving all single-period
problems first, and then assign routes to drivers for all periods minimizing the range. In thisapproach, we assume that all requests of all days are known in advance, which is not realistic
in the practice. This approach provides the minimal routing cost and, even if it does not mathematically guarantee a lower bound on the range when the cost is minimized, it should give agood approximation on the best range that could be achieved.
The periodic problem is solved with a specific Branch-and-Price algorithm. Its complete study
is not the object of this work, instead we focus on the impact of adding the equity constraints(mentioned above) on the column generation algorithm. Adding equity constraints enforce toadd a specific resource in the label definition of the pricing problem. We call the resource π.
Each time a customer i is visited, π is updated π ← π + πit . For SPCE, the management ofresource π is easy as the limit is the same for all routes. However, for MPCE and MPAE, thelimit of painfulness varies between drivers within a same period.
The intuitive way to tackle this difficulty would be to introduce a different pricing problem
for each driver. Instead, we modify the Master Problem. Drivers have individual limits ofpainfulness but some might be equal. Hence drivers can be grouped into L groups. Each groupl2ll1< πmaxif(l ∈ {1, . . . , L}) and πmax
gl is composed of Kl drivers with the same limit πmax
L−1
l1 < l2 . Only the drivers of group gL are allowed to have a route more painful than πmax so, at
L−1 . In the same principle, at most K
most KL routes can exceed πmax
L−1 + KL routes can exceed
L−2πmax and so on, which gives L − 1 new constraints. In the pricing problem, for each groups gl(l > 1), the new associated dual variable λl0 is not counted initially and counted when the levell−1 .
of painfulness of the current route exceeds the limit πmax

4NUMERICAL EXPERIMENTS

Experiments are conducted on a benchmark of realistic instances extracted from the city of
Aix-en-Provence, France. The painfulness of a request πit is a value selected uniformly in theset {0, 1, 2, 4, 8}. 50% of the requests are inbound, resp. outbound. We generated 10 instances. Each instance is composed of 20 periods of 50 requests and corresponds to a time
horizon of a month (assuming that drivers work 5 days a week). From those 10 instances wededuced 10 instances of 5 days (one working week). For all instances, we apply the 5 approaches
mentioned above with different parameters for approaches involving equity constraints: SPCEand MPCE for all α ∈ {1.1, 1.08, 1.06, 1.04, 1.02, 1.01} and MPAE with αs = 1.1 and for all
αe ∈ {1.08, 1.06, 1.04, 1.02, 1.01}.
TRISTAN XI Symposium

Original abstract submittal

M. Agius, N. Absi, D. Feillet and T. Garaix

14RFESPIRFESSPCEMPCEMPAE

1210RFESPIRFESSPCEMPCEMPAE

4range (%)

range (%)

4864

32120.0

0.5

1.0

1.5
2.0
2.5
cost increase (%)

3.0

3.5

0.0(a) Experiments with T = 5

0.5

1.0
1.5
2.0
cost increase (%)

2.5

3.0(b) Experiments with T = 20

Figure 1 – Results of experiments on instances with T = 5 and T = 20 periods
Figure 1 shows computational results for instances with 5 and 20 periods. Each point corresponds to an approach (combined with a parameter value α for SPCE and MPCE, or αe forMPAE) and is located according to the average value of cost and equity on the 10 instances. Thex-axis corresponds to the average increase (in %) of travel cost against the best cost (obtainedby RFES and RFESPI). The y-axis corresponds to the average range expressed as a percentageof the average painfulness.
In addition, Table 1 shows the number of times a feasible solution was found by the different
methods. Indeed, enforcing the equity too strictly sometimes prevent from finding a feasiblesolution (in at least one period of the horizon).
Table 1 – Feasibility of different approaches
Approachα/αe#feas inst for T = 5#feas inst for T = 20

RFESPI
1010RFES
1010

1.1
1010

1.08
1010SPCE
1.06 1.04
10592

1.02
00

1.01
00

1.1
1010

1.08
1010

MPCE
1.06 1.04
108108

1.02
10

1.01
00

1.08
10101.06
1010

MPAE
1.04 1.02
1010
1010

1.01
910

These results will largely be discussed at the conference.

Acknowledgments
This work is part of project FITS - “Flexible and Intelligent Transportation Systems”, supportedby the French National Research Agency (ANR - Agence Nationale de la Recherche) under grantANR-18-CE22-0014.

References
Agius, Maxime, Absi, Nabil, Feillet, Dominique, & Garaix, Thierry. 2021. A branch-and-price algorithm
for a routing problem with inbound and outbound requests. Tech. rept. MSE CMP–SFL 2021/12.
Khorsi, Maliheh, Chaharsooghi, Seyed Kamal, Bozorgi-Amiri, Ali, & Kashan, Ali Husseinzadeh. 2020.
A multi-objective multi-period model for humanitarian relief logistics with split delivery and multiple
uses of vehicles. Journal of Systems Science and Systems Engineering, 29, 360–378.
Matl, Piotr, Hartl, Richard F, & Vidal, Thibaut. 2018. Workload equity in vehicle routing problems: Asurvey and analysis. Transportation Science, 52(2), 239–260.
Matl, Piotr, Hartl, Richard F, & Vidal, Thibaut. 2019. Workload equity in vehicle routing: The impactof alternative workload resources. Computers & Operations Research, 110, 116–129.
Wen, Min, Cordeau, Jean-François, Laporte, Gilbert, & Larsen, Jesper. 2010. The dynamic multi-periodvehicle routing problem. Computers & Operations Research, 37(9), 1615–1623.

TRISTAN XI Symposium

Original abstract submittal