Researchers Sahar Bsaybes, Alain Quilliot y Annegret K.Wagler from the University Clermont Auvergne, Clermont-Ferrand, France, published an article online (by Hal.archives-ouvertes.fr) regarding the fleet management for autonomous vehicles. The article provides an a-up to date review on this issue. Here there are some of the key issues.
VIPAFLEET is a framework to manage a fleet of Individual public autonomous vehicles (VIPA). Researchers consider a fleet of cars distributed at specified stations in an industrial area to supply internal transportation, where the cars can be used in different modes of circulation (tram mode, elevator mode, taxi mode).
The research is about the pickup and delivery problem related to the taxi mode by means of flows in time-expanded networks. This enables researchers to compute optimal offline solutions, to propose strategies for the online situation, and to evaluate their performance in comparison with the optimal offline solution.
A VIPA can operate in three different circulation modes:
– Tram mode VIPAs continuously run on predefined lines or cycles in a predefined direction and stop at a station if requested to let users enter or leave.
– Elevator mode VIPAs run on predefined lines and react to requests by moving to a station to let users enter or leave, thereby changing their driving direction if needed.
– Taxi mode VIPAs run on a connected network to serve transport requests (from any start to any destination station in the network within given time windows).
In this paper, the researchers treat the PDP related to the taxi mode as the most advanced circulation mode for VIPAs in the dynamic fleet management system. The transport requests are released over time and need to be served within a specified time window. The case in consideration is that, at each time, at most one customer can be transported by a VIPA (where one customer can be a group of people not exceeding the capacity of the VIPA), and a VIPA cannot serve other requests until the current one is delivered.
Note that, due to the time windows and the above additional restrictions, it is not always possible to serve all transport requests. Hence, the studied PDP includes firstly to accept/reject requests and secondly to generate tours for the VIPAs to serve the accepted requests. Thus, this article treat here both the quality-of-service aspect of the problem (with the goal of accepting as many requests as possible) and the economic aspect (with the goal of serving the accepted requests at minimum costs, expressed in terms of minimizing the total tour length of the constructed tours).
It´s necessary to distinguish between the online and the offline version of the problem: the online version occurs in practice (since the transport requests become known over time), whereas the offline version is important in theory to rate the quality of solutions for the online problem, by comparison with the optimal offline solution (computed knowing the entire request sequence already in advance).
To solve the Online TMP, three approaches are considered:
– A simple Earliest Pickup Heuristic that incrementally constructs tours by always choosing from the subsequence of currently waiting requests (i.e., already released but not yet served requests).
– The two well-known meta-strategies Replan and Ignore that determine which requests can be accepted and compute optimal (partial) tours to serve them, where Replan performs these tours until new requests are released, but – Ignore completely performs these tours before it checks for newly released Requests.
The conclusion is that IGNORE is not suitable for the Online TMP, since the way in which to construct tours may result in many rejected requests and the decision to accept/reject a request may be taken late, which does not comply with the quality-of-service aspect of the fleet management. Therefore, this paper focus on the other two approaches and perform computational results only for EPH and REPLAN, with the expectation that EPH is faster, but REPLAN achieves a higher acceptance rate.
In practice, EPH is faster, but REPLAN provides solutions of reasonable quality within a short time for each recomputation step and achieves a better acceptance rate.
The researchers highlight that the proposed REPLAN strategy is already a promising algorithm to handle the Online TMP for the taxi mode in the studied VIPAFLEET management system, with a reasonable ratio of computation times in each replanning step and an acceptance rate of about 55% compared to the optimal offline solution on realistic test instances.
Computational experiments revealed that the acceptance rate can be increased in some cases (on average about 13 % compared to the here studied REPLAN strategy), but that the possible increase strongly depends on the ratio of the request loads and the VIPA capacity.
On the other hand, the computation times in each replanning step are much higher, and the constructed tours are sometimes preemptive which causes inconveniences for the users (as they may have to change VIPAs and are not always transported along a shortest path from their origin to their destination).
Thus, the researchers conclude that the REPLAN strategy for the preemptive case has no clear advantage compared to the here proposed REPLAN strategy for the non-preemptive case, so that the operator of a VIPAFLEET system has to decide whether or not it is worth to have preemptive tours and longer computation times in each replanning step, taking the ratio of the average request loads and the VIPA capacity and, thus, the expected increase of the acceptance rate into account.
As future work, these researchers plan to improve the runtime of the here proposed REPLAN strategy by reducing the time-expanded network built in each replanning step without loss of optimality.