Introduction

Ride-sharing [1] is a mode of transportation in which individual travelers share a vehicle and, eventually, its costs. Typically, passengers have the same unique destination. Passengers may leave from the same starting point or may 5 be collected along the way of the first passenger to the shared destination. Ride-sharing combines the flexibility and speed of private cars with the reduced cost of fixed-line systems. In static ride-sharing, passenger arrangements are pre-computed and cannot be modified during the service.

10

In dynamic ride-sharing, automatic ride-matching between participants can occur on very short notice or even en route.

The problem of ride-sharing aims at optimizing the path of the vehicle. Optimization is helpful under several terms: travel costs, travel time, and environmental pollution are 15 just a few of them. The problem can be enriched by several intermediate stops, spatiotemporal constraints, and external constraints (e.g. traffic congestion), adding uncertainty and increasing the overall complexity.

Ride-sharing in healthcare has been considered as a way to the weaker patients' categories because of transportation barriers. Among the specific requirements that need to be addressed when planning ride-sharing for patients, we consider here:

• the maximum allowed duration of the trip for spe-35 cific patients, who cannot afford too long trips; • the strict ranges of allowed waiting times, as patients are not able to face too long waiting times (or to rush for too short deadlines); • the flexibility in reaching the final destination, avoid-40 ing both a rush and a too-long waiting time at the healthcare center, a not feasible situation especially for patients and in this pandemic context.

In the following, we shall consider the general issue of medical transportation, where a driver picks up some pa-45 tients from their respective starting points (e.g., homes), and drops them off at the same care center. The approach we propose in this paper considers the integrated application of both temporal and spatial reasoning, focusing on the management of temporal uncertainty, taking into account 50 the specific requirements of such kind of transportation. Temporal issues refer to the preferred arrival time every passenger may have. Spatial issues refer to the path of the shared vehicle. External constraints refer to traffic conditions, which may also occur dynamically, i.e. during the 55 journey, and not just before the journey starts.

The paper is structured as follows: Section 2 describes related work from the literature on both temporal and spatial topics, and the background methodological concepts; Section 3 describes the application domain and how we 60 model the problem; Section 4 describes a proof-of-concept prototype we implement; Section 5 highlights the achieved conclusions and sketches out some future research directions.

Background and Related Work

This section describes the background and the related work on temporal networks and on the ride-sharing problem, and how we select the proper methodology to cope with the selected application domain. Ride-sharing problems are commonly formalized by graphs, which are then analyzed by temporal networks.

Background: STNUs

A Simple Temporal Problem (STP) is a problem involving quantitative time constraints [5] between pairs of time points. A Simple Temporal Network (STN) is a framework for planning and scheduling applications of a STP, which is represented through a set of nodes, i.e./ time points, and weighted edges between nodes, representing quantitative temporal constraints: the formalization is adopted to check consistency in many constraint-based planning systems [6].

STNU refers to STN with uncertainty, where the occurrences of some time points, named contingent, are within specified time ranges, but beyond the control of the planning agent [7]. An STNU is controllable if a solution satisfying every constraint in the network can be found. One of the strategies for STNU is the RTED (Real Time Execution Decision) strategy [7,8], to manage contingent time points (events) which occur at run-time, and cannot be controlled (scheduled) by the agent, but are simply observed. An STNU is dynamically controllable iff (i.e., "if and only if") an execution strategy based on RTED exists. Intuitively, according to RTED, the agent, responsible for the network execution, can only observe the occurrence of contingent time points but is capable to react to such occurrences, by deciding when to execute the other time points, which are under its control.

95

The RTED strategy is based on a table known as all-pairshortest-semi-reducible paths (APSSRP), which for every couple of nodes in a weighted graph returns the measure of the shortest path (or weighted edge) connecting those two nodes [7], that represent the strongest constraints that 100 any reliable execution strategy must satisfy. If no semireducible negative loop is in the APSSRP, then the RTED strategy can dynamically assign values to the network time points, satisfying all the given temporal constraints.

