# An Iterative Algorithm for the Management of an Electric Car-Rental Service

Authors: J. Alberto Conejero; Cristina Jordán; Esther Sanabria-Codesal
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

The management of a car-rental service becomes more complex as long as one-way bookings between different depots are accepted. These bookings can increase the operational costs due to the necessity of moving vehicles from one depot to another by the company staff in order to attend previously accepted bookings. We present an iterative model based on flows on networks for the acceptance of bookings by a car-rental service that permits one-way reservations. Our model lets us also recover the movement of the fleet of vehicles between the depots over the time. In addition, it also permits including restrictions on the amount of cars managed at every single depot. These results can be of interest for an electric car-rental service that operates at different depots within a city or region.


---

## Body

## 1. Introduction

Car rentals can admit bookings where the pick-up and drop-off location can coincide or not. If bookings are only admitted when both locations coincide, their management is not as complicated as if bookings are only accepted when the locations are different (one-way bookings). When this happens, these companies face much more difficulties in order to cope with the management of their fleet of vehicles, since these bookings could entail a huge increment of operational costs due to deadhead times. Nevertheless, in order to offer a high level of service thier policy is to accept bookings without a deep examination of its consequences on the operational costs [1].The use of fully electric vehicles (FEV) is fostered by government authorities in order to contribute to the lowering of the current pollution levels [2]. This comes jointly with a gradual phasing out of conventionally-fuelled vehicles from the urban environment [3]. Some references concerning the adoption of these new transportation devices can also be found in [4, 5].The easiest way to implement a rental service of electric vehicles is to make the users return them at the place where the cars have been picked off. This is done in order to be sure that every car has its own parking place with a charging point. Therefore, an improvement in the process of acceptance of bookings that consider one-way trips between different stations and try to avoid, as far as possible, the amount of staff dedicated to the rearrangement of vehicles between the depots is of particular interest in order to facilitate and extend their use among the potential users. Therefore, a social benefit is obtained as long as the number of reservations of these shared vehicles is increased and the number of private cars running is reduced.Flows and networks were firstly used in the air industry for solving fleet routing problems, see for instance [6–9]. The problems that can be solved using them range from schedule design, flight assignment [10], and crew scheduling [11] to scheduling of air cargo alliances [12]. Their techniques have been also considered in the management of car-rental services in order to answer questions of strategic and tactical decisions, revenue and capacity management, and pricing, see for instance [1, 13–15].We suppose that a simulation of bookings for a car-rental service is given. We model the process of acceptance/rejection of those petitions. This depends on having a car available at the departure point (without leaving unattended any other previously scheduled booking from that place) and on having an empty parking space at the arrival destination. We assume that an answer should be given as fast as possible to the client. Therefore, we will answer each petition before considering the next one. We do not consider the case that a rejected booking can turn to be admissible after some other booking has been accepted. As we said before, the general practice in the car-rental industry is to accept bookings and later to optimize the management of the fleet of vehicles.The car-rental services considered in the frame of this paper are managed with a little different policy. We assume that one of these services does not need to compete with other services and it is just an optional element inside the mobility network of an urban area, where other means of transport are offered to the citizens. Therefore, if a booking should be rejected because of the lack of available cars or empty parking slots, then we reject it since we consider that this will have a low impact on the service perception of prospective users, as long as other means of transport can be used. In this way we determine which bookings should be admitted without falling on deadhead times due to the rearrangement of cars by the car-rental service staff.The paper is organized as follows. In Section2 we introduce some basics of graph theory about flows and networks. We also present time-expanded networks. Our model for managing the bookings using a network is presented in Section 3. Section 4 is devoted to explain the theoretical background that backs our computational method. A first algorithmic approach based on Ford-Fulkerson algorithm is presented in Section 5. We will see that the problem that arises can be stated in terms of finding an admissible flow on a network with minimum capacities at certain edges. Later, an iterative method based on a simplification of the auxiliary network defined for considering the admissibility of the flow will be given in Section 6. This method lays on a solution of certain shortest path problem. An analysis of the results is reported in Section 7. Finally in Section 8 we discuss the contribution of the model to the management of a service in order to offer a cheaper rental service, which will contribute to extend its use for the movements within an urban area. Our algorithm helps to determine if it is advisable to increase the fleet of vehicles or the size of the parking at a certain depot, attending to the increments of cost and to the number of additional bookings accepted.


