Keywords

1 Introduction

Nowadays, one of the major classes of transportation is that of Transport on Demand (TOD) (Cordeau et al. 2007). This class of public and private transportation cope with the rise of demands with specific needs of people with reduced mobility or within areas not covered by the global public transport network. The research community has thus introduced the Dial-A-Ride Problem (DARP) of (Cordeau and Laporte 2003a), as part of the more general TOD problem (Rekiek et al. 2006), and especially as a door-to-door transportation problem (Cordeau and Laporte 2003a; Rekiek et al. 2006; Melachrinoudis and Min 2011). The DARP consists of satisfying TOD requests under a set of problem constraints. This problem is NP-Hard as it is shown by Healy and Moll (1995). In this class of problems, several users are transported by the same vehicle according to the maximal vehicle capacity. The users specify when they wish to be picked up and when they have to reach their destination. This demand is called a request. The users do not specify an exact time of the day, but rather time windows are chosen for the request. The users have to specify either the pickup or the delivery time window and an operator has to assign the other time window. A maximal ride time is also proposed as a bound for satisfying all the requests. Thus, the users have inconvenience times (time spent aboard the vehicle from the pickup to the destination) which must respect the supposed maximal ride time for all transportation requests. The main DARP objective consists of minimizing vehicles tours’ costs in a complete transportation network of nodes and arcs. The nodes are the pickup and delivery locations of customers with a single depot which represents the starting and final arrival point of all the vehicles of the fleet. All vehicles’ tours have to respect a maximal travel total duration. Each arc has a transit time and cost. A request of transport on demand is related to a set of persons who want to travel from a node of pickup to a node of delivery. These two nodes are successively the origin and the destination of a request. Each couple must be visited by the same vehicle. A service time expresses the time needed for loading and unloading a customer.

1.1 Quality of Service in DARPs

The quality of service is expressed as the degree of conformity to customers’ requirements in a general framework. In this review, we focus on the quality of service in Dial-A-Ride problems. Paquette et al. (2009) reviewed in a set of definitions from two classes of quality of service. The customer-based approach is based on customer perceptions while the technical approach relies on technical specifications.

From the customer perceptions viewpoint, Pagano and McKnight (1983), stated that the service quality relies on comfort, reliability, convenience of making reservations, extent of service, vehicle access, and safety. This later is the main motivation for customers with disability or reduced mobility. In this regard, there is also a strong need for assistance in moving from the vehicle to the destination, as well as short distances from the origin or destination to the means of transport. Besides, travel time is also seen from the customer perception as a major indicator of service quality. It relies on waiting time, total tour duration, and pickup time. This attribute is generally considered as operational costs by transportation providers.

On the technical side, large and various specifications for service quality have been defined in Paquette et al. (2009), since 1976. Most of these specifications are included as part of DARPs model as constraints. Some of these are expressed as time windows, see Melachrinoudis et al. (2007), Parragh et al. (2009), Cordeau (2006), Rekiek et al. (2006).

Other constraints define deviations from the desired or promised time at origin or destination like in the works of Jorgensen et al. (2007), Melachrinoudis et al. (2007).

The quality of service is sometimes specified by a maximum ride time and total travel time like in the work of Diana (2004), a deviation between the ride time and the direct travel time as in the contribution of Wolfler Calvo and Colorni (2007), the total waiting time (during the ride or before the pickup) as it is stated in Diana (2004), Jorgensen et al. (2007). The maximum or excess ride time (Jorgensen et al. 2007) and the delay between the call and the delivery time (Wilson et al. 1976), can also help to measure the level of quality of service. The maximum number of stops during the customer route has also been identified by Armstrong and Garfinkel (1982), as a parameter to measure the quality of service. Whatever the dimension of quality by perception or specification, Paquette et al. (2009), outpointed the favor of combining them into a single DARP model. This is intended to find a trade-off between costs and service quality.

