Optimizing a vehicle’s route in an on-demand ridesharing system in which users might walk

Abstract

Within the context of a shared on-demand transport system, we study the problem of selecting the stopping points from which passengers should walk to their exact destinations (or from their exact origins). We focus on the single-vehicle case that must follow a predefined order of requests, posing the mathematical program, showing that it can be solved in polynomial time and proposing a heuristic that runs faster. We compare the optimal algorithm, the heuristic, and the routes that visit the exact request points, and we show that avoiding detours can reduce total costs by almost one fifth and vehicle costs by more than one third. The heuristic yields competitive results. Simulations over the real street network from Manhattan show that the time reduction achieved by the heuristic might be crucial to enable the system to operate in real-time.

Keywords:

• Detour
• on-demand
• pick-up and drop-off
• ridesharing
• walking

Introduction

Transport and network researchers have studied on-demand systems for a long time. The DAR (dial-a-ride) problem was analyzed widely during the seventies and eighties (for example Jaw et al., 1986; Psaraftis, 1983; Wilson et al., 1976), usually assuming trips requested by phone. In the past few years, the problem has gained new attention due to the massive coordination abilities provided by online (real-time) apps (as shown by Uber or Cabify), which changes the problem as now there are many more requests, and they arrive more often. This increase in the number of users enhances the possibility of using shared systems, in which different users can ride the same vehicle at the same time,¹ making these systems more similar to public transport systems, and the problem also related to VRP (vehicle routing problem). Martinez and Crist (2016), Alonso-Mora et al. (2017), and Fagnant and Kockelman (2018), for instance, study different ways to operate such systems in Lisbon, Manhattan, and Austin, respectively. They all assume a driverless technology, which also favors the massiveness of this type of system by reducing the operating costs. Nevertheless, they act as private taxis when dealing with their routes, as they carry every passenger from their specific origin to their specific destination, rather than requesting them to walk to/from nearby points.²

Traditional public transport systems (with fixed routes) collect users in stops for two main reasons: 1) to gather enough passengers close to those routes, and 2) to avoid unnecessary detours. The first reason becomes irrelevant when vehicles can coordinate online with users; but the second one is still valid, such that there is a tradeoff between shortening these detours and preventing passengers from walking long distances. Moreover, on-demand systems do not need to rely on predetermined meeting points, but they can be decided online, adjusting to each vehicle’s route.

To illustrate the potential benefits of users’ walks, consider Figures 1 and 2 based on real-world examples. Figure 1 shows snapshots from Google Maps in Santiago, Chile, for a vehicle that’s on its way to pick up (or drop off) a passenger. If walks are not admitted and the service is door-to-door, a detour of three minutes is required to arrive at the passenger’s exact origin. On the other hand, if the system can require users to walk, then this passenger needs to walk a very short distance to meet the vehicle in the same street its currently driving, inducing zero detour. Note that in this case, the savings are mostly justified by the directions of the streets.

Figure 1. Snapshots from Google Maps in Santiago, Chile, showing (a) the detour induced to a vehicle if it needs to pick a passenger in his/her door, (b) the walk required by the same passenger to meet the vehicle.

Figure 2. The corner between (a) Huis te Landelaan, a fast street, and (b) Van Vredenburchweg, a slow street, in Rijswijk, The Netherlands.

Figure 2 is not related with those directions, but with the velocity of each street. It shows pictures from a real corner in Rijswijk, Netherlands, in which one of the streets involved is fast, and the other one is very narrow and cars share the space with bicycles. If a ridesharing vehicle is driving through the fast street, and needs to pick up (or drop off) a passenger in a point that lays over the slow street, then going to the exact point will induce a severe delay, that would be saved if the passenger can walk to the said corner.

In this paper, we study how to optimize the route of a vehicle that needs to visit some requested points, which might be origins or destinations, but not necessarily at their exact locations, facing a tradeoff between the vehicle’s costs and users’ walking costs. Introducing users’ walks when optimizing a full ridesharing system (i.e., when deciding the assignments between passengers and vehicles at the same time) is a quite complex problem. For instance, in a previous work (Fielbaum et al., 2021) we have extended the assignment model by Alonso-Mora et al. (2017) to include the optimization of where to pick-up and drop-off the users: results are promising, but methods have to be specifically designed for the assignment algorithm, which hinders the analysis of the impact of avoiding detours from a more general perspective; this is likely to be the case for any method that optimizes everything together, because of the complexity of the assignment problem by itself, that combines DAR with the VRP, two traditional NP-Hard problems. This is why we focus on a single vehicle, which allows us to provide neat algorithms and results; moreover, the methods proposed here are suitable for the many different ways of modeling and solving ridesharing systems, that include agent-based models (such as Fagnant & Kockelman, 2018, or Martinez & Crist, 2016) and algorithmic approaches (such as Alonso-Mora et al., 2017, or Tsao et al., 2019).

State of the art

On-demand mobility systems have been increasingly studied in the last few years, both in shared and non-shared versions. Different types of shared systems (including the ones in which drivers have their own itinerary, and passengers sharing vehicles with cargo) have been surveyed by Mourad et al. (2019), while Silwal et al. (2019) reviews ridesharing systems with an emphasis on their operational architectures. Carsharing systems (in which rides might be non-shared), on the other hand, have been surveyed by Narayanan et al. (2020) and by Wang and Yang (2019).

The single-vehicle problem with flexible pick-up and drop-off locations within an on-demand ridesharing framework, has been studied by Li et al. (2016), in which they also optimize the order in which these points are visited, a problem that is naturally NP-Hard as it extends TSP (traveling salesman problem). However, assuming that the order is endogenous might be troublesome:

• Unless we assume that passengers have a common origin or a common destination (which would limit severely the range of application of this problem), the order must include some precedence constraints, namely that pick-ups must occur before drop-offs.

• Not all requests emerge at the same time, which might require some orders that are close to some FIFO rules, to keep waiting times bounded for all, and to ensure that the vehicle arrives not before the passenger.

• Taking all this into account would again be specific to the ridesharing method and to the assignment algorithm, limiting the generality of the results.

These reasons make the problem in which the order of the visits is fixed but the exact location is optimized a natural one, which has not been studied from a theoretical point of view.