## 2. Preliminaries

Adirected graphG=(V,E) is given by a set of nodes V and a set of ordered pairs of nodes (arcs). If an arc connects the node u with the node v, we will simply denote it by (u,v). We recall that a 5-tuple N=(V,E,s,t,c) is namednetwork if it is a directed weakly connected graph where V is the set of nodes, E is the set of arcs, s is a node with outgoing degree positive (at least one edge departs from it) usually calledsource, t is a node with ingoing degree positive (at least one edge arrives to it) usually calledsink, and c is a function from E to N that assigns to every edge (u,v)∈E a value c(u,v) that will represent the maximum capacity permitted on this edge. Given a network N, we can consider flows on them. Aflowf is a function f:E→N such that f(u,v)≤c(u,v) for every (u,v)∈E, and for every v∈V∖{s,t} the sum of the values of the flow on the edges with v as initial node coincides with the sum of the flows on the edges with v as final node; that is,
(1)∑u∈V,(u,v)∈E‍f(u,v)=∑u∈V,(v,u)∈E‍f(v,u).Condition (1) is usually known as theconservation law of the flow. The value of the flow f on N, f(N), is defined as the sum of the flows on the adjacent arcs to s (or to t):
(2)f(N)=∑u∈V,(s,u)∈E‍f(s,u)=∑u∈V,(u,t)∈E‍f(u,t).A flowf on N is said to bemaximum if it has the maximum value among all possible flows that can be defined on N. We refer the reader to [16–24] for general information on flows and networks and graph theory.In particular, we are going to considertime-expanded networks, also calledtime-space networks [18, 25]. In these networks, the inner nodes of the network (not the sink nor the source) represent locations at certain times. The source is connected with all locations at the initial time and all locations at the final time are connected with the sink. This is also the structure used for dealing with problems in which the flow emerges from several sources and leaves at several sinks.Now, we transform this network into a one time-expanded network in which we reply cities as many times as time periods we are going to consider, see Figure1. Nodes in each column represent the same city and each level represents the same time period for different cities.Figure 1
A time-expanded network withn depots at m times. Arcs in green represent bookings of cars and arcs in black represent staying at the parking of each depot.In this model we also consider another value associated with each arc named itsminimum capacity. The minimum capacity is a function m:E→N. The flow through every edge (u,v)∈E must verify m(u,v)≤f(u,v)≤c(u,v). We denote a network N with minimum capacities as N=(V,E,s,t,m,c), where V is the set of nodes, E the set of edges, s the source, t the sink, and m,c the minimum and maximum capacities, respectively. Networks with maximum and minimum capacities cannot always admit a flow that respects the upper and lower bounds. It is compulsory that, for every node v∈V, the sum of the maximum capacities of all the edges that arrive to v was greater than or equal to the sum of the minimum capacities of all the edges that depart from it. Consider
(3)∑u∈V,(v,u)∈E‍m(v,u)≤∑u∈V,(u,v)∈E‍c(u,v).If not, the conservation law never holds.In the next section, we proceed to explain in detail the steps that let us construct a model for deciding whether to accept or reject a booking attending to the distribution of cars at the departure depot and the existence of empty parking places at the arrival one.


## 3. A Car-Rental Booking Model