1.2 Motivation, Objectives, and Methodology Used for This Survey

Few research works are addressing the specification of services offered to customers according to their preferences. This topic has started to emerge recently (since 2015). The recent work that emphasized this scope is that of Molenbruch et al. (2017a), which highlights the operational effects of the variations in the level of quality of service for the Dial-a-Ride Problem. As compared with this review and the one of Ho et al. (2018b), our focus and research directions are not similar. We specify our research on advanced services in DARPs like real-life characteristics, new customers preferences, innovative services quality, and decision- making systems. Then, we zoom on customer-based approaches in terms of customers’ expectations of nowadays and their effects on TOD systems. We also focus more on resolution methods improving the service quality aspect in dial-a-ride services and diverse trade-offs between costs and service quality. We emphasize on applications where balancing costs and service quality should be considered as insights. For our research review, we accessed Elsevier and Google Scholar databases using the keywords dial-a-ride, on demand transport, on demand mobility, demand responsive transport, service quality, and dial-a-ride services. A total of sixty publications since 2003, were considered with the biggest contribution published in Computers and Operations Research, Transportation Research Part B, Transportation Science, European Journal of Operational Research, Operations Research Letters, Public Transport, and Transportation Research Part C.

Our survey is organized as follows. Section 2 reviews the variants of DARPs, giving the main applications found in the literature. The next section reviews the different ways through which service quality is expressed in customer-oriented DARPs models either in static or dynamic frameworks. A survey on the existing resolution methods and benchmark instances is provided in Sect. 4. A discussion on the literature review is given in the next section, as well as perspectives for future researches. Finally, the conclusion is set.

2 Classical Dial-A-Ride Problem

2.1 Relevant Variants

DARPs have been extensively studied in the literature. Many variants are provided in Cordeau and Laporte (2007), to deal with various routing transportation situations depending on static or dynamic environments involving a single or multiple vehicles. If all data necessary for the decision-making are provided before the start of the operations, the DARP is considered as static. But, if some decisional information arises during the operations, the problem is considered dynamic. A recently reviewed classification can also be found in Ho et al. (2018b), where it was argued that either in the static or dynamic class, a DARP may be treated as deterministic or stochastic. At the decision time, information is known with certainty in a deterministic DARP, while it is unknown or uncertain in a stochastic DARP. Numerous works are found in the literature where DARP was differently modeled and solved. But the largest set of DARP studies is related to static frameworks. In this survey, we propose to highlight the customer service quality while respecting the general DARP classification of Ho et al. (2018b). Quality of service in dial-a-ride operations is studied in Paquette et al. (2009). This latter work outpoints the need for aligning the customer requirements with the specifications of DARP models. The first model which established the relationship between operational costs and service quality was proposed in Paquette et al. (2007). The common and the general quality specifications used by operations researchers are related to time windows and maximum user ride time. Thus, the optimization of the quality of service can be one of the multiple DARP objectives.

Several trade-offs between conflicting criteria are expressed through mono-objective, bi-objective, and multi-objective models. But the largest number of studies was concerned by mono-objective models with multi-criteria decision variables like in Jorgensen et al. (2007), Melachrinoudis and Min (2011), Parragh (2011), Paquette et al. (2013), Lehu et al. (2014). The aim in Jorgensen et al. (2007) was to minimize the objective function through two measures: low costs and a high level for the quality of service for the customers which is proportional to the total excess ride time and total waiting time. In Paquette et al. (2013), the objective consisted in minimizing the total routing costs and the penalties on waiting times when users are aboard. Authors in Melachrinoudis and Min (2011), proposed a multi-depot, multi-vehicle, double request DARP in a healthcare organization. The objective consists of minimizing a weighted sum of the total costs, total client inconvenience times, and the extent of earliness due to a client delivery before service and a late pickup after service. To define the interaction between operational costs and quality of service for users, Lehu et al. (2014), proposed high weights for elements which are related to either vehicle operator preferences or users preferences.

