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 language | English (US) |
|---|---|
| Pages (from-to) | 290-308 |
| Number of pages | 19 |
| Journal | Networks |
| Volume | 61 |
| Issue number | 4 |
| DOIs | |
| State | Published - Jul 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