Improved bounds for vehicle routing solutions

Agustín Bompadre; Moshe Dror; James B. Orlin

doi:10.1016/j.disopt.2006.04.002

Improved bounds for vehicle routing solutions

Agustín Bompadre, Moshe Dror, James B. Orlin

Research output: Contribution to journal › Article › peer-review

30 Scopus citations

Abstract

We present lower bounds for the vehicle routing problem (VRP) with and without split deliveries, improving the well known bound of Haimovich and Rinnooy Kan. These bounds are then utilized in a design of best-to-date approximation algorithms.

Original language	English (US)
Pages (from-to)	299-316
Number of pages	18
Journal	Discrete Optimization
Volume	3
Issue number	4
DOIs	https://doi.org/10.1016/j.disopt.2006.04.002
State	Published - Dec 1 2006
Externally published	Yes

Keywords

Approximation algorithm
Lower bound
Vehicle routing problem

ASJC Scopus subject areas

Theoretical Computer Science
Computational Theory and Mathematics
Applied Mathematics

Access to Document

10.1016/j.disopt.2006.04.002

Cite this

@article{0d1f0239f5334e17b6367d19744bf47c,

title = "Improved bounds for vehicle routing solutions",

abstract = "We present lower bounds for the vehicle routing problem (VRP) with and without split deliveries, improving the well known bound of Haimovich and Rinnooy Kan. These bounds are then utilized in a design of best-to-date approximation algorithms.",

keywords = "Approximation algorithm, Lower bound, Vehicle routing problem",

author = "Agust{\'i}n Bompadre and Moshe Dror and Orlin, {James B.}",

year = "2006",

month = dec,

day = "1",

doi = "10.1016/j.disopt.2006.04.002",

language = "English (US)",

volume = "3",

pages = "299--316",

journal = "Discrete Optimization",

issn = "1572-5286",

publisher = "Elsevier",

number = "4",

}

TY - JOUR

T1 - Improved bounds for vehicle routing solutions

AU - Bompadre, Agustín

AU - Dror, Moshe

AU - Orlin, James B.

PY - 2006/12/1

Y1 - 2006/12/1

N2 - We present lower bounds for the vehicle routing problem (VRP) with and without split deliveries, improving the well known bound of Haimovich and Rinnooy Kan. These bounds are then utilized in a design of best-to-date approximation algorithms.

AB - We present lower bounds for the vehicle routing problem (VRP) with and without split deliveries, improving the well known bound of Haimovich and Rinnooy Kan. These bounds are then utilized in a design of best-to-date approximation algorithms.

KW - Approximation algorithm

KW - Lower bound

KW - Vehicle routing problem

UR - http://www.scopus.com/inward/record.url?scp=33748463814&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33748463814&partnerID=8YFLogxK

U2 - 10.1016/j.disopt.2006.04.002

DO - 10.1016/j.disopt.2006.04.002

M3 - Article

SN - 1572-5286

VL - 3

SP - 299

EP - 316

JO - Discrete Optimization

JF - Discrete Optimization

IS - 4

ER -

Improved bounds for vehicle routing solutions

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this