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. trafic 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 of 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 diferent possible constraints.
Ride-sharing [
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:
15 travel costs, travel time, and environmental pollution are
just a few of them. The problem can be enriched by several
intermediate stops, spatiotemporal constraints, and external
constraints (e.g. trafic congestion), adding uncertainty and
increasing the overall complexity.
20 Ride-sharing in healthcare has been considered as a way
of increasing the number of people possibly accessing
medical care, as it is less expensive than other services and
available also in places where public transportation is
missing [
In the following, we shall consider the general issue of 45 medical transportation, where a driver picks up some patients from their respective starting points (e.g., homes), and drops them of 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 50 management of temporal uncertainty, taking into account 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 trafic condi55 tions, which may also occur dynamically, i.e. during the 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; 60 Section 3 describes the application domain and how we 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. 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 70 commonly formalized by graphs, which are then analyzed by temporal networks.
A Simple Temporal Problem (STP) is a problem
involving quantitative time constraints [5] between pairs of time
75 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
80 consistency in many constraint-based planning systems [
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 [
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
100 two nodes [
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
135 transportation [
The problem of ride-sharing of patients falls within the wider topic of patient transportation. Many issues have been 140 faced in this direction: intra-hospital patient transportation; 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 trans145 portation); evaluating ride-sharing services. Without being 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 [
As already mentioned, ambulance providers support both
ALS and BLS ambulances. In [
Indeed, while BLS ambulances deal with non-urgent transportations, ALS have to deal with urgent ones. However, BLS ambulances often do not sufice for the required transportation, and the use of ALS for not urgent transportation 165 is deployed, if any critical event occurs. Some specific features 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 [
In [
This section describes the application domain of ride-sharing and the modeling technique we deployed. We start with 185 spatial modeling, define the ride-sharing graph, and then enrich the modeling by the temporalities of the graph.
The problem of ride-sharing is a general problem where one (or more) driver, equipped with one (or more respective) 190 vehicle, has to pick up one or more passengers, dropping them of 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 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 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; v. Dynamic: ride-sharing arrangement system may re-adjust strategies at run-time, to facilitate the ridesharing services according to run-time input. 195 200 205 215 220
To find the optimal, or sub-optimal, solution, some of the 210 optimization goals can be: i. Number of drivers: minimize the total number of required drivers; ii. Total distance/time: minimize the total travel distance/time of drivers’ trips; iii. Travelling time of passengers: minimize the total travel time of passengers’ trips; iv. Served requests: maximize the number of matched (served) requests, thus collecting as many passengers as possible; v. Cost for drivers’ trips: minimize the cost for the drivers’ trips; vi. Cost for passengers’ trips: minimize the cost for the passengers’ trips.
We initially focus on static ride-sharing, i.e. all the con225 straints are known before starting the journey, and on temporal 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 230 must arrive on time. We specifically focus on temporal 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-of time constraints. Moreover, we want 235 to model some temporal uncertainty, resulting in a more 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 desti240 nation within a certain schedule.
The entire problem can be formalized as a graph = (, ), with a non-empty set of vertexes (or nodes) , and 245 a non-empty set of edges . Each edge is a connection between two nodes , ∈ . The cardinality of , denoted as | |, is the number of nodes in : analogously, || is the number of edges. Given a pair of nodes , ∈ , the edge between and is represented as = {, }. The degree of 250 a vertex , namely (), is the number of edges incident to . An undirected graph features edges with no direction: 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, 255 only. A graph can be traversed, namely, some paths can be constructed through it. We define a walk as an alternating sequence between nodes and edges, and if the edges are all diferent, then we define the walk as a path. A graph is connected if at least one path between every node exists. 260 An edge can have a weight, i.e. a value associated with that 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 265 multi-graph , which consists of a set of vertexes (crossroads 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) 270
In our case, the weight of an edge = {, } represents 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 275 of two nodes in : for instance = {, }, where is 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 280 reach the nearest intersection from his/her original position. 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 285 time constraint () = [, ]. These constraints 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 290 arrival temporal constraints. Since we are focusing on static 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 295 precedes its ending point .
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 300 point in a time ∈ (). Next, we formalize the temporal aspects and provide a workflow for the resolution of an instance of the ride-sharing problem.
The road network of Subsection 3.1.1 is a graph. We have 305 to detect a valid sequence of starting and ending points in 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
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
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
composed of 2 nodes, where is the number of persons
320 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 .
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 [
From the real-world map and having 3 passengers, we ifnd six nodes ( 3! = 6), and we build the distance network of Figure 1. Considered nodes are: 350 355 360 • Driver d: – Starting point: – Ending point: – Departure time interval: = [1, 2] – Arrival time interval: = [1, 2] • Patient 1: – Starting point: – Ending point: – Departure time interval: 1 = [1, 2] – Arrival time interval: 1 = [1, 2] • Patient 2: – Starting point: – Ending point: – Departure time interval: 2 = [1, 2] – Arrival time interval: 2 = [1, 2]
The distance network results in the complete graph of 365 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 : , , , , , , , , , , , , , , , , , , , , = ⎢⎢⎢⎢
number of edges in a complete graph with nodes is (︀ 2)︀ : 395 in our scenario – up to 5 passengers (i.e., 4 patients and 1 driver) – we obtain a temporal constraint network with at most 5 × 2 = 10 nodes, which results in (︀ 120)︀ = 45 edges, assuming that each passenger has starting and ending points diferent from the ones of the other passengers. In our 400 examples, we shall consider as starting points the diferent points of each passenger (the first point being that of the driver) and one single ending point (i.e., the location of the healthcare center). Thus, we shall have 6 nodes, with at most (︀ 6)︀ = 15 edges.
2 405 The path has now a time range, . Every person (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 410 constraint further increases the complexity of the requests 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 415 kind of constraint, we add an edge for every participant 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 420 in Figure 4.
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 425 a homogeneous way, we define a special node ( , anchor 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. 430 Therefore, any further constraint is defined with reference to . The agent will exploit this to execute the network. 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, 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 440 could be [75, 105] minutes after 8:00 a.m.
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: 445 i. the three nodes have one incoming edge from for 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 450 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. 455 We can specify a temporal range in which we can reach 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 trafic jam, an accident, or a detour. We can expect that in most cases we can 460 move from node to node in a given amount of time, but we cannot be sure of how efectively 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 465 path in a real-world scenario, where we assume the path to 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 470 outcome of the time assignment, and act consequently to 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 475 other time points to fulfill all the temporal conditions, including both trip time and passenger time requirements. 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. 480 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 be485 tween them is controllable: we can ride faster or slower, and we can foresee the arrival time with no particular problem. Otherwise, if we cross two districts, we can experience trafifc congestion, or many intersections to cross can sometimes increase the travel time. Therefore, we define contingent 490 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 diferent district: thus, the edge → will be considered contingent and depicted by a green line as in 495 Figure 6.
This section describes the proof-of-concept prototype. We
ifrst apply the algorithm to check the dynamic
controllability of the network by [
We now describe the implementation of the system experimenting our approach. As development tools, we choose 505 Python and the NetworkX package for managing networks.
The overall architecture has three modules: 510 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, pro515 520 525 535 550 555 560 565 cesses all the possible contingency points, and by the RTED strategy computes the execution strategy; 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 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
graphical representation and the checking of STNU [
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: • 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; • 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 prob540 lem. The driver collects the patients, drops them of at care 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 545 three patients, located in three diferent areas of the city, need to reach three diferent destinations. Precisely, the participants of the ride-sharing process are: • Patient 1 • Patient 2 • Patient 3 – Starting point 0: Southern District – Ending point 1: Southern District – Departure time: from 8:00 a.m. to 8:05 a.m. – Arrival time: from 8:05 a.m. to 8:15 a.m. – Starting point 2: Southern District – Ending point 3: Western District – Departure time: from 8:00 a.m. to 8:10 a.m. – Arrival time: from 8:05 a.m. to 8:25 a.m. – Starting point 4: Western District – Ending point End: Eastern District – Departure time: from 8:05 a.m. to 8:15 a.m.
– Arrival time: from 8:10 a.m. to 8:30 a.m.
The driver’s ending point, departure time, and arrival times are: • starting point Start: Southern District • ending point End: Eastern District • departure time: from 8:00 a.m. to 8:05 a.m. • arrival time: from 8:10 a.m. to 8:30 a.m.
We also add another constraint on the path, namely node 570 5: it depicts a request from patient 3 to stop at node 5 to 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 575 division of districts. District division is relevant: in our formalization, a path that crosses one (or more) district borders is considered to be of uncertain duration. Trafic conditions and other factors could afect major connections in a city. 580 The resulting path, depicted in red in Figure 7, is the 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 585 starting point and ending point, respectively. The path chosen as the shortest one, called , is composed as: South 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. 610 As explained in Section 3.2 and by Figure 5, we add a special 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 615 temporal ranges related to the time required to move from 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. 620 After running the procedure, we extrapolate the complete network and are able to verify that, in this case, the network is controllable.
Not every valid path, namely a sequence where each starting 625 point is reached before its respective ending point, is feasible. 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 630 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 635 of at the destination before picking the passenger up. This reduces the space to 90 valid paths, which is 12, 5% of all paths. We refer to them as the “valid paths”. Moreover, we ifnd the “feasible paths”, that both are valid and fulfill all the temporal constraints. The “feasible paths” set is fully 640 contained in the “valid paths” set: we shall have at most 90 feasible paths. Reasonably, the number of feasible paths is smaller that the number of valid paths, for a not-trivial network with reasonable time constraints.
A valid path could be not feasible due to two main reasons 645 (or both of them): • the requested time constraint is too strict; • the distance between points is too large, so it results in a long travel time for that specific path, which will not satisfy the time constraint(s). 650 As an example, in Figure 10 we insert a time constraint 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 655 1, so the request edge can be translated as “patient 1 needs 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 660 added constraint is clearly not satisfiable.
4
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, 665 we assume to have one driver and one car, two or more passengers 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-of time. During the trip, some events 670 may occur, such as trafic congestion, detour, and - more 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, 675 where decisions must be taken at run time.
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 tem680 poral constraints. In this paper, we formalized the problem by graphs, deploy spatial and temporal networks to analyze the graphs, and demonstrate the approach by a running prototype.
5.1. Future Research Directions 685 We consider here some future research directions. We plan 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 690 them back home. More constraints need to be considered, 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. 695 The analysis can be further extended to consider the patient’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 700 prioritizing patients according to several facets, including the patient’s status, type of disease or injury, and resource availability in the care centers.
C.C., A.F., and R.P. are partially funded by Dipartimento 705 di Informatica, University of Verona, Italy. G.P. is partially funded by the EU H2020 program: “PERISCOPE: Pan European Response to the ImpactS of CoViD-19 and future Pandemics and Epidemics” (grant n. 101016233) and by Dipartimento di Elettronica, Informazione e Bioingegneria, 710 Politecnico di Milano, Italy.