Article Preview
Top1. Introduction
Nowadays, along with the increase of population and the dispersion of habitation, public transport service is often incapable of effectively servicing the areas where cost-effective transportation systems cannot be set up. As a result, more and more people use private vehicles for their daily transportation. However, the high use of private vehicles combined with increased human mobility increases the load on the environment and raises transportation issues such as congestion, parking problem and low transfer velocity.
In order to ease these issues, different innovative mobility services are emerging. Car pooling is a mobility service proposed and organized by large organizations, such as large companies, public administrations and universities. These organizations encourage their employees or students to pick up or take back colleagues or schoolmates while driving to or from a common site. The service tries to decrease the number of private vehicles travel on the road by improving the average car occupancy. Car pooling reduces travel costs by sharing journey expenses such as fuel, tolls and car rental between the travelers. It is also a more environmentally friendly and sustainable way to travel, as sharing journey reduces carbon emissions, traffic congestion and requirement for parking spaces. Car pooling can also decrease driving stress since each driver has only to drive in one or two days during one week. It also creates increased social interaction between friends, neighbors and colleagues. As a matter of fact, it can enhance the sense of connectedness within the community as a social network.
Nowadays car pooling has already been considered as an important alternative transportation service throughout the world. Some countries have introduced high-occupancy vehicle lanes to encourage car pooling. Successful car pooling development has tended to be associated mainly with densely populated areas such as city centers and more recently universities and other campuses. In USA, most of the universities have introduced the car pool system to their students. For instances, the Zimride system is currently being used by nearly one hundred universities and colleges, such as Stanford University and UCLA. Also, more than 30 universities and colleges in Boise state have applied the Zipcars system to their students and employees (Gates, 2007).
Car pooling can be classiðed into two different forms: Daily Car Pooling Problem (DCPP) and Long-Term Car Pooling Problem (LTCPP). In the DCPP (Calvo et al., 2004), a number of users declare their availability for picking up or bringing back colleagues on one particular day. These users are considered as servers, then the problem becomes to assign users to servers and to identify the routes to be driven by the servers. Based on this view, the DCPP can be considered as a special case of Dial-a-Ride Problem (DARP) (Bodin & Sextion, 1986). In the LTCPP, each user has to act as both a server and a client and the objective is to define user pools where each user will in turn, on different days, pick up the remaining pool members. The objective becomes to minimize the amount of vehicles used and the total distance traveled by all users, subject to car capacity and time window constraints. Considering the various successful implemented approaches for DARP and the similarity between DCPP and DARP, the DCPP can be solved simply by adapting the approaches from DARP. But the LTCPP has so far received little attention from the optimization community. The solution to a LTCPP is to partition users into subsets, or pools, such that each pool member in turn will pick up the remaining members in order to drive together to the destination. A few researches have been carried out on this problem; however, their studies are either time consuming or lacking of solution quality when dealing with large scale instances. Thus, a more efficient and powerful meta-heuristic is still required in the real-world application.