On-Demand Transport (ODT) systems have attracted increasing attention in recent years. Traditional centralized dispatching can achieve optimal solutions with NP-Hard complexity, making it unsuitable for online and dynamic problems. Decentralized approaches can achieve fast feasible solution at run-time with no guarantee on the quality. Starting from feasible not optimal solution, we present in this work a new decentralized, insertion heuristic algorithm to solve a special case of the dynamic Dial-A-Ride-Problem (DARP) as an ODT system, in which vehicles communicate via Vehicle-to-vehicle communication (V2V) and take decentralized decisions. In our solution model we add an optimization phase in order to improve the quality of global solution achieved by decentralized decision at run-time by exchanging resources between vehicles. We evaluate and analyze the promising results of our contributed technique on synthetic data for taxis operating in Saint-Étienne city, against a classical greedy approach. The concept of On-Demand Transport (ODT) was formulated for the first time around 1990 as a solution to the growing disaffection of potential users of public transport, especially at night [2]. There exist similar terms in the literature describing several transportation systems that could be similar in some characteristics and differ in others; e.g. the term Demand-Responsive-Transport (DRT) refers to the same concept. Seeking simplicity, here we only use the term ODT:
Definition 1 “On-Demand Transport is a transit mode consisting of
passenger vehicles, vans or small buses that respond to the calls
of passengers or their agents to the transit operator, who then
sends a vehicle to collect passengers and transport them to their
destinations."[
The allocation problem is one of the most studied optimization
problems in the literature [
The computational complexity of the problem, which extends the
NP-Hard traveling salesman problem (TSP), makes it difficult for the
central dispatcher to manage the dynamics of the problem during
execution (online requests, variable fleet size or heterogeneous fleets,
traffic problems and other environment dynamics). Therefore one
may expect that decentralization can cop off with these problems. The
insertion heuristics proposed by [
In this work, we propose the Autonomous Vehicle Fleet Allocation
Problem (AVFAP), which extends the traditional DARP with the
usage of fleet of autonomous vehicles, replacing the central dispatcher
with the coordination between each other via Peer to Peer (P2P)
communication in order to take decentralized decision, as illustrated in
Figure 1. V2V communication via Dedicated Short-Range
Communication (DSRC) provides low latency, fast network connectivity with
a range of communication up to 300 meters [
The paper is organized as follows. In Section 2, we overview the efforts done in literature to address related ODT problems. Section 3 expounds the model we consider for the decentralized resource allocation problem for autonomous vehicle fleets with an illustrative scenario showing the main components of the ODT system. Then the contribution for fast decision is presented in Section 4 and an optimization protocol is detailed in Section 5. Experimental parameters, evaluation and results are detailed in Section 6. Finally, we conclude the paper in Section 7 with some perspectives. 2
Traditional approaches for ODT consider centralized dispatcher
architecture like in [
Investigating the applicability of genetic programming (GP) for
developing decentralized MASs that solve dynamic DARP, [
An agent-based model based on simulated events for the real taxi
market was proposed by [
To address the uncertainty caused by the dynamic nature of online
demands, with ignoring the time required to execute a planning
algorithm, [
Based on vehicle coordination via message passing using P2P
communication, In our previous work [
So far and to the best of our knowledge, efforts done in ODT planning domain provide either optimized solutions ignoring the execution time, or provide very fast, just feasible solution to respond quickly to dynamic online demands. In this work, as optimal solution for this dynamic problem is unachievable with rational computational time, our proposal combines the benefits of these approaches in one heuristic that provide fast auction based response (fast feasible solution), and at runtime this solution is improved gradually with demand-exchange rescheduling.
The Autonomous Vehicle Fleet Allocation Problem (AVFAP) extends the traditional DARP by considering a fleet of autonomous vehicles that coordinate without a central dispatcher. The vehicles make decentralized decisions based on information exchanged via Peer to Peer (P2P) communication as illustrated in Figure 1.
The city map graph, shown in Figure 2, consists of nodes representing geographic locations and edges representing the road connections between these locations. A fleet of autonomous vehicles is distributed throughout the city, each vehicle has a set of properties whose values are constant (capacity, cost and average speed) or variable (location, schedule) because they are time-dependent. Passengers emit demands from different locations (which we will call sources later). Each one takes the form of a request that defines: the pick-up and delivery locations associated with the desired service time window. We define a solution as a schedule for each vehicle that meets the demands by satisfying their constraints, minimizing passenger waiting time and minimizing vehicle travel costs.
The vehicles communicate by broadcast via an ad-hoc Vehicle-tovehicle (V2V) communication network, where the communication range is limited. Each vehicle that receives new information broadcasts it again and the vehicles are thus connected by transitivity within the communication range.
In this context, a vehicle is not aware of requests outside its communication area. The vehicle’s belief evolves during the execution time, as the vehicle moves around, receives new requests from request sources, meets other vehicles and exchanges messages with them.
The AVFAP model is defined as:
AV F AP :=< M; V; D; T >
M :=< G; w > V := fv1; v2; : : : ; vng D := fd1; d2; : : : ; dmg
T := ft0; t1; : : : ; tendg where, M defines the urban infrastructure map (locations, roads and distances); the offer is represented by a V fleet of n autonomous vehicles; D defines a dynamic set of passenger demands that occur at the time of execution; and T defines the time horizon within which vehicles must respond to passenger demands. We define time T as a discrete set of ticks. 3.1
The urban infrastructure map is defined by a weighted directed graph M , as shown in Figure 2.
G :=< N; E > w := fwe1 ; we2 ; : : : ; wjEjg
G is a directed connected graph where N is the set of nodes, E is the set of edges between nodes. The valuation function w associates each edge e with the value we based on a measure of temporal distance (for example, average driving time in minutes), which will be used to calculate the operational costs of vehicle trips. 3.2
Each v 2 V is defined by v :=< capa; cpd; range > where capa defines the total number of passenger seats in the vehicle, cpd defines the cost of the vehicle per unit of distance, and range defines the communication range within which the vehicle can communicate with other entities. At any given time t 2 T a vehicle v 2 V knows its current situation: v_location defines the location of v that could be located in a node or moving through an arc; and f ree_seats defines the number of free seats available in v at time t. 3.3
A demand d 2 D is defined as a request
d :=< required; tw; pick_up; drop_of f > where required is the number of seats required; tw defines a time interval (tmin; tmax) in which the pickup event is considered acceptable; pick_up and drop_of f are the origin and destination of the request, respectively. As for vehicles, at time t 2 T , we will consider that a request d 2 D can also be communicated using the V2V network. The request could be issued by the customer or the infrastructure (roadside unit). 4
The main objective of vehicle agents is to provide feasible schedules that maximize their utility, by minimizing the global operational cost of serving the maximum number of requests.
Given a vehicle v having a potential demand set Dv, providing
a schedule for v to that satisfies all the requests d 2 Dv means
solving a TSP to produce the best ordering of requests in the schedule.
Considering the dynamic aspect of our model, we use an insertion
heuristic like the one described in [
In our model the agents handle request based on their priority order. The priority function is used by an agent to assign priority values to the requests he knows. Given a vehicle v, the priority function returns for a demand d a value that is inversely proportional to the cost costDemand(d; v) of inserting the demand in the schedule of v: 1=costDemand(d; v). Thus the lower the cost, the higher the priority.
In the simplest form the cost function returns the distance of d’s pickup location from v’s location, thus agents assign highest priority to the request with the nearest pick-up location.
Each agent determines his schedule to maximize the value of the
quality of his solution. Since several vehicles may be interested in
the same request, we need a coordination mechanism to resolve these
conflicts. We will use an auction mechanism for this purpose, which
is one of the effective and proven ways to solve such problems [
At time t, v selects the first request in the queue ds, generates a set of alternatives, each of which is a potential schedule resulting from the insertion of ds in a feasible step of the v’s current schedule. Every alternative is associated with a cost which is the marginal operational cost of adding this request to the schedule. The choice with the best cost is considered to broadcast an offer
with tstart the time of pick_up for ds.
In this document, we consider the operational cost of a trip as the total length of its route (sum of the distances shown in Figure 2). The marginal cost of insertion is therefore the difference in path length between the initial path and the new path. Bids remain available for a specific time period texpire. Thus, if the bid cost of v is less than any other bid received at t + texpire to serve a request d, it considers itself the winner of the auction, and updates its schedule with the new bid path.
Example 1 The simple scenario in Figure 3 shows two vehicles V1 and V2 located in A and B, with empty schedules at the beginning. At time t1, the first request is announced d1 :< 1; (t10; t20); C; H >. Both vehicles now know d1. V1 can serve it by following the path A ! C ! E ! F ! H, so V1 places the offer BiddV11 (t10; 11). V2 can serve it via the path B ! D ! C ! E ! F ! H, so issues the offer BiddV12 (t10; 13). V1 is considered a winner and adds d1 to its schedule, so that the overall operational cost of the fleet is now 11. In order to be able to make effective bids for new requests or to improve the solution, we propose that the vehicles exchange their planned requests.
Example 2 Figure 4 shows a situation where the use of the bidbased insertion heuristic is very reactive but does not guarantee good scheduling. At the moment t2 when the new request d2 :< 1; (t15; t40); J; K > arrives, both vehicles are aware of it and place their possible bids. In the absence of any exchange capacity, V1 still has d1 in its schedule (with an initial cost of 11), so the best offer it can place is to serve both requests with a marginal cost of 14. While V2 places the winning bid BiddV22 (t15; +11), it adds d2 to its schedule, and the overall cost becomes 22. Note that in this case, serving d2 with V1 and letting V2 take care of d1 results in an overall operational cost gain of 21, but this solution is never realized because d1 is already scheduled on V1. 5
In the following we propose a local optimization protocol to improve the quality of the solution for cases like Figure 4 and the Example 4.
This protocol is based mainly on the k-exchange neighborhoods (kopt) which is a path improvement algorithm, where at each planning phase, k steps from the current plan are replaced by k steps to get A 3 B
V1 4
J
3 4 4 V2 d1 C 2 D 2 d' 10 G E 5 3 4
F
2
H
2
I
a cheaper path [
Similar to the Rolling Horizon strategy of [
The application of this strategy requires that all vehicle schedules are in shared memory, so that when a vehicle vi offers to serve a request d, it knows if it is scheduled by another vehicle vj , and therefore if it should send its offer cost to vj . Then vj will calculate the gain (or loss) in operating cost by abandoning d compared to the cost proposed by vi. If there is a gain, it agrees to abandon d and then vi updates its schedule with d, otherwise the bid is rejected.
In our protocol, we do not use the concept of committed request, but a vehicle can only bid on requests that it can satisfy, so requests that are rescheduled or that do not have enough time to be rescheduled are automatically ignored by the agent. Another difference here is that we don’t have a shared memory. Agents exchange information about the context of the environment and about requests through information messages.
Step 1 A set of new demands enters the system based on announcement time order.
Step 2 Each new request is distributed to the connected set to which the sources belong. Each agent in this set can select his potential requests from the set of requests that includes new requests, scheduled and unscheduled requests that haven’t yet reached their scheduled departure time.
Step 3 The agents enter the auction to serve their potential demands in similar auction criteria of the initial phase Step 4 Each agent searches among its scheduled requests for the one to satisfy the next tick, this request is called dnext. If dnext exists, the agent broadcasts a "clear_demand" message to inform other agents that it handles dnext. Each receiver deletes it from their potential and known sets of requests. In addition, each agent deletes any other requests that reach their time window upper-bound because staying any longer available for rescheduling would violate their time constraints.
Step 5 The scheduled and unscheduled requests that still have time remain announced by their sources (Step 2). This allows better planning in the next tick, if new requests are announced, or some new agents join the connected set.
In addition, the proposal of [
Given the decentralized context, the use of the insertion heuristic is
very efficient in terms of response time. The temporal complexity of
the basic insertion heuristic for the Vehicle Routing Problem (VRP)
is of O(n3)[
Example 4 Let’s consider another case illustrated in Figure 6, where V1 has d1 in its schedule, V2 has an empty schedule, and a new request d0 :< (t10; t20); D; F > is announced. The bids of the vehicles are thus BiddV01 (t12; +4), and BiddV02 (t10; +13). It is obvious that BiddV11;d0 is the winner, and V1 will handle the two requests with an overall cost of 15. With the «Pull-demand» protocol, d1 and d0 enters in the set of candidate requests for V1 and V2, so that the vehicles can make combinatorial offers: BiddV11;d((t10; t12); 0) and BiddV02;d1 ( 2). The cost of V2 is 13 and the gain of V1 is 15). V1 has nothing to change in its schedule. V2 wins and the solution is improved with an additional optimization round. Let’s look at the applied protocol, step by step.
Step 1 d0 enters the system at t2 and both vehicles are aware of this,
V1 wins the auction with an overall cost of 15 Step 2 d1 and d0 are now in the set of requests known by both vehicles, V2 calculates the costs to serve d1 alone (13), d0 alone (9) and both requests together making 13. It then selects the two requests as its potential requests. V1 has no potential request because it already has the two requests in its schedule.
Step 3 V2 places a bid P ull_BiddV02;d1 ((t10; t12); 13). For V1 the cost to serve both requests is 15 so it accepts P ull_BiddV02;d1 because it causes a gain of 2.
Step 4 None of the requests reach their scheduled service time or the upper-bound of their time window.
Step 5 All known requests remain announced and available for the next potential improvement. 6
In this section, we experimentally evaluate the performance of our contributed pull-demand approach, using synthetic data and Open Street Map information. 6.1
The city map of Saint-Étienne was chosen for the simulation. The structure of the graph G =< N; E > including nodes, edges and a set of sources of the S N request is extracted from OpenStreetMap (OSM2). In all the experiments, we set the number of sources jSj = 20, having a set ES E of edges, such that jES j = 75 connecting the sources, each edge has a number of points which varies according to its length and the information extracted from OSM. The distance between two consecutive points is 40 meters. We used a discrete-time transport simulator available in the Plateforme Territoire3 to evaluate the proposed strategy and analyze it in terms of quality of service and gain.
A fleet V of n vehicles is distributed randomly through S at the beginning of execution. Each vehicle v 2 V moves from one point to another on the same edge during each simulation cycle. In our test we consider that vehicles communicate via (DSRC) with a realistic communication range of 250m, so that a vehicle can send/receive messages to/from other entities located in its range. Each vehicle v can adopt two distinct travel behaviors: either marauding for requests or going to a destination: going_to defines the state of a vehicle when it has a specific destination, i.e. a request to serve. The vehicle is either going_to pickup location if the request is not yet picked up, or going_to delivery location otherwise. marauding defines the state of a vehicle when it does not have a request to serve, i.e. at the beginning of the simulation, each vehicle marauds until it decides to serve a request. Once a passenger is dropped off, the vehicle reverts to marauding. In this state, the vehicle randomly moves through its neighborhood to find requests to serve.
At each simulation cycle, 0 or 1 request is generated in a uniformly random manner. For each request, the origin and destination points are randomly and uniformly generated from all sources. The time window for the requests is generated using two constant parameters l and u for the lower and upper limits as follows [twmin; twmax] is initialized with two uniform random values where :
twmin < twmax twmin twmax tactual + l twmin + u The evaluation criteria for these simulations are mainly the number of requests satisfied as a measure of Quality of Service (QoS), the simulated profit of the solution as a measure of Quality of Business (QoB). The profit is calculated in terms of the difference between the simulated travel price and the cost. where prof it = total_income
total_cost total_income = X P + p
distance(d) d2Ds Ds D is the set of all satisfied requests, P is a fixed price (service fee) per request, p is a pricing factor per unit of distance travelled, distance(d) is the total travel distance for a request d and total_cost =
v2V In our tests, we consider the vehicles to be identical in terms of cpd( ) travel cost and p pricing factor. We set P = 1:5, p = 2 and cpd(v) = 1 for all v. 6.2
To assess the feasibility of the «Pull-demand» Heuristic , we compare
it to a greedy approach (programming a single request in advance)
which has been mentioned by [
Note that it is impossible to achieve a 100% quality of service rate in these scenarios, because there will always be requests that will be generated until the last cycle, assuming that the scenario execution continues to serve them, while the execution stops at the last cycle, leaving them unserved. Although QoS values of our algorithm are close to those generated by greedy, they remain slightly ahead of them in most cases, as shown in Figure 9.
Starting from small fleet of 4 vehicles the Pull-demand heuristic allows to obtain solutions with the same QoS and QoB values as those of the greedy algorithm. By increasing the size of the fleet, more requests can be satisfied, which increases the QoS and QoB
We find that the increase of these values for the heuristic is greater than that of the greedy approach. This can be explained by the fact that demand planning improves the system profit in the foreseeable future, as it reduces the process of roaming without a specific destination until a new demand is chosen, which is the behaviour of the vehicles in the greedy algorithm.
The value of QoS continues to grow as the fleet size increases, until it reaches a nQoS threshold where the addition of new vehicles becomes unnecessary, as all requests received in the system now or in the future (except those received in the last moments of execution) can be served with the current fleet size. The same is true for QoB, but the difference here is that the vehicles added will result in additional operational expenses, resulting in a loss of profit value after reaching its nQoB growth threshold. In general, nQoB is less than nQoS , and we can see a trade-off between improving QoS or QoB.
According to the Figure 10, we see that the greedy fleet has ngQreoeBdy = 12 with a QoS of only about 60%, while npQuoll-Bdemand = 16 with a QoS of about 70%. Note that npQuoll-Bdemand < npQuoll-Bdemand and even if it decreases afterwards, the value of npQuoll-Bdemand remains higher than npQuoll-Bdemand. This gives a wider range of options for combining the enhancements of the provided solution (QoS and QoB). The above results show that in all cases, scheduling several requests in advance with the optimization protocol Pull-demand gives better results than scheduling a single request, with reduced computation time and no global information sharing. 7
In this paper, we proposed a decentralised protocol for the exchange of requests, based on an insertion heuristic, to allocate requests to vehicles in the context of dynamic transport on demand. We show through examples that the request exchange protocol can be a promising improvement in the quality of the solutions. In order to assess the feasibility of the proposed protocol, we evaluated the results of our technique on synthetic data for taxis operating in the city of SaintÉtienne, and showed that it outperforms a classical greedy approach. In future work, we plan to evaluate the efficiency, performance, robustness and optimality of this heuristic with respect to different approaches, by simulating different parameters on information distribution, decision criteria and different levels of problem dynamics.