In logistics, a similar problem has also been studied for a single vehicle: a truck delivering some goods, that can use a drone to visit the exact customers’ locations (similar to “walking”), while the truck continues to move toward the following customer, optimizing the places in which the drone is launched (Carlsson & Song, 2018). They, too, optimize the order in which the requests are visited, although they discuss the case in which this order exogenous. As in our problem, the extra freedom provided by the drone (like the walking user) allows defining a more direct route for the main vehicle, reducing the detours. However, three structural aspects of the problem are different in comparison with ours, implying significant modeling and mathematical differences:

• First, they work over the Euclidean space, because the drone can move unaffected by the road network and the traffic, which allows using several continuous and geometrical tools that are not available in this combinatorial version.

• Second, when studying people’s mobility, each user’s time and need to be taken into account, whereas in logistics, one can consider just the total circuit time (as done by Carlsson & Song, 2018). This means that what counts is how the truck and the drone effectively coordinate to advance simultaneously, rather than achieving low times for both the car and the walking user, as we do here. Among other implications, this makes the objective function to consider the maximum between the truck’s and drone’s times, instead of the sum of the vehicle’s and user’s times.

• Third, because the logistics scheme works with a single drone, the vehicle’s route needs to allow the drone to go back and forth each time, which implies that the location of a customer relates directly with two consecutive truck’s stops: where the drone is launched and the last point it might land. In our problem, each vehicle’s stop is related only with one request, representing either a pick-up or a drop-off, which naturally entails differences in the respective objective functions and the resulting optimal routes.

A few previous papers, besides the ones already described (Carlsson & Song, 2018; Fielbaum et al., 2021; Li et al., 2016), study avoiding-detours on-demand systems from diverse perspectives. Zhao et al. (2018) propose a mathematical model in a non-shared on-demand scheme that optimize where to pick-up and drop-off the passengers. Stiglic et al. (2015) and Li et al. (2018) also solve the complete problem, but they impose a pre-defined set of “meeting points” to which all passengers have to walk, and that are selected from a subset of the nodes. Fielbaum (2020) studies a feeder transit system in which users need to get gathered at some optimized point, but over a simplified city model; a similar approach is followed by Daganzo (1984) under a dial-a-ride scheme, who analyzes under which scenarios it is best to use fixed lines or a flexible dial-a-ride system that might have fixed meeting points. Finally, Pei et al. (2019) and Zheng et al. (2019) also consider meeting points for “flex-route” systems, in which traditional transit routes are allowed to make constrained changes on-demand.

While a new topic for on-demand systems, the tradeoff between walking and vehicles’ routes has been thoroughly studied in public transport. Hurdle (1973), Kocur and Hendrickson (1982), and Chang and Schonfeld (1991) have studied systems formed by parallel transit lines, to optimize their spatial density. More complex systems have been analyzed by Daganzo (2010) and Badia et al. (2014), who optimize spatial density when considering bus transit networks, and by Tirachini et al. (2010), who compare different modes. On a related note, Tirachini (2014) optimizes the distance between bus stops, which affect passengers’ walks and vehicles’ speed, although not their routes. All these papers provide some intuition regarding ridesharing systems, as they propose sound methodologies to optimize operators’ and users’ costs jointly, and they show that walks can be beneficial not only for operators but also for users (at least partially), by reducing waiting and in-vehicle times. However, as public transport provides fixed routes (as opposed to on-demand), there are also structural differences with on-demand ridesharing systems; in particular, one expects that latter can still provide door-to-door service to requests that do not induce relevant detours.

Contribution and organization of this paper

The problem of optimizing the route of a single shared vehicle that must serve a fixed order of requests, in which users might be requested to walk to a different node, has not been studied from a theoretical point of view. In this paper we fill that gap. We show that this problem can be optimized with a polynomial algorithm, whose complexity for serving $N$ requests in a graph with $\left|V\right|$ nodes is $O({\left|V\right|}^{2}N),$ and that is based on searching the shortest path touring exactly $N$ arcs with costs that evolve with each step. This complexity might yield times that are too long for online systems, so we also propose a heuristic that runs much faster, as it drops the dependence on $N$ because it computes one step at a time rather than the whole route at once. We compare the results of the three procedures: the optimal one (OPT), the heuristic (HEU), and the one that does not avoid detours and visit the exact origins and destinations (DET), and we show that HEU is much better than DET and not so worse than OPT. Simulations over simplified networks allow us to provide a clear intuition behind the results yielded by each procedure, while simulations over a real network (representing Manhattan) reveal that HEU is able to work over large scales, whereas OPT depends on the specific conditions of the problem.

This paper is structured as follows. “The mathematical program” poses the optimization problem formally and provides the polynomial optimal algorithm, the heuristic, and some results regarding the competitive ratio of this problem. “Numerical simulations” compares the three algorithms over random networks, a small transport network representing a ridesharing system, and over the real graph underlying Manhattan’s streets. “Conclusions and future research” concludes and proposes some lines for future research.

The mathematical program

Consider a single vehicle that has to fulfill some requests, i.e., visit some points in space that represent origins or destinations of some users’ trips, but these visits do not need to be exact. We aim to optimize the vehicle’s route such that its length is not so long, and passengers do not need to walk too much. Deciding in which order to serve these requests should be served can be modeled in different ways (such as using a first-in-first-out rule or some modifications of TSP). We will assume this order is exogenous. Note that we can characterize each feasible route by its initial and ending points, and by the stopping points serving each request: the paths between these points are the shortest ones.

In order to pose the problem formally, let us define some necessary notation. We will consider a directed and strongly connected graph $G=(V,E).$ Each arc $e$ has two positive cost functions $c_V(e)$ and $c_W(e),$ representing the total costs of touring the arc using the vehicle ($c_V,$ that should include the whole costs induced at the system’s operator, such as the extra travel or waiting time for the rest of the passengers and the extra monetary costs required to operate the vehicle) or walking ($c_W$), which we assume to fulfill triangular inequalities. The direction of an arc applies for vehicles only, i.e., they can always be walked in either direction. Costs might take the value $+\infty$ in some arcs; when that happens, we shall say that this arc exists only for the mode with finite costs. The two cost functions do not need to be related, which allows representing different types of connections (such as highways, in which $c_V$ is much lower than $c_W,$ pedestrian paths in which the opposite occurs, one-directional streets that can be walked in either direction, etc.). The requested points are $q_1,\dots ,q_N;$ the vehicle departs at $r$ and must finish at $t$ (we will see later that having no fixed initial or final point can be solved equivalently). The mathematical program is then to find the optimal set of stops $x_1,\dots ,x_N:$ (1) $$\underset{\left\{x_1,\dots ,x_N\right\}}{\min }\sum _{i=0}^N{c}_V\left(P_{x_{i,}{x}_{i+1}}^V\right)+\sum _{i=1}^N{c}_W(P_{x_i,q_i}^W)$$(1) where $x_0=q_0=r,x_{N+1}=t,$ and $P_{uv}^k$ is the shortest path between $u$ and $v$ using costs $c_k.$ The first term represents the vehicle costs, whereas the second term represents the walking costs. Note that the sub-optimal solution DET, that visits the exact requested points, can be arbitrarily bad; for instance, if $c_W\equiv 0$ and $r=t,$ then the minimum cost for (1) is 0 (the vehicle does not move at all) and the sub-optimal one is strictly positive.

