Taxi is the most flexible demand-responsive transport (DRT) system that offers on-demand call-up door-to-door service from any origin to any destination in a service area. In big cities it can happen that many taxi passengers have a common destination located in the same general area, and in this case taxi sharing service could be of great benefit. The reasons are the following:
Passengers pay lower fares for door-to-door journeys than they would if traveling alone.
If there is a long queue of passengers or a local shortage of taxis, passenger waiting times will be reduced.
From these arrangements not only benefit customers, but the trade and local communities too:
Drivers get more revenue for each trip than they normally would
There are fewer taxi trips overall, resulting in less noise, disruption, traffic congestion and pollution
Taxi-sharing services is mainly for people who have recurring travel needs - like going to work, office or business. It works as well for one time travel requirements like a trip to the sports event, concert. Beside daytime activities cab-sharing service fits perfectly in cities at night, when mass amounts of people are leaving bars, restaurants, clubs, etc in nightlife areas and heading to residential areas. And for that matter, works well the other way too, when mass amounts of people are leaving residential areas and heading to the restaurant, bar and club areas.
Recently some taxi-sharing web-based and mobile-based application [1] have emerged. Unfortunately from our observations these applications haven't been embraced wildly by the passengers and the reasons are the following:
Low rate of matching requests: most of the passengers don't get to share the taxi ride.
Lack of dynamism in the application: Traveling requirements of people are becoming more complicated and ad-hoc every day. Home-office transportation fills the major portion of their routine traveling needs. Apart from that, many instant travel requirements may arise in unpredictable manners, which result in more complex, dynamic traveling.
Lack of pervasiveness and usability: passenger need to plan their journey in advance or rely on other certain people. None of the application gives users intelligent reminders and dynamic recommendations. Many applications require prolonged assistance of the passengers for user manual operation on data input and event processing .
The motivation of this work is to create an architecture for a dynamic tax-sharing system with smart interaction and pervasive connection abilities . This work proposes a novel instant taxi-sharing system which uses Multi-Agent technology for ride matching and routing, and Android technologies, like Cloud to Device Messaging Framework, to ensure pervasiveness.
In this work dynamic scenario is considered, in which the vehicle progress is monitored; clients can modify or cancel their trip requests, vehicle delays can occur, clients may not show up at the pickup place and vehicles can breakdown, all of them involving the re-scheduling of the trips and their management.
Cab-Sharing problem definition and formulation
From a mathematical point of view the transportation problem of people corresponds to the Dial-a-ride Problem (DARP) which is a variation of Vehicle Routing Problem known to be NP-hard[1].
DARP dwells with finding vehicle routes and schedules for n user who specify pickup and delivery requests between origins and destinations. In the standard version, transport is provided by a fleet of m identical vehicles. The aim is to plan a set of routes capable of satisfying as many requests as possible under certain conditions and at minimum cost.
The DARP is an extension of PDP((Pickup & Delivery Problem ), where the transportation of goods is replaced by the transportation of persons. Because it deals with transportation of human beings, DARP concentrates more on satisfaction of these individuals needs. Moreover DARP are characterized by the presence of three objectives, that are often contradictory:
maximization of the number of demands to be satisfied
minimization of operational costs for the vehicles or for the passengers
minimization of inconveniences for the passengers
The quality of service for DARP include route duration, route length, customer waiting time, customer ride time(i.e. Total time spent in the car), total time between actual and desired delivery time. Some of these criteria could be considered as constraints or part of the objective function.
Another distinct aspect for DARP is its temporal dimension. The passengers are often let to specify time windows for their departure and arrival. This last dimension is particularly important in the urgent cases. This time windows could be very narrow and following Jaw[2] we believe that just one of the time windows should be specified either for arrival or departure. Next section presents all the aspects invoked above in a mathematical manner.
2.1 Mathematical model
In order to understand the complexity of the problem this chapter presents the mathematical model for DARP. Cordeau [3] formulates the DARP on a directed graph G = (V , A). The vertex set V is partitioned into {{0, 2n + 1}, P , D} where 0 and 2n + 1 are two copies of the depot, P = {1, . . . , n} is the set of pickup vertices and D = {n + 1, . . . , 2n} is the set of delivery vertices. A request is a couple (i, n + i), where i ∈ P and n + i ∈ D. To each vertex vi ∈ V are associated a load qi , with q0 = q2n+1 = 0, qi ≥ 0 for i = 1, . . . , n and qi = −qi−n for i = n + 1, . . . , 2n, and a service duration di ≥ 0 with d0 = d2n+1 = 0. The arc set is defined as A = {(i, j ): i = 0, j ∈ P , or i, j ∈ P ∪ D, i ≠j and i ≠n + j , or i ∈ D, j = 2n + 1}. The capacity of vehicle k is Qk and the maximal duration of route k ∈ K is denoted by Tk. The cost of traversing arc (i, j ) with vehicle k is equal to ckij , and the travel time of arc (i, j ) is denoted by tij. The maximal ride time is denoted by L and the time window of vertex i is [ei , li ].
The model uses binary three-index variables xij equal to 1 if and only if arc (i, j ) is traversed by vehicle k ∈ K. In addition, let uik be the time at which vehicle k starts servicing vertex i, wik the load of vehicle k upon leaving vertex i, and rik the ride time of user i (corresponding to request (i, n + i) on vehicle k). The model is then as follows.
Minimize (1)
subject to (2)
(3)
(4)
(5)
(6)
(7)
(8)
(9)
(10)
(11)
(12)
(13)
In this formulation, constraints (2) and (4) ensure that each request is served once by the same vehicle, while constraints (3) and (5) guarantee that each vehicle starts and ends its route at the depot. Constraints (6) to (8) define starts of service times, vehicle loads and user ride times, respectively, while constraints (9) to (12) ensure that these will be feasible.
Review of approaches to solve DARP
There is little research on the multi-vehicle dynamic DARP(D-DARP) in the scientific literature. From practical reasons most of the research is targeted to the dynamic version of Pick-up and Delivery problem, which has a wide application in logistics.
One of the first to tackle D-DARP was Madsen[4], who have solved a real-life problem involving services to elderly and disabled people in Copenhagen. The algorithm behaved reasonably well on 300-customer, 24-vehicle problem. Passengers could specify a desired pick-up or drop-off time window, but not both. Requests arrive dynamically throughout the day. The system was considering a heterogeneous fleet of vehicles with variable speed and the fact that vehicles may become unavailable due to breakdowns. The authors have developed an insertion algorithm, called REBUS, based on greedy insertion heuristics procedure previously developed by Jaw[3]. New requests are dynamically inserted in vehicle routes taking into account their difficulty of insertion into an existing route.
An innovative software system for D-DARP was proposed by Horn [5]. The optimization capabilities of the system are based on least-cost insertions of new requests accompanied by a periodic re-optimization of the planned routes.
Soft computing has also been applied to the transport domain with the use of genetic algorithms (GA) for the optimization of the assignment (see [8] and [10]) and systems based on an ant-colony as reported in [12]. Teodorovic and Radivojevic [11] have later studied a generic version of the dynamic DARP using fuzzy logic for the travel times, as well as Kikuchi and Donnelly [9].
In [6] and [7] are presented the fist attempts of using agent-based approach. All of them make use of the CNP for the assignment of client's rides. Authors use three types of agents - Customer, Broker and Vehicle agents. The approach is based on the contract-net protocol (CNP) allocation and optimization based on exchange of tasks between the Vehicle Agents. The Vehicle Agents use an insertion heuristic and improvement strategy for task swapping between them.
Multi-agent Architecture for the cab-sharing system
In order to address the complexity of the system in case, it was decided to design a system build around a set of cooperative software agents, each of which represents the interests and behavior of entities in the domain. Each agent has its own goal to satisfy the user's requirements to whom it is serving for. These agents would interact among themselves to find the best matching for taxi-sharing requests. Since agents are sensitive to their operating environment and are autonomous, they can effectively handle uncertain situations inherent in instant taxi-sharing than any other technology. Managing uncertainty is solely done through inter-agent communication. Next, it can easily be scaled up by adding new agents to serve each new passenger. By keeping respective agents alive until the requirements of the user are satisfied, the system takes care of the user throughout the ride.
The system is composed of the following agents:
Taxi Agent - for route planning and optimization
Allocation Agent - for maintaining allocation and the improvement process
Passenger Agent - for processing of taxi-sharing requests and allocation invocations
The scenario of the execution is described as follows: a user connects to the system via a given support (smartphone, Web server.), it is then instantiated by a Passenger agent whose function consists in representing it in the system. The user indicates his departure point and his destination and a time window for departure or destinatio. Thus, the Passenger agent enters in interaction with the Allocation agent (see figure 2).
The latter broadcasts the request of the user to other Tax agents located in an environment which is modeled in the following section.
Our model is based on two simultaneous phases, an offer phase and a choice phase.
We want to establish an agreement between the proposals for a transport and the
needs of the customer. This is done according to a mechanism of negotiation. A key
element of the system is pairing vehicles and customers. Which vehicle is the best
for servicing a given request? Who determines it and how? How a vehicle knows if
it has been selected to service a new demand? These questions are not independent.
The best vehicle corresponding to each user will be selected; it must minimize the
additional effort C to service the customers. To know this additional effort, a
vehicle calculates, on the one hand, the total cost (in time) of its current route,
that of the route to discharge the current passengers and charge already planned
ones. On the other hand, a vehicle calculates also the cost of the new route to
service actual passengers by including the new one. The difference between the two
costs is the additional effort or overcost.
Each customer request is diffused to all vehicles. When receiving a new request, each
vehicle calculates its overcost to service the request and diffuses it to all the fleet.
Then, it compares the received answers to its overcost. It orders the received offers
and broadcasts the head of list. Finally, the determined winner is the one being the
most times ranked first in the received answers. Ideally, one could exempt these last
phases: if the diffusion is perfect, all the fleet will obtain the correct classification
directly. But, because of non perfect diffusion, we proceed to this additional phase
after a possible problem (a vehicle crossing a tunnel for example), and this to be
sure that all the vehicles agree on the winner vehicle wich will take the passenger.
Preliminary design of the CabShare application -- i.e the main components + their interactions