In this paper, the aim is to review the different ways through which service quality is expressed in customer-oriented DARPs models either in static or dynamic frameworks.

2.2 Applications and Benchmarks of DARPs

Numerous applications of DARP are found in the literature either in artificial or real-life studies. Major earliest DARP applications used artificial benchmark instances like the ones of Cordeau et al. (2006), having as main objective the minimization of cost. However, recent DARP applications are motivated by real-life cases. To better address such real problems, real-life benchmark instances have been set up by Chassaing et al. 2016 in Instances of Chassaing (2016). The main and traditional applications focus on elderly and disabled persons like in the works of Faria et al. (2010), Masson et al. (2014), transportation, health care transportation services, transport complementary to public transport, and private on demand mobility.

The first integrated DARP is proposed by Hll et al. (2009), where some part of each request may be performed by an existing fixed route service and the design of integrated routes is the key for this kind of on demand responsive service. Recent related works are proposed by Posada et al. (2017), Ma et al. (2019). Health care transportation services have a focus on various vehicles capacities and prioritized requests in the works of Beaudry et al. (2010), Tlili et al. (2018), Jlassi et al. (2012), Melachrinoudis and Min (2011).

The problem of vehicle reconfiguration to ensure the transportation to various persons is addressed by Cappart et al. (2018), Detti et al. (2017), Molenbruch et al. (2017b), Qu and Bard (2015). Demand responsive transportation which may replace unavailable public transportation services for low demand periods are treated by Mulley and Nelson (2009).

DARPs are tackled for providing services to specific facilities such as airports, markets, public places or to specific areas such as employment areas and service areas such as in the case provided by Enrique Fernindez et al. (2008). Then private on demand mobility is an application of DARPs which allows connecting private drivers and passengers through an integrated platform for mobility, see the papers of Çetin (2017) and Li et al. (2019). This kind of on demand responsive application provides an alternative to private cars in urban mobility.

3 Customer Service Quality in DARPs

The relationship between the service level criteria on operational costs is seriously highlighted in Molenbruch et al. (2017c). The authors stated that the variations in the level of service provided, impact the operational DARP results. To show several levels of trade-offs, they investigate 78 different scenarios for service quality. They are based on maximum deviation from the user’s preference time and relative maximum exceedance of the direct ride time. However, the analysis is limited to artificial instances of Cordeau and Laporte (2003b), and cannot be assumed in real-life applications of TOD. The main focus of the service level scenarios is the establishment of a decision system. It will be able to select the appropriate scenario for a specific operating context according to customer preferences. Based on users’ preferences, Molenbruch et al. (2017c), outpointed two relevant specifications in DARP services which directly influence the service level experience. Firstly, the time windows width at the pickup and delivery locations is a parameter which helps to measure the allowed deviation from the user’s preferred departure or arrival time. Consequently, it influences the waiting time for a user. Secondly, the maximum user ride time is a maximal bound of the direct ride time related to a vehicle’s tour. This bound corresponds to the time spent by a user aboard a vehicle and can be used for defining successive time windows.

Furthermore, in the classical DARP of Cordeau and Laporte (2003b), the maximum ride time is defined as a common bound for all users. However, Molenbruch et al. (2017c), antagonize such an assumption by explaining that the ride time is highly customer related and contributes in neglecting a possible vehicle’s detour. Thus, the authors define a direct ride time for each user. In what follows, we review the contribution of the literature in the static environment.

3.1 Customer Service Quality in Static DARPs