Suppose that our car-rental service operates with only one type of car. Letn be the number of locations (depots) and assume that depot i starts with a given number of cars ki. Let k0 be the total number of cars of the company; that is, k0=∑i=1n‍ki. In addition, we suppose that depot i has pi parking slots at its location to park the cars that are not used by any client and are recharging and waiting to be reserved. We assume that this number cannot be increased along the time.We also consider the bookings alongm consecutive days, h possible times a day. Then the sequence {tj:1≤j≤hm} represents all the possible time periods. For instance, if we consider the times 9:00, 10:00,…, 20:00 then h=12. So that vi,12(a-1)+b, for some 1≤a≤m and 1≤b≤12, represents (8+b):00 a.m. of the day a at the location i.The set of nodesV will consist of s,t (the source and the sink) and all the possible combinations of locations and times {vi,j:1≤i≤n;1≤j≤hm} where vi,j represents the location i at time tj.The setE is formed by four types of arcs. The first three are the following ones.(i)
(s,vi,1), 1≤i≤n, that connect the source with the depots at the first instant of time.(ii)
(vi,j,vi,j+1), 1≤i≤n, 1≤j≤hm-1, that represent staying at a parking between two consecutive times.(iii)
(vi,hm,t), 1≤i≤n, that connect the depots at the last time to the sink.Our objective is to know if we can accept a booking ofw cars between two determined depots at two different time moments under the restrictions of having enough vehicles at the departure depot and free space at the arrival one. We define a booking by a 5-tuple r=(ip,tp,id,td,w), where 1≤ip,id≤n, 1≤tp<td≤hm, and n∈N, with ip being the pick-up depot, td being the pick-up time, id being the drop-off city, td being the drop-off time, and w being the number of cars to be reserved. Each booking r=(ip,tp,id,td,w) is converted into a new edge from node vip,tp to node vid,td. This will be the fourth type of arcs of our network.Now, we analyze which capacities are necessary to model the movement of the cars along the time and to accept only admissible bookings.We have supposed that depoti has pi parking spaces. To set this restriction we assign pi as maximum capacity to the edge (vi,j,vi,j+1)1≤i≤n, 1≤j≤hm, and every node of the form vi,hm, 1≤i≤n, must be connected with the sink t by an edge with pi as maximum capacity.Finally we must assign a minimum capacity to arcs(s,vi,1). If not, the cars at a depot i could not be considered in the parking in the future. In Figures 2 and 3 every edge (u,v)∈E has a 3-tuple (m(u,v),f(u,v),c(u,v)) associated with it where m and c are the minimum and maximum capacities, respectively, and f denotes the flow. If we suppose that arcs (s,vi,1) have assigned minimum capacity equal to the number of cars of every depot, ki, we will avoid the aforementioned problem. The following example shows the necessity of a minimum capacity for the edges that represent the starting time at every parking.Figure 2
Without minimum capacities on the arcs that depart fromS.Figure 3
With minimum capacities on the arcs that depart fromS.Example 1.
Suppose that we start with6 cars at depot 1 at time t=1 and with 7 cars at depot 2 at time t=1 too. We also consider that we have 7 and 8 parking slots, respectively, at each one of these depots. Let us suppose that we have to decide whether the booking (2,1,1,2,3) could be accepted or not.
In Figure2 we have a piece of a network without minimum capacities in the edges (s,v1,1) and (s,v2,1). In this case, there is a flow of 3 cars across the edge (v2,1,v1,2), and therefore the booking would be accepted. Nevertheless, there are 6 cars parked at slot 1 during all periods of time and this is not taken into account. If they were, then the proposed booking cannot be accepted as it is indicated in Figure 3, since we will have a total number of 9 cars that arrive to node v1,2. This is not possible since the conservation law fails due to the fact that the maximum capacity of the only edge that departs from (v1,2) is 7.For edges representing bookings, we also have to consider that the minimum and maximum capacity must coincide in order to be sure that the cars follow the booking itinerary and do not stay at the parking of the picking up depot. Next example shows the necessity of minimum capacity for edges associated with bookings.Example 2.
Suppose that we want to represent a booking of the form(1,2,2,3,1). This is done by considering a flow of 1 car along the edge (v1,2,v2,3).
In Figure4 we have a piece of a network without minimum capacities at the edge (v1,2,v2,3). In this case, we cannot be sure that the flow of 1 unit that corresponds to this booking will traverse the edge, and therefore the car will go from depot 1 to depot 2 at those times. We can only ensure this if we assign a minimum capacity of 1 unit to this edge, as it is shown in Figure 5.Figure 4
Without minimum capacities on the arcs that represent a booking.Figure 5
With minimum capacities on the arcs that represent a booking.


## 4. Existence of an Admissible Flow on the Network

