Chapter 1

Dynamic Car-pooling

1.1. Introduction

In order to mitigate the negative impact of private cars and thus heal the environmental image of a personal vehicle, car-sharing systems were born. Within this context, car-pooling in particular has been a notable success thanks to the contributions it brings mainly by reducing the number of cars on the road. Indeed, making the personal car a common mode of transport, car-pooling plays a role in the reduction of harmful gas emission rates. The contributions are quantifiable in terms of “non-emitted” CO2, in addition to the many advantages it offers on both an individual and a collective level (e.g. reduction of budgets allocated for transport, time-space flexibility, comfort, social balance, etc.). Thus it has made its entrance into the field of research, and numerous systems have since emerged. Several studies have been conducted in a manner that draws on the fields of computer science, artificial intelligence, GIS (Geographical Information Systems), the Internet and telecommunications, etc. Making use of new technologies and the establishment of a more or less evolved system has precedence over any other goal in existing approaches. Web-based media are today operational and allow the general public to register and benefit from fairly limited services such as publications and consultation of offers and demand, as well as acquisition of contact details for potential car-poolers. Unfortunately, this type of system is the only one that deserves recognition because the rest, despite their openness to advanced features such as the integration of real time and the automation of allocation tasks based on multi-agent systems, have remained at the “idea” or “draft” stage, and are not liable to improvement. Irrevocably launched onto the road towards improvement, in this chapter we propose the implementation of an optimized dynamic car-pooling system. Two main concepts will be discussed in particular, namely the modeling of the problem as a distributed dynamic graph, on the basis of which distributed software architecture is established, and the deployment of a multitude of autonomous entities under this architecture. The combination of multi-agent systems with the foundations for optimization has thus been put in the service of effectiveness of processing for the establishment of an approach in the context of distributed artificial intelligence.

1.2. State of the art

In recent years, the sharing of vehicles has become a remarkable phenomenon mainly due to the economic and environmental benefits it offers. Thus, people tend to go for the “self-shared” vehicles (self-service vehicles, car-pooling, etc.) and discard their own automobiles. In this context, there are nowadays several studies that revolve around the sharing of vehicles, allowing the completion of relatively efficient systems to exist in about 1,000 cities around the world already [WCC]. These systems provide more or less satisfactory services for users but are still in the early stages. The work done to date can be subdivided into two categories according to the criteria for booking management adopted within the system. The first category is based on a static booking management while the second deals in real time with a dynamic aspect. In what follows, we present a non-exhaustive list of what has been done in this regard by making a distinction between:

– operational systems implementing the concept of “Shared Vehicles” (we actually focus on car-sharing, car-pooling sites remaining, for the most part, open and non-optimized systems); – the academic work done for modeling and optimization of such systems.

The existing operational systems are:

Static systems

– SEFAGE (SElbstFAhrerGEnossenshaft), which could be translated as “drivers club”. This is the oldest car-sharing organization traceable in the literature. It was founded in Zurich, Switzerland in 1948. It was essentially a club where members came together to buy a car. Without any commercial purpose, the main objective was to offer the service of having a vehicle available when needed. As the initiators were not aware of its innovative characteristics, SEFAGE never developed further. – Lilas [LIL]: car-sharing was strongly implemented in Lille in France through this service in which a booking is made in advance by phone or online using a member number. The member, who receives a monthly invoice, must book each time for at least one hour of service but has the freedom of choosing a car of their choice from a station of their choice. However, despite the variety of stations and vehicles it provides to customers, the Lilas system has the disadvantage of limiting the time of use of its vehicles, working in a loop (return by the user to the station of departure) and not having real-time reservation services. Lilac offers competitive pricing for users subscribed to local transport and for families, and combines well with other forms of transport. – Modulauto is the name associated with the car-sharing service available to the inhabitants of the city of Montpellier and the town of Nîmes in France. As part of the France Auto-partage service, Modulauto offers its members a fleet of self-service vehicles. Users reserve a car online or by phone at least 30 minutes in advance and the vehicle must be returned to a Modulauto station. – Mobility is the market leader for car-sharing in Switzerland, with a portfolio of 55,500 clients for which it provides 1,700 vehicles. A partnership with public transport has contributed largely to the development of Mobility. – Communauto [BEN] in Canada (Quebec, Montreal, Sherbrooke, Gatineau): since its foundation in 1994, Communauto appears to be a pioneering enterprise in America, as the manager of the oldest and one of the most important car-sharing services that has emerged on its side of the Atlantic. Communauto, which now has more than 14,000 members in Quebec, is the first car-sharing organization in the world to have signed the Charter for Sustainable Development of the International Union of Public Transport (IUPT). – City Car Club presents itself as the solution to problems faced by owners of private vehicles in the UK. It is a car-sharing service offered to British citizens and, like its predecessors, has a fleet of self-service vehicles that members share amongst themselves. – Cambio Stadt [MOB] in the city of Bremen in Germany: implemented in 2002 and owing to a partnership with Vivaldi and cooperation with Civitas, during its first three years, this project experienced a 43% increase in the number of users (2,455 to 3,512 in January 2005). – I-GO and zipcar USA: having the same principle as the majority of the various systems listed above, car-sharing in the United States presents itself, for the zipcar company founded in June 2000 [ZIP] and I-GO [IGO], as a system of advance booking of self-service vehicles of limited use duration. These vehicles are collected from stations designed for this purpose and delivered back to the starting station after use.

The static systems described above require advance booking based on static reasoning, without considering instantaneous events. Thus, these systems do not provide real-time vehicle allocation, nor do they provide an immediate response to the user. To remedy this deficit, dynamic car-sharing systems have emerged with real-time service management.

Dynamic systems

– PRAXITELE: the PRAXITELE Research and Development program was founded in 1993 based on a consortium from the industry (CGEA, Renault, the Dassault Electronics Group and EDF) and two research institutes (INRIA and INRETS). The service became operational in October 1997 in Saint-Quentin-en-Yvelines with 50 cars (PRAXICARS) and five carparks (PRAXIPARKS). PRAXITELE is a new form of public transport complementary to public transport and taxis. This new service is primarily intended for journeys and schedules when demand is diffuse and public transport is inadequate in terms of frequency and profitability. Its use is restricted to a geographical area ranging from a few hundred meters to several kilometers in some cases. To use PRAXITELE, one must first become a member of the service. A “credit card”-type memory card using contactless technology, the PRAXICARD, is then delivered to the client allowing them to access the cars, consult the information terminals installed in the stations and carry out payment. The PRAXIPARK stations act both as an interface between the system and its users through information terminals (information exchange with PRAXICENTRE, controls), and as a local operation system through its chargers (for recharging vehicles, etc.). The PRAXICAR vehicles use electric engines and are equipped with automatic chargers which charge by induction, facilitating their use, management and operation. They include an on-board computer which controls the opening in order to collect payment and ensure a dialogue with the user. Currently, the vehicles are electric versions of existing models (Renault Clio). Eventually, the idea is to use the concept of small electric cars, with dimensions better suited to urban use. – LISELEC [LIS]: created by PSA, VIA GTI and Alcatel CGA Transport, LISELEC is part of the global travel policy that has been leading the the La Rochelle agglomeration for many years. The experiment began in September 1999 in partnership with: the General Council of Charente-Maritime, the Regional Council of...