User inconvenience is commonly expressed by the time spent aboard a vehicle. To model such inconvenience time, authors are attributing customer related maximal ride times as restrictions from a customer-oriented quality of service viewpoint. The maximum ride time is restricted for each customer see Parragh et al. (2009), Molenbruch et al. (2017b), Chassaing et al. (2016) and used to provide time windows. In the problem of Parragh et al. (2009), a request is split into a set of persons’ groups and has a revenue. The objective is to maximize the total profit which is equal to the total revenue minus the total cost. Time windows are redefined for only the delivery location using a service time (the time needed to enter and leave a vehicle), a transit time, and a maximal ride time. A cooperative dial-a-ride service was studied in Molenbruch et al. (2017b), as a multi-depot DARP where a request can be exchanged through transportation service providers. The aim of this cooperation is the minimization of the overall routing costs for a system involving multiple service providers. The customized maximal ride time is also bounded by a maximal common ride time for all requests. Moreover, time windows are imposed for each request at the pickup. The results indicated that the benefits of this horizontal cooperation are enhanced by a decrease in the width of the customers time windows. A DARP variant of Chassaing et al. (2016), consists of minimizing travel costs. Constraints on maximal ride time and time windows are aligned to those of Cordeau and Laporte (2003b), with a more restriction on the maximal ride time. Three measures are suggested for the solution quality which are the total duration, the total riding time, and the total waiting time.

Time windows width is a factor which helps in decision-making systems. Different scenarios of variations in the quality of service are defined as multi-criteria models (Markovi et al. 2015). Markovi et al. (2015) proposed a mobile resource management system which manages Dial-A-Ride services. Time windows and route duration are factors that considerably influence operator costs and service quality through diverse demand distributions. Thus, their constraints relaxation has led to an operating cost decrease and fewer vehicles needed for transportation. The objective was to minimize fixed and variable trip outsourcing costs. The obtained results explain the trade-offs between quality of service and various system characteristics helping in decision-making. As it is outpointed, a larger width of time windows provides more flexibility to system provider, but a lower level of service for customers. The need for redefining time windows was outpointed in the work of Hu and Chang (2015), explaining the correlation between ride time and time windows. Indeed, the time windows width significantly influences the users’ ride time: its increase negatively impacts the service quality in terms of the ride and a decrease of the width increases the level of customer service quality. Ho et al. (2018a) addressed a static dial-a-ride problem. This is performed by a time window adjustment using a method of relaxation. The objective consists of minimizing the travel costs under constraints such as vehicle capacity, time window, ride time, and route duration. These constraints are penalized in the objective function. A maximal ride time is offered for all requests and it is used to bound the related ride time of each request. Moreover, the adjustment of the time windows is made by the use of some parameters such as the maximal ride time of all users, the beginning of service, and old bounds of time windows. As stated by Molenbruch et al. (2017b), to enhance a flexible strategy while deciding in the cooperative requests’ exchange, all information on customer requests should be shared. The authors outlined that other operational characteristics should also contribute to the decision-making strategy such as the heterogeneity of customers, as well as their expectations.

To the best of our knowledge, the only one model of DARP which addresses customer service quality deeper is that of Nasri and Bouziri (2017). The aim was to minimize the travel costs through more customized vehicles routing plans in a static framework. Their model includes customers-dependent constraints which give more specification and adequacy to passengers. Two terms are suggested in the objective function: a total travel time for all vehicles routes and a penalty for time windows violations. Both time windows on pickup and delivery are redefined and adjusted taking into consideration minimal values for upper bounds and maximal values for lower bounds. For each bound computation, two values are suggested: the initial supposed bound and the new customized-bound. The customers’ expectations include for each request related parameters such as the customer-dependent maximal ride time, the related customer service time, the travel time between origin, and destination of a request.

3.2 Customer Service Quality in Dynamic DARPs

Given the complex nature of dynamic DARPs as compared with static DARPs, and considering the customer-oriented quality of service, few contributions were found. There are only two dynamic DARPs which address the customer service quality, the ones of Wong et al. (2014), Carotenuto and Martis (2017) through the definition of a maximal ride time. In the dynamic and stochastic DARP of Wong et al. (2014), the requests’ arrivals are defined by a Poisson distribution function without considering any external condition such as the weather, congestion or blocked routes. The objective was to minimize the operational costs in terms of the number of vehicles used and the total distance traveled satisfying service quality-related constraints. They include a customer-dependent maximal ride time and desired time windows. The maximal ride time depends on the urgency of a request for transportation and a maximum acceptable time needed by a passenger for waiting at the pickup location.