Major related work on STNU refers to the algorithms to check the consistency of the network and its dynamic controllability (i.e. there exists a dynamic strategy for guaranteeing all the constraints, no matter when contingent time points occur), as well as supporting the dynamic execution of the network. Morris et al [9] present a polynomial time algorithm to check the dynamic controllability of a STNU: the complexity of the algorithm is 𝑂(𝑁 5 ), being 𝑁 the number of nodes in the network. The algorithm is based on constraint propagation, where the edges, which represent time constraints between two nodes, are expanded to explicitly state all the constraints that affect each node of the network. However, the authors assumed that non-shortest labeled edges in an STNU could be disregarded -which turns out to be far from trivial to prove [7,10]. Morris [11] presents a faster 𝑂(𝑁 4 ) algorithm, which relies on a new approach to analyze some graphical properties of the simple temporal network with no uncertainty. The same author [12] presents an even faster version of the algorithm: the algorithm has a time complexity of 𝑂(𝑁 3 ). All the algorithms for dynamic controllability checking, currently proposed by other authors, have the same complexity as in [12]. For sake of simplicity, as these last algorithms are quite complex and full of technicalities, in this paper, we consider as the fundamental starting point the 𝑂(𝑁 5 ) dynamic controllability checking algorithm of [9] for STNUs. 130

Related Work

The issue of patient transportation is of great relevance: it is estimated that 5.8 million people in the US during 2017 delayed non-emergency medical care due to lack of transportation [13]: the CoViD-19 pandemic hardened the 135 problem. A taxonomy of innovative health care mobility services is reported in [14].

The problem of ride-sharing of patients falls within the wider topic of patient transportation. Many issues have been faced in this direction: intra-hospital patient transportation; 140 optimizing the use of Advance Life Support (ALS) services (managing patients requiring high level of medical monitoring and emergency care) and Basic Life Support (BLS) (managing patients requiring non-emergency medical transportation); evaluating ride-sharing services. Without being 145 complete, in the following we shall briefly discuss some technical contributions, providing an overall picture of the context, within which we propose our original contribution.

In [15], the authors propose a generalization of the diala-ride problem, modeling some real-life requirements for 150 patient transportation. A multi-directional local search algorithm is developed to solve this problem, taking into account the fundamental tradeoff between operational efficiency and service quality, by considering specific constraints for patients and drivers. Moreover, the authors propose an original 155 scheduling procedure, minimizing the total user ride time.

As already mentioned, ambulance providers support both ALS and BLS ambulances. In [16], the authors propose a model that determines the routes for BLS ambulances while maximizing the remaining coverage by ALS ambulances. 160 Indeed, while BLS ambulances deal with non-urgent transportations, ALS have to deal with urgent ones. However, BLS ambulances often do not suffice for the required transportation, and the use of ALS for not urgent transportation is deployed, if any critical event occurs. Some specific fea-165 tures of the faced issue are that only one patient can be transported at a time, and the requests are known dynamically, especially for urgent transportation.

Fulgenzi et al. in [17] propose a simulation-based system to improve the quality and efficiency of (intra) hospital trans-170 portation system, according to the patient's condition, the human and technical resources, and the time requirements.

In [18], the authors consider patient transportation in the Republic of Korea. They propose a web-based software system able to optimize patient transportation, by consid-

Ride-Sharing

The problem of ride-sharing is a general problem where one (or more) driver, equipped with one (or more respective) vehicle, has to pick up one or more passengers, dropping 190 them off at one or more arrival bases. Major features of the problem refer to: i. Independence: every driver is independent from the others: ii. Automatic-matching: a central logic unit is the 195 matching agency (system), facilitating the ride-sharing arrangement; iii. Cost-sharing: the grand total travel cost is considered, only; iv. Carpooling: the ride-sharing participants are known 200 in advance, and the matched commuters usually have similar schedules, starting locations, and arrival destinations, or the driver who provides the ride service does not need to detour from his/her preferred route; 205 v. Dynamic: ride-sharing arrangement system may re-adjust strategies at run-time, to facilitate the ridesharing services according to run-time input.

To find the optimal, or sub-optimal, solution, some of the optimization goals can be: We initially focus on static ride-sharing, i.e. all the constraints are known before starting the journey, and on tem-225 poral aspects. We assume to have one vehicle, one driver, many passengers (home patients), and one unique common arrival destination -the hospital or care center, where patients have their visits scheduled, and where patients must arrive on time. We specifically focus on temporal 230 constraints, involving both the patients and the driver.

