Analyses of advanced iterated tour partitioning heuristics for generalized vehicle routing problems

Anupam Seth*, Diego Klabjan, Placid M. Ferreira

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

Theoretical analyses of a set of iterated-tour partitioning vehicle routing algorithms applicable to a wide variety of commonly used vehicle routing problem variants are presented. We analyze the worst-case performance of the algorithms and establish tightness of the derived bounds. Among other variants, we capture the cases of pick-up and delivery and multiple depots. We also introduce brand new concepts such as mobile depots, partitioning of customer nodes into groups, and potential opportunistic under-utilization of vehicle capacity by only partially loading the vehicle, among others, which arise from a printed circuit board application. The problems studied are of critical importance in many practical applications.

Original languageEnglish (US)
Pages (from-to)290-308
Number of pages19
JournalNetworks
Volume61
Issue number4
DOIs
StatePublished - Jul 1 2013

Keywords

  • approximation algorithms
  • printed circuit board
  • vehicle routing
  • worst-case analysis

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'Analyses of advanced iterated tour partitioning heuristics for generalized vehicle routing problems'. Together they form a unique fingerprint.

Cite this