The flow over the network that we have already presented simulates the movement of the cars over time. As we said before, a flow through a network with minimum capacities could not be admissible. Firstly, the initial number of cars at every depot must be smaller or equal to the number of parking slots at each depot; that is,ki≤pi for i=1,…,n. Secondly, a list of bookings, which is in fact a list of new edges to be added to the former network, could result into a network without any admissible flow.Now, we start with the initial networkN that contains only the first three types of edges that were previously mentioned. This network has the following values as maximum capacities at their edges:
(4)c(u,v)={kiforu=s,v=vi,1,i=1,…,npiforu=vi,j,v=vi,j+1,i=1,…,n,j=1,…,hm-1,piforu=vi,hm,v=t,i=1,…,n.In addition, we also set the following minimum capacities:(5)m(u,v)={kiforu=s,v=vi,1,i=1,…,n0foru=vi,j,v=vi,j+1,i=1,…,n,j=1,…,hm-1,0foru=vi,hm,v=t,i=1,…,n.Then, the following flow results in being admissible on this network:(6)f(u,v)={kiforu=s,v=vi,1,i=1,…,nkiforu=vi,j,v=vi,j+1,i=1,…,n,j=1,…,hm-1,kiforu=vi,hm,v=t,i=1,…,n.Now, let us suppose that we have an ordered list ofL bookings requests {r1,…,rL}, where each booking is given by its corresponding 5-tuple. Consider that these bookings have arrived to us in advance to t1, for instance through the website of the car-rental company. We have to decide whether we can accept them or not. The acceptance of each booking depends on the acceptance or not of the previous ones. We assume that all bookings must be answered following a first-in/first-out criterion, which is the closest approach to the management of bookings that arrive through a web service.We start with the first booking requestr1=(ip1,tp1,id1,td1,w1) and we add the corresponding edge from node vip1,tp1 to vid1,td1 with maximum and minimum capacities equal to w1.In order to know if there exists an admissible flow in the networkN=(V,E,s,t,m,c) with the additional edge corresponding to booking r1, we define an auxiliary network N′ and apply Ford-Fulkerson algorithm on it. The explanation of Ford-Fulkerson algorithm can also be found in [16, 18, 19, 21].The use of this networkN′ in order to determine the existence of an admissible flow on a network with minimum capacities is given by the following result that can be found either in [16, page 83] or in [21, page 92]. Its application provides us with a theoretical support for modeling our problem.Theorem 3.
LetN=(V,E,s,t,m,c) be a network and let one consider its auxiliary network N′ defined as follows. (1)
The set of nodes ofN′ consists of the nodes of N and two new auxiliary nodes s′,t′ that will be the source and the sink, respectively, of the network N′.(2)
To defineE′ we consider all the edges of E and we add a new one from t to s, with infinite capacity.(3)
For every edge(u,v)∈E with capacity m(u,v)≥0 we also change its maximum capacity c(u,v) by c(u,v)-m(u,v) and we add a new edge (s′,v) with maximum capacity c′(s′,v)=m(u,v) and another one (u,t′) with maximum capacity c′(u,t′)=m(u,v).(4)
We also set all the minimum capacities ofN′ to zero.
Letf′ be a flow of maximum value f′(N′) on N′, and let f′(t,s) be the flow of f′ through the edge (t,s). There exists an admissible flow of value f′(t,s) on N if and only if f′(N′)=∑(u,v)∈E‍m(u,v).Remark 4.
The proof of Theorem3 shows how to construct the admissible flow; we just have to define f(u,v)=f′(u,v)+m(u,v) for every edge (u,v) in the initial network N, and its value will be f′(t,s).To sum up, the networkN′ obtained when considering also the first booking r1 has V∪{s′,t′} as the set of nodes, s′ as the source, t′ as the sink, and the following edges with their corresponding maximum capacities. These new capacities are defined as:
(7)c(u,v)={∞,foru=t,v=s,∑i=1n‍kiforu=s,v=t′,kiforu=s′,v=vi,1,i=1,…,n,piforu=vi,j,v=vi,j+1,i=1,…,n,j=1,…,hm-1,piforu=vi,hm,v=t,i=1,…,n,w1foru=vip1,tp1,v=t′,w1foru=s′,v=vid1,td1.We have eliminated the edges that should appear onN′ with maximum capacity equal to 0. If there exists a maximum flow on this network of value f′(N′)=∑i=1n‍ki+w1, then the booking should be accepted by Theorem 3. If it is not accepted, we remove the edges (vip1,tp1,t′) and (s′,vid1,td1). If yes, then we keep these two edges on N′.Example 5.
Suppose that we have two depots,1 and 2, with k1 cars at depot 1 and k2 cars at depot 2. We consider each depot at two different times, t=1 and t=2. Suppose that we have a booking of w1 cars from depot 1 at time t1 to depot 2 at time t2. In Figure 6 we have the initial network N with the minimum and maximum capacities at every edge. The flow is not indicated at any arc. In Figure 7 we have the corresponding auxiliary network N′ where we have reduced the minimum capacities 0 of the arcs as it is indicated in (7). We recall that the arcs with maximum capacity equal to 0 are also removed.Figure 6
NetworkN.Figure 7
Auxiliary networkN′.After dealing withr1, we pass to next booking r2=(ip2,tp2,id2,td2,w2) and we proceed as before, adding two new edges to N′ with capacity w2:
(8)c(u,v)={w2,foru=vip2,tp2,v=t′,w2,foru=s′,v=vid2,td2.If for dealing with an arbitrary bookingr=(ip,tp,id,td,w), one (or two) of the edges (vip,tp,t′) and (s′,vip,tp) are already defined on N′; what we have to do is to sum w to the existing maximum capacity of that edge and test the admissibility of N′. If the booking should not be accepted, then we just have to decrease the maximum capacity of that edge on w, leaving the edge with the previous capacity.Remark 6.
Our model lets us cancel a booking some time after it was already accepted. It is sufficient to decrease the maximum capacity along the corresponding edge in as many units as the booking indicates, removing it if, afterwards, its maximum capacity is0. But we have to check if doing this we get a network without an admissible flow. On one hand, this could happen with one-way bookings when the car was required to be at another city in the future for being used for another booking departing from there. In this case, the car must be moved there by the company staff. On the other hand, the lack of an admissible flow on the network can also come from the necessity of needing more parking spaces available at the departure city during part of the time that the car was reserved.


## 5. Algorithm for Computing the Admissibility of the NetworkN

In this section we explain how we define the graph ofN′ in order to maximize the flow on this network. The Ford-Fulkerson algorithm provides a solution for the quest of a maximum flow between a source and a sink on a network.As we have mentioned in the previous section, the acceptance of a booking depends on verifying whether a certain networkN with minimum capacities admits a flow or not, and this can be reduced to find a maximum flow on an auxiliary network N′. The following algorithm shows how to define N′ and how to use it in order to accept or reject a reservation.Step 1.
Notation(1.1)
n, number of depots.(1.2)
For every1≤i≤n, pi stands for the number of parking places available at depot i.(1.3)
For every1≤i≤n, ki denotes the initial number of cars at depot i.(1.4)
hm is the total number of time moments considered, t1,…,thm.(1.5)
The networkN′ will have hmn+4 nodes; that is, n depots at hm different times plus 4 nodes for s,t,s′, and t′.(1.6)
A=(ai,j) is matrix of capacities in N′, whose dimensions are (hmn+4)×(hmn+4). The nodes are enumerated in the adjacency matrix as follows:
(i)
For1≤i≤n,1≤j≤hm,vi,j→n(j-1)+i,
(ii)
t→hmn+1,(iii)
s→hmn+2,(iv)
t′→hmn+3,(v)
s′→hmn+4.(1.7)
Set{r1,…,rL} as a list of bookings. Set α=1, which will be the counter for the reservations.(1.8)
SetΛ=0, which will accumulate the number of cars in accepted bookings.Step 2.
InitilializeA
For every1≤i,j≤hmn+4, we define the following:
(9)ai,j={plfori=kn+l,j=i+n,0≤k≤hm-2,1≤l≤n,plfori=(hm-1)n+l,j=hmn+1,1≤l≤n,klfori=hmn+4,j=l,1≤l≤n,∑l=1n‍klfori=hmn+2,j=hmn+3,∞fori=hmn+1,j=hmn+2,0elsewhere.Remark.
a
i
,
j
=
0 can represent the lack of an edge or the existence of an edge with capacity equal to 0.Step 3.
Analyze the bookings.
Whileα≤L, take rα=(ip,α,tp,α,id,α,td,α,wα). (3.1)
Update the following elements ofA:
(10)ai,j={ai,j+wαfori=hmn+4,j=n(td,α-1)+id,α,ai,j+wαfori=n(tp,α-1)+ip,α,j=hmn+3.(3.2)
Maximize the flowf(N′) of the network N′ using Ford-Fulkerson algorithm.(3.3)
Iff(N′)=Λ+∑i=1n‍ki+wα, then
(i)
accept the bookingrα,(ii)
updateΛ=Λ+wαelsewhere,
(iii)
undo the assignments inA of Step (3.1).(3.4)
Setα=α+1 and return to Step 3.Step 4.
We finish when all the bookings have been processed.In order to reduce the computational cost of the above algorithm we have analyzed its implementation based on the notion of a residual network. LetN=(V,E,s,t,c) be a network with a flow f over N. Without loss of generality, we assume that each pair of nodes is connected in just one sense, either (u,v)∈E or (v,u)∈E but not at the same time. We define theresidual networkNf as the network Nf=(V,E,s,t,c~), with the same nodes, source, and sink as N. The set of arcs E consists of all the arcs of the form (u,v) such that either (u,v) or (v,u) belong to E; that is, every arc of E is maintained and it has also an associated arc in the opposite sense. Besides, the new capacities, c~, on this new set E are defined as
(11)c~(u,v)={c(u,v)-f(u,v),if(u,v)∈E,f(u,v),if(v,u)∈E.We define anf-augmenting path on Nf as a path from s to t, namely, p~, such that all the edges in this path have positive capacity. We define thecapacity ofp~, namely, c~p~ as the minimum of the capacities of all the arcs in p~. The flow is maximum when there is not an f-augmenting path on Nf.Let us consider the networkNf′ associated with the network N′ defined in previous algorithm with the initial flow defined in (6), which results in being admissible in N′. Then, the new adjacency matrix Af=(ai,jf) that corresponds to the network Nf′ will be
(12)ai,jf={pl-klfori=kn+l,j=i+n,0≤k≤hm-2,1≤l≤n,klforj=kn+l,i=j-n,1≤k≤hm-1,1≤l≤n,pl-klfori=(hm-1)n+l,j=hmn+1,1≤l≤n,klfori=hmn+1,j=(hm-1)n+l,1≤l≤n,klfori=l,j=hmn+4,1≤l≤n,∑l=1n‍klfori=hmn+3,j=hmn+2,∑l=1n‍klfori=hmn+2,j=hmn+1,∞fori=hmn+1,j=hmn+2,0elsewhere.After each bookingrα=(ip,α,tp,α,id,α,td,α,wα), we look for an f augmenting path p~ from s′ to t′ in the residual network associated with the network Nf′. The residual one is updated following the indications in (10). For the sake of clarity, we provide, in Figure 8, the residual network of N′ in Example 5 after the first iteration of Step (3.1) in the algorithm. The edges with 0 capacity and the labels of all the nodes except s′ and t′ have been removed in order to get a neater picture.Figure 8
The network of Example5 after the first iteration of Step (3.1) in the algorithm. The arcs in black belong to N′, and the arcs with a purple (dashed) line represent the additional edges to be considered with the former ones of N′ in order to have the residual network of N′.


## 6. A Simplified Algorithm for Computing the Admissibility of a Flow on a Network

We refer again to Example5. The nodes that stand for the drop-off depot before the drop-off time, the nodes that refer to the pick-up depot before the pick-up time, and s can be removed because if some of them appear in an f-augmenting path, they do it in a cycle, and this cycle can be erased from the f-augmenting path without decreasing its capacity. Therefore, the only way to find an f-augmenting path without cycles from s′ to t′ is to consider the following path: {s′,v2,2,t,v1,2,v1,1,t′}. Therefore, a simplification of the residual network in what concerns to this booking can be seen in Figure 9. Such a path exists if the following conditions are fulfilled whether w1≤p1-k1 and w1≤k2. So by checking them we can omit the restrictions given by the arcs (s′,v2,2) and (v1,1,t′), and the network N′ is reduced to the time-space part plus the initial sink t, see Figure 10.Figure 9
A simplified version of the residual network of Example5 is to be considered in order to decide whether to accept or not the booking (v1,1,v2,2,w1). This is accepted if we find an f-augmenting path from S′ to T′ to be increased in w1 units. The arcs in the f-augmenting path are represented in green.Figure 10
A more simplified version of the residual network of Example5. The booking (v1,1,v2,2,w1) will be accepted if there is an f-augmenting path from v2 at time t=2 to v1 at time t=1 to be increased in w1 units. The arcs in the f-augmenting path are represented in green.Taking this into account, Step3 in the algorithm of Section 5 can be significantly simplified. Let us take a booking (ip,tp,id,td,w). In order to accept it, we only have to find, if there exists, a path that connects the node vid,td with the node vip,tp with capacity greater than or equal to w. Such a path can be easily found using a shortest path algorithm, like Dijkstra’s, in the residual network associated with N′. This path will be of the form
(13)vip,tp,vip,tp+1,…,vip,thm,t,vid,thm,…,vid,td+1,vid,td.Further information concerning Dijkstra’s algorithm can be found, for instance, in [16, 18, 19, 21, 24].We point out that the use of a shortest path algorithm prevents us from getting anf-augmenting path with cycles. With respect to the previous algorithm, we modify the steps indicated below but considering the matrix Af previously defined.Step  1
′
. Notation(1.6.bis)
Af=(ai,jf) a matrix of dimensions (hmn+1)×(hmn+1). The nodes are enumerated in the adjacency matrix as follows:(i)
vi,j→n(j-1)+i,(ii)
t→hmn+1;that is, we have removed the vertexs,t′, and s′ and the adjacent arcs to them. In addition, Step (1.8) is removed.Step  2
′
. Initialization of AfIn the same way as in (12), but restricting ourselves to the new dimensions of  Af, we omit s,s′,t′, and their adjacent arcs.Step  3
′
. Analyze the bookingsWhileα≤L, take rα=(ip,α,tp,α,id,α,td,α,wα).(3.1)′
Find a shortest pathp~ between the nodes n(td,α-1)+id,α and n(tp,α-1)+ip,α.(3.2)′
Compute the capacity ofp~, namely, c~p~.(3.3)′
Ifwα≤c~p~ then do the following.
(i)
Accept the bookingrα.(ii)
Update the following elements ofAf:
(14)ai,jf={ai,jf-wαfori=n(td,α-1)+id,α+kn,j=i+(k+1)n,k=0,…,hm-td,α,ai,jf+wαfori=j+(k+1)n,j=n(td,α-1)+id,α+kn,k=0,…,hm-td,α,ai,jf-wαfori=n(hm-1)+id,α,j=hmn+1,ai,jf+wαfori=hmn+1,j=n(hm-1)+id,α,ai,jf+wαfori=n(hm-1)+ip,α,j=hmn+1,ai,jf-wαfori=hmn+1,j=n(hm-1)+ip,α,ai,jf+wαfori=n(tp,α-1)+ip,α+kn,j=i+(k+1)n,k=0,…,hm-tp,α,ai,jf-wαfori=j+(k+1)n,j=n(tp,α-1)+ip,α+kn,k=0,…,hm-tp,α.elsewhere
(iii)
Reject the bookingrα.(3.4)′
Setα=α+1 and return to Step 3.Step  4
′
. We finish when all the bookings have been processed.


## 7. Some Additional Considerations about the Model

In our assumptions we have considered that we start the scheduling of bookings from scratch starting on timet1, but this is only the real case once in the company lifetime. The interval of time t1,…,thm must be finite. Nevertheless, we can consider that before running the algorithm on the model we have already confirmed some bookings that started before t1 and some that will finish after thm. In order to introduce them in our model:(i)
for every existing booking(ip,tp,id,td,w) with tp<t1 and t1≤td≤thm, we add a new edge (s,vid,td) with maximum and minimum capacity equal to w,(ii)
for every existing booking(ip,tp,id,td,w) with t1≤tp≤thm and thm<td, we add a new edge (vip,tp,t) with maximum and minimum capacity equal to w.We have also considered that we are dealing with only one type of car. If our fleet has several types of cars ordered in increasing category asx1≺x2≺⋯≺xl, we will propose a model with l-layers. In the lower one we have a network for cars of type x1, in the one above of it we deal with the cars of type x2, and so on. We should point out that in this case the number of parking spaces is shared by several types of cars. Sometimes the clients could ask for a car of low type, for instance x1, and the company could have none of those cars available of this layer for renting. However, we can try to see if we can offer him a car of type x2. If this is the case, we can confirm the booking and grant the client with an upgrade when he arrives to the pick-up depot. The client will be happy and the service have accepted a booking that otherwise could be lost.


## 8. Results and Discussion

The proposed model simulates the flow of the fleet of vehicles of a car-rental service without staff dedicated to move cars from one location to another one, as could sometimes be needed to do due to one-way bookings. This model has the advantage that let us recover the flow of cars across the depots along the time, as it is indicated in Remark6.The model is based on determining the admissibility of a flow on a network with minimum capacities. Its implementation is backed by Theorem3. In our first model every new booking only requires defining at most one new edge on the auxiliary network and applying the well-known Ford-Fulkerson algorithm on it. Later, a simplification of the network permits us to solve the problem using a shortest path algorithm.On one hand, Ford-Fulkerson algorithm can be easily computed on a network withMathematica© by using the commandNetworkFlow [network, source, sink] of theCombinatorica package. In our case,network would be the graph associated with N′, s′ would be the source, and t′ would be the sink. The complexity of Ford-Fulkerson algorithm is O(|E|·f(N′)), where E is the set of edges in the network N′ and f(N′) is the maximum flow on it, see for instance [19, 20, 26]. Therefore, every time a booking r=(ip,tp,id,td,w) is accepted we add at most two more new edges and the flow is increased in w, which is the number of cars in the booking. An implementation using Edmonds-Karp algorithm has a complexity O(|V|·|E|2), which is independent of the number of cars considered and only depends on the set of vertex V′ and the set of edges E, [19, 20, 26].On the other hand, the shortest path between two nodes in a network can be easily computed withMathematica usingFindShortestPath [network, source, sink] of theCombinatorica package, with the same values fornetwork, source, andsink as before. There are several algorithms for solving the shortest path problem between two points. The well-known Dijkstra algorithm has a cost O(|V|2) when it is implemented with lists. The order of the cost can be reduced if it is implemented with binary heaps, O((|E|)log⁡|V|), or with Fibonacci heaps, O(|E|+|V|log⁡|V|), see [19, 20, 26]. Therefore, the simplification proposed of the algorithm shown in Section 6 can provide much more better computational results.This can be seen on a simulation carried out over time-expanded network of 6 depots at 20 different times and 500 bookings. The computations were performed on a computer with a processor of 2.50 GHz and 3.25 Gb of RAM usingMathematica©8.0. The comparison of the execution times of each one of these methods is presented in Table 1. We observe a significant improvement in the computational time required to solve the problem if we use the simplified algorithm based on the search of shortest paths using the residual network.Table 1
Comparison between the 2 algorithms for 6 cities at 20 different times.
Number ofbookings
With NetworkFlow (s.)
With FindShortestPath (s.)
1
0.125
0.062
5
0.718
0.266
10
1.828
0.515
15
3.265
0.782
30
9.235
1.562
75
34.609
4.078
125
61.547
6.765
200
100.265
11.00
300
139.593
16.657
400
163.484
22.422
500
207.984
28.281Finally, this model let us simulate if it is profitable for the company that manages the service to invest or not, either in more cars or in more parking slots, taking into account the historic of petitions of bookings received. This can be done using a list of all the requests of bookings received during a period of time, despite they were accepted or not. We analyze, with the historical data of petitions, if when we increase the maximum and minimum capacities at one or some of the edges(s,vi,1) the number of accepted bookings is increased, and whether the new expected incomes coming from these bookings are enough to invite us to invest. Analogously, we can consider if there is a significant increment of benefits if we augment the number of parking spaces at one or some depots. Both types of analysis can be jointly considered.



---

*Source: 483734-2014-05-25.xml*