We formalize the problem, considering the grand total travel time and the requests from every patient, in terms of pick-up and drop-off time constraints. Moreover, we want to model some temporal uncertainty, resulting in a more 235 complex problem with respect to the simpler version with no temporal uncertainty. This enhances the ability of the system to deal with real-case scenarios, where passengers want to share rides, but they want also to reach their destination within a certain schedule.

Problem Formalization for Ride-Sharing by Graphs

The entire problem can be formalized as a graph 𝐺 = (𝑉, 𝐸), with a non-empty set of vertexes (or nodes) 𝑉 , and a non-empty set of edges 𝐸. Each edge is a connection be- given 𝑒 = {𝑢, 𝑣}, we can "traverse" the edge from 𝑢 to 𝑣, as well as backward. A directed graph requires edges to have a direction, so they can be traversed in one direction, only. A graph can be traversed, namely, some paths can be 255 constructed through it. We define a walk as an alternating sequence between nodes and edges, and if the edges are all different, then we define the walk as a path. A graph is connected if at least one path between every node exists.

An edge can have a weight, i.e. a value associated with that 260 edge. In a more complex scenario, a weight can involve more values, with a particular meaning, thus increasing the overall complexity of the graph.

We can express a road network by an undirected weighted multi-graph 𝐺, which consists of a set 𝑉 of vertexes (cross-265 roads in the network) and a set 𝐸 of edges, where each edge {𝑢, 𝑣} represents a road between 𝑢 and 𝑣. The multi-graph is a special kind of graph where more edges between a pair of nodes are permitted. Thus some edges can exist like:

𝑒1 = {𝑢, 𝑣}, 𝑒2 = {𝑢, 𝑣}, ..., 𝑒3 = {𝑢, 𝑣}(1)

In our case, the weight of an edge 𝑒 = {𝑢, 𝑣} represents 270 the length (in Km) of a specific road from 𝑢 to 𝑣.

By the graph, we can then construct the following formalization. Given a set of persons (one driver 𝑑𝑖 and many passengers 𝑝𝑖), everyone has a ride 𝑟𝑖, which is composed of two nodes in 𝐺: for instance 𝑟𝑖 = {𝑢𝑖, 𝑣𝑖}, where 𝑢𝑖 is 275 the starting point and 𝑣𝑖 is the ending point for passenger 𝑝𝑖. Nodes in 𝐺 are road intersections: thus every passenger 𝑝𝑖 has as a starting/ending point one of such intersections. This is a simplification of the problem, assuming that 𝑝𝑖 will reach the nearest intersection from his/her original posi-280 tion. In the following, we perform spatial reasoning at the intersection granularity.

Each passenger 𝑝𝑖 has also two time constraints: a leaving time constraint 𝑡(𝑢𝑖) = [𝑎𝑠𝑡𝑎𝑟𝑡, 𝑎 𝑒𝑛𝑑 ]; and an arrival time constraint 𝑡(𝑣𝑖) = [𝑏𝑠𝑡𝑎𝑟𝑡, 𝑏 𝑒𝑛𝑑 ]. These constraints 285 are depicted as temporal ranges: a passenger 𝑝𝑖 needs to leave the starting place between time 𝑎𝑠𝑡𝑎𝑟𝑡 and 𝑎 𝑒𝑛𝑑 , and must reach the arrival destination between time 𝑏𝑠𝑡𝑎𝑟𝑡 and 𝑏 𝑒𝑛𝑑 . The driver, denoted as 𝑑𝑖, has his/her own leaving and arrival temporal constraints. Since we are focusing on static 290 ride-sharing, the order according to which passengers are picked up by the driver is decided in advance: thus, the path must be one valid sequence of starting and ending points. A sequence is said to be valid if, for every 𝑝𝑖, its starting point 𝑢𝑖 precedes its ending point 𝑣𝑖.

295

The described ride-sharing problem aims at finding a valid sequence of starting and ending points where, given some temporal constraint, every passenger 𝑝𝑖 leaves the starting point in a time 𝑡 𝑙𝑒𝑎𝑣𝑒 ∈ 𝑡(𝑢𝑖) and arrives at the ending point in a time 𝑡𝑎𝑟𝑟𝑖𝑣𝑒 ∈ 𝑡(𝑣𝑖). Next, we formalize the 300 temporal aspects and provide a workflow for the resolution of an instance of the ride-sharing problem.

