Aggregating courier deliveries. Steele, P., Henderson, S. G., & Shmoys, D. B. Naval Research Logistics, 65(3):187-202, 2018.
Aggregating courier deliveries [link]Paper  abstract   bibtex   
We consider the problem of efficiently scheduling deliveries by an uncapacitated courier from a central location under online arrivals. We consider both adversary-controlled and Poisson arrival processes. In the adversarial setting we provide a randomized $\paren{3 β Δ / 2 δ - 1 }$-competitive algorithm, where $β$ is the approximation ratio of the Traveling Salesman Problem, $δ$ is the minimum distance between the central location and any customer, and $Δ$ is the length of the optimal Traveling Salesman tour over all customer locations and the central location. We provide instances showing that this analysis is tight. We also prove a $1 + 0.271 Δ / δ$ lower-bound on the competitive ratio of any algorithm in this setting. In the Poisson setting, we relax our assumption of deterministic travel times by assuming that travel times are distributed with a mean equal to the excursion length. We prove that optimal policies in this setting follow a threshold structure and describe this structure. For the half-line metric space we bound the performance of the randomized algorithm in the Poisson setting, and show through numerical experiments that the performance of the algorithm is often much better than this bound.
@article{stehenshm16,
	abstract = {  We consider the problem of efficiently scheduling deliveries by an
  uncapacitated courier from a central location under online
  arrivals. We consider both adversary-controlled and Poisson arrival
  processes. In the adversarial setting we provide a randomized
  $\paren{3 \beta \Delta / 2 \delta - 1 }$-competitive algorithm,
  where $\beta$ is the approximation ratio of the Traveling Salesman
  Problem, $\delta$ is the minimum distance between the central
  location and any customer, and $\Delta$ is the length of the optimal
  Traveling Salesman tour over all customer locations and the central
  location. We provide instances showing that this analysis is
  tight. We also prove a $1 + 0.271 \Delta / \delta$ lower-bound on
  the competitive ratio of any algorithm in this setting. In the
  Poisson setting, we relax our assumption of deterministic travel
  times by assuming that travel times are distributed with a mean
  equal to the excursion length. We prove that optimal policies in
  this setting follow a threshold structure and describe this
  structure. For the half-line metric space we bound the performance
  of the randomized algorithm in the Poisson setting, and show through
  numerical experiments that the performance of the algorithm is often
  much better than this bound. },
	author = {Patrick Steele and Shane G. Henderson and David B. Shmoys},
	date-added = {2016-03-17 17:07:15 +0000},
	date-modified = {2018-09-07 02:21:35 +0000},
	journal = {Naval Research Logistics},
	number = {3},
	pages = {187-202},
	title = {Aggregating courier deliveries},
	url_paper = {https://rdcu.be/4Cfy},
	volume = {65},
	year = {2018}}
Downloads: 0
About
Documentation
Keywords
Search
Users
Terms and Conditions of Use
Privacy Policy
Sitemap
© BibBase.org 2021