Go to page

Bibliographic Metadata

Restriction-Information
  •  The document is publicly available on the WWW
Links
Files
Classification
Abstract
  • The dial-a-ride problem (DARP) consists of two interrelated tasks: on the one hand, a series of transport requests defined by origin, destination, number of seats as well as time windows and ride time need to be assigned to a set of vehicles routes and on the other hand, vehicle schedules need to be computed, both while minimizing a given objective function. State-of-the-art MILP formulations for the DARP are based on binary variables which indicate whether two locations are visited directly after each other. In contrast to these location-based formulations, we propose the concept of event-based modeling. In the resulting event-based (EB) formulation, capacity, pairing and precedence constraints are implicitly encoded. We show that this formulation outperforms the location-based formulations from the literature. Next, the EB MILP is combined with a location-based formulation into a location-augmented-event-based (LAEB) MILP, whose superiority is proven theoretically and computationally. Under the assumption that time windows imply a unique pairwise ordering of locations and other conditions, the LAEB formulation is integral. Ultimately, the concept of event-based modeling is transferred to the dynamic DARP by iteratively solving the EB formulation in a rolling-horizon algorithm, resulting in optimal insertion positions in 99.5% of all iterations on real-life instances.
Content
Stats
  • The PDF-Document has been downloaded 49 times.
License/Rightsstatement