Network Modelling

The road network of Subsection 3.1.1 is a graph. We have to detect a valid sequence of starting and ending points in 305 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 driver and of the passengers.

Once we have identified in the graph the starting and arrival 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 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 composed of 2𝑛 nodes, where 𝑛 is the number of persons sharing the ride (the driver is included). Each node represents 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 constraint of the shortest path between node 𝑢 and node 𝑣.

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].

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𝑛 points (every person has a starting and ending point). The valid sequence that minimizes the total travel distance can be found in 𝑂(2𝑛!) ∈ 𝑂(𝑛!). In real-case applications, cars can have up to five seats (i.e., 𝑛 = 5, five persons including the driver): the application will have to deal with five persons, including the driver. Considering that the driver starting point will be the first one in the permutation, and the ending point will be the last one, we expect at most to compute ((5 − 1) × 2)! = 8! = 40320 permutations. 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 (pick-up and drop-off times).

From the real-world map and having 3 passengers, we find six nodes (3! = 6), and we build the distance network of The distance network results in the complete graph of Figure 1, with |𝑉 | = 6. Each edge 𝑒 𝑘 = {𝑢, 𝑣} depicts the shortest path between nodes 𝑢 and 𝑣, and its weight 𝑤(𝑒 𝑘 ) ∈ ℛ depicts the length of the such shortest path. The distance network can be represented by the 6 × 6 symmetric matrix 𝑄:

𝑄 = ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ 0 𝑑 𝑎𝑏 𝑑𝑎𝑐 𝑑 𝑎𝑑 𝑑𝑎𝑒 𝑑 𝑎𝑓 𝑑 𝑏𝑎 0 𝑑 𝑏𝑐 𝑑 𝑏𝑑 𝑑 𝑏𝑒 𝑑 𝑏𝑓 𝑑𝑐𝑎 𝑑 𝑐𝑏 0 𝑑 𝑐𝑑 𝑑𝑐𝑒 𝑑 𝑐𝑓 𝑑 𝑑𝑎 𝑑 𝑑𝑏 𝑑 𝑑𝑐 0 𝑑 𝑑𝑒 𝑑 𝑑𝑓 𝑑𝑒𝑎 𝑑 𝑒𝑏 𝑑𝑒𝑐 𝑑 𝑒𝑑 0 𝑑 𝑒𝑓 𝑑 𝑓 𝑎 𝑑 𝑓 𝑏 𝑑 𝑓 𝑐 𝑑 𝑓 𝑑 𝑑 𝑓 𝑒 0 ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦

We now have to find the valid sequence of nodes mini-370 mizing the overall travel distance. We recall that a sequence is valid if, for every person, its starting point precedes its ending point. The considered permutations concern passenger nodes, only, since the driver's nodes are fixed. Let's suppose that the resulting valid permutation featuring the 375 shortest path of Example 1 is (Figure 3):

𝛼 = [𝐹, 𝐴, 𝐶, 𝐵, 𝐸, 𝐷](2)

We now compute the temporal range for every edge in 𝛼: this adds one more element of complexity, namely the temporal dimension. The path from a place to a destination requires some time, depending on traffic conditions, speed 380 limits, and other aspects. In the temporal constraint network, we assign to each edge 𝑒 𝑘 , i.e. to the shortest path between two nodes in the road network, a range 𝑒 𝑘 (𝑡) = [𝑡1, 𝑡2], where 𝑡1, 𝑡2 ∈ 𝒩 . The range depicts the possible duration required to traverse the path, according to two hypothetical 385 average speeds. For example, a route inside a city has some speed limits. In this case, the lower bound of 𝑒 𝑘 (𝑡), namely 𝑡1, refers to an average speed of 30 km/h, whereas the upper bound 𝑡2 refers to an average speed of 50 km/h (see Figure 3). Specific lower and upper bounds can be set, according to the 390 possible speed limits in the different route segments. By the distances from the road network, very simple computations assign the time range for every edge in the network. The (driver or passenger) has to reach the destination within a given temporal constraint between the departure time and the arrival time. The constraint is expressed as a temporal range, i.e. an upper bound and a lower bound. This constraint further increases the complexity of the requests 410 and could depend on the patient's condition. For instance, a patient requires to have an overall journey not longer than 30 minutes. Thus, the allowed temporal range for the patient's journey could be [0, 30] minutes. To define this kind of constraint, we add an edge 𝑒 𝑑𝑒𝑠𝑡 for every partici-415 pant from the starting point to the destination point in 𝛼𝑡, where 𝑒 𝑑𝑒𝑠𝑡 (𝑡) is derived from 𝑝𝑖 𝑠𝑡𝑎𝑟𝑡 and 𝑝𝑖 𝑒𝑛𝑑 (or 𝑑𝑠𝑡𝑎𝑟𝑡 and 𝑑 𝑒𝑛𝑑 in case of the driver) or it is a further ad-hoc temporal range. Constraint edges are depicted by red lines, as in Figure 4.