The service quality level is enhanced in the work of Carotenuto and Martis (2017), through a good-quality requests’ schedule and provides a fast users’ satisfaction by a dynamic insertion of the requests. The objective consists of minimizing the variance between the desired and effective time of the requests for pickup and delivery. To improve the user convenience, a redefinition of the maximal ride time is based on the redefinition of the delivery time taking into account the minimal travel time between the pickup and the delivery plus a constant function of time.

4 Resolution Methods for Customer-Oriented DARPs

The choice of a resolution method depends strongly on the nature of the problem treated. It can be an exact method like the branch and bound (Serrano et al. 2013; Bennekrouf et al. 2013), or other branching methods (Amroun et al. 2016). For larger sized problems metaheuristics like local search methods, evolutionary techniques (Aggoune-Mtalaa and Aggoune 2014), or hybridized ones (Rezgui et al. 2017, 2018), are more appropriate. In this section, we will follow the classification given in Ho et al. (2018b), for solving customer-oriented DARPs with exact, heuristics, and metaheuristic methods.

4.1 Exact Methods

In this part of the study, we focus on exploring a set of related works proposed for DARPs with the emphasis on measuring the quality of service for the customer. Given the high complexity of dynamic and real-life DARPs, there are no exact resolutions proposed for such problems. The dynamic nature of the problem increases the complexity at such an extent that it makes its exact resolution timely impossible. Moreover, dynamic instances do not exist in the literature, and those which are found are modified according to the problem framework.

There is a work which addresses a stochastic and deterministic DARP in Heilporn et al. (2011), using a Branch and Cut algorithm. The arrival of customers is distributed according to probabilistic delays. For each customer, a maximal ride time is defined according to his travel time and an adjusted time windows. The stochastic nature of the problem increases the complexity, which avoids its exact resolution.

The majority of exact methods are dedicated to static and deterministic DARPs. This fact is due to the complexity of realistic DARP instances, especially for high sized instances. Therefore, the exact methods are generally used for artificial instances since it is too complicated to solve real-life cases exactly. Besides, an exact resolution is limited to problems of small size with a fixed computational time. There are few studies where a customer service quality is introduced, especially for the maximal ride time, see for instance Braekers et al. (2014), Parragh et al. (2015). In Parragh et al. (2015), authors introduced more real-life features to the instances of Cordeau and Laporte (2006), and more restrictions to the time windows computation. Their experimentation have shown that the exact resolution is optimal within 4 h on large artificial benchmarks, which is not the case for instances with some real-life and customized distances measurements.

4.2 Heuristics

As discussed previously, finding optimal solutions to complex DARPs is computationally intractable or difficult. Heuristics are methods designed for specific problems which produce a good solution to the problem without guaranteeing an optimum. Moreover, heuristics may be used to construct initial solutions for DARPs or to investigate the problem. Moreover, several heuristics may be combined in a single algorithm in order to produce efficient solutions for DARP such as in Luo and Schonfeld (2007). The authors proposed an insertion heuristic for solving a static multi-vehicle Dial-A-Ride Problem. The heuristic was based on a rejection of infeasible requests’insertion and their reinsertion into the best position. All related request operations are evaluated and improved with respect to all DARP constraints and the optimization of the global objective function. The aim was the minimization of the number of vehicles used for satisfying all requests with service quality-related constraints. Thus time windows constraints are designed considering the desired pickup and delivery time for each customer and a customized maximal ride time. The efficiency of the problem is shown through tests on randomly generated problems. An insertion-based heuristic was provided for solving a DARP with customized constraints in Markovi et al. (2015). The heuristic was based on the parallel insertion heuristic of Jaw et al. (1986). Some customer-oriented constraints are improved to fulfill various users requirements. The heuristic was implemented and compared to the exact method of Cordeau and Laporte (2006), on their benchmark instances (Instances of Cordeau 2006). Results were compared to known best solutions and were competitive on only small instances. To cope with customer-oriented and other real-life features of the problem, a mobile resource management system was implemented for a broader analysis. It provides a decision-making tool using various operational scenarios allowing the analysis of trade-offs between service quality level and some provider system parameters (time windows width, fleet needed for fulfilling the requests, distribution of demand over time, vehicle capacity).

