Discrete Optimization
A fast heuristic for solving a large-scale static dial-a-ride problem under complex constraints

https://doi.org/10.1016/j.ejor.2004.09.060Get rights and content

Abstract

This paper presents a heuristic, which concentrates on solving a large-scale static dial-a-ride problem bearing complex constraints. In this heuristic, a properly organized local search strategy and a diversification strategy are used to improve initial solutions. Then the improved solutions can be refined further by an intensification strategy. The performance of this heuristic was evaluated by intensive computational tests on some randomly generated instances. Small gaps to the lower bounds from the column generation method were obtained in very short time for instances with no more than 200 requests. Although the result is not sensitive to the initial solution, the computational time can be greatly reduced if some effort is spent to construct a good initial solution. With this good initial solution, larger instances up to 2000 requests were solved in less than 10 hours on a popular personal computer.

Introduction

In this paper, we consider a kind of dial-a-ride problem (DARP) which involves scheduling a heterogeneous vehicle fleet and a group of drivers with different qualifications based at a single depot to cover the transportation requests of customers. After negotiating with the agency, the customer specifies the pickup time window and the tolerable extra travelling time on the trip. Customers of different types may require different type of accommodations. Each type of vehicle varies in the number and the type of accommodations and it can only be driven by the corresponding qualified drivers. Drivers are under the constraints of the maximum driving duration of one trip, the break time between two successive trips and the upper bound of the accumulated driving time in one servicing horizon (e.g., one day). To the authors’ knowledge, these real life constraints are seldom discussed together in literatures, especially the matching among customers, vehicles and drivers. The aim of the scheduling is to find the least cost trips to serve the maximum number of customers.

The DARP is a generalization of the capacitated pickup and delivery problem with time windows, which was first examined by Wilson et al. (1971). Thereafter, extensive studies were carried out over the past three decades (see the recent reviews of Desaulniers et al., 2002; Cordeau and Laporte, 2002). Since in practice the transportation requests are usually known in advance, most of the work has focused on static DARPs. However, a fast static algorithm is also very helpful for dynamic scenarios, where schedules are adjusted in real time.

Although the DARP is NP-hard (Healy and Moll, 1995), efforts were still made to get exact solutions. Early approaches (Psaraftis, 1980, Psaraftis, 1983a, Psaraftis, 1983b) focused on solving single-vehicle problems using pure dynamic programming (DP) method. Then Desrosiers et al. (1986) introduced the concept of dominance to reduce intermediate states. This technique greatly speeds up the DP process if the problem subjects to strong constraints. Based on this work, some multi-vehicle problems can be exactly solved by the combination of the column generation (CG) method and the branch-and-bound process (Dumas et al., 1991). Instead of using the DP algorithm, some heuristics can also be used to get approximate solutions of the auxiliary subproblem (SP) in the CG framework (Savelsbergh and Sol, 1998; Xu et al., 2003). Thus, this method is capable of approximately solving large-scale and less strongly constrained problems.

Owing to the complexity of the DARP, the most popular approaches are still varieties of heuristics, which are usually characterized with two phases: a construction phase in which an initial schedule is obtained, and a tuning phase in which the solution is improved further.

In the construction phase, the techniques of sequential insertion (Jaw et al., 1986; Nanry and Barnes, 2000; Cordeau and Laporte, 2003) and parallel insertion (Roy et al., 1984a, Roy et al., 1984b; Toth and Vigo, 1997) are commonly used, according to a certain criterion, e.g., the nearest distance or the minimum cost. The concept of cluster first and route second (Bodin and Sexton, 1986) may also be introduced into this step, in which the geographically close customers are grouped together before applying the single vehicle routing algorithm to each cluster. To overcome the difficulty arising from the dispersion of the two locations (pickup and delivery) represented by each customer, the use of mini-clusters is recommended (Dumas et al., 1989; Desrosiers et al., 1991; Ioachim et al., 1995).

In the tuning phase, the solution is improved by some local searches, which consist of intra-trip exchanges and inter-trip exchanges. The intra-trip exchanges adjust the sequence of stops within a single trip. The corresponding algorithms are usually based on Lin’s (1965) λ-opt mechanism, which can be accomplished in O(nλ) time (n is the number of stops in a trip). Several modifications were also developed, such as the algorithms of Lin and Kernighan (1973) and Or (1976). The inter-trip exchanges involve the exchange of stops among multiple trips. The details can be found in the work of Van Breedam (2001) and Kinderwater and Savelsbergh (1997).

Classical heuristics use only some local searches in a descent way, i.e., the value of the objective function at current iteration step is better than those at previous steps. The final result is usually observed as local optimum and is sensitive to the initial solution (Van Breedam, 2001). Modern heuristics, on the contrary, can temporarily accept some worse solutions during the optimization procedure. Thus, it is possible to drive the search out of local optima. The rules for accepting the worse solutions are termed diversifications. And these modern heuristics are often called meta-heuristics, for example, the simulated annealing (SA) (Kirckpatrick et al., 1983), the genetic algorithm (GA) (Holland, 1975), the Ant algorithm (AA) (Dorigo et al., 1991), the Tabu search (TS) (Glover and Laguna, 1997), the guided local search (GLS) (Voudouris and Tsang, 1995), etc. The most popular meta-heuristic used for solving the DARP is probably the TS (Toth and Vigo, 1997; Nanry and Barnes, 2000; Cordeau and Laporte, 2003). By comparing different algorithms (Laporte et al., 2000; Van Breedam, 2001; Tan et al., 2001), it is observed that (1) descent algorithms usually generate local optima in a short time and are sensitive to initial solutions; (2) thanks to the diversification, meta-heuristics can generate ‘global’ optima and are insensitive to initial solutions; (3) meta-heuristics have no stopping criterion (usually stop after a number of iterations) and contain many case-sensitive empirical parameters, which may cause some difficulties for practical implementations.

Although many algorithms have been proposed for solving the DARP over the past three decades, new algorithms are still needed to meet the practical requirements. These new algorithms should be faster, simpler (with fewer empirical parameters) and more robust (Laporte et al., 2000). The goal of our current work is aimed at developing such a heuristic to generate acceptable solutions for large-scale real life applications.

It is noticed that the construction phase usually takes less than 1 second for the problem with hundreds of customers, while the tuning phase is the most time consuming part in the whole solving procedure. Therefore, the quality of the initial schedule and the efficiency of the tuning operation are the two critical aspects that should be concerned when developing a good algorithm. In this paper, a simple initial solution is proposed to give a good starting point, which speeds up the heuristic. And the tuning phase consists of a local search strategy, a diversification strategy and an intensification strategy. The local search strategy involves very simple but properly organized inter-trip exchanges, while the intra-trip exchange is accomplished simultaneously. Moreover, a concept of margin time is introduced to facilitate the local search and determines the starting time of a trip. The efficiency of the diversification strategy is guaranteed by a secondary objective function which points out a promising direction of diversification. Then by evaluating the average wasted cost of a single trip, the intensification strategy excludes some good trips from further refinement. Thus, the remaining trips get some chances to be refined further and many useless explorations are avoided.

The following sections of this paper are organized as: the problem is defined in Section 2; the heuristic is described in Section 3; computational results are detailed in Section 4; final conclusions are drawn in Section 5.

Section snippets

The problem

Practically, customer requests may be classified into outbound trips and inbound trips (Toth and Vigo, 1997). However, these two types of trips are treated as two indifferent requests in this heuristic. Therefore, we take into account only the requests of picking up one customer and delivering him or her to the destination. The depot, the pickup site and the delivery site are represented by a vertex set V = {v0, v1, …, v2n}, where n is the number of requests; v0 is the depot; vi (i = 1, 2, …, n) denotes

The heuristic

Before plunging into the details of this heuristic, how to determine the starting time of a trip should be discussed. It is clear that the earlier to start, the better to avoid violating the time window constraint. A simple way is to set the departure time from the depot as e1st  t0,1st (this time should not be less than e0), where 1st is the number of the first pickup site in the trip. However, it is possible to shrink the waiting time and the total duration of the trip by delaying the starting

Computational experiments

Although DARP has been extensively studied, to the authors’ knowledge, there is no benchmark for the problem with the same constraints considered in this paper. Therefore, our only choice to evaluate this heuristic was comparing the results with the lower bound obtained from the CG method. The CG algorithm adopted here almost follows the work of Dumas et al. (1991). However, small modifications were made, because the problems are different in the objective function and constraints. The modified

Conclusions

This paper presents a fast heuristic, which is dedicated to solving the large-scale static DARP under complex constraints. Intensive numerical experiments reveal that this heuristic is capable of quickly obtaining acceptable results and not sensitive to the initial solution. Moreover, it is flexible to cope with many practical constraints and does not contain any case-sensitive empirical parameter. These good performances are the results of the following techniques:

  • (1)

    The network of the problem is

Acknowledgments

This work is supported by a post-doctoral fellowship granted by the Conseil Regional de Champagne-Ardenne. This support is gratefully acknowledged. Thanks also go to anonymous referees. This paper has been greatly improved according to their valuable comments.

References (38)

  • L.D. Bodin et al.

    The multi-vehicle subscriber dial-a-ride problem

    TIMS Studies in Management Science

    (1986)
  • Cordeau, J.F., Laporte G., 2002. The dial-a-ride problem: Variants, modeling issues and algorithms, Technical report...
  • R. Cordone et al.

    A heuristic for the vehicle routing problem with time windows

    Journal of Heuristics

    (2001)
  • Desaulniers, G., Desrosiers, J., Erdmann, A., Solomon, M.M., Soumis, F., 2002. VRP with pickup and delivery. In: Toth,...
  • J. Desrosiers et al.

    A dynamic programming solution of the large-scale single-vehicle dial-a-ride problem with time windows

    American Journal of Mathematical and Management Sciences

    (1986)
  • Desrosiers, J., Dumas, Y., Soumis, F., Taillefer, S., Villeneuve, D., 1991. An algorithm for mini-clustering in...
  • Dorigo, M., Maniezzo, V., Colorni, A., 1991. The ant system: An autocatalytic optimizing process. Technical report No....
  • Dumas, Y., Desrosiers, J., Soumis, F., 1989. Large scale multi-vehicle dial-a-ride problems. Cahier du GERAD G-89-30,...
  • B. Gillett et al.

    A heuristic algorithm for the vehicle dispatch problem

    Operations Research

    (1974)
  • Cited by (0)

    View full text