The formulation of the objective function in Equation (1)(1) $$\underset{\left\{x_1,\dots ,x_N\right\}}{\min }\sum _{i=0}^N{c}_V\left(P_{x_{i,}{x}_{i+1}}^V\right)+\sum _{i=1}^N{c}_W(P_{x_i,q_i}^W)$$(1) entails that we are aiming for a social optimum, as all costs are taken into account. From the stakeholders’ points of view, it is apparent that operators are benefited by requiring some users to walk, because the vehicle needs to tour shorter distances to serve the same number of requests. Users, on the other hand, can be directly benefited with shorter waiting and traveling times, and indirectly benefited because the overall gain in efficiency can induce lower fares.

Equation (1)(1) $$\underset{\left\{x_1,\dots ,x_N\right\}}{\min }\sum _{i=0}^N{c}_V\left(P_{x_{i,}{x}_{i+1}}^V\right)+\sum _{i=1}^N{c}_W(P_{x_i,q_i}^W)$$(1) entails that walking costs grow linearly with the length of the route. However, the problem can be easily generalized to consider other increasing functions $f:{\mathbb{R}}_{+}\to {\mathbb{R}}_{+},$ just by considering ${f(c}_W(P_{x_i,q_i}^W))$ in the second sum. Such functions $f$ allow to include space windows³, as done by Zhao et al. (2018), that can be either strong (by taking $f\left(x\right)=+\infty$ if $x$ exceeds the window) or weak (by taking $f\left(x\right)=x+p,$ with $p$ a penalization, when $x$ exceeds the window). A concave $f$ would represent that the very fact of walking is already disturbing, but once a user is walking the distance becomes less relevant, whereas a convex $f$ can take into account that the user becomes tired while walking.

A polynomial algorithm

Problem (1) can be solved exactly in polynomial time. To see this, let us first consider the metric completion of the graph with respect to both cost functions: on the complete graph $(V,\overline{E}$), we consider cost functions defined by the cost of the shortest path (concerning both $c_V$ and $c_W$) connecting each pair of nodes. To simplify the notation, let us call these costs $c_V$ and $c_W$ as well (they coincide in the arcs $e\in E$ due to the triangular inequalities). If we are considering $f(c_W),$ as discussed in the preceding paragraph, the graph is completed in the same way, and then the resulting costs $c_W$ are replaced by $f(c_W).$ In what follows, we keep the notation $c_W$ because it is simpler.

On this complete graph, we are looking for paths formed by $N+1$ arcs (let us say that it takes $N+1$ “steps”) that start at $r$ and end at $t.$ We define step-evolving costs on the edges as: (2) $$c\left(e=uv,i\right)=c_V\left(e\right)+c_W(v,q_i)\forall i=1,\dots ,N+1$$(2)

The first term in the sum represents the cost associated with the vehicle moving from one stopping point to the next one; the second term is the walking cost faced by the user requesting $q_i.$ Note that if the detour is not optimized, such that vehicles go to the exact origins and destinations, the second term vanishes.

Problem (1) reduces to the following: given any graph $G\prime =\left(V\prime ,E\prime \right),$ a path-evolving cost function $c\prime$ on the arcs, and an integer $k,$ find the less costly path between some origin $r\prime$ and a destination $t\prime$ that takes exactly $k$ steps (or show that no such path exists). (3) $$\underset{P=r^{\mathrm{\text{'}}}{,x}_{1,}\dots x_{k-1},t^{\mathrm{\text{'}}}}{\min }{c}^{\mathrm{\text{'}}}\left(r\mathrm{\text{'}}{x}_1,1\right)+c^{\mathrm{\text{'}}}\left(x_1{x}_2,2\right)+\dots +c^{\mathrm{\text{'}}}\left(x_{k-2}{x}_{k-1},k-1\right)+c\mathrm{\text{'}}(x_{k-1}t\mathrm{\text{'}},k)$$(3)