More adapted algorithms for DARPs with customer service quality highlighted the need to design specific methods, see Wong et al. (2014), Carotenuto and Martis (2017). A double dynamic fast algorithm to solve a multi-vehicle Dial-A-Ride Problem in a dynamic framework is proposed in Carotenuto and Martis (2017), to cope with future demand through several degrees of dynamism.

4.3 Metaheuristic Methods

This section presents metaheuristic based approaches dedicated to customer-oriented transport on demand problems. We emphasize on the papers which proposed metaheuristics for problems including customer-oriented quality of service aspects. Cordeau and Laporte (2003b) and Molenbruch et al. (2017b) investigated local search approaches. More precisely, a Tabu Search (TS) was proposed by Cordeau and Laporte (2003b), and was applied with success on static DARP instances.

Several works are based on the Tabu Search of Cordeau and Laporte (2003b), which was adapted to new real-life DARP applications. That of Ho et al. (2018a), was designed for a customer-oriented DARP framework. The new TS was enhanced and compared to that of Cordeau and Laporte (2003b), and tested on their instances (Instance of Cordeau 2003). Results showed that with the redefinition of time windows through a constructive heuristic, a high quality of solutions in term of costs and run time is provided.

A large neighborhood search algorithm of Molenbruch et al. (2017b), outperformed best known solutions of DARP tests on modified instances of Cordeauand Laporte (2006) (Instances of Cordeau 2006). More real-life customers requirements are introduced to cope with unpredictable cases in such TOD problems. The adding computational efforts are guaranteed by the local search technique including additional specific operators to address specific customers’ needs. To enhance the search in promising regions, a diversification mechanism has been periodically repeated.

To solve large instances of the multi-depot DARP with heterogeneous users and vehicles, a deterministic simulated annealing metaheuristic was firstly proposed providing an upper bound for the problem, see Braekers et al. (2014). A set of local search operators were investigated. Three modified sets of benchmark instances of Parragh (2011), were used and efficiently solved.

Another work is that of Chassaing et al. (2016), which is related to an evolutionary local search-based approach. Six operators are managed through dynamic probabilities in the local search. This method was proposed for solving the classic DARP of Cordeau and Laporte (2003b), with a customer-oriented maximal ride time and used as a resolution method for recent real-life instances of Instances of Chassaing (2016). Results are obtained using 20 instances introduced by Cordeau and Laporte (Instance of Cordeau 2003), where the Tabu Search is the resolution method. To better analyze the provider’s cooperation, more real-life characteristics are added to the artificial instances.

5 Discussion and Prospects

In most of the works, a common objective of the DARP is considered from the service provider perspective. The aim is to minimize costs involved by the total transportation time, total distance traveled by the vehicles, total route duration, and the number of vehicles required. These costs are enriched by operational costs for measuring the quality of service in the objective function. These costs are related to the inconvenience felt by the passengers mainly those related to the total ride time and the waiting time. Since the objective functions are diverse and depend on the problem addressed and its field of application, the ways of seeking a compromise between operational costs and the level of quality offered to customers are also multiple. In some works the terms of quality of service translated in time windows and maximal ride time are expressed in the form of constraints like in the works of Wong et al. (2014) and Chassaing et al. (2016). In this kind of problem, the service level is implicit since it translates the satisfaction of these constraints impacting the costs.

As it is stated by Paquette et al. (2012), the improvement of the service quality in dial-a-ride problems relies on its good integration and design within optimization models. They also underline the fact that a reliable measurement scale of the quality must first be set and then integrated through a multi-criteria optimization model. In this way, a trade-off between costs and service quality is feasible and would help provide optimal routing schedules maintaining a certain level of quality. However, improving quality through such decision-making systems is not enough. In our personal view, the customization of the quality of service deals with a higher level of satisfaction of the customer. This can be possible by using service quality parameters modeled in accordance with customers expectations. Therefore, artificial instances need modifications to be used for such customer-dependent modeling problems. Few real data exist to test customer-dependent modeling except that of Chassaing et al. 2016 (Instances of Chassaing 2016). Moreover, the maximal ride time is hugely customer-dependent, see Molenbruch et al. (2017c), and should be designed for each customer in a problem. There are a few and recent related works which consider this assumption. The maximal ride time was used for the time windows redefinition for all users, see the works of Ho et al. (2018a). The investigation of a customized maximal ride time in the time windows redefinition is a new trend over the recent years followed by Parragh et al. (2015), Markovi et al. (2015), and Nasri and Bouziri (2017). In Parragh et al. (2015), service time and maximal ride time are related to each customer and used for redefining time windows bounds on destination with the consideration of the bounds on the pickup time windows. However, only time windows on the delivery locations are redefined according to some customers expectations. With this concern, time windows on the pick up will not be adjusted to the customer’s desired time of pickup. Besides, more customized features should be addressed and considered through time windows setting since they are considered as the main factors influencing service quality in Markovi et al. (2015), and user inconvenience Parragh et al. (2015).

Time windows width is a factor which also helps in decision maker system (Molenbruch et al. 2017b; Markovi et al. 2015). Therefore, all information on customer requests should be incorporated through a decision-making system, as well as the heterogeneity of customers and their expectations. Therefore, the redefinition of both time windows on origin and time window on destination should be considered in any customer-oriented model. This attempt of taking into account the customers’ preferences while satisfying their requests enhances the DARP costs minimization. For instance, the trade-off between service provider costs and customers service quality level could be handled through a multi-objective optimization framework to properly examine the different objective function terms and their importance depending on the problem specificity and real-world experimentation for further decision-making.

Regarding the customized DARP resolution, it was outpointed that more customized features of the problem do not lead to high cost. However, the real-life character of the applications or instances tested increases the complexity of an exact search for the optimal solution mainly for large instances.

The role of heuristics in the resolution of DARP is often to build a first initial solution for a more complex method or seek a better final solution to the problem. They contribute in obtaining good results in an acceptable computational time. Given their problem dependency, they are adapted for addressing customized problems.

Despite the great importance of dynamic realistic applications of DARP, no metaheuristic method was provided for DARPs integrating the customer-oriented quality of service (Agatz et al. 2012). To cope with new frameworks for dynamic DARPs, enhanced method should be considered as for instance evolutionary ones and hybridized metaheuristics.

6 Conclusion

To enhance the practical applicability of DARPs within the Transport On Demand domain, researchers are more and more focusing on problem variants that adopt additional real-life characteristics. In this survey, we emphasize the need for assessing new service quality levels defined from a customer-oriented approach coping with customer expectations of nowadays. Dial-a-ride services involve many interactions with customers and their perceptions of the service. Ideally, a model of the dial-a-ride problem would take into account all customers expectations, as well as adding stochastic factors. However, for practical reasons, uncertainty factors should be integrated through a dynamic model. As described in the survey, some researches have already been done on customized and dynamic models for dial-a-ride services. There are other possible avenues of research like dedicated constraints absorbing new real-life features and new solving methods.