[𝑏1, 𝑏2] [𝑐1, 𝑐2] [𝑑1, 𝑑2] [𝑒1, 𝑒2] [𝑓1, 𝑓2] [𝑔1, 𝑔2] [ℎ1, ℎ2]

420

Analogously, one person can express a temporal constraint also for the pick-up time. The patient is not available until 10:00 a.m.: the temporal range will be [120, ∞] minutes after 8:00 a.m.. To represent all these constraints in a homogeneous way, we define a special node (𝑍, anchor 425 node), which depicts the initial time of the entire network. 𝑍 is set to a predefined time, and all the edges referring to a starting time constraint are depicted as minutes after the anchor node 𝑍. In the above example, 𝑍 is set to 8:00 a.m. Therefore, any further constraint is defined with reference 430 to 𝑍. The agent will exploit this to execute the network. Black edges, as in Figure 5, depict such temporal constraints.

𝐴 𝐵 𝐶 𝐷 𝐸 𝐹 𝑍 [𝑡1, 𝑡2] [𝑏1, 𝑏2] [𝑐1, 𝑐2] [𝑑1, 𝑑2] [𝑒1, 𝑒2] [𝑓1, 𝑓2] [𝑔1, 𝑔2] [ℎ1, ℎ2] [𝑗1, 𝑗2] [𝑘1, 𝑘2] [𝑚1, 𝑚2]

A similar approach could be considered also for arrival time. For instance, a patient needs to have an exam in a hospital lab at 9:45 a.m., but the lab opens at 8:30 a.m. and, 435 according to the CoViD-19-restrictions [20], patients cannot 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 could be [75, 105] minutes after 8:00 a.m.

440

The resulting network includes all the required temporal constraints. We now extend the network to consider uncertainty, too. Three starting point nodes, namely 𝐹, 𝐴, 𝐶, come with two types of temporal constraints: i. the three nodes have one incoming edge from 𝑍 for 445 the starting time constraint 𝑝𝑖 𝑠𝑡𝑎𝑟𝑡 ; ii. the three nodes have one outgoing edge for the ending time constraint 𝑝𝑖 𝑒𝑛𝑑 .

The setting of these time points is crucial, as they have implications all over the network. The agent has to consider also the time needed to reach the destination, which depends on the assignments of other nodes. Due to these hard constraints, it may sometime happen that the network is not controllable, i.e. some constraints cannot be fulfilled.

We can specify a temporal range in which we can reach 455 a destination, starting from a location. However, we can encounter something that forces us to reach the destination with some delay, e.g. some unexpected traffic jam, an accident, or a detour. We can expect that in most cases we can move from node 𝑋 to node 𝑌 in a given amount of time, 460 but we cannot be sure of how effectively we can reach 𝑋. Therefore, we have to model this scenario in the network by means of contingent time points, which introduce contingent edges in the network. We define a contingent edge 𝑒 as a path in a real-world scenario, where we assume the path to 465 be traversed in a given amount of time 𝑡 ∈ [𝑡1, 𝑡2]: we can observe the time 𝑡 only after the event occurred, without controlling it. That temporal range is defined: however, the agent during the execution phase can only observe the outcome of the time assignment, and act consequently to 470 fulfill the temporal constraints. Dynamic controllability plays a key role. In a not dynamically controllable network, if some contingent time points assume given values, the agent cannot schedule/re-schedule In a dynamically controllable network, every passenger's temporal constraints are satisfied, both starting and ending ones, no matter where the contingent time points will be.

