=Paper=
{{Paper
|id=Vol-3651/HeDAI_paper1
|storemode=property
|title=Ride-Sharing in Medical Transportations: Dealing with Temporal Requirements
|pdfUrl=https://ceur-ws.org/Vol-3651/HeDAI-1.pdf
|volume=Vol-3651
|authors=Giovanni Alberto Beltrame,Carlo Combi,Alessandro Farinelli,Roberto Posenato,Giuseppe Pozzi
|dblpUrl=https://dblp.org/rec/conf/edbt/BeltrameCFPP24
}}
==Ride-Sharing in Medical Transportations: Dealing with Temporal Requirements==
https://ceur-ws.org/Vol-3651/HeDAI-1.pdf
Ride-Sharing in Medical Transportations: Dealing with Temporal
Requirements
Giovanni Alberto Beltrame1,† , Carlo Combi2,† , Alessandro Farinelli2,† , Roberto Posenato2,† and
Giuseppe Pozzi3,*,†
1
Former student, Università di Verona, Strada Le Grazie, I-37134, Verona, Italy
2
Dipartimento di Informatica, Università di Verona, Strada Le Grazie, I-37134, Verona, Italy
3
DEIB, Politecnico di Milano, P.za L. da Vinci 32, I-20133, Milano, Italy
Abstract
The ride-sharing problem aims at optimizing the path from one starting point to one destination point. The problem can be enriched by
intermediate stops, spatio-temporal constraints, and external constraints (e.g. traffic congestion), adding uncertainty and increasing the
overall complexity.
Spatio-temporal networks can properly describe the problem by graphs, helping to identify the optimal or sub-optimal solution.
We face here the specific issue, where a driver picks up several patients from their respective pick-up locations and drops them off at
one care center. Ride-sharing of patients has specific requirements due to the particular health state of every patient. Indeed, every
patient has his/her own constraints, which could be related to the maximum sustainable duration of the trip, according to the patient’s
conditions, the maximum waiting time, and the time when the visit or treatment is scheduled.
In our approach, we first consider the spatial facets, and then we superimpose the temporal facets, to recommend the best paths and
schedules, allowing some kind of temporal uncertainty in the specification of different possible constraints.
Keywords
Spatio-temporal networks, Uncertainty, Graphs, Ride-sharing, Patient transportation
1. Introduction not considering the specific requirements of ride-sharing in
the context of healthcare domains may produce low-quality
Ride-sharing [1] is a mode of transportation in which in- 30 services, which possibly prevent delivering the right care
dividual travelers share a vehicle and, eventually, its costs. to the weaker patients’ categories because of transporta-
Typically, passengers have the same unique destination. tion barriers. Among the specific requirements that need to
5 Passengers may leave from the same starting point or may be addressed when planning ride-sharing for patients, we
be collected along the way of the first passenger to the consider here:
shared destination. Ride-sharing combines the flexibility
and speed of private cars with the reduced cost of fixed-line 35 • the maximum allowed duration of the trip for spe-
systems. In static ride-sharing, passenger arrangements are cific patients, who cannot afford too long trips;
10 pre-computed and cannot be modified during the service. • the strict ranges of allowed waiting times, as patients
In dynamic ride-sharing, automatic ride-matching between are not able to face too long waiting times (or to rush
participants can occur on very short notice or even en route. for too short deadlines);
The problem of ride-sharing aims at optimizing the path 40 • the flexibility in reaching the final destination, avoid-
of the vehicle. Optimization is helpful under several terms: ing both a rush and a too-long waiting time at the
15 travel costs, travel time, and environmental pollution are healthcare center, a not feasible situation especially
just a few of them. The problem can be enriched by several for patients and in this pandemic context.
intermediate stops, spatiotemporal constraints, and external
constraints (e.g. traffic congestion), adding uncertainty and In the following, we shall consider the general issue of
increasing the overall complexity. 45 medical transportation, where a driver picks up some pa-
20 Ride-sharing in healthcare has been considered as a way tients from their respective starting points (e.g., homes), and
of increasing the number of people possibly accessing med- drops them off at the same care center. The approach we
ical care, as it is less expensive than other services and propose in this paper considers the integrated application
available also in places where public transportation is miss- of both temporal and spatial reasoning, focusing on the
50 management of temporal uncertainty, taking into account
ing [2, 3, 4]. Besides several policy- and healthcare-related
25 issues, ride-sharing in healthcare has some specific features,
the specific requirements of such kind of transportation.
which need to be considered when designing software sys- Temporal issues refer to the preferred arrival time every
tems supporting ride-sharing activities for patients. Indeed, passenger may have. Spatial issues refer to the path of the
shared vehicle. External constraints refer to traffic condi-
Published in the Workshop Proceedings of the EDBT/ICDT 2024 Joint 55 tions, which may also occur dynamically, i.e. during the
Conference (March 25-March 28, 2024), Pæstum, Italy journey, and not just before the journey starts.
*
Corresponding author.
† The paper is structured as follows: Section 2 describes
These authors contributed equally.
$ beltramegiovannialberto@gmail.com (G. A. Beltrame); related work from the literature on both temporal and spa-
carlo.combi@univr.it (C. Combi); alessandro.farinelli@univr.it tial topics, and the background methodological concepts;
(A. Farinelli); roberto.posenato@univr.it (R. Posenato); 60 Section 3 describes the application domain and how we
giuseppe.pozzi@polimi.it (G. Pozzi) model the problem; Section 4 describes a proof-of-concept
https://www.deib.polimi.it/pozzi (G. Pozzi)
— (G. A. Beltrame); 0000-0002-4837-4701 (C. Combi);
prototype we implement; Section 5 highlights the achieved
0000-0002-2592-5814 (A. Farinelli); 0000-0003-0944-0419 (R. Posenato); conclusions and sketches out some future research direc-
0000-0002-2828-862X (G. Pozzi) tions.
© 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribu-
tion 4.0 International (CC BY 4.0).
CEUR
ceur-ws.org
Workshop ISSN 1613-0073
Proceedings
65 2. Background and Related Work simplicity, as these last algorithms are quite complex and
full of technicalities, in this paper, we consider as the fun-
This section describes the background and the related work damental starting point the 𝑂(𝑁 5 ) dynamic controllability
on temporal networks and on the ride-sharing problem, and 130 checking algorithm of [9] for STNUs.
how we select the proper methodology to cope with the
selected application domain. Ride-sharing problems are
70 commonly formalized by graphs, which are then analyzed
2.2. Related Work
by temporal networks. The issue of patient transportation is of great relevance:
it is estimated that 5.8 million people in the US during
2.1. Background: STNUs 2017 delayed non-emergency medical care due to lack of
135 transportation [13]: the CoViD-19 pandemic hardened the
A Simple Temporal Problem (STP) is a problem involv- problem. A taxonomy of innovative health care mobility
ing quantitative time constraints [5] between pairs of time services is reported in [14].
75 points. A Simple Temporal Network (STN) is a framework The problem of ride-sharing of patients falls within the
for planning and scheduling applications of a STP, which wider topic of patient transportation. Many issues have been
is represented through a set of nodes, i.e./ time points, and 140 faced in this direction: intra-hospital patient transportation;
weighted edges between nodes, representing quantitative optimizing the use of Advance Life Support (ALS) services
temporal constraints: the formalization is adopted to check (managing patients requiring high level of medical moni-
80 consistency in many constraint-based planning systems [6]. toring and emergency care) and Basic Life Support (BLS)
STNU refers to STN with uncertainty, where the occur- (managing patients requiring non-emergency medical trans-
rences of some time points, named contingent, are within 145 portation); evaluating ride-sharing services. Without being
specified time ranges, but beyond the control of the planning complete, in the following we shall briefly discuss some
agent [7]. An STNU is controllable if a solution satisfying technical contributions, providing an overall picture of the
85 every constraint in the network can be found. One of the context, within which we propose our original contribution.
strategies for STNU is the RTED (Real Time Execution De- In [15], the authors propose a generalization of the dial-
cision) strategy [7, 8], to manage contingent time points 150 a-ride problem, modeling some real-life requirements for
(events) which occur at run-time, and cannot be controlled patient transportation. A multi-directional local search algo-
(scheduled) by the agent, but are simply observed. An STNU rithm is developed to solve this problem, taking into account
90 is dynamically controllable iff (i.e., “if and only if”) an execu- the fundamental tradeoff between operational efficiency and
tion strategy based on RTED exists. Intuitively, according to service quality, by considering specific constraints for pa-
RTED, the agent, responsible for the network execution, can 155 tients and drivers. Moreover, the authors propose an original
only observe the occurrence of contingent time points but scheduling procedure, minimizing the total user ride time.
is capable to react to such occurrences, by deciding when to As already mentioned, ambulance providers support both
95 execute the other time points, which are under its control. ALS and BLS ambulances. In [16], the authors propose a
The RTED strategy is based on a table known as all-pair- model that determines the routes for BLS ambulances while
shortest-semi-reducible paths (APSSRP), which for every 160 maximizing the remaining coverage by ALS ambulances.
couple of nodes in a weighted graph returns the measure Indeed, while BLS ambulances deal with non-urgent trans-
of the shortest path (or weighted edge) connecting those portations, ALS have to deal with urgent ones. However,
100 two nodes [7], that represent the strongest constraints that BLS ambulances often do not suffice for the required trans-
any reliable execution strategy must satisfy. If no semi- portation, and the use of ALS for not urgent transportation
reducible negative loop is in the APSSRP, then the RTED 165 is deployed, if any critical event occurs. Some specific fea-
strategy can dynamically assign values to the network time tures of the faced issue are that only one patient can be
points, satisfying all the given temporal constraints. transported at a time, and the requests are known dynami-
105 Major related work on STNU refers to the algorithms cally, especially for urgent transportation.
to check the consistency of the network and its dynamic Fulgenzi et al. in [17] propose a simulation-based system
controllability (i.e. there exists a dynamic strategy for guar- 170 to improve the quality and efficiency of (intra) hospital trans-
anteeing all the constraints, no matter when contingent time portation system, according to the patient’s condition, the
points occur), as well as supporting the dynamic execution human and technical resources, and the time requirements.
110 of the network. Morris et al [9] present a polynomial time al- In [18], the authors consider patient transportation in
gorithm to check the dynamic controllability of a STNU: the the Republic of Korea. They propose a web-based software
complexity of the algorithm is 𝑂(𝑁 5 ), being 𝑁 the number 175 system able to optimize patient transportation, by consid-
of nodes in the network. The algorithm is based on con- ering patients’ pathologies, distances from the specialized
straint propagation, where the edges, which represent time hospitals, required times, travel costs, and so on. Routes
115 constraints between two nodes, are expanded to explicitly and hospitals are identified, also through the use of crawled
state all the constraints that affect each node of the network. data, suitably collected and analyzed in big-data, distributed
However, the authors assumed that non-shortest labeled 180 context, to support decision-makers.
edges in an STNU could be disregarded – which turns out
to be far from trivial to prove [7, 10]. Morris [11] presents a
4
120 faster 𝑂(𝑁 ) algorithm, which relies on a new approach to 3. Problem Definition and
analyze some graphical properties of the simple temporal Modelling
network with no uncertainty. The same author [12] presents
an even faster version of the algorithm: the algorithm has This section describes the application domain of ride-sharing
a time complexity of 𝑂(𝑁 3 ). All the algorithms for dy- and the modeling technique we deployed. We start with
125 namic controllability checking, currently proposed by other 185 spatial modeling, define the ride-sharing graph, and then
authors, have the same complexity as in [12]. For sake of enrich the modeling by the temporalities of the graph.
3.1. Ride-Sharing as |𝑉 |, is the number of nodes in 𝐺: analogously, |𝐸| is the
number of edges. Given a pair of nodes 𝑣, 𝑢 ∈ 𝑉 , the edge 𝑒
The problem of ride-sharing is a general problem where one
between 𝑢 and 𝑣 is represented as 𝑒 = {𝑢, 𝑣}. The degree of
(or more) driver, equipped with one (or more respective)
250 a vertex 𝑣, namely 𝑑𝑒𝑔(𝑣), is the number of edges incident
190 vehicle, has to pick up one or more passengers, dropping
to 𝑣. An undirected graph features edges with no direction:
them off at one or more arrival bases. Major features of the
given 𝑒 = {𝑢, 𝑣}, we can “traverse” the edge from 𝑢 to 𝑣,
problem refer to:
as well as backward. A directed graph requires edges to
i. Independence: every driver is independent from have a direction, so they can be traversed in one direction,
the others: 255 only. A graph can be traversed, namely, some paths can be
195 ii. Automatic-matching: a central logic unit is the constructed through it. We define a walk as an alternating
matching agency (system), facilitating the ride-sharing sequence between nodes and edges, and if the edges are
arrangement; all different, then we define the walk as a path. A graph is
iii. Cost-sharing: the grand total travel cost is consid- connected if at least one path between every node exists.
ered, only; 260 An edge can have a weight, i.e. a value associated with that
200 iv. Carpooling: the ride-sharing participants are known edge. In a more complex scenario, a weight can involve
in advance, and the matched commuters usually more values, with a particular meaning, thus increasing the
have similar schedules, starting locations, and ar- overall complexity of the graph.
rival destinations, or the driver who provides the We can express a road network by an undirected weighted
ride service does not need to detour from his/her 265 multi-graph 𝐺, which consists of a set 𝑉 of vertexes (cross-
205 preferred route; roads in the network) and a set 𝐸 of edges, where each edge
v. Dynamic: ride-sharing arrangement system may {𝑢, 𝑣} represents a road between 𝑢 and 𝑣. The multi-graph
re-adjust strategies at run-time, to facilitate the ride- is a special kind of graph where more edges between a pair
sharing services according to run-time input. of nodes are permitted. Thus some edges can exist like:
To find the optimal, or sub-optimal, solution, some of the 𝑒1 = {𝑢, 𝑣}, 𝑒2 = {𝑢, 𝑣}, ..., 𝑒3 = {𝑢, 𝑣} (1)
210 optimization goals can be:
270 In our case, the weight of an edge 𝑒 = {𝑢, 𝑣} represents
i. Number of drivers: minimize the total number of the length (in Km) of a specific road from 𝑢 to 𝑣.
required drivers;
By the graph, we can then construct the following for-
ii. Total distance/time: minimize the total travel dis-
malization. Given a set of persons (one driver 𝑑𝑖 and many
tance/time of drivers’ trips;
passengers 𝑝𝑖 ), everyone has a ride 𝑟𝑖 , which is composed
215 iii. Travelling time of passengers: minimize the total
275 of two nodes in 𝐺: for instance 𝑟𝑖 = {𝑢𝑖 , 𝑣𝑖 }, where 𝑢𝑖 is
travel time of passengers’ trips;
the starting point and 𝑣𝑖 is the ending point for passenger
iv. Served requests: maximize the number of matched
𝑝𝑖 . Nodes in 𝐺 are road intersections: thus every passenger
(served) requests, thus collecting as many passen-
𝑝𝑖 has as a starting/ending point one of such intersections.
gers as possible;
This is a simplification of the problem, assuming that 𝑝𝑖 will
220 v. Cost for drivers’ trips: minimize the cost for the 280 reach the nearest intersection from his/her original posi-
drivers’ trips; tion. In the following, we perform spatial reasoning at the
vi. Cost for passengers’ trips: minimize the cost for intersection granularity.
the passengers’ trips. Each passenger 𝑝𝑖 has also two time constraints: a leav-
We initially focus on static ride-sharing, i.e. all the con- ing time constraint 𝑡(𝑢𝑖 ) = [𝑎𝑠𝑡𝑎𝑟𝑡 , 𝑎𝑒𝑛𝑑 ]; and an arrival
285 time constraint 𝑡(𝑣𝑖 ) = [𝑏𝑠𝑡𝑎𝑟𝑡 , 𝑏𝑒𝑛𝑑 ]. These constraints
225 straints are known before starting the journey, and on tem-
poral aspects. We assume to have one vehicle, one driver, are depicted as temporal ranges: a passenger 𝑝𝑖 needs to
many passengers (home patients), and one unique com- leave the starting place between time 𝑎𝑠𝑡𝑎𝑟𝑡 and 𝑎𝑒𝑛𝑑 , and
mon arrival destination – the hospital or care center, where must reach the arrival destination between time 𝑏𝑠𝑡𝑎𝑟𝑡 and
patients have their visits scheduled, and where patients 𝑏𝑒𝑛𝑑 . The driver, denoted as 𝑑𝑖 , has his/her own leaving and
290 arrival temporal constraints. Since we are focusing on static
230 must arrive on time. We specifically focus on temporal
constraints, involving both the patients and the driver. ride-sharing, the order according to which passengers are
We formalize the problem, considering the grand total picked up by the driver is decided in advance: thus, the path
travel time and the requests from every patient, in terms of must be one valid sequence of starting and ending points. A
pick-up and drop-off time constraints. Moreover, we want sequence is said to be valid if, for every 𝑝𝑖 , its starting point
295 𝑢𝑖 precedes its ending point 𝑣𝑖 .
235 to model some temporal uncertainty, resulting in a more
complex problem with respect to the simpler version with The described ride-sharing problem aims at finding a valid
no temporal uncertainty. This enhances the ability of the sequence of starting and ending points where, given some
system to deal with real-case scenarios, where passengers temporal constraint, every passenger 𝑝𝑖 leaves the starting
want to share rides, but they want also to reach their desti- point in a time 𝑡𝑙𝑒𝑎𝑣𝑒 ∈ 𝑡(𝑢𝑖 ) and arrives at the ending
300 point in a time 𝑡𝑎𝑟𝑟𝑖𝑣𝑒 ∈ 𝑡(𝑣𝑖 ). Next, we formalize the
240 nation within a certain schedule.
temporal aspects and provide a workflow for the resolution
3.1.1. Problem Formalization for Ride-Sharing by of an instance of the ride-sharing problem.
Graphs
3.2. Network Modelling
The entire problem can be formalized as a graph 𝐺 =
(𝑉, 𝐸), with a non-empty set of vertexes (or nodes) 𝑉 , and The road network of Subsection 3.1.1 is a graph. We have
245 a non-empty set of edges 𝐸. Each edge is a connection be- 305 to detect a valid sequence of starting and ending points in
tween two nodes 𝑣𝑖 , 𝑣𝑗 ∈ 𝑉 . The cardinality of 𝑉 , denoted the graph, minimizing the total travel cost, i.e. the overall
𝑑𝑏,𝑐
length of the trip, for both the driver and the passengers. 𝐵 𝐶
This introduces a complexity element, i.e. the minimization
of the total distance, to increase the satisfaction both of the 𝑑𝑎,𝑏 𝑑𝑎,𝑐 𝑑𝑏,𝑑 𝑑𝑐,𝑑
310 driver and of the passengers.
Once we have identified in the graph the starting and ar- 𝑑𝑏,𝑓 𝑑𝑐,𝑓 𝑑𝑐,𝑒
𝐴 𝐷
rival points, we can construct a distance network to include 𝑑𝑎,𝑑 𝑑𝑏,𝑒
distances between points, and a temporal constraint network 𝑑𝑎,𝑓 𝑑𝑎,𝑒 𝑑𝑑,𝑓 𝑑𝑑,𝑒
to consider temporal constraints when moving from one
315 point to another one. We thus obtain one network where
𝑑𝑒,𝑓
the weight of every edge represents the distance between 𝐹 𝐸
two points and one network where the weight represents
time ranges (intervals or durations). These networks are Figure 1: Complete graph with distances (distance network).
composed of 2𝑛 nodes, where 𝑛 is the number of persons
320 sharing the ride (the driver is included). Each node repre-
𝑑𝑏,𝑐
sents a starting point or an ending point. Every network 𝐵 𝐶
is a complete graph: every edge 𝑒𝑘 = {𝑢, 𝑣} has a weight
𝑑𝑎,𝑏 𝑑𝑎,𝑐 𝑑𝑏,𝑑 𝑑𝑐,𝑑
𝑤(𝑒𝑘 ) which represents the distance or the temporal con-
straint of the shortest path between node 𝑢 and node 𝑣.
𝑑𝑏,𝑓 𝑑𝑐,𝑓 𝑑𝑐,𝑒
325 The symmetric 2𝑛 × 2𝑛 matrix 𝑄 depicts the distance 𝐴 𝐷
𝑑𝑎,𝑑 𝑑𝑏,𝑒
network, where 𝑄[𝑖, 𝑗] defines the distance of the shortest
path between node 𝑖 and 𝑗. We assume in the following that 𝑑𝑎,𝑓 𝑑𝑎,𝑒 𝑑𝑑,𝑓 𝑑𝑑,𝑒
the shortest path between every couple of nodes is already
computed in the distance network, e.g. by OSMnx [19]. 𝑑𝑒,𝑓
𝐹 𝐸
330 By 𝑄, we compute the valid sequence which minimizes
the total travel distance. By brute force, we compute all
the possible permutations for the 𝑛 persons, therefore 2𝑛 Figure 2: Shortest path 𝛼, according to distances.
points (every person has a starting and ending point). The
valid sequence that minimizes the total travel distance can
335 be found in 𝑂(2𝑛!) ∈ 𝑂(𝑛!). In real-case applications, cars
can have up to five seats (i.e., 𝑛 = 5, five persons includ- ⎡ ⎤
ing the driver): the application will have to deal with five 0 𝑑𝑎𝑏 𝑑𝑎𝑐 𝑑𝑎𝑑 𝑑𝑎𝑒 𝑑𝑎𝑓
⎢ 𝑑𝑏𝑎 0 𝑑𝑏𝑐 𝑑𝑏𝑑 𝑑𝑏𝑒 𝑑𝑏𝑓 ⎥
persons, including the driver. Considering that the driver ⎢ ⎥
⎢ 𝑑𝑐𝑎 𝑑𝑐𝑏 0 𝑑𝑐𝑑 𝑑𝑐𝑒 𝑑𝑐𝑓 ⎥
starting point will be the first one in the permutation, and 𝑄=⎢ ⎥
⎢𝑑𝑑𝑎 𝑑𝑑𝑏 𝑑𝑑𝑐 0 𝑑𝑑𝑒 𝑑𝑑𝑓 ⎥
340 the ending point will be the last one, we expect at most to ⎢ ⎥
⎣ 𝑑𝑒𝑎 𝑑𝑒𝑏 𝑑𝑒𝑐 𝑑𝑒𝑑 0 𝑑𝑒𝑓 ⎦
compute ((5 − 1) × 2)! = 8! = 40320 permutations.
𝑑𝑓 𝑎 𝑑𝑓 𝑏 𝑑𝑓 𝑐 𝑑𝑓 𝑑 𝑑𝑓 𝑒 0
Example 1. We assume to have three persons, i.e. one
driver and two passengers, sharing one ride. Every person
has starting and ending points, and temporal constraints
345 (pick-up and drop-off times). 370 We now have to find the valid sequence of nodes mini-
From the real-world map and having 3 passengers, we mizing the overall travel distance. We recall that a sequence
find six nodes (3! = 6), and we build the distance network is valid if, for every person, its starting point precedes its
of Figure 1. Considered nodes are: ending point. The considered permutations concern pas-
senger nodes, only, since the driver’s nodes are fixed. Let’s
• Driver d: 375 suppose that the resulting valid permutation featuring the
350 – Starting point: 𝐹 shortest path of Example 1 is (Figure 3):
– Ending point: 𝐷
– Departure time interval: 𝑑𝑠𝑡𝑎𝑟𝑡 = [𝑡𝑠1 , 𝑡𝑠2 ] 𝛼 = [𝐹, 𝐴, 𝐶, 𝐵, 𝐸, 𝐷] (2)
– Arrival time interval: 𝑑𝑒𝑛𝑑 = [𝑡𝑒1 , 𝑡𝑒2 ]
• Patient 𝑝1 : We now compute the temporal range for every edge in
𝛼: this adds one more element of complexity, namely the
355 – Starting point: 𝐴
temporal dimension. The path from a place to a destination
– Ending point: 𝐵
380 requires some time, depending on traffic conditions, speed
– Departure time interval: 𝑝1𝑠𝑡𝑎𝑟𝑡 = [𝑞𝑠1 , 𝑞𝑠2 ]
limits, and other aspects. In the temporal constraint network,
– Arrival time interval: 𝑝1𝑒𝑛𝑑 = [𝑞𝑒1 , 𝑡𝑒2 ]
we assign to each edge 𝑒𝑘 , i.e. to the shortest path between
• Patient 𝑝2 : two nodes in the road network, a range 𝑒𝑘 (𝑡) = [𝑡1 , 𝑡2 ],
360 – Starting point: 𝐶 where 𝑡1 , 𝑡2 ∈ 𝒩 . The range depicts the possible duration
– Ending point: 𝐸 385 required to traverse the path, according to two hypothetical
– Departure time interval: 𝑝2𝑠𝑡𝑎𝑟𝑡 = [𝑤𝑠1 , 𝑤𝑠2 ] average speeds. For example, a route inside a city has some
– Arrival time interval: 𝑝2𝑒𝑛𝑑 = [𝑤𝑒1 , 𝑤𝑒2 ] speed limits. In this case, the lower bound of 𝑒𝑘 (𝑡), namely
The distance network results in the complete graph of 𝑡1 , refers to an average speed of 30 km/h, whereas the upper
365 Figure 1, with |𝑉 | = 6. Each edge 𝑒𝑘 = {𝑢, 𝑣} depicts bound 𝑡2 refers to an average speed of 50 km/h (see Figure 3).
390 Specific lower and upper bounds can be set, according to the
the shortest path between nodes 𝑢 and 𝑣, and its weight
𝑤(𝑒𝑘 ) ∈ ℛ depicts the length of the such shortest path. The possible speed limits in the different route segments. By the
distance network can be represented by the 6 × 6 symmetric distances from the road network, very simple computations
matrix 𝑄: assign the time range for every edge in the network. The
[𝑐1 , 𝑐2 ] [𝑐1 , 𝑐2 ]
𝐵 𝐶 𝐵 𝐶
[𝑓1 , 𝑓2 ]
[𝑏1 , 𝑏2 ]
[𝑏1 , 𝑏2 ]
𝐴 [𝑑1 , 𝑑2 ] [ℎ1 , ℎ2 ] 𝐷
𝐴 [𝑑1 , 𝑑2 ] 𝐷
[𝑡1 , 𝑡2 ] [𝑔1 , 𝑔2 ] [𝑒1 , 𝑒2 ]
[𝑡1 , 𝑡2 ] [𝑒1 , 𝑒2 ]
[𝑚1 , 𝑚2 ]
𝐹 𝐸
𝐹 𝐸
[𝑗1 , 𝑗2 ] [𝑘1 , 𝑘2 ]
Figure 3: Shortest path 𝛼 with temporal intervals.
𝑍
[𝑐1 , 𝑐2 ]
𝐵 𝐶
Figure 5: Shortest path 𝛼 with temporal intervals with arrival
[𝑓1 , 𝑓2 ] and departure constraints.
[𝑏1 , 𝑏2 ]
𝐴 [𝑑1 , 𝑑2 ] [ℎ1 , ℎ2 ] 𝐷
430 Therefore, any further constraint is defined with reference
to 𝑍. The agent will exploit this to execute the network.
[𝑡1 , 𝑡2 ] [𝑔1 , 𝑔2 ] [𝑒1 , 𝑒2 ] Black edges, as in Figure 5, depict such temporal constraints.
A similar approach could be considered also for arrival
𝐹 𝐸 time. For instance, a patient needs to have an exam in a
435 hospital lab at 9:45 a.m., but the lab opens at 8:30 a.m. and,
Figure 4: Shortest path 𝛼 with temporal intervals and arrival according to the CoViD-19-restrictions [20], patients cannot
constraints. enter the hospital too early (more than 30 minutes before
the appointment time). Therefore, for no reason, the patient
has to reach the lab before. An allowable temporal interval
number of edges in a complete graph with 𝑛 nodes is 𝑛2 :
(︀ )︀
440 could be [75, 105] minutes after 8:00 a.m.
395 in our scenario – up to 5 passengers (i.e., 4 patients and
The resulting network includes all the required temporal
1 driver) – we obtain a temporal constraint network(︀ )︀ with constraints. We now extend the network to consider un-
at most 5 × 2 = 10 nodes, which results in 10 2
= 45 certainty, too. Three starting point nodes, namely 𝐹, 𝐴, 𝐶,
edges, assuming that each passenger has starting and ending come with two types of temporal constraints:
points different from the ones of the other passengers. In our
400 examples, we shall consider as starting points the different 445 i. the three nodes have one incoming edge from 𝑍 for
points of each passenger (the first point being that of the the starting time constraint 𝑝𝑖𝑠𝑡𝑎𝑟𝑡 ;
driver) and one single ending point (i.e., the location of the ii. the three nodes have one outgoing edge for the end-
healthcare
(︀ )︀ center). Thus, we shall have 6 nodes, with at ing time constraint 𝑝𝑖𝑒𝑛𝑑 .
most 62 = 15 edges.
The setting of these time points is crucial, as they have
405 The path 𝛼 has now a time range, 𝛼𝑡 . Every person 450 implications all over the network. The agent has to con-
(driver or passenger) has to reach the destination within a sider also the time needed to reach the destination, which
given temporal constraint between the departure time and depends on the assignments of other nodes. Due to these
the arrival time. The constraint is expressed as a tempo- hard constraints, it may sometime happen that the network
ral range, i.e. an upper bound and a lower bound. This is not controllable, i.e. some constraints cannot be fulfilled.
410 constraint further increases the complexity of the requests
455 We can specify a temporal range in which we can reach
and could depend on the patient’s condition. For instance, a destination, starting from a location. However, we can
a patient requires to have an overall journey not longer encounter something that forces us to reach the destination
than 30 minutes. Thus, the allowed temporal range for the with some delay, e.g. some unexpected traffic jam, an acci-
patient’s journey could be [0, 30] minutes. To define this dent, or a detour. We can expect that in most cases we can
415 kind of constraint, we add an edge 𝑒𝑑𝑒𝑠𝑡 for every partici-
460 move from node 𝑋 to node 𝑌 in a given amount of time,
pant from the starting point to the destination point in 𝛼𝑡 , but we cannot be sure of how effectively we can reach 𝑋.
where 𝑒𝑑𝑒𝑠𝑡 (𝑡) is derived from 𝑝𝑖𝑠𝑡𝑎𝑟𝑡 and 𝑝𝑖𝑒𝑛𝑑 (or 𝑑𝑠𝑡𝑎𝑟𝑡 Therefore, we have to model this scenario in the network by
and 𝑑𝑒𝑛𝑑 in case of the driver) or it is a further ad-hoc tem- means of contingent time points, which introduce contingent
poral range. Constraint edges are depicted by red lines, as edges in the network. We define a contingent edge 𝑒 as a
420 in Figure 4.
465 path in a real-world scenario, where we assume the path to
Analogously, one person can express a temporal con- be traversed in a given amount of time 𝑡 ∈ [𝑡1 , 𝑡2 ]: we can
straint also for the pick-up time. The patient is not available observe the time 𝑡 only after the event occurred, without
until 10:00 a.m.: the temporal range will be [120, ∞] min- controlling it. That temporal range is defined: however,
utes after 8:00 a.m.. To represent all these constraints in the agent during the execution phase can only observe the
425 a homogeneous way, we define a special node (𝑍, anchor 470 outcome of the time assignment, and act consequently to
node), which depicts the initial time of the entire network. fulfill the temporal constraints.
𝑍 is set to a predefined time, and all the edges referring to Dynamic controllability plays a key role. In a not dynam-
a starting time constraint are depicted as minutes after the ically controllable network, if some contingent time points
anchor node 𝑍. In the above example, 𝑍 is set to 8:00 a.m. assume given values, the agent cannot schedule/re-schedule
[𝑐1 , 𝑐2 ]
𝐵 𝐶 cesses all the possible contingency points, and by
[𝑓1 , 𝑓2 ] 515 the RTED strategy computes the execution strategy;
[𝑏1 , 𝑏2 ] iii. map and route planner: the module connects to an
Open Street Map server, and retrieves the real-world
𝐴 [𝑑1 , 𝑑2 ] [ℎ1 , ℎ2 ] 𝐷 map for the ride-sharing scenario. Next, the module
identifies the starting and ending points on the map
[𝑡1 , 𝑡2 ] [𝑔1 , 𝑔2 ] [𝑒1 , 𝑒2 ] 520 and computes the distances between all the points
[𝑚1 , 𝑚2 ]
of the network: the resulting network comes with
𝐹 𝐸 weighted edges with temporal intervals. Finally, the
module computes all the possible permutations and
[𝑗1 , 𝑗2 ] [𝑘1 , 𝑘2 ] extracts the shortest one.
𝑍 525 Moreover, we used an open-source Java tool, allowing the
graphical representation and the checking of STNU [21].
Figure 6: Shortest path 𝛼 with temporal intervals, contingent
edges, arrival, and departure constraints. Green edge: contingent 4.2. Ride-sharing Instance
travel time constraint; Blue edge: travel time constraint; Red edge:
arrival time constraint; Black edge: departure time constraint. We consider a ride-sharing problem in Verona with one
driver and three patients. All of them have one starting
530 and one ending point, and temporal constraints for both
departure and arrival times. The multiple objectives are:
475 other time points to fulfill all the temporal conditions, in-
cluding both trip time and passenger time requirements. • minimize the total travel distance, or minimize the
In a dynamically controllable network, every passenger’s costs for all the passengers;
temporal constraints are satisfied, both starting and ending • verify the consistency of the temporal constraints,
ones, no matter where the contingent time points will be. 535 by means of dynamic controllability;
480 One more parametric aspect of the problem refers to • schedule the time arrival for every point, simulating
which edges are to be considered contingent: therefore their a temporal dimension to react to contingent events
pointing nodes will be contingent time points. As an exam- by means of a RTED strategy.
ple, in our context, we may assume that if two locations are
in the same district, reasonably the time needed to move be- We start by considering the spatial features of the prob-
485 tween them is controllable: we can ride faster or slower, and 540 lem. The driver collects the patients, drops them off at care
we can foresee the arrival time with no particular problem. centers, and then brings them back home. The driver moves
Otherwise, if we cross two districts, we can experience traf- from one of the University hospitals, point Start in Verona
fic congestion, or many intersections to cross can sometimes (Figure 7). The driver needs to reach, in the end, a care
increase the travel time. Therefore, we define contingent center in the East area of the city (point End, Figure 7). The
490 edges as those about a path that involves more than one 545 three patients, located in three different areas of the city,
district. In our example, we suppose that points 𝐹, 𝐴, 𝐶, 𝐵 need to reach three different destinations. Precisely, the
belong to the same district, whereas points 𝐸, 𝐷 belong to participants of the ride-sharing process are:
another different district: thus, the edge 𝐵 → 𝐸 will be
considered contingent and depicted by a green line as in • Patient 𝑝1
495 Figure 6. – Starting point 0: Southern District
550 – Ending point 1: Southern District
4. Implementation Details – Departure time: from 8:00 a.m. to 8:05 a.m.
– Arrival time: from 8:05 a.m. to 8:15 a.m.
This section describes the proof-of-concept prototype. We • Patient 𝑝2
first apply the algorithm to check the dynamic controllabil-
– Starting point 2: Southern District
ity of the network by [9]; then, we simulate a real scenario
500 for the RTED strategy, where the agent has to react to a
555 – Ending point 3: Western District
contingent time point and reschedule the ride. – Departure time: from 8:00 a.m. to 8:10 a.m.
– Arrival time: from 8:05 a.m. to 8:25 a.m.
4.1. System Description • Patient 𝑝3
We now describe the implementation of the system exper- – Starting point 4: Western District
imenting our approach. As development tools, we choose 560 – Ending point End: Eastern District
505 Python and the NetworkX package for managing networks.
– Departure time: from 8:05 a.m. to 8:15 a.m.
The overall architecture has three modules: – Arrival time: from 8:10 a.m. to 8:30 a.m.
i. STNU management: the module reads the graph of The driver’s ending point, departure time, and arrival
the network, and computes the respective distance times are:
graph. Next, the module computes the APSSRP ta-
510 ble and checks the dynamic controllability of the 565 • starting point Start: Southern District
distance graph; • ending point End: Eastern District
ii. network execution: the module analyzes the dis- • departure time: from 8:00 a.m. to 8:05 a.m.
tance graph network from the previous step, pro- • arrival time: from 8:10 a.m. to 8:30 a.m.
West East
South
Figure 7: Planned trip (left) and district division (right).
4
We also add another constraint on the path, namely node [3, 5] [3, 4]
570 5: it depicts a request from patient 𝑝3 to stop at node 5 to [1, 1]
5 𝐸𝑛𝑑
pick up one relative of his/hers for assistance. Thus, both 3
patient 𝑝3 and the driver need to reach a medical center in [5, 8]
E, but the path must go through node 5, Eastern District. 1
Figure 7 depicts the planned trip, along with the adopted [1, 2]
575 division of districts. District division is relevant: in our
2
formalization, a path that crosses one (or more) district
borders is considered to be of uncertain duration. Traffic [2, 3]
[1, 1]
𝑆𝑡𝑎𝑟𝑡
conditions and other factors could affect major connections
0
in a city.
580 The resulting path, depicted in red in Figure 7, is the
Figure 8: Real world network formalization.
shortest path among all the possible valid permutations,
where a permutation is defined as valid if every starting
point of every patient precedes its respective ending point.
The first and last points are fixed, describing the driver’s run these paths with respect to the computed time range.
585 starting point and ending point, respectively. The path The network is then enriched by two other kinds of tem-
chosen as the shortest one, called 𝛼, is composed as: poral constraints, namely arrival and destination constraints.
610 As explained in Section 3.2 and by Figure 5, we add a special
𝛼 = [Start, 0, 2, 1, 3, 4, 5, End] (3) node 𝑍 which represents “time zero”. In our example, 𝑍 is
set as 8:00 a.m., which is the anchor timestamp according
and it is 12.44 km long. In particular, the path is a combina- to which temporal constraints are defined.
tion of the shortest paths among points, whose distances Figure 9 depicts the network previously obtained–with
and temporal constraints are: from D to 0: 0.7 km with time 615 temporal ranges related to the time required to move from
590 interval [1,1]; from 0 to 2: 1.504 km with time interval [2,3];
a point to the next one according to the derived route– com-
from 2 to 1: 1.109 km with time interval [1,2]; from 1 to 3: pleted with the temporal constraints related to patient 𝑝1,
4.004 km with time interval [5,8]; from 3 to 4: 0.685 km with who has to move from point 0 to point 1, and to the driver,
time interval [1,1]; from 4 to 5: 2.303 km with time interval who moves from Start to End.
[3,5]; from 5 to E: 2.135 km with time interval [3,4]. 620 After running the procedure, we extrapolate the complete
595 We can now continue by considering the temporal fea- network and are able to verify that, in this case, the network
tures of the problem. Time ranges are estimated at a constant is controllable.
speed of 50 km/h as the lower bound, and at a speed of 30
km/h as the upper bound. The selected path minimizes the
overall distance since the path will reduce the total travel 4.3. Feasible Solutions
600 cost: with a certain probability, the path can also be feasi-
Not every valid path, namely a sequence where each starting
ble with regard to the temporal constraints imposed by the 625 point is reached before its respective ending point, is feasi-
participant (patient or driver). ble. In the above example, the driver does not participate
Figure 8 depicts the formalized network. Green dotted in counting all the possible permutations, having a fixed
edges depict contingent edges, which lead to contingent starting point and a fixed ending point: the starting point
605 time points. Since those edges depict paths that cross district
is the first one, and the ending point is the last one, with
borders, we cannot predict exactly how much it will take to 630 respect to all the other participants. Thus, the remainder 3
4
[3, 5] [3, 4]
5. Discussion and Conclusions
5 𝐸𝑛𝑑
[1, 1]
We faced the problem of ride-sharing, where two or more
3
[5, 8]
passengers want to share a ride: the goal is that of minimiz-
1
ing the overall length of the trip. To simplify the scenario,
665 we assume to have one driver and one car, two or more pas-
[1, 2] [10, 30]
sengers with their respective starting points, and one com-
2 [0, 15] [5, 15] mon final destination. In a real-case scenario, passengers
may also have some temporal constraints, referring to the
[2, 3] 𝑆𝑡𝑎𝑟𝑡
[1, 1] pick-up time or drop-off time. During the trip, some events
[0, 5]
0 𝑍 670 may occur, such as traffic congestion, detour, and - more
[0, 5]
generally - delays: this adds uncertainty to the problem.
Figure 9: Real world network formalization with some passen- Moreover, crossing city districts increases the probability
gers’ constraints. of encountering such events, and may force them to switch
from a statically planned trip to a dynamically planned one,
675 where decisions must be taken at run time.
𝑝𝑎𝑡𝑖𝑒𝑛𝑡𝑠 × (𝑝𝑖𝑐𝑘-𝑢𝑝 𝑝𝑜𝑖𝑛𝑡 + 𝑑𝑟𝑜𝑝-𝑜𝑓 𝑓 𝑝𝑜𝑖𝑛𝑡) = 6 points As an application domain, we considered medical trans-
need to permute, resulting in 6! = 720 possible paths. This portation: passengers are patients who need to reach the
set is the “all paths” set: among those paths, we obviously common care center, where some visits/therapies/treatments
consider only the valid ones, i.e. we cannot drop a passenger are scheduled for them. This feature adds even more tem-
680 poral constraints. In this paper, we formalized the problem
635 off at the destination before picking the passenger up. This
reduces the space to 90 valid paths, which is 12, 5% of all by graphs, deploy spatial and temporal networks to analyze
paths. We refer to them as the “valid paths”. Moreover, we the graphs, and demonstrate the approach by a running
find the “feasible paths”, that both are valid and fulfill all prototype.
the temporal constraints. The “feasible paths” set is fully
640 contained in the “valid paths” set: we shall have at most 5.1. Future Research Directions
90 feasible paths. Reasonably, the number of feasible paths
is smaller that the number of valid paths, for a not-trivial 685 We consider here some future research directions. We plan
network with reasonable time constraints. to enrich the analysis to consider more complex situations,
A valid path could be not feasible due to two main reasons e.g. having more drivers, more cars, more than 5 passengers
645 (or both of them):
per car such as in vans, as well as considering the return trip,
picking up the patients from the care center, and dropping
690 them back home. More constraints need to be considered,
• the requested time constraint is too strict;
• the distance between points is too large, so it results e.g. a patient who went through a radio-therapy can’t be
in a long travel time for that specific path, which transported in the same vehicle with a pregnant patient or
will not satisfy the time constraint(s). with a kid. To this end, we have to face the scalability issues
of this inherently intractable (𝑁 𝑃 ) problem.
650 As an example, in Figure 10 we insert a time constraint 695 The analysis can be further extended to consider the pa-
that is too strict: the resulting network will be not dynami- tient’s priority, which could help in increasing the revenues
cally controllable. In fact (Figure 10), the red line depicts a of the care center by avoiding dead times of highly expensive
too-strict time constraint from node 0 to node 1. We remind instrumentation, or in avoiding insurance claims.
that patient 𝑝1 ’s starting point is 0, and the ending point is The analysis can also consider emergency situations, thus
700 prioritizing patients according to several facets, including
655 1, so the request edge can be translated as “patient 𝑝1 needs
to reach the destination between 1 and 2 minutes after de- the patient’s status, type of disease or injury, and resource
parture”. It can be easily observed that, since we have to availability in the care centers.
pass through point 2, which is patient 𝑝2 ’s starting point,
we can reach point 1 at least 3 minutes after departure: the Acknowledgments
660 added constraint is clearly not satisfiable.
C.C., A.F., and R.P. are partially funded by Dipartimento
4
705 di Informatica, University of Verona, Italy. G.P. is partially
[3, 5] [3, 4] funded by the EU H2020 program: “PERISCOPE: Pan Eu-
5 𝐸𝑛𝑑
[1, 1]
ropean Response to the ImpactS of CoViD-19 and future
3 Pandemics and Epidemics” (grant n. 101016233) and by Di-
[5, 8] partimento di Elettronica, Informazione e Bioingegneria,
1
710 Politecnico di Milano, Italy.
[1, 2] [10, 30]
[1, 2]
2 [0, 15] [5, 15] References
[2, 3] 𝑆𝑡𝑎𝑟𝑡
[1, 1] [1] N. Chan, S. Shaheen, Ridesharing in North America:
[0, 5]
0
[0, 5]
𝑍 Past, present, and future, Transport Reviews 32 (2012)
93–112. doi:10.1080/01441647.2011.621557.
Figure 10: Non dynamically controllable example 715 [2] K. H. Chaiyachati, R. A. Hubbard, A. Yeager, B. Mugo,
J. A. Shea, R. Rosin, D. Grande, Rideshare-based medi-
cal transportation for medicaid patients and primary
care show rates: A difference-in-difference analysis of May 19-23, 2014. Proceedings, volume 8451 of Lecture
a pilot program, Journal of General Internal Medicine Notes in Computer Science, Springer, 2014, pp. 464–
720 33 (2018) 863–868. 785 479. URL: https://doi.org/10.1007/978-3-319-07046-9_
[3] B. W. Powers, S. Rinefort, S. H. Jain, Nonemergency 33. doi:10.1007/978-3-319-07046-9\_33.
medical transportation: Delivering care in the era of [13] M. K. Wolfe, N. C. McDonald, G. M. Holmes, Trans-
lyft and uber, JAMA 316 (2016) 921–922. URL: https: portation barriers to health care in the United
//doi.org/10.1001/jama.2016.9970. doi:10.1001/jama. States: Findings from the National Health Inter-
725 2016.9970. 790 view Survey, 1997–2017, American Journal of
[4] R. Collier, Uber enters medicine but disrupting health Public Health 110 (2020) 815–822. URL: https://doi.
care may prove difficult, CMAJ 190 (2018) E756– org/10.2105/AJPH.2020.305579. doi:10.2105/AJPH.
E757. URL: https://www.cmaj.ca/content/190/24/E756. 2020.305579, pMID: 32298170.
doi:10.1503/cmaj.109-5615. [14] M. K. Wolfe, N. C. McDonald, Innovative health care
730 [5] R. Dechter, I. Meiri, J. Pearl, Temporal constraint net- 795 mobility services in the US, BMC Public Health 20
works, Artif. Intell. 49 (1991) 61–95. URL: https:// (2020). doi:10.1186/s12889-020-08803-5.
doi.org/10.1016/0004-3702(91)90006-6. doi:10.1016/ [15] Y. Molenbruch, K. Braekers, A. Caris, G. V. Berghe,
0004-3702(91)90006-6. Multi-directional local search for a bi-objective dial-a-
[6] N. Muscettola, P. P. Nayak, B. Pell, B. C. Williams, ride problem in patient transportation, Comput. Oper.
735 Remote agent: To boldly go where no AI system 800 Res. 77 (2017) 58–71. URL: https://doi.org/10.1016/j.cor.
has gone before, Artif. Intell. 103 (1998) 5–47. 2016.07.020. doi:10.1016/j.cor.2016.07.020.
URL: https://doi.org/10.1016/S0004-3702(98)00068-X. [16] P. L. van den Berg, J. T. van Essen, Scheduling non-
doi:10.1016/S0004-3702(98)00068-X. urgent patient transportation while maximizing emer-
[7] L. Hunsberger, Efficient execution of dynamically gency coverage, Transp. Sci. 53 (2019) 492–509. URL:
740 controllable simple temporal networks with uncer- 805 https://doi.org/10.1287/trsc.2018.0823. doi:10.1287/
tainty, Acta Informatica 53 (2016) 89–147. URL: https: trsc.2018.0823.
//doi.org/10.1007/s00236-015-0227-0. doi:10.1007/ [17] R. Fulgenzi, S. Gitto, G. Murgia, E. Pessot, Simu-
s00236-015-0227-0. lation of patient-centred scenarios for the improve-
[8] M. Cairo, L. Hunsberger, R. Rizzi, Faster dynamic con- ment of transportation service in hospitals, in: L. M.
745 trollability checking for simple temporal networks 810 Camarinha-Matos, Á. Ortiz, X. Boucher, A. L. Osório
with uncertainty, in: N. Alechina, K. Nørvåg, (Eds.), Collaborative Networks in Digitalization and
W. Penczek (Eds.), 25th International Symposium Society 5.0 - 23rd IFIP WG 5.5 Working Conference
on Temporal Representation and Reasoning, TIME on Virtual Enterprises, PRO-VE 2022, Lisbon, Por-
2018, Warsaw, Poland, October 15-17, 2018, volume tugal, September 19-21, 2022, Proceedings, volume
750 120 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum 815 662 of IFIP Advances in Information and Communi-
für Informatik, Dagsthul, Germany, 2018, pp. 8:1– cation Technology, Springer, 2022, pp. 356–365. URL:
8:16. URL: https://doi.org/10.4230/LIPIcs.TIME.2018.8. https://doi.org/10.1007/978-3-031-14844-6_29. doi:10.
doi:10.4230/LIPIcs.TIME.2018.8. 1007/978-3-031-14844-6\_29.
[9] P. H. Morris, N. Muscettola, Temporal dynamic con- [18] H. Thai, J. Huh, Optimizing patient transportation
755 trollability revisited, in: M. M. Veloso, S. Kambhampati 820 by applying cloud computing and big data analysis,
(Eds.), Proceedings, The Twentieth National Confer- J. Supercomput. 78 (2022) 18061–18090. URL: https:
ence on Artificial Intelligence and the Seventeenth //doi.org/10.1007/s11227-022-04576-3. doi:10.1007/
Innovative Applications of Artificial Intelligence Con- s11227-022-04576-3.
ference, July 9-13, 2005, Pittsburgh, Pennsylvania, [19] G. Boeing, OSMnx: New methods for acquir-
760 USA, AAAI Press / The MIT Press, 2005, pp. 1193– 825 ing, constructing, analyzing, and visualizing com-
1198. URL: http://www.aaai.org/Library/AAAI/2005/ plex street networks, Comput. Environ. Urban
aaai05-189.php. Syst. 65 (2017) 126–139. URL: https://doi.org/10.
[10] L. Hunsberger, R. Posenato, Simpler and faster algo- 1016/j.compenvurbsys.2017.05.004. doi:10.1016/j.
rithm for checking the dynamic consistency of con- compenvurbsys.2017.05.004.
765 ditional simple temporal networks, in: J. Lang (Ed.), 830 [20] C. Combi, G. Pozzi, Health informatics: Clinical infor-
Proceedings of the Twenty-Seventh International Joint mation systems and artificial intelligence to support
Conference on Artificial Intelligence, IJCAI 2018, July medicine in the CoViD-19 pandemic, in: 9th IEEE
13-19, 2018, Stockholm, Sweden, ijcai.org, 2018, pp. International Conference on Healthcare Informatics,
1324–1330. URL: https://doi.org/10.24963/ijcai.2018/ ICHI 2021, Victoria, BC, Canada, August 9-12, 2021,
770 184. doi:10.24963/ijcai.2018/184. 835 IEEE, Los Alamitos, CA, USA, 2021, pp. 480–488. URL:
[11] P. H. Morris, A structural characterization of tem- https://doi.org/10.1109/ICHI52183.2021.00083. doi:10.
poral dynamic controllability, in: F. Benhamou (Ed.), 1109/ICHI52183.2021.00083.
Principles and Practice of Constraint Programming [21] R. Posenato, CSTNU tool: A Java library
- CP 2006, 12th International Conference, CP 2006, for checking temporal networks, SoftwareX 17
775 Nantes, France, September 25-29, 2006, Proceedings, 840 (2022) 100905. URL: https://doi.org/10.1016/j.softx.
volume 4204 of Lecture Notes in Computer Science, 2021.100905. doi:10.1016/j.softx.2021.100905.
Springer, 2006, pp. 375–389. URL: https://doi.org/10.
1007/11889205_28. doi:10.1007/11889205\_28.
[12] P. H. Morris, Dynamic controllability and dispatchabil-
780 ity relationships, in: H. Simonis (Ed.), Integration of AI
and OR Techniques in Constraint Programming - 11th
International Conference, CPAIOR 2014, Cork, Ireland,