3 years ago

Sweep Algorithms for the Capacitated Vehicle Routing Problem with Structured Time Window.

Christoph Hertrich, Philipp Hungerländer, Christian Truden

The capacitated Vehicle Routing Problem with structured Time Windows (cVRPsTW) is concerned with finding optimal tours for vehicles with given capacity constraints to deliver goods to customers within assigned time windows. In our problem variant these time windows have a special structure, namely they are non-overlapping and each time window holds several customers. This is a reasonable assumption for Attended Home Delivery services. Sweep algorithms are known as simple, yet effective heuristics for the classical capacitated Vehicle Routing Problem. We propose variants of the sweep algorithm that are not only able to deal with time windows, but also exploit the additional structure of the time windows in a cVRPsTW. Afterwards we suggest local improvement heuristics to decrease our objective function even further. A carefully constructed benchmark set that resembles real-world data is used to prove the efficacy of our algorithms in a computational study.

Publisher URL: http://arxiv.org/abs/1901.02771

DOI: arXiv:1901.02771v1

You might also like
Discover & Discuss Important Research

Keeping up-to-date with research can feel impossible, with papers being published faster than you'll ever be able to read them. That's where Researcher comes in: we're simplifying discovery and making important discussions happen. With over 19,000 sources, including peer-reviewed journals, preprints, blogs, universities, podcasts and Live events across 10 research areas, you'll never miss what's important to you. It's like social media, but better. Oh, and we should mention - it's free.

  • Download from Google Play
  • Download from App Store
  • Download from AppInChina

Researcher displays publicly available abstracts and doesn’t host any full article content. If the content is open access, we will direct clicks from the abstracts to the publisher website and display the PDF copy on our platform. Clicks to view the full text will be directed to the publisher website, where only users with subscriptions or access through their institution are able to view the full article.