Reallocation of Empty PRT Vehicles en Route
by Dr. Ingmar Andrčasson
LogistikCentrum,
Taljegardsgatan 11, SE-431 53 Molndal, Sweden
November 10, 2002
This paper was presented at the Transportation Research Board Annual Meeting, Washington, D.C., January, 2003. Posting here does not imply endorsement of a particular product, method or practice by the Transportation Research Board. It will be published at some future time in the Transportation Research Record.
Abstract
Personal Rapid Transit (PRT) takes passenger parties on demand direct to their desired destination. Empty vehicles need to be moved to stations with waiting passengers or with expected demand. Efficient redistribution of empty vehicles is critical in larger PRT networks where running times are longer than acceptable waiting-times.
We have previously developed methods for allocating destinations to empty PRT vehicles sequentially as they become available. In this paper the allocation of empty vehicles is refined into three stages. The first stage is essentially the previous sequential allocation. In the second and third stage empty vehicles en route are reallocated by switching destinations between each other. In the second stage waiting passengers are allocated the nearest vehicle in order of longest wait. In the third stage remaining empty vehicles en route are reallocated based on minimum running distance. The optimization problem in the third stage corresponds to the transportation problem and it is solved approximately by a heuristic method suggested by Russel.
Applied to a network with 25 stations, 16 kilometers of guide-way and 200 vehicles the combined reallocation methods reduced average waiting and the longest wait to about half compared with sequential decisions alone.
The Vehicle Redistribution Problem
In Personal Rapid Transit (PRT) vehicles are normally waiting for passengers at stations ready to depart immediately for the passengerís destination. After the trip the vehicle will be at a station where the demand may be low or the vehicle may be blocking the way for other vehicles. In most cases an empty vehicle needs to be sent to another station with an expected demand. This paper deals with strategies for redistributing empty PRT vehicles.
Redistribution of vehicles is based on supply of empty vehicles at each station and demand from passengers waiting to depart. Since it may take several minutes to call an empty vehicle it is necessary to predict supply and demand to reduce passenger waiting-times. Demand forecasts are based on statistics on passenger origins based on previous corresponding periods corrected for weather and special events. Supply forecasts are based on vehicles (loaded or empty) on their way to each destination.
Due to the random nature of demand a vehicle allocation which was optimal when decided may need to be changed due to unexpected new demand. The challenge of the planning problem lies in the fact that call and send decisions have to be taken immediately in real time while conditions may change while the vehicle is en route.
One obvious way of improving service is to add more vehicles. This is not only expensive but too many vehicles would be obstacles on guide-ways and in stations. Excessive vehicles in off-peak hours should be stored in a depot.
In small networks with few vehicles the problem is not critical. All vehicles are available within a short call time. In large networks a called vehicle may take long before it arrives. Passengers still expect the same fast service so that calls have to be placed based on anticipated demand with a longer planning horizon. Changes are likely to occur while the called vehicle is on its way in a large network.
The methods of this paper offer significant efficiency and service improvements, at least for reasonably large PRT networks with vehicle utilization near capacity.
Our Previous Work
In our previous works we were seeking the best possible sequential allocation decisions. The following procedure is described in (1) (available on-line, click here).
Each time a new passenger shows up a vehicle call is considered. The call decision is based on vehicle supply and queuing passengers corrected for vehicles on their way to each station and for expected demand within a given horizon. If more vehicles are needed, one is called from the nearest station with a surplus.
An improvement is described in (2). The static transportation problem is solved in advance based on the OD matrix for travel demand which is assumed to be known. Origins of passenger trips constitute vehicle demand and passenger destinations determine empty vehicle supply. Movements of empty vehicles are minimized with a standard optimization method called Transportation Simplex. For every station with an expected vehicle surplus, destinations in the optimum solution are listed. Similarly for each station with an expected deficit a list of source stations is constructed. In real time when a call or send is necessary the stations on these lists are used if possible. This means that whenever possible a redistribution will be chosen that is part of the optimum solution. In that way the sum of the sequential redistribution decisions will tend to mimic the total optimum redistribution.
Recurrent Solution of Transportation Problem
The new feature of this paper is the added possibility of reallocating empty vehicles while they run. Even if each vehicle destination was determined in the best possible way, it was based on the situation at starting time and with all previous assignments being fixed. We now suggest to review all ongoing redistributions at regular intervals. The number of empty vehicles running towards each station is not changed but they may swap destinations between each other.
This is again a classic transportation problem with all running empties constituting supplies at their current positions and all their destinations constituting demands. Since each empty has exactly one destination the new problem is always balanced. We will solve this problem many times and it needs to be done fast. Therefore we chose to use Russel's approximation (3) which gives a fast, feasible, normally good but not necessarily optimum solution.
Russel's approximation method works as follows:
Let c(i,j) be the matrix of running times from supply (vehicle) i to demand (station) j.
Let u(i) denote the largest element of row i in c(i,j)
Let v(j) denote the largest element c(i,j) of column j.
Determine the pair (i,j) for which c(i,j)-u(i)-v(j) is the most negative.
Allocate vehicle i to station j.
Eliminate row i and reduce demand j
Repeat until all vehicles have been allocated.
The interpretation of the above method is to pick the allocation from i to j which gives the best improvement over the longest run for vehicle i and the longest run to station j.
Average Wait Versus Longest Wait
The optimum solution to the transportation problem is the one that minimizes total transportation cost which in our case is empty running time. The same solution also minimizes total and average waiting-times of passengers. In a PRT system we wish to offer minimum average waiting-time but also to avoid any passenger experiencing an excessive waiting-time.
We can give more weight to stations where a passenger has been waiting long. Weighting can be done by scaling up the corresponding column in the matrix of run times so that all transports to that station seem longer and more important to minimize. Each column is multiplied by the factor:
1 + alfa * longest wait(j).
With a large alfa the optimization will minimize the longest wait while alfa = 0 will minimize average wait. The focus on longest wait will be at the expense of average wait which is no longer minimized.
We have tried this approach without success. A possible explanation for the failure is that only the first waiting passenger in each station is considered in the assignment (using average or total waiting at each station would not focus the maximum wait). Total empty running will increase and may cause congestion.
Longest Waiting Passenger Gets the Nearest Empty
Russel's approximation is a heuristic allocation method focusing on avoiding long runs. The following heuristic method aims directly at minimizing the longest wait.
As with all sequential methods one allocation does not consider consequences for remaining allocations. The only sure thing is that the first allocation is optimum for that passenger. Another limitation of this method is that most of the empties are sent towards anticipated demand with no passenger waiting. Remember that the idea of PRT is that passengers normally shall not have to wait. The following method attempts to optimize remaining allocations with no passenger waiting.
Longest Wait Plus Transportation Solution
Most of the empty vehicles are running to destinations where no passenger is waiting. This may be because the call was made in anticipation of demand that has not yet shown up or the passenger has already been served. Vehicles sent to stations without passengers will not be reallocated with the above method. Some of them may have been picked to other stations with waiting passengers so they all need to be reassigned.
We have used Russel's approximation to assign remaining empty vehicles en route after the waiting passengers have been assigned their nearest empties. This combination of methods means that real waits are served in priority order while remaining empties are reassigned for efficiency.
Decision Rules for Sequential Calls and Sends
We have slightly modified our previous rules for successive calls and sends. Knowing that reallocations will normally take place we focus the successive decisions on surplus and deficits and not on distance. Considering that the set of destinations will not be changed it is important that priorities are based on demand only.
At the arrival of a passenger we consider making a call for an empty vehicle. A call is made to that station if the following inequality holds:
Vehicles at this station
- Vehicles booked to depart + Vehicles (loaded or empty) on their way towards this station
are less than passenger groups queuing to depart
+ Expected passenger groups during the empty call time for that station.
Empty call times are estimated for each station by smoothing of historic call times (as calculated at the time of call). A vehicle is called from the station with the largest surplus (not the nearest as in our previous method) or from a depot. The depot is used only to store excessive vehicles during off-peak.
Similarly if a station has a surplus or a vehicle needs to be pushed away or an empty vehicle is diverted from entering a full station, then a send is made to the station with the largest deficit.
These decisions to call or send empty vehicles are made sequentially in real time, in our example some 3000 decisions per hour. Then at regular intervals (60 per hour) all moving empty vehicles are reallocated, first in wait priority order and then for reduced total distance (giving reduced average and total wait).
Vehicle Management Within Stations
We have assumed that all stations are off-line with space for deceleration, vehicle waiting positions and a platform for combined de-boarding and boarding. The exit track has a space for vehicles waiting to exit and for acceleration. Vehicles advance on the station track as soon as space becomes available.
The station design has an impact on empty vehicle management in several ways. All station tracks are (off-line) through tracks with no separate space to store empty vehicles. This design puts a high demand on empty vehicle management. Empties are generally moving around in the network or are stored in designated vehicle depots during off-peak.
Even if station sizes have been carefully dimensioned it may sometimes happen that the station is full when a vehicle arrives. If the arriving vehicle has passengers it will make a loop in the network to come back to the same station. Stations are dimensioned to avoid this from happening and at least one vehicle space is kept free for arriving loaded vehicles. Empty vehicles sometimes get diverted and are given a new destination based on predicted demand in the same way as vehicles sent from a surplus.
Empty vehicles which are not needed elsewhere can stay in a station until needed or until they block platform space for de-boarding passengers.
If stations have parallel platforms for de-boarding/boarding then vehicle management is simplified in the following ways:
We have not applied parallel platforms since stations would take up more space.
Ride-Sharing with Multiple Drop-Offs
We have applied ride-sharing in our simulations in order to reduce the necessary fleet size. In previous applications we have proven by simulation that ride-sharing can double the load factor (reducing fleet demand to half) with only marginal increase in waiting-time and riding-time. The effect of ride-sharing depends on the demand pattern, fare incentives and matching strategies (one or more destinations, maximum wait to find a match etc). The most advantageous application of ride-sharing is at transfer stations where passengers arrive in bunches from mass transit modes.
From the perspective of empty vehicle management a ride-sharing trip is like any other trip except the empty vehicle will emerge when the last passenger gets off. However there is one complication that we need to take care of. If multiple destinations are allowed, a station track needs to be cleared (unless there are parallel platforms) for a dropping vehicle to continue. The empty vehicles that are pushed away cause some additional empty running.
Although we have applied ride-sharing in our test example the effects of reassigning empty vehicles are independent of whether ride-sharing is applied or not.
(see Figure 1 for diagram) that we used for this study has 25 stations (2 of which are bi-directional), 16 kilometers of guide-way and 200 vehicles with four seats and ride-sharing. Results are summarized in Table 1. Without ride-sharing the fleet needs to be more than 400 vehicles for the same level-of-service.Control System Considerations
We are assuming that the control system is flexible enough to allow destination changes en route. With fully synchronous control, vehicles have been assigned passage time-slots through all merge points along the route. A change of destination other than shortening a route would most often not be possible. With other control systems i.e. asynchronous or point-synchronous control (4), passage-times through merges are allocated dynamically so that a change of destination is no problem.
Application to Fornebu Network
We have developed a tentative PRT network for the Fornebu area in Oslo, Norway. The former airport has been relocated and the area is being developed for business, industry and housing. The area is poorly served by public transport and some kind of automated people-mover is being planned connecting to the Lysaker train station. No decision has been taking about PRT, and if built it will initially be a smaller network than the one simulated and with fewer vehicles.
The PRT network
Table 1. Sample summary results from Fornebu network
|
Table 2 compares waiting-time performance in 3 cases: 1)without reallocation, 2)with transportation solution and 3)with longest wait plus transportation solution. The successive call/send decisions are the same in all cases.
Table 2. Waiting-time performance of three methods, average and (min-max), in minutes
Method Average wait, minutes 99th Percentile Maximum wait No reallocation 1.1 (1.0 - 1.2) 4.2 (3.6 - 4.8) 15 (11-22) Transportation solution 0.6 (0.6 - 0.7) 2.1 (2.4 - 2.8) 10 (9 - 13) Longest wait + tpt.solution 0.5 (0.5 - 0.6) 2.2 (2.0 - 2.8) 9 (5-9) Each reallocation involved on average 52 empty vehicles. 22 % of the empty vehicles were reallocated based on longest wait while the remaining 78 % were reallocated with the transportation solution. With the combined strategy case 3) empty running was reduced in each reallocation by average 33 %. Ranges for waiting-times given in Table 2 are minimum and maximum from four simulations each covering 90 minutes (the initial 30 minutes for warm-up) with some 4200 passenger trips. Results with all three methods were obtained with the same four random streams for passenger arrivals in four simulations.
Figure 2 compares waiting-time distribution without/with reallocation (longest wait plus transportation solution) once every minute. Shorter reallocation intervals showed no additional effect whereas longer intervals were less efficient. The average impact of the combined methods over sequential allocations only was a reduction of 58 % on average passenger waiting and 47 % on the longest wait. The added computing time for the improved methods was not noticeable.
Figure 2. Waiting-time distributions without (left) and with reallocation of empties
WAITING-TIMES Mins Percent of passengers
0.0 **********
0.2 ************
0.4 ************
0.6 ************
0.8 *********
1.0 ********
1.2 ****
1.4 *****
1.6 ***
1.8 ***
2.0 ***
2.2 ***
2.4 **
2.6 *
2.8 **
3.0 **
3.2 *
3.4 *
3.6 *
3.8 *
4.0 *
4.2
4.4 *
4.6
4.8 *
5.0
WAITING-TIMES Mins Percent of passengers
0.0 **************
0.2 ********************
0.4 ******************
0.6 ***************
0.8 **********
1.0 *******
1.2 ****
1.4 ****
1.6 **
1.8 **
2.0 *
2.2 *
2.4
2.6
2.8
3.0
3.2
3.4
3.6
3.8
4.0
4.2
4.4
4.6
4.8
5.0
Conclusions
- Reallocation of empty vehicles en route offers significant improvements over sequential allocations only
- The best results were based on longest wait and then reduced distance
- Each reallocation en route for Fornebu reduced empty running by one third
- Average waiting-times and the longest wait were both reduced to about half
Acknowledgements
This research has been performed within the EDICT project (Evaluation and Demonstration of Innovative City transport) financed by the EU Commission and Vinnova (The Swedish Agency for Innovation Systems).
References
1. Andrčasson, I. Vehicle Distribution in Large Personal Rapid Transit Systems. Transportation Research Record 1451 (1995).
2. Andrčasson, I. Quasi-Optimum Redistribution of Empty PRT Vehicles. Proc., 6th ASCE Conference for APMs,1997.
3. Hillier & Lieberman. Introduction to Operations Research, 5th edition, McGraw-Hill, 1990, pp 219-233.
4. Andrčasson, I. Simulation of Large PRT Systems for Swedish Cities. Proc., 3rd ASCE Conference for APMs, 1993
Last modified: February 17, 2003