On the capacitated vehicle routing problem View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2003-01

AUTHORS

T.K. Ralphs, L. Kopman, W.R. Pulleyblank, L.E. Trotter

ABSTRACT

We consider the Vehicle Routing Problem, in which a fixed fleet of delivery vehicles of uniform capacity must service known customer demands for a single commodity from a common depot at minimum transit cost. This difficult combinatorial problem contains both the Bin Packing Problem and the Traveling Salesman Problem (TSP) as special cases and conceptually lies at the intersection of these two well-studied problems. The capacity constraints of the integer programming formulation of this routing model provide the link between the underlying routing and packing structures. We describe a decomposition-based separation methodology for the capacity constraints that takes advantage of our ability to solve small instances of the TSP efficiently. Specifically, when standard procedures fail to separate a candidate point, we attempt to decompose it into a convex combination of TSP tours; if successful, the tours present in this decomposition are examined for violated capacity constraints; if not, the Farkas Theorem provides a hyperplane separating the point from the TSP polytope. We present some extensions of this basic concept and a general framework within which it can be applied to other combinatorial models. Computational results are given for an implementation within the parallel branch, cut, and price framework SYMPHONY. More... »

PAGES

343-359

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s10107-002-0323-0

DOI

http://dx.doi.org/10.1007/s10107-002-0323-0

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1039204048


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Lehigh University", 
          "id": "https://www.grid.ac/institutes/grid.259029.5", 
          "name": [
            "Department of Industrial and Systems Engineering, Lehigh University, Bethlehem, PA 18017, e-mail: tkralphs@lehigh.edu, http://www.lehigh.edu/\u223ctkr2, US"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ralphs", 
        "givenName": "T.K.", 
        "id": "sg:person.016167704725.20", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016167704725.20"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Cornell University", 
          "id": "https://www.grid.ac/institutes/grid.5386.8", 
          "name": [
            "School of OR&IE, Cornell University, Ithaca, NY 14853, US"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kopman", 
        "givenName": "L.", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "IBM Research \u2013 Thomas J. Watson Research Center", 
          "id": "https://www.grid.ac/institutes/grid.481554.9", 
          "name": [
            "Exploratory Server Systems and The Deep Computing Institute, IBM Research, Yorktown Heights, NY 10598, US"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Pulleyblank", 
        "givenName": "W.R.", 
        "id": "sg:person.015302455656.15", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015302455656.15"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Cornell University", 
          "id": "https://www.grid.ac/institutes/grid.5386.8", 
          "name": [
            "School of OR&IE, Cornell University, Ithaca, NY 14853, e-mail: ltrotter@cs.cornell.edu, US"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Trotter", 
        "givenName": "L.E.", 
        "id": "sg:person.01226662634.19", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01226662634.19"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2003-01", 
    "datePublishedReg": "2003-01-01", 
    "description": "We consider the Vehicle Routing Problem, in which a fixed fleet of delivery vehicles of uniform capacity must service known customer demands for a single commodity from a common depot at minimum transit cost. This difficult combinatorial problem contains both the Bin Packing Problem and the Traveling Salesman Problem (TSP) as special cases and conceptually lies at the intersection of these two well-studied problems. The capacity constraints of the integer programming formulation of this routing model provide the link between the underlying routing and packing structures. We describe a decomposition-based separation methodology for the capacity constraints that takes advantage of our ability to solve small instances of the TSP efficiently. Specifically, when standard procedures fail to separate a candidate point, we attempt to decompose it into a convex combination of TSP tours; if successful, the tours present in this decomposition are examined for violated capacity constraints; if not, the Farkas Theorem provides a hyperplane separating the point from the TSP polytope. We present some extensions of this basic concept and a general framework within which it can be applied to other combinatorial models. Computational results are given for an implementation within the parallel branch, cut, and price framework SYMPHONY.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s10107-002-0323-0", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1047630", 
        "issn": [
          "0025-5610", 
          "1436-4646"
        ], 
        "name": "Mathematical Programming", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "2", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "94"
      }
    ], 
    "name": "On the capacitated vehicle routing problem", 
    "pagination": "343-359", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "babf51dceb15eff07a0ba5f99165af981956fc050595455f28c60f44b51afbc6"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s10107-002-0323-0"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1039204048"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s10107-002-0323-0", 
      "https://app.dimensions.ai/details/publication/pub.1039204048"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-10T17:35", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8672_00000533.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007%2Fs10107-002-0323-0"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s10107-002-0323-0'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s10107-002-0323-0'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10107-002-0323-0'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s10107-002-0323-0'


 

This table displays all metadata directly associated to this object as RDF triples.

88 TRIPLES      20 PREDICATES      27 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s10107-002-0323-0 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N3383568e9bfe4efe96eca791df1134b8
4 schema:datePublished 2003-01
5 schema:datePublishedReg 2003-01-01
6 schema:description We consider the Vehicle Routing Problem, in which a fixed fleet of delivery vehicles of uniform capacity must service known customer demands for a single commodity from a common depot at minimum transit cost. This difficult combinatorial problem contains both the Bin Packing Problem and the Traveling Salesman Problem (TSP) as special cases and conceptually lies at the intersection of these two well-studied problems. The capacity constraints of the integer programming formulation of this routing model provide the link between the underlying routing and packing structures. We describe a decomposition-based separation methodology for the capacity constraints that takes advantage of our ability to solve small instances of the TSP efficiently. Specifically, when standard procedures fail to separate a candidate point, we attempt to decompose it into a convex combination of TSP tours; if successful, the tours present in this decomposition are examined for violated capacity constraints; if not, the Farkas Theorem provides a hyperplane separating the point from the TSP polytope. We present some extensions of this basic concept and a general framework within which it can be applied to other combinatorial models. Computational results are given for an implementation within the parallel branch, cut, and price framework SYMPHONY.
7 schema:genre research_article
8 schema:inLanguage en
9 schema:isAccessibleForFree true
10 schema:isPartOf N1b6005dd1b3345178c8e87c938bbf29d
11 N628e7bc42d4f40679bf5dd6cb356e764
12 sg:journal.1047630
13 schema:name On the capacitated vehicle routing problem
14 schema:pagination 343-359
15 schema:productId N576f9e26cbf4450d8ba0e270e14f85aa
16 Ne74f4b9ab1434d8e956c3f22842c836d
17 Nf04c108aca1e4be0a10872b83b53b3f7
18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039204048
19 https://doi.org/10.1007/s10107-002-0323-0
20 schema:sdDatePublished 2019-04-10T17:35
21 schema:sdLicense https://scigraph.springernature.com/explorer/license/
22 schema:sdPublisher Nef02c2e55b614024ac359778249e94d5
23 schema:url http://link.springer.com/10.1007%2Fs10107-002-0323-0
24 sgo:license sg:explorer/license/
25 sgo:sdDataset articles
26 rdf:type schema:ScholarlyArticle
27 N1b6005dd1b3345178c8e87c938bbf29d schema:volumeNumber 94
28 rdf:type schema:PublicationVolume
29 N3383568e9bfe4efe96eca791df1134b8 rdf:first sg:person.016167704725.20
30 rdf:rest Nba3f2cf6093c447a84c492f3a2f49f70
31 N36b54e39d6954ab086b6959db3525f1a rdf:first sg:person.015302455656.15
32 rdf:rest Nb75d3917867c4b0fadeded502b0bc52e
33 N576f9e26cbf4450d8ba0e270e14f85aa schema:name dimensions_id
34 schema:value pub.1039204048
35 rdf:type schema:PropertyValue
36 N628e7bc42d4f40679bf5dd6cb356e764 schema:issueNumber 2
37 rdf:type schema:PublicationIssue
38 Nb75d3917867c4b0fadeded502b0bc52e rdf:first sg:person.01226662634.19
39 rdf:rest rdf:nil
40 Nba3f2cf6093c447a84c492f3a2f49f70 rdf:first Nd8cc2ed31df34fa1826ada80ff0aa131
41 rdf:rest N36b54e39d6954ab086b6959db3525f1a
42 Nd8cc2ed31df34fa1826ada80ff0aa131 schema:affiliation https://www.grid.ac/institutes/grid.5386.8
43 schema:familyName Kopman
44 schema:givenName L.
45 rdf:type schema:Person
46 Ne74f4b9ab1434d8e956c3f22842c836d schema:name doi
47 schema:value 10.1007/s10107-002-0323-0
48 rdf:type schema:PropertyValue
49 Nef02c2e55b614024ac359778249e94d5 schema:name Springer Nature - SN SciGraph project
50 rdf:type schema:Organization
51 Nf04c108aca1e4be0a10872b83b53b3f7 schema:name readcube_id
52 schema:value babf51dceb15eff07a0ba5f99165af981956fc050595455f28c60f44b51afbc6
53 rdf:type schema:PropertyValue
54 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
55 schema:name Information and Computing Sciences
56 rdf:type schema:DefinedTerm
57 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
58 schema:name Computation Theory and Mathematics
59 rdf:type schema:DefinedTerm
60 sg:journal.1047630 schema:issn 0025-5610
61 1436-4646
62 schema:name Mathematical Programming
63 rdf:type schema:Periodical
64 sg:person.01226662634.19 schema:affiliation https://www.grid.ac/institutes/grid.5386.8
65 schema:familyName Trotter
66 schema:givenName L.E.
67 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01226662634.19
68 rdf:type schema:Person
69 sg:person.015302455656.15 schema:affiliation https://www.grid.ac/institutes/grid.481554.9
70 schema:familyName Pulleyblank
71 schema:givenName W.R.
72 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015302455656.15
73 rdf:type schema:Person
74 sg:person.016167704725.20 schema:affiliation https://www.grid.ac/institutes/grid.259029.5
75 schema:familyName Ralphs
76 schema:givenName T.K.
77 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016167704725.20
78 rdf:type schema:Person
79 https://www.grid.ac/institutes/grid.259029.5 schema:alternateName Lehigh University
80 schema:name Department of Industrial and Systems Engineering, Lehigh University, Bethlehem, PA 18017, e-mail: tkralphs@lehigh.edu, http://www.lehigh.edu/∼tkr2, US
81 rdf:type schema:Organization
82 https://www.grid.ac/institutes/grid.481554.9 schema:alternateName IBM Research – Thomas J. Watson Research Center
83 schema:name Exploratory Server Systems and The Deep Computing Institute, IBM Research, Yorktown Heights, NY 10598, US
84 rdf:type schema:Organization
85 https://www.grid.ac/institutes/grid.5386.8 schema:alternateName Cornell University
86 schema:name School of OR&IE, Cornell University, Ithaca, NY 14853, US
87 School of OR&IE, Cornell University, Ithaca, NY 14853, e-mail: ltrotter@cs.cornell.edu, US
88 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...