Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
Simple Temporal Problems in Route Scheduling for the Dial–a–Ride Problem with Transfers
verfasst von : Renaud Masson, Fabien Lehuédé, Olivier Péton
Erschienen in: Integration of AI and OR Techniques in Contraint Programming for Combinatorial Optimzation Problems
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The Dial–A–Ride Problem (DARP) consists in defining a set of routes that satisfy transportation requests between a set of pickup points and a set of delivery points. This paper addresses a variant of the DARP where requests can change of vehicle during their trip. This transshipment is made on specific locations called “transfer points”. The corresponding problem is called the Dial–A–Ride Problem with Transfers (DARPT). Solving the DARPT yields modeling and algorithmic difficulties. In this paper, we focus on efficiently checking the feasibility of routes with regards to the problem temporal constraints in a Large Neighborhood Search. This feasibility problem is a Simple Temporal Problem, well studied in particular in Artificial Intelligence [8]. We propose necessary and sufficient conditions to fasten the detection of unfeasible or feasible routes.