Theory and methodology
A new extension of local search applied to the Dial-A-Ride Problem

https://doi.org/10.1016/0377-2217(93)E0292-6Get rights and content

Abstract

In this paper we propose a cheap yet effective extension to the traditional local improvement algorithm. We present this extension in the context of the Dial-A-Ride Problem, a variant of the Traveling Salesman Problem. This extension, which we call sacrificing, yields significant improvements over its plain local improvement counterpart without adversely affecting the algorithm's running time.

References (24)

  • H.N. Psaraftis

    k-Interchange procedures for local search in a precedence-constrained routing problem

    European Journal of Operational Research

    (1983)
  • M.W.P. Savelsbergh

    An efficient implementation of local search algorithms for constrained routing problems

    European Journal of Operational Research

    (1990)
  • J.L. Bentley

    Experiments on traveling salesman heuristics

  • F. Bock

    An algorithm for solving ‘traveling-salesman’ and related network optimization problems

  • N.E. Collins et al.

    Simulated annealing: An annotated bibliography

  • G.A. Croes

    A method for solving traveling-salesman problems

    Operations Research

    (1958)
  • C. Friden et al.

    STABULUS: A technique for finding stable sets in large graphs with tabu search

    Computing

    (1989)
  • F. Glover

    Tabu search - Part I

    ORSA Journal on Computing

    (1989)
  • P. Healy

    Rule-based local search in rectangle layout

  • P. Healy

    Sacrificing: An augmentation of local search

  • A. Hertz et al.

    Using tabu search techniques for graph coloring

    Computing

    (1987)
  • D.S. Johnson et al.

    Optimization by simulated annealing: An experimental evaluation, Part 1 (graph partitioning)

    Operations Research

    (1989)
  • Cited by (86)

    • The electric on-demand bus routing problem with partial charging and nonlinear function

      2023, Transportation Research Part C: Emerging Technologies
    • Comparison of anticipatory algorithms for a dial-a-ride problem

      2022, European Journal of Operational Research
    • Proactive shuttle dispatching in large-scale dynamic dial-a-ride systems

      2021, Transportation Research Part B: Methodological
      Citation Excerpt :

      Compared to other types of routing problems, DARP is usually considered for transporting humans with tight time windows, and the capacity of vehicles are mostly binding (Cordeau and Laporte, 2007). The static version of this problem is a well-studied problem in combinatorial optimization (Healy and Moll, 1995). In static DARP, it is assumed that all requests have been realized prior to the routing and scheduling of the fleet.

    • A new bi-objective vehicle routing-scheduling problem with cross-docking: Mathematical model and algorithms

      2020, Computers and Industrial Engineering
      Citation Excerpt :

      Thus, to avoid this violation, vehicle scheduling should be jointly considered in vehicle routing optimization (Chen & Lee, 2009; Chen & Song, 2009). As far as the NP-hardness of the VRPCD and the truck scheduling problem is concerned (Healy & Moll, 1995), it is important to consider an efficient solution method to achieve suitable results. In the relevant literature review, several heuristic algorithms have been developed to identify Pareto solutions and to achieve the best compromise among all objective functions.

    • Pricing and allocation algorithm designs in dynamic ridesharing system

      2020, Theoretical Computer Science
      Citation Excerpt :

      The NP-hardness of DARP has been proved by reducing TSP to it. Thus, our schedule problem is also NP-hard[9]. As have been showed above, allocation and pricing are the most important and basic parts in the ridesharing system which require special and elaborate designs.

    View all citing articles on Scopus
    View full text