𝐴 𝐵 𝐶 𝐷 𝐸 𝐹 𝑍 [𝑡1, 𝑡2] [𝑏1, 𝑏2] [𝑐1, 𝑐2] [𝑒1, 𝑒2] [𝑓1, 𝑓2] [𝑔1, 𝑔2] [ℎ1, ℎ2] [𝑗1, 𝑗2] [𝑘1, 𝑘2] [𝑚1, 𝑚2] [𝑑1, 𝑑2]

One more parametric aspect of the problem refers to which edges are to be considered contingent: therefore their pointing nodes will be contingent time points. As an example, in our context, we may assume that if two locations are in the same district, reasonably the time needed to move between them is controllable: we can ride faster or slower, and 485 we can foresee the arrival time with no particular problem. Otherwise, if we cross two districts, we can experience traffic congestion, or many intersections to cross can sometimes increase the travel time. Therefore, we define contingent edges as those about a path that involves more than one district. In our example, we suppose that points 𝐹, 𝐴, 𝐶, 𝐵 belong to the same district, whereas points 𝐸, 𝐷 belong to another different district: thus, the edge 𝐵 → 𝐸 will be considered contingent and depicted by a green line as in Figure 6.

Implementation Details

This section describes the proof-of-concept prototype. We first apply the algorithm to check the dynamic controllability of the network by [9]; then, we simulate a real scenario for the RTED strategy, where the agent has to react to a 500 contingent time point and reschedule the ride.

System Description

We now describe the implementation of the system experimenting our approach. As development tools, we choose Python and the NetworkX package for managing networks.

505

The overall architecture has three modules:

i. STNU management: the module reads the graph of the network, and computes the respective distance graph. Next, the module computes the APSSRP table and checks the dynamic controllability of the distance graph; ii. network execution: the module analyzes the distance graph network from the previous step, pro-cesses all the possible contingency points, and by the RTED strategy computes the execution strategy;

515

iii. map and route planner: the module connects to an Open Street Map server, and retrieves the real-world map for the ride-sharing scenario. Next, the module identifies the starting and ending points on the map and computes the distances between all the points 520 of the network: the resulting network comes with weighted edges with temporal intervals. Finally, the module computes all the possible permutations and extracts the shortest one.

Moreover, we used an open-source Java tool, allowing the 525 graphical representation and the checking of STNU [21].

Ride-sharing Instance

We consider a ride-sharing problem in Verona with one driver and three patients. All of them have one starting and one ending point, and temporal constraints for both 530 departure and arrival times. The multiple objectives are:

• minimize the total travel distance, or minimize the costs for all the passengers; • verify the consistency of the temporal constraints, by means of dynamic controllability;

535

• schedule the time arrival for every point, simulating a temporal dimension to react to contingent events by means of a RTED strategy.

We start by considering the spatial features of the problem. The driver collects the patients, drops them off at care 540 centers, and then brings them back home. The driver moves from one of the University hospitals, point Start in Verona (Figure 7). The driver needs to reach, in the end, a care center in the East area of the city (point End, Figure 7). The three patients, located in three different areas of the city, We also add another constraint on the path, namely node 5: it depicts a request from patient 𝑝3 to stop at node 5 to 570 pick up one relative of his/hers for assistance. Thus, both patient 𝑝3 and the driver need to reach a medical center in E, but the path must go through node 5, Eastern District. Figure 7 depicts the planned trip, along with the adopted division of districts. District division is relevant: in our 575 formalization, a path that crosses one (or more) district borders is considered to be of uncertain duration. Traffic conditions and other factors could affect major connections in a city.

The resulting path, depicted in red in Figure 7, is the 580 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 starting point and ending point, respectively. The path 585 chosen as the shortest one, called 𝛼, is composed as:

𝛼 = [Start, 0, 2, 1, 3, 4, 5, End](3)

and it is 12.44 km long. In particular, the path is a combination of the shortest paths among points, whose distances and temporal constraints are: from D 0: 0.7 km with time interval [1,1]; from 0 to 2: 1.504 km with time interval [2,3]; 590 from 2 to 1: 1.109 km with time interval [1,2]; from 1 to 3: 4.004 km with time interval [5,8]; from 3 to 4: 0.685 km with time interval [1,1]; from 4 to 5: 2.303 km with time interval [3,5]; from 5 to E: 2.135 km with time interval [3,4].

We can now continue by considering the temporal fea-595 tures of the problem. Time ranges are estimated at a constant 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 cost: with a certain probability, the path can also be feasi-600 ble with regard to the temporal constraints imposed by the participant (patient or driver). Figure 8 depicts the formalized network. Green dotted edges depict contingent edges, which lead to contingent time points. Since those edges depict paths that cross district 605 borders, we cannot predict exactly how much it will take to run these paths with respect to the computed time range. The network is then enriched by two other kinds of temporal constraints, namely arrival and destination constraints. As explained in Section 3.2 and by Figure 5, we add a special 610 node 𝑍 which represents "time zero". In our example, 𝑍 is set as 8:00 a.m., which is the anchor timestamp according to which temporal constraints are defined.

Figure 9 depicts the network previously obtained-with temporal ranges related to the time required to move from 615 a point to the next one according to the derived route-completed with the temporal constraints related to patient 𝑝1, who has to move from point 0 to point 1, and to the driver, who moves from Start to End.

After running the procedure, we extrapolate the complete 620 network and are able to verify that, in this case, the network is controllable.

Feasible Solutions

Not every valid path, namely a sequence where each starting point is reached before its respective ending point, is feasi-625 ble. In the above example, the driver does not participate in counting all the possible permutations, having a fixed starting point and a fixed ending point: the starting point is the first one, and the ending point is the last one, with respect to all the other participants. Thus, the remainder 3 𝑝𝑎𝑡𝑖𝑒𝑛𝑡𝑠 × (𝑝𝑖𝑐𝑘-𝑢𝑝 𝑝𝑜𝑖𝑛𝑡 + 𝑑𝑟𝑜𝑝-𝑜𝑓 𝑓 𝑝𝑜𝑖𝑛𝑡) = 6 points need to permute, resulting in 6! = 720 possible paths. This set is the "all paths" set: among those paths, we obviously consider only the valid ones, i.e. we cannot drop a passenger off at the destination before picking the passenger up. This that is too strict: the resulting network will be not dynamically controllable. In fact (Figure 10), the red line depicts a too-strict time constraint from node 0 to node 1. We remind that patient 𝑝1's starting point is 0, and the ending point is 1, so the request edge can be translated as "patient 𝑝1 needs 655 to reach the destination between 1 and 2 minutes after departure". It can be easily observed that, since we have to pass through point 2, which is patient 𝑝2's starting point, we can reach point 1 at least 3 minutes after departure: the added constraint is clearly not satisfiable.

Discussion and Conclusions

We faced the problem of ride-sharing, where two or more passengers want to share a ride: the goal is that of minimizing the overall length of the trip. To simplify the scenario, we assume to have one driver and one car, two or more pas-665 sengers with their respective starting points, and one common final destination. In a real-case scenario, passengers may also have some temporal constraints, referring to the pick-up time or drop-off time. During the trip, some events may occur, such as traffic congestion, detour, and -more 670 generally -delays: this adds uncertainty to the problem. Moreover, crossing city districts increases the probability of encountering such events, and may force them to switch from a statically planned trip to a dynamically planned one, where decisions must be taken at run time.

675

As an application domain, we considered medical transportation: passengers are patients who need to reach the common care center, where some visits/therapies/treatments are scheduled for them. This feature adds even more temporal constraints. In this paper, we formalized the problem 680 by graphs, deploy spatial and temporal networks to analyze the graphs, and demonstrate the approach by a running prototype.

Future Research Directions

We consider here some future research directions. We plan 685 to enrich the analysis to consider more complex situations, e.g. having more drivers, more cars, more than 5 passengers per car such as in vans, as well as considering the return trip, picking up the patients from the care center, and dropping them back home. More constraints need to be considered, 690 e.g. a patient who went through a radio-therapy can't be transported in the same vehicle with a pregnant patient or with a kid. To this end, we have to face the scalability issues of this inherently intractable (𝑁 𝑃 ) problem.

The analysis can be further extended to consider the pa-695 tient's priority, which could help in increasing the revenues of the care center by avoiding dead times of highly expensive instrumentation, or in avoiding insurance claims. The analysis can also consider emergency situations, thus prioritizing patients according to several facets, including 700 the patient's status, type of disease or injury, and resource availability in the care centers.