Before proving that problem (3) can be solved in polynomial time, let us show that (3) can be adapted to solve (1) with free starting or ending node: If the starting point is flexible, we consider an additional auxiliary node $r^{*}\notin V,$ $E^{*}=E\cup \{r^{*}u:u\in V\}$ and (4) $$c\left(r^{\mathrm{*}}u,i\right)=\{\begin{array}{c}0\mathit{\text{if i}}=1\\ +\infty \sim \end{array}$$(4)

It is straightforward to observe that solving (3) with $G^{*}=(V\cup \{r^{*}\},E^{*}),$ cost functions $c,$ $k+1$ steps, and starting point $r^{*}$ is equivalent to solve the original problem with a flexible starting node. An analogous procedure allows (3) to find the optimal path with a flexible ending node, adding an auxiliary node $t^{*},$ arcs $u{t}^{*}$ with nil costs for the last step and infinite costs for any previous step.

We now show that (3) can be solved in polynomial time, adapting well-known algorithms for the case in which costs do not evolve. The algorithm is dynamic, finding the less costly path in $j$ steps iteratively for $j=1,\dots ,k,$ based on the fact that each subpath of a less costly path must be the less costly path for the respective number of steps. It is useful to define (5) $$\mathrm{\gamma }\left(u,j\right)=\underset{P\in {\mathrm{\Gamma }}_{\mathit{uj}}}{\min }c\left(P\right)$$(5) where ${\Gamma }_{uj}$ is the set of all the $r-u$ paths that take $j$ steps. Then, $\forall j\ge 1$ it must be fulfilled that: (6) $$\mathrm{\gamma }\left(v,j\right)=\underset{u:\mathit{uv}\in E^{\mathrm{\text{'}}}}{\min }\left\{\gamma \right(u,j-1)+c(uv,j\left)\right\}$$(6)

With the initial conditions: (7) $$\gamma \left(r,0\right)=0,\text{and}\gamma \left(u,0\right)=+\mathrm{\infty }\mathrm{}\forall u\ne r$$(7)

The algorithm consists in solving (6) for $j=1,\dots ,k,$ and then tracking back iteratively the parent-node at which (6) reaches its minimum from the final node $t.$ The algorithm is polynomial, because, for a given $j,$ (6) can be solved with the following procedure that begins with $\gamma \left(v,j\right)=+\infty \forall u\in V$ and then: (8) $$\forall uv\in E,\text{if}\gamma \left(u,j-1\right)+c\left(uv,j\right)<\gamma \left(v,j\right),\mathrm{}\text{then}:\mathrm{}\gamma \left(v,j\right)\leftarrow \gamma \left(u,j-1\right)+c\left(uv,j\right)$$(8)

That is to say, solving (6) takes $\left|E\right|$ steps for each $j=1,\dots k,$ making the complete algorithm⁴ $O(|E|k).$ Recalling that the original problem (1) requires solving (3) over the metric completion of the graph, then (1) is solvable in $O({\left|V\right|}^{2}N).$ We are not considering the time required to obtain the shortest paths (using Dijkstra’s algorithm or any other), as they can be calculated in a preprocess. We will use OPT to denote the solution given by this algorithm.

As a final remark, it is interesting to compare problem (4) with the so-called shortest path with time-dependent costs (SPTD), studied by Foschini et al. (2014). SPTD deals with finding the shortest path between two points, with cost functions that evolve with time, rather than with the number of steps as in (4). If waiting at the nodes is forbidden, this slight change from step-dependent to time-dependent makes SPTD an NP-Hard problem, although some specific variants are polynomial or quasi-polynomial.

A heuristic approach

Despite the polynomial nature of the optimal algorithm studied in “A polynomial algorithm,” it might be the case that it is still too slow to be used in online on-demand tools, that need to run their algorithms with tiny time windows (Alonso-Mora et al., 2017, for instance, do it each 30 seconds). We now propose a heuristic that diminishes the required running time.

Problem (1) is about solving the tradeoff between providing short access/egress times and routing the vehicles without large deviations. Intuitively, one could expect that routes are adjusted such that vehicles stop at points that put them on track toward the very next request, overlooking at the following ones. This idea exalts the relevance of studying its competitive ratio.

Some results on the competitive ratio

Consider a mathematical problem in which the inputs are not all known in advance, but are revealed during the execution of any solution for the problem (i.e., an online problem). One can naturally ask how damaging is this lack of information. To analyze this, researchers have defined the competitive ratio of the problem as the quotient between the best solution achievable by an algorithm that look only at the available partial information, and the overall optimum with complete information in advance (Borodin, 1992; Sleator & Tarjan, 1983). In our case, however, vehicles can be carrying $k_0>1$ passengers, such that any algorithm should know at least $k_0$ requests -their drop offs- in advance when operating (which we define as future memory equal or larger than $k_0$). The competitive ratio of a specific algorithm (with limited future memory) is the quotient between its result and the overall optimal.

Consider the following $k$-algorithm (with future memory equal to $k+1$): beginning at the starting node, apply the optimal algorithm to the route formed by the following $k+1$ requests and go to the first stop given by the obtained solution; when arriving there, reboot the algorithm with this starting point and iterate. When there are fewer than $k+1$ remaining points, apply the optimal algorithm to all of them. This algorithm is not necessarily the best one with future memory equal to $k+1,$ but it is quite an intuitive one. The following proposition shows that the worst case for the $k$-algorithm can be unboundedly bad.

Proposition.

Let $J\in \mathbb{N}$. There exists an instance of Problem 1 such that the $k$-algorithm reaches a competitive ratio larger than $J.$

Proof.

In Appendix A.

It is worth remarking that we have studied the competitive ratio for a particular algorithm. If $k=1$ (i.e., when the system only knows one request at a time) our model is trivially a particular case of the so-called metrical task systems, such that any deterministic online algorithm will have a competitive ratio no lower than $2\left|V\right|-1$ (Borodin et al., 1992).

The heuristic

The example shown in the previous section rests on a particular network topology: the graphs induced by the vehicle arcs have a connectivity degree equal to 1, which is not likely to be the case in real transport networks. This suggests that, after all, a heuristic of limited future memory could work well. Let us define the function $c_T(u,v)$ as the minimum cost if the vehicle is in $u$ and it has only one request from $v,$ i.e., (12) $$c_T\left(u,v\right)=\underset{x\in V}{\min }{[c}_V\left(u,x\right)+c_W(x,v)]$$(12)

Recalling that we aim to reduce the computational time, this definition of $c_T$ is not very helpful, as it requires calculating $c_V\left(u,x\right)+c_W(x,v)$ for each node $x.$ Instead, we use $c_T\prime ,$ which results by solving (12) approximately using a local search -a discrete version of the gradient method:

Calculation of $c_T\mathrm{\text{'}}(u,v)$

Initialize $x=v,\mathrm{}{c}_T^{\mathrm{\text{'}}}\left(u,v\right)=c_w(u,v)$

While true

Define $A_x=\{y\in V:xy\in E$ or $yx\in E$} (Nodes that are walking-incident in x).

Define $x_0=\mathrm{argmi}{\mathrm{n}}_{\mathrm{y}\in {\mathrm{A}}_{\mathrm{x}}}{c}_V\left(u,y\right)+c_W(y,v)$

If $c_V\left(u,x_0\right)+c_W\left(x_0,v\right)\ge c_V\left(u,x\right)+c_W\left(x,v\right)$

 Break

Else

 $x\leftarrow x_0,\mathrm{}{c}_T^{\mathrm{\text{'}}}\left(u,v\right)\leftarrow c_V\left(u,x\right)+c_W\left(x,v\right)$

End

End

That is to say, look at all the nodes that are walking-incident in $x,$ and select the one the diminishes the cost the most; iterate until the cost is no longer reduced (a local minimum has been reached).

The heuristic we describe now has future memory equal to two. Consecutively, it solves (1) considering only the current position of the vehicle and the following two requests; the first stopping of this partial solution (associated to the following request) is added to the heuristic route, and it becomes the new current position of the vehicle. This would be the 1-algorithm, but we perform a local search in order to reduce the required computational time. It is useful then to define $v\left(q_0,q_1,q_2\right)$ as the first stop when using the 1-algorithm: (13) $$v\left(q_0,q_1,q_2\right)={\mathrm{argmin}}_{x\in V\mathrm{}}{c}_V\left(q_0,x\right)+c_W\left(x,q_1\right)+c_T(x,q_2)$$(13)

Also, define $v\prime$ as the solution to (13), but considering $c_T\prime$ (instead of $c_T$) in the objective function, and finding the argmin through a local search analogous to the one used to calculate $c_T\prime .$ In the worst case, finding $v\prime$ requires looking at all nodes in this local search, and when looking at each node, searching again in all the graph to calculate $c_T\prime .$ That is to say, equation (13)(13) $$v\left(q_0,q_1,q_2\right)={\mathrm{argmin}}_{x\in V\mathrm{}}{c}_V\left(q_0,x\right)+c_W\left(x,q_1\right)+c_T(x,q_2)$$(13) might require at most ${\left|V\right|}^2$ steps, but the local searches will rarely take that long. The whole heuristic can be described as:

Heuristic

Initialize: $y_0=r,\mathrm{}{y}_1=q_1,y_2=q_2,$ $\mathit{Route}=r,i=1$

While true

$x=v\mathrm{\text{'}}(y_0,y_1,y_2)$

If $i=N,$ break

Else $\mathit{Route}\leftarrow \left(\mathit{Route},x\right),\mathrm{}{y}_0\leftarrow x,y_1\leftarrow q_{i+1},y_2\leftarrow q_{i+2},i\leftarrow i+1$

End while

$$\mathit{Route}\leftarrow \left(\mathit{Route},t\right)$$

That is to say, once the heuristic has a built a path $r{x}_1\dots x_k,$ it defines it next stop looking at the problem that has $x_k$ as a root and only one request $q_{k+1}$ and that must stop at $q_{k+2}.$ In order to select its single stop (related to $q_{k+1}$), it performs a local search around $q_{k+1}.$

If the in-degree of the nodes is small (as it is usual in real transport networks), and if the local searches end in nodes that are close to $x_1$ (which is also expectable), then the heuristic should run fast. The required time has to be multiplied by the number of requests if we are calculating the whole route; nevertheless, in an online on-demand system (the scheme that might require heuristics) it is not necessary to know the complete route in advance, because most of the times the algorithm will be rerun before reaching the next stop, i.e., obtaining one stop at a time is enough.

Scalability when dealing with a fleet of vehicles

The three methods considered in this paper DET (visit the exact requests without avoiding detours), OPT (the optimal algorithm) and HEU (the heuristic explained in 2.2.2), deal only with the route of a single vehicle. However, ridesharing systems should be able to handle fleets of thousands of vehicles simultaneously. Therefore, it is crucial to study what happens with computational times when there is a fleet of vehicles, which can be managed in two different ways:

1. One might aim to optimize the routes of every vehicle together with how to assign them to the requests, assuming that they might walk. This problem is very complex (it extends dial-a-ride, for instance), and proposing practical ways to solve it is the scope of the papers by Fielbaum et al. (2021), Stiglic et al. (2015), and Li et al. (2018). As discussed in the introduction, the complexity of this approach hinders the chance of obtaining theoretical insights, and the procedures discussed above are not useless in this case as they assume a fixed set and order of requests.

2. In order to use the methods studied in this paper, one should assume that each vehicle has a sequence of requests to serve (computed with some other technique), and then the said methods can be applied to each vehicle independently. If there are $\mu$ vehicles, then the required computational steps to determine the routes for all them is $\mu$ times the steps required for a single vehicle, i.e., the complexity is linear on the number of vehicles and the algorithms remain polynomial. Moreover, as the vehicles’ path are independent from each other, the calculations can be easily parallelized (for instance, each vehicle could have an own computer, yielding a complexity that is constant regardless the number of vehicles).

Numerical simulations

In order to compare the results given by DET (visit the exact requests without avoiding detours), OPT (the optimal algorithm) and HEU (the heuristic explained in 2.2.2), we are going to test them under two different schemes. First, we run them in random graphs: we know that OPT can be arbitrarily better than DET and HEU, but this requires ad hoc graphs, so we aim to analyze what happens on average. Second, we propose a specific transport network and study in detail the routes that emerge when applying each of the algorithms, in order to gain intuition concerning the different paths yielded by them. In addition, we compare the times needed by each algorithm in a real-sized network.

Comparison of the algorithms over random graphs

We applied the three algorithms to 100 graphs, each formed by 50 nodes and considering a random vector of 10 requests. For each pair $u,v$ of nodes, the probabilities that the directed arc $uv$ exists for both vehicles and walking, only for walking or does not exist at all are 0.5, 0.1 and 0.4, respectively. Including some pedestrian arcs is useful to enlighten the role played by the chance of walking, by making DET comparatively worse-off. Both $c_W$ and $c_V$ take random integer values between 1,…, 10 [u$] at each (existing) arc, with [u$] an artificial cost unit.

Results are synthesized in Figures 3 and 4 and Tables 1 and 2. Figure 3 shows the total costs of the three algorithms for each of the random graphs, which were sorted (in the abscissa) according to the DET’s costs. The analysis of this Figure verifies that the optimal algorithm always yields the best results, but it also reveals a remarkable result: the heuristic always outperforms the results obtained when visiting the exact requests, despite its limited memory.

Figure 3. Total costs of the three algorithms over 100 random graphs. The graphs are ordered in the x-axis according to the cost of the DET algorithm.

Figure 4. Decomposition of vehicle and walking costs for (a) the optimal algorithm and (b) the heuristic, when applied over 100 random graphs, which are ordered in the x-axis according to the cost of the DET algorithm.

Table 1. Comparison of the three algorithms.

	Mean	Max	Min
OPT/DET	0.62	0.84	0.42
HEU/DET	0.75	1	0.54
HEU/OPT	1.2	1.6	1

Each row deals with the ratio (dimensionless) between the costs of two of the algorithms, showing their means, maximum and minimum values, when they are applied over 100 random graphs.

Table 2. Ratios (dimensionless) between walking and vehicle costs for HEU and OPT.

Ratio $c_V/c_W$	Mean	Max	Min
HEU	3.03	27	0.17
OPT	0.72	2.7	0.056

Table 1 reveals the mean, maximum, and minimum values reached by the vectors that contain the quotients between the costs of the respective pairs of algorithms. The first row shows that OPT saves more than a third of total costs on average, and can save more than half: reducing detours via requesting users to walk can be a crucial way to improve ridesharing systems. Regarding HEU, its performance depends heavily on the graph, as it can be as good as OPT or as bad as DET.

Figure 4 looks deeper into the performances of OPT (Figure 4a) and HEU (Figure 4b), by decomposing their costs in vehicle costs and walking costs. As apparent, in most instances vehicle costs exceed walking costs for HEU (black columns are taller than gray columns), whereas the contrary occurs for OPT, which can be interpreted by analyzing the two main characteristics that make HEU a heuristic:

1. Recalling that when HEU searches for the stop associated to a request $q_i,$ it minimizes $c_T^{\prime }$ instead of $c_T.$ The difference between both is that $c_T^{\prime }$ is computed through a local search starting from $q_i$ itself, which is likely to find nodes that are close to that starting point. That is to say, HEU prioritizes stops at short distance of the exact requests, which obviously reduces walking times but fails to optimize the vehicle’s time.

2. The limited future memory of HEU implies that the route it chooses does not take into account future requests in a perfect way, so when solving the tradeoff between walking time for a current user and vehicle’s time for all the future ones, the latter is underestimated and the tradeoff is inclined toward reducing walking.

Table 2 synthesizes this information and confirms that both methods present quite different costs’ decomposition. OPT is much more stable, as the ratio between vehicle’s and walking costs do not change as much as in HEU.

Comparison of the algorithms over a simplified transport network

To mimic the context in which these algorithms are required, we now create a simple on-demand transport network and study the solutions that emerge when they are applied. We consider a 10 × 10 grid, in which there are three types of street: slow (20 km/h), mid-speed (30 km/h) and fast (40 km/h). Slow and fast streets are bidirectional, unlike mid-speed ones which are one-way. The vehicle departs from one extreme of the grid and needs to serve ten random requests $s_1,\dots ,s_{10}.$

To simulate the fact that the systems get updated when new requests arrive, we will assume that at every point the vehicle only knows in advance the following four requests (or all the remaining requests, when they are fewer than four). Algorithms are modified as follows to account for this incomplete information:

• DET always goes to the closest request within the following 4. For a proper comparison, the resulting route $R=q_1,\dots ,q_{10}$ (which is a permutation of the original requests vector) is the input for the other two algorithms.

• OPT is repeatedly applied over the following 4 nodes in $R,$ and the first resulting stop provides the subsequent stop of the vehicle. Note that the vehicle does not follow this output further, as the algorithm is going to be applied again when reaching that stop.

• HEU does not need to be modified, as its future memory is lower than 4.

Table 3 shows arcs’ costs, whose calculations are explained in Appendix B. Figure 5 show the network (Figure 5a) and requests (Figure 5b). The width and color of the edges represent the type of street: red (slow), gray (mid-speed) and brown (fast). Arrows show if streets are one-way or two-ways. In Figure 5b, the red node represents the starting point of the vehicle, and the green nodes the requests $s_1,\dots ,s_{10}.$

Figure 5. The network (a) and the requests (b). Red arcs are slow, gray are mid-speed and brown are fast. Green nodes represent the requests, and the red node is the starting place.

Table 3. Costs of arcs in the transport network example.

Type of arc	Slow	Mid-speed	Fast
$c_V$ [US$]	0.394	0.262	0.197
$c_W$ [US$]	0.261	0.261	0.261

Figures 6 show the route generated by each of the algorithms: DET (Figure 6a), OPT (Figure 6b), and HEU (Figure 6c). To prevent curves from overlapping, routes’ figures are divided into two halves (before and after visiting the 5th stop). Note that all three algorithms stop in the exact fifth request, such that we can compare each half separately. Requests are shown in green and stops in purple; when they coincide in OPT or HEU, we use light blue.

Figure 6. Emerging routes when applying DET (a), OPT (b), and HEU (c).

The first half of the trips (left column in Figure 6) is quite illustrative of the different solutions provided by these algorithms. DET requires using all kinds of streets, including the slow ones. The opposite happens with OPT, which uses almost only fast streets; the only exception occurs at the beginning of the route because the initial node does not have incident fast streets. Moreover, it reduces the number of arcs toured by avoiding the detour between the first and second requests. HEU’s outcome is some intermediate solution: it makes a detour between the first and second requests, but this detour is smaller than DET’s one. After the second stop, it imitates the same path followed by DET, including another detour that prevents passengers of the third and fourth requests from walking; OPT avoids this detour.

The second half of the trips (right column in Figure 6) shows exact coincidence between OPT and HEU: their path uses one mid-speed street, which is justified because there are four requests located over that street; afterward, they only use fast streets. DET adds two detours, to visit the eighth and ninth requests, which forces the route to use two slow arcs.

As a synthesis, Figure 6 show that OPT operates very differently from DET, taking advantage of the flexibility induced by the chance of walking, which creates shorter routes by using fewer and faster arcs. HEU sometimes behaves as DET (when going from the second to the fifth requests), sometimes as OPT (after the fifth request) and sometimes as an intermediate solution (before the second request). Table 4 shows the cost of each algorithm. Although OPT is better than HEU, the difference between the latter and DET is even larger, showing that using HEU is a sound strategy over transport networks. More than one quarter of in-vehicle costs can be saved when long detours are avoided with either HEU or OPT. Moreover, HEU took 0.0093 [sec] and OPT required 0.24 [sec]. There is a huge improvement in running times at a little cost.

Table 4. Walking and in-vehicle costs per method over the simplified transport network.

Algorithm	DET	OPT	HEU
Total cost [US$]	11.61	9.3	9.83
Walking cost [US$]	0	2.09	1.04
In-vehicle cost [US$]	11.61	7.21	8.70

These results are robust. If we repeat the same experiment 100 times, HEU is on average 19% less costly than DET, and only 5% costlier than OPT. As a final remark, we also analyzed what happens if OPT is calculated knowing the whole ten requests in advance (rather than only four). In the example explained in this section, the result does not change, and the same happens 84 times in 100 repetitions of the experiment, while in the most extreme case only 2.6% of the costs are saved: there is no need of long future memory when working over transport networks.

Comparison of the algorithms over a real-life case

In “Comparison of the algorithms over a simplified transport network,” we showed that running OPT could take 24 times more than HEU; nevertheless, as they were applied over a small example, both procedures required reasonable times. What happens if we make a similar comparison over a large real-life network? And how would total costs compare?

To answer this question, we test the algorithms over a graph that represents Manhattan, in which each edges are the real streets and nodes are corners or dead-ends. This graph contains 4,092 nodes and 9,451 edges, and it has been used previously by Alonso-Mora et al. (2017) and by Fielbaum et al. (2021) to test ridesharing algorithms. Walking times are proportional to the distance, while vehicle times are considered as twice the real ones, to account for users traveling in the vehicle or waiting for it. We compute 50 rides of a vehicle that starts in a random node and receives four random requests.

As shown in Figure 7, conclusions with respect to costs are similar to was stated in “Comparison of the algorithms over a simplified transport network,” whereas the differences regarding computational times are much higher. Let us explain and discuss these results further:

Figure 7. Comparison of the results obtained by OPT and HEU when solving random instances over Manhattan, (a) Ratio between total costs, and (b) Ratio between computational times. In both cases OPT is in the numerator and HEU in the denominator. Both figures are sorted in increasing order.

• When HEU is executed, the controller of the system needs to execute just one step at a time, because the next step can be calculated after the vehicle has already moved (which is an advantage of using limited memory). Therefore, computational times are computed just considering one step, and they lay in the range of milliseconds, i.e., they do not increase with the scale of the network, which is a consequence of performing local searches.

• On the other hand, the complexity of OPT is proportional to ${\left|V\right|}^2,$ as discussed in “A polynomial algorithm,” which yields computational times that lay in the range of a few seconds. Although Figure 7b) reveals that the comparison between methods can change dramatically, the difference is always of some orders of magnitude, i.e., HEU is much faster than OPT when solving real-life instances.

• Figure 7a) reveals contradictory situations. It is true that in most instances, HEU increases costs in less than 5%, reaching the optimal solution in some occasions. However, there might be specific conditions that extends the difference among the two methods to almost 20%.

• Taking everything into account, it is better to use OPT when possible, but HEU provides a good alternative when OPT is too slow, which depends largely on the computational power. For instance, Alonso-Mora et al. (2017) decide which requests assign to each vehicle each 30 [sec]. For a single vehicle, it might be possible to spend some seconds to determine its exact route; however, when thousands of vehicles are managed simultaneously, this is no longer possible and HEU should be chosen, unless there is plenty of computational power (for instance, each vehicle could compute its own route independently).

Conclusions and future research

In this paper, we have studied the problem of finding the optimal route of a shared vehicle, assuming that users can walk from their origins to (or to their destinations from) a different node where they meet (leave) the vehicle. Considering an exogenous order in which to fulfill the requests, we have shown that this is a polynomial problem, providing the respective algorithm.

In order to further reduce the required computational time, we proposed a heuristic with limited future memory. We compared these two algorithms and the one that visits the exact requests, by applying them over random graphs, a simplified transport network and a real-life case, showing that shortening the detours (with the optimal algorithm or with the heuristic) improves the results.

As we provide two suitable algorithms (the optimal one and the heuristic), it is worth discussing in detail the comparison among them. The heuristic can run hundreds of times faster when solving real-life instances. However, it can increase the costs up to 20%, a difference that may justify the extra time if this is compatible with operating the vehicles. How to solve this tradeoff will depend on the specific characteristics of the mobility system. Moreover, some intermediate solutions might be built by extending the so-called future memory of the heuristic. Any extension should keep the local searches utilized by the heuristic studied here, to prevent looking (repeatedly) at all the nodes in the graph.

From a practical point of view, we can identify at least two situations in which it is possible to utilize the optimal algorithm, that requires a few seconds to optimize the route of each vehicle. First, if the problem is not solved online but in advance (for instance, the night before executing the trips); in this case, optimizing the routes of thousands of vehicles would be feasible, as the process would require some hours. Second, if the routes can be computed in a distributed fashion, e.g., if each vehicle carries its own computer, so that only some seconds are required; the fact that the route of each vehicle can be computed independently is a virtue of both algorithms. On the other hand, if the calculations are centrally computed and the system works online, then the optimal algorithm is too slow and the heuristic is required.

We have shown that there might be very significant savings when optimizing the route instead of following a door-to-door scheme. The large magnitude of these savings is crucial, because it implies that it is possible to distribute such savings in a way that all the involved agents end up in a better situation. In other words: one of the central conclusions of this paper is that requiring some users to walk can be beneficial to everybody and help making these emerging mobility systems to succeed. Moreover, avoiding detours can be a strategic decision when expanding on-demand systems in order to make them part of the public transport network (as studied by Hrnčíř et al. (2015) and Mounce et al. (2018)), when improving the so-called MaaS systems (Hensher, 2017), and for carpooling systems in which different private users share the vehicle of one of them (Li et al., 2020; Tamannaei & Irandoost, 2019). It is worth recalling that the results and methods proposed here can be applied to any of the ridesharing systems that have emerged recently in the literature.

There are several promising avenues to pursue in future research. When analyzing the competitive ratio of this problem, the degree of connectivity of the graph seemed to be critical; transport networks are usually very well connected, as there are many different paths for each origin-destination pair: is it possible to obtain more promising results regarding the competitive ratio if more hypotheses with respect to the topology of the graph are assumed? Including some constraints on the walking times, as well as the chance that some users might be late (Hyland & Mahmassani, 2020; Kucharski et al., 2020), could make a more realistic model.

Acknowledgments

The author wishes to thank Víctor Verdugo and Gonzalo Muñoz, both from Universidad de O’Higgins, for their valuable comments that helped to improve this paper.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Notes

1 Some authors define “sharing” as different users riding the same vehicle but at different times. This difference has significant impacts over the whole transport systems: Santi et al. (2014), for instance, show that sharing taxis in New York would reduce the vehicles-kilometer traveled by this mode in about 40%.

2 There are a few real-life shared systems in which passengers are requested to walk. Uber Express Pool is already working in some American cities, although it requires that all users are gathered in the same meeting point. Many airports (Sidney, Melbourne and Madrid are some examples) have created specific spots where a passenger has to walk to meet his/her (possibly non-shared) cab. These examples, however, are very incipient, and the underlying optimization processes do not always pursue social optimum criteria.

3 As the order of the requests is fixed, the times in which requests are visited cannot change much, which is why space windows are more significant than the more traditional time windows in this scheme.

4 Classical Dijkstra’s algorithm could also be used, over a modified graph that contains the root and copies of each vertex. If is an arc in the original graph, then is an arc in the modified graph, with cost . The complexity of original Dijkstra is , that would become , which is worse than the algorithm described in the main text.

5 Moreover, papers that do model these systems usually obtain numerical results rather than analytical expressions (as Alonso-Mora et al., 2017; Fagnant & Kockelman, 2018; Martinez & Crist, 2016).

6 This assumes that vehicles arrive at constant headways; otherwise, a larger number replaces the ½.

Appendix A:

Proof of the proposition in “Some results on the competitive ratio”

Without loss of generality, we assume that$k\le J.$ Define a graph $G=(V,E),$ with $V=\left\{r\right\}\cup V_0\cup \dots \cup V_J.$ Let $D$ be a large number (eventually, we will make $D\to \infty$) and let $\epsilon \le \raisebox{1ex}{$1$}\!\left/ \!\raisebox{-1ex}{$D^2$}\right..$ Each set $V_i$ contains $D+i$ nodes $V_i=\{v_{i,1},\dots ,v_{i,D+i}\}$ which form a vehicle path (let us call it a “highway”), i.e., $e=v_{i,j}{v}_{i,j+1}\in E,$ with $c_V\left(e\right)=1,c_W\left(e\right)=+\infty .$ There are arcs between the respective nodes of consecutive paths, representing very short pedestrian bridges, i.e., $e=v_{i,j}{v}_{i+1,j}\in E,$ with $c_V\left(e\right)=+\infty ,c_W\left(e\right)=\epsilon .$ The vehicle starts at the root $r,$ and the requests vector is $(v_{0,1},v_{0,2},\dots ,v_{0,D},v_{1,D+1},v_{2,D+2},\dots ,v_{J-1,D+J-1},v_{J,D+J}).$ Figure A1 shows this network, with the requests in solid blue.

Figure A1. Network and requests that yield a competitive ratio larger than $\mathit{J}.$

If $\epsilon$ is small enough, the optimal route is taking the $J$-th highway, because it needs to be taken at some moment to reach the final request, and walking costs are negligible. This yields: (9) $$c_{\mathit{OPT}}\left(D\right)=(D+J)+DJ\epsilon +\epsilon +2\epsilon +\dots +\left(J-1\right)\epsilon$$(9)

The first term in (9) are vehicle’s costs, the second term represents the first $D$ requests (the cost of walking toward the first highway), and the following terms come from the other requests’ walking costs. Note that only the first term will be relevant when making $D\to +\infty .$

What happens with the $k$-algorithm? At the beginning, it only looks at requests that are located over the first highway, so it is going to take it. When reaching the $D-k$ th request, node $v_{1,D+1}$ enters the requests vector, which cannot be reached walking from the first highway, forcing the vehicle to go back to the root and to take the second highway. The same happens repeatedly afterward, making the vehicle tour completely all the highways from the second to the last one, yielding: (10) $$c_k\left(D\right)=2\left(D-k\right)+\sum _{i=1}^k\left[2\right(D-k+i)+i\epsilon ]+\sum _{i=1}^{J-k}\left[2\left(D+i\right)+k\epsilon \right]+\left[D+J+\epsilon +2\epsilon +\dots +\left(k-1\right)\epsilon \right]$$(10)

The first term in (10) is induced by going from the root to $v_{0,D-k}$ and back. The second term appears when visiting the next $k$ stops (whose passengers need to walk to the first highway). The third term represents visiting all the next highways but the last one, whose stops are $k$ bridges away from the respective exact requests. The last term is caused by touring the last highway, responding to $k$ requests on the way. Rearranging: (11) $$c_k\left(D\right)=3D+2JD+f(J,k,\epsilon )$$(11) where $f(J,k,\epsilon )$ is a term that does not depend on $D$ and in which $\epsilon$ appears only multiplying some terms, such that it is irrelevant when $D\to +\infty .$ It is apparent then that $\underset{D\to +\infty }{\mathit{lim}}\frac{c_k(D)}{c_{\mathit{OPT}}(D)}=3+2J>J,$ which proves the proposition.

Appendix B:

Arc’s costs in “Comparison of the algorithms over a simplified transport network”

To calculate the vehicle and walking costs, we follow the guidelines of ridesharing transport systems, but without using a detailed model, such that $c_V$ is the sum of operators’ and users’ costs, while $c_W$ depends only on users. Let us denote $d_0$ the (homogenous) length of the arcs.

• Explicit expressions for operators’ costs would require a detailed model for an on-demand system, which is beyond the scope of this paper. Instead, we take as reference the well-known expression for a single line in a traditional public transport system $c_O=B(c_0+c_{1}K)$ (Jansson, 1980; Jara-Díaz & Gschwender, 2009), in which $B$ is the fleet size, $K$ is the capacity of the vehicles (which is fixed in this system), and $c_0$ and $c_1$ are exogenous parameters. In that model, the fleet size is given by $B=\frac{1}{2t_w}{t}_c,$ where $t_w$ is the average users’ waiting time and $t_c$ is the cycle time. Using the arc $e$ increases cycle time by an amount that depends on the vehicle’s speed in that arc $v_e.$ Using some exogenous value $t_{w0}$ for the average waiting time yields: (A1) $$c_{Oe}=\frac{1}{2t_{w0}}\frac{d_0}{v_e}(c_0+c_{1}K)$$(A1)

• Users’ costs increase due to the delay on their arrival times, by an amount that depends on the arc’s speed. If $p_V$ is the monetary value of one unit of time, and considering an average of 4 users assigned to each vehicle yields: (A2) $$c_{Ue}={4p}_V\frac{d_0}{v_e}$$(A2)

• Walking costs depend on the walking speed $v_W$ and on the value of one unit of time walking $p_W.$ Then every arc has the same walking cost: (A3) $$c_W=\frac{d_0}{v_W}{p}_W$$(A3)

The numeric value of the parameters is shown in Appendix C.

Appendix C:

Numeric value of the parameters

When needed, costs are taken from Fielbaum (2020).

Table A1. Numeric value of the parameters.

Parameter	Meaning	Value
$c_0$	Fixed cost per vehicle	4.02 [US$]
$c_1$	Variable cost per vehicle	0.29 [US$]
$K$	Number of seats in each vehicle	4
$d_0$	Length of each arc	150 [m]
$t_{w0}$	Average waiting time	3 [min]
$p_v$	Value of one unit of time traveling	2.32 [US$/h]
$v_w$	Walking speed	4 [km/h]
$p_w$	Value of one unit of time walking	6.96 [US$/h]