Article Preview
Top1. Introduction
The Dial-a-Ride Problem (DARP) is a variant of the Pickup and Delivery Problem (PDP), frequently arising in door-to-door transportation services for elderly and disabled people or in services for patients. In recent years, dial-a-ride services have been steadily increasing in response to popular demand (Cordeau & Laporte, 2007). A DARP consists of n customers who want to be transported from an origin to a destination.
Due to the application oriented character of vehicles routing problems no standardized problems definition exists. In the last years several works has been published, trying to find a standard classification of all given works, such that has already been made and those that will be done. The classification has proved difficult and it depends on several criteria: the objectives applied range from the maximization of the number of user served to the minimization of user waiting time or routing costs. The constraints considered are usually tailored to the specific problem situation. The transported objects varied from goods to be fulfilling to depots to the persons or patients to be transporting from home to the hospital or from hospital back to the home. The transport requires only one vehicle or several vehicles homogeneous, and so on. The one of the best classification survey works was provided by Cordeau and Laporte (2007), Berbeglia et al. (2007), Parragh et al. (2008a), and Parragh et al. (2008b).
According to Parragh et al. (2008a) the field of pickup and delivery problems is classified into two problem classes. The first class refers Vehicle Routing Problems with Backhauls (VRPB), where delivered goods have to be loaded at one or several depots and all goods picked up have to be transported to one or several depots. The second class it comprises all problems where goods (passengers) are transported between pickup and delivery customers (points) and will be referred to as Vehicle Routing Problems with Pickups and Deliveries (VRPPD).
The VRPB can be subdivided into four subclasses. In the first two subclasses, customers are either delivery or pickup customers but cannot be both. In the last two subclasses, each customer requires a delivery and a pickup. The first subclass is characterized by the requirement that the group or cluster of delivery customers has to be served before the first pickup customer can be visited. Delivery customers are also denoted as linehaul customers, pickup customers as backhaul customers. In the literature this problem class is denoted as Vehicle Routing Problem (VRP) with Backhauls (VRPB). The second VRPB subclass does not consider a clustering restriction. Mixed visiting sequences are explicitly allowed. The third VRPB subclass describes situations where customers are associated with both a linehaul and a backhaul quantity but, every customer is only visited once. The fourth VRPB subclass covers situations where every customer is associated with a linehaul as well as a backhaul quantity. It is imposed that every customer can only be visited exactly once.