English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Dial-a-Ride problems consist of a set V of n vertices in a metric space (denoting travel time between vertices) and a set of m objects represented as source-destination pairs {(si,ti)}mi=1, where each object requires to be moved from its source to destination vertex. In the multi-vehicle Dial-a-Ride problem, there are q vehicles, each having capacity k and where each vehicle j ∈ [q] has its own depot-vertex rj ∈ V. A feasible schedule consists of a capacitated route for each vehicle (where vehicle j originates and ends at its depot rj) that together move all objects from their sources to destinations. The objective is to find a feasible schedule that minimizes the maximum completion time (i.e., makespan) of vehicles, where the completion time of vehicle j is the time when it returns to its depot rj at the end of its route. We study the preemptive version of multi-vehicle Dial-a-Ride, in which an object may be left at intermediate vertices and transported by more than one vehicle, while being moved from source to destination. Our main results are an O(log3n)-approximation algorithm for preemptive multi-vehicle Dial-a-Ride, and an improved O(log t)-approximation for its special case when there is no capacity constraint (here t≤ n is the number of distinct depot-vertices). There is an Ω (log1/4-ε n) hardness of approximation known even for single vehicle capacitated Dial-a-Ride [Gørtz 2006]. For uncapacitated multi-vehicle Dial-a-Ride, we show that there are instances when natural lower bounds (used in our algorithm) are ˜Ω(log t) factor away from the optimum. We also consider the special class of metrics induced by graphs excluding any fixed minor (e.g., planar metrics). In this case, we obtain improved guarantees of O(log2 n) for capacitated multi-vehicle Dial-a-Ride, and O(1) for the uncapacitated problem.

Minimum Makespan Multi-Vehicle Dial-a-Ride