DROPS

Document

DOI: 10.4230/OASIcs.ATMOS.2021.1

Efficient Duration-Based Workload Balancing for Interdependent Vehicle Routes

Authors: Carlo S. Sartori, Pieter Smet, and Greet Vanden Berghe

Published in: OASIcs, Volume 96, 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)

Abstract

Vehicle routing and scheduling problems with interdependent routes arise when some services must be performed by at least two vehicles and temporal synchronization is thus required between the starting times of these services. These problems are often coupled with time window constraints in order to model various real-world applications such as pickup and delivery with transfers, cross-docking and home care scheduling. Interdependent routes in these applications can lead to large idle times for some drivers, unnecessarily lengthening their working hours. To remedy this unfairness, it is necessary to balance the duration of the drivers' routes. However, quickly evaluating duration-based equity functions for interdependent vehicle routes with time windows poses a significant computational challenge, particularly when the departure time of routes is flexible. This paper introduces models and algorithms to compute two well-known equity functions in flexible departure time settings: min-max and range minimization. We explore the challenges and algorithmic complexities of evaluating these functions both from a theoretical and an experimental viewpoint. The results of this paper enable the development of new heuristic methods to balance the workload of interdependent vehicle routes with time windows.

Cite as

Carlo S. Sartori, Pieter Smet, and Greet Vanden Berghe. Efficient Duration-Based Workload Balancing for Interdependent Vehicle Routes. In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 1:1-1:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{sartori_et_al:OASIcs.ATMOS.2021.1,
  author =	{Sartori, Carlo S. and Smet, Pieter and Vanden Berghe, Greet},
  title =	{{Efficient Duration-Based Workload Balancing for Interdependent Vehicle Routes}},
  booktitle =	{21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
  pages =	{1:1--1:15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-213-6},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{96},
  editor =	{M\"{u}ller-Hannemann, Matthias and Perea, Federico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.1},
  URN =		{urn:nbn:de:0030-drops-148703},
  doi =		{10.4230/OASIcs.ATMOS.2021.1},
  annote =	{Keywords: Vehicle scheduling, Workload balancing, Route duration, Interdependent routes, Time windows}
}

Search Results

Documents authored by Vanden Berghe, Greet

Efficient Duration-Based Workload Balancing for Interdependent Vehicle Routes

Abstract

Cite as

Thanks for your feedback!

Could not send message