K-Interchange Procedures For Local Search In A Precedence-Constrained Routing Problem

Research output: Contribution to journalJournal articleResearchpeer-review

163 Downloads (Pure)


We develop k-interchange procedures to perform local search in a precedence-constrained routing problem. The problem in question is known in the Transportation literature as the single vehicle many-to-many Dial-A-Ride Problem, or DARP. The DARP is the problem of minimizing the length of the tour traveled by a vehicle to service N customers, each of whom wishes to go from a distinct origin to a distinct destination. The vehicle departs from a specified point and returns to that point upon service of all customers. Precedence constraints in the DARP exist because the origin of each customer must precede his/her destination on the route. As in the interchange procedure of Lin for the Traveling Salesman Problem (TSP), a k-interchange is a substitution of k of the links of an initial feasible DARP tour with k other links, and a DARP tour is k-optimal if it is impossible to obtain a shorter tour by replacing any k of its links by k other links. However, in contrast to the TSP where each individual interchange takes O(1) time, checking whether each individual DARP interchange satisfies the origin-destination precedence constraints normally requires O(N2) time. In this paper we develop a method which still finds the best k-interchange that can be produced from an initial feasible DARP tour in O(Nk) time, the same order of magnitude as in the Lin heuristic for the TSP. This method is then embedded in a breadth-first or a depth-first search procedure to produce a k-optimal DARP tour. The paper focuses on the k = 2 and k = 3 cases. Experience with the procedures is presented. in which k-optimal tours are produced by applying a 2-opt or 3-opt search to initial DARP tours produced either randomly or by a fast O(N2) heuristic. The breadth-first and depth-first search modes are compared. The heuristics are seen to produce very good or near-optimal DARP tours.
Original languageEnglish
JournalEuropean Journal of Operational Research
Issue number4
Pages (from-to)391-402
Number of pages12
Publication statusPublished - 1983
Externally publishedYes


Dive into the research topics of '<i>K</i>-Interchange Procedures For Local Search In A Precedence-Constrained Routing Problem'. Together they form a unique fingerprint.

Cite this