Elsevier

Parallel Computing

Volume 30, Issue 3, March 2004, Pages 377-387
Parallel Computing

Parallel Tabu search heuristics for the dynamic multi-vehicle dial-a-ride problem

https://doi.org/10.1016/j.parco.2003.12.001Get rights and content

Abstract

In the Dial-a-Ride problem (DARP) users specify transportation requests between origins and destinations to be served by vehicles. In the dynamic DARP, requests are received throughout the day and the primary objective is to accept as many requests as possible while satisfying operational constraints. This article describes and compares a number of parallel implementations of a Tabu search heuristic previously developed for the static DARP, i.e., the variant of the problem where all requests are known in advance. Computational results show that the proposed algorithms are able to satisfy a high percentage of user requests.

Introduction

The Dial-a-Ride problem (DARP) arises in contexts where n users specify transportation requests between origins and destinations, subject to scheduling constraints. These requests must be satisfied in a cost effective fashion by a fleet of m vehicles, subject to a number of operational constraints. The most common application of the DARP is encountered in door-to-door transportation services for the elderly and the handicapped (see, e.g., Madsen et al. [8], Toth and Vigo [10], [11], and Borndörfer et al. [1]). With the ageing of the population and the need to reduce public expenditures in most western societies, we believe dial-a-ride services will gain in popularity in coming years and the need to run these efficiently will also increase.

Dial-a-ride services operate according to one of two modes. In the static mode all requests are known in advance, typically one day before transportation actually takes place. In the dynamic mode requests are gradually revealed and assigned to existing vehicle routes in real-time so that a priori planning is impossible. In practice, the distinction between these two modes is not always clear cut. Even if planned routes are available, changes may be necessary due to last minute cancellations. Also, in dynamic environments, a large number of requests are often known at the start of the planning horizon. There also exist several versions of the DARP for both modes since the objective, constraints and operating rules vary from one context to another.

In the last 20 years or so, several models and algorithms have been devoted to the DARP. For a recent overview, see Cordeau and Laporte [3]. With a few exceptions, most available algorithms are heuristics. Tabu search (TS)––see, e.g., Cordeau and Laporte [4]––stands out as a very powerful tool for the DARP since it is at the same time highly flexible and efficient. Flexibility stems from the capacity of handling a large number of variants within the same search framework. Efficiency is associated with solution quality. It is now clear that TS is capable of consistently generating high quality solutions on a large variety of routing problems (see, e.g., Cordeau et al. [2]).

On the negative side the running time of TS algorithms can be rather high. Thus, using real data from a Danish transporter (with n=200 and 295), Cordeau and Laporte have run three versions of their TS algorithm. These versions vary in the thoroughness of the exploration of the solution space and yield highly varying running times. The simplest version yielded computing times varying between 13.21 and 28.40 min on a Pentium 4, 2 GHz computer, while the most thorough version required between 104.48 and 267.82 min. The improvement in solution quality between the two versions is almost 6%. There are two reasons why it is important to devise faster algorithms. First, there exist several contexts where the problem size is much larger (the number of requests per day in some European and North-American cities often exceeds 2000). Second, while it makes sense to run an algorithm for a few hours in a static context, much faster response times are required in a dynamic environment (see, e.g., [6] and [7]). In fact whenever a user makes a transportation request by telephone or on the internet, the operating system should be able to tell, within a few seconds, whether the request can be accommodated. In addition, if the request is accepted, it should be embedded in the existing vehicle routes within a relatively short time (no more than ten minutes, say).

One natural way to speed up computation time is through the use of parallel computing. We report on the use of a number of parallel implementations of the Cordeau and Laporte [4] static DARP heuristic in a real-time context. The remainder of this article is organized as follows. In Section 2, we describe the main features of our version of the DARP. This is followed by a summary of the single processor static TS heuristic in Section 3, and by its parallel and dynamic implementations in Section 4. A computational assessment of the parallel and dynamic implementations is presented in Section 5 and conclusions follow in Section 6.

Section snippets

Problem definition

As is often the case in dial-a-ride contexts, users specify an outbound request from their home to a destination (e.g., a hospital) and an inbound request for the return trip. To achieve a fair balance between user convenience and the transporter's cost, we believe users should be able to specify windows on the arrival time of their outbound journey and on the departure time of their inbound journey. The transporter guarantees each user a maximal ride time, i.e., an upper bound on the time

Sequential Tabu search heuristic

The TS algorithm developed by Cordeau and Laporte [4] for the static DARP works as follows. Starting from an initial solution s0, the algorithm moves at iteration t from st to the best solution in a neighbourhood N(st) of st. To avoid cycling, solutions possessing some attributes of recently visited solutions are declared forbidden, or Tabu, for a number of iterations, unless they constitute a new incumbent. As is common in such algorithms, a continuous diversification mechanism is put in place

Dynamic and parallel implementations

Our dynamic and parallel DARP algorithms work as follows. A static solution is constructed on the basis of the requests known at the start of the planning horizon. When a new request arrives, the algorithm performs a feasibility check, i.e., it searches for a feasible solution including the new service request. Once it has been decided whether the new request can be accepted or not, the algorithm performs a post-optimization, i.e., it tries to improve the current solution. In the following the

Computational results

The proposed parallel heuristics were implemented on a cluster of eight PCs, each of which has a Pentium III processor clocked at 700 MHz. Each process was coded in C++ and process communications was handled by the Message Passing Interface (MPI) software [12].

Except for the IP feasibility check, penalty parameters have been set as follows. In the SPMS procedures, parameters δmax, λmax and θmax were set equal to 0.01, 0.005nm and 5log10n, respectively, for the p/2 processors performing

Conclusion

We have developed a number of parallel heuristics for the dynamic DARP, based on a Tabu search previously proposed for the static case. Computational experiments indicate that parallel computing can be beneficial in solving real-time vehicle routing problems. Moreover, the IP mechanism turns out to provide the best results while the choice of the initial static solution seems to be irrelevant. As far as future research is concerned, efforts should be concentrated on incorporating some

Acknowledgments

This research was partially supported by the Italian National Research Council, by the Center of Excellence on High-Performance Computing, University of Calabria, Italy, by a Strategic research grant provided by HEC Montréal, and by the Canadian Natural Sciences and Engineering Research Council under grants 227837-00 and OGP0039682. This support is gratefully acknowledged.

References (12)

  • J.-F. Cordeau et al.

    A Tabu search heuristic for the static multi-vehicle dial-a-ride problem

    Transportation Research B

    (2003)
  • G. Ghiani et al.

    Real-time vehicle routing: solution concepts

    Algorithms and parallel computing strategies, European Journal of Operational Research

    (2003)
  • R. Borndörfer, M. Grötschel, F. Klostermeier, C. Küttner. Telebus Berlin: vehicle scheduling in a dial-a-ride system,...
  • J.-F. Cordeau et al.

    A guide to vehicle routing heuristics

    Journal of the Operational Research Society

    (2002)
  • J.-F. Cordeau et al.

    The dial-a-ride problem: variants, modeling issues and algorithms

    4OR––Quarterly Journal of the Belgian, French and Italian Operations Research Societies

    (2003)
  • T.G. Crainic et al.

    Towards a taxonomy of parallel Tabu search algorithms

    INFORMS Journal on Computing

    (1997)
There are more references available in the full text version of this article.

Cited by (190)

  • Sustainable decisions in a ridesharing system with a tri-objective optimization approach

    2023, Transportation Research Part D: Transport and Environment
  • A machine learning-driven two-phase metaheuristic for autonomous ridesharing operations

    2022, Transportation Research Part E: Logistics and Transportation Review
  • Comparison of anticipatory algorithms for a dial-a-ride problem

    2022, European Journal of Operational Research
View all citing articles on Scopus
View full text