Ontology type: schema:ScholarlyArticle
1993-06
AUTHORSGerard Cornuejols, Farid Harche
ABSTRACTThe capacitated vehicle routing problem (CVRP) considered in this paper occurs when goods must be delivered from a central depot to clients with known demands, usingk vehicles of fixed capacity. Each client must be assigned to exactly one of the vehicles. The set of clients assigned to each vehicle must satisfy the capacity constraint. The goal is to minimize the total distance traveled. When the capacity of the vehicles is large enough, this problem reduces to the famous traveling salesman problem (TSP). A variant of the problem in which each client is visited by at least one vehicle, called the graphical vehicle routing problem (GVRP), is also considered in this paper and used as a relaxation of CVRP. Our approach for CVRP and GVRP is to extend the polyhedral results known for TSP. For example, the subtour elimination constraints can be generalized to facets of both CVRP and GVRP. Interesting classes of facets arise as a generalization of the comb inequalities, depending on whether the depot is in a handle, a tooth, both or neither. We report on the optimal solution of two problem instances by a cutting plane algorithm that only uses inequalities from the above classes. More... »
PAGES21-52
http://scigraph.springernature.com/pub.10.1007/bf01580599
DOIhttp://dx.doi.org/10.1007/bf01580599
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1023949375
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/1117",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Public Health and Health Services",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/11",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Medical and Health Sciences",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Carnegie Mellon University",
"id": "https://www.grid.ac/institutes/grid.147455.6",
"name": [
"Graduate School of Industrial Administration, Carnegie Mellon University, Schenley Park, 15213-3890, Pittsburgh, PA, USA"
],
"type": "Organization"
},
"familyName": "Cornuejols",
"givenName": "Gerard",
"id": "sg:person.011070022275.03",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011070022275.03"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "New York University",
"id": "https://www.grid.ac/institutes/grid.137628.9",
"name": [
"New York University, New York, USA"
],
"type": "Organization"
},
"familyName": "Harche",
"givenName": "Farid",
"id": "sg:person.013112655251.41",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013112655251.41"
],
"type": "Person"
}
],
"citation": [
{
"id": "sg:pub.10.1007/bf01580109",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1004030153",
"https://doi.org/10.1007/bf01580109"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf01580109",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1004030153",
"https://doi.org/10.1007/bf01580109"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf01582008",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1005195379",
"https://doi.org/10.1007/bf01582008"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bfb0120887",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1006229491",
"https://doi.org/10.1007/bfb0120887"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bfb0120887",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1006229491",
"https://doi.org/10.1007/bfb0120887"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1002/net.3230110209",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1007364559"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf01580734",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1008102426",
"https://doi.org/10.1007/bf01580734"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf01580734",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1008102426",
"https://doi.org/10.1007/bf01580734"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0377-2217(91)90337-u",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1017991079"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0377-2217(91)90337-u",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1017991079"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bfb0120888",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1024358292",
"https://doi.org/10.1007/bfb0120888"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bfb0120888",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1024358292",
"https://doi.org/10.1007/bfb0120888"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1057/jors.1969.75",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1028694763",
"https://doi.org/10.1057/jors.1969.75"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf01582116",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1030377517",
"https://doi.org/10.1007/bf01582116"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/s0304-0208(08)73235-3",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1047260413"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0167-6377(87)90002-2",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1048218240"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0167-6377(87)90002-2",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1048218240"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1057/jors.1976.63",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1050109789",
"https://doi.org/10.1057/jors.1976.63"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1287/moor.11.4.537",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1064723118"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1287/opre.2.4.393",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1064727730"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1287/opre.33.5.1050",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1064729652"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.2307/3008733",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1102672464"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.2307/3009018",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1102735613"
],
"type": "CreativeWork"
},
{
"id": "https://app.dimensions.ai/details/publication/pub.1106882407",
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1002/9781118627372",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1106882407"
],
"type": "CreativeWork"
}
],
"datePublished": "1993-06",
"datePublishedReg": "1993-06-01",
"description": "The capacitated vehicle routing problem (CVRP) considered in this paper occurs when goods must be delivered from a central depot to clients with known demands, usingk vehicles of fixed capacity. Each client must be assigned to exactly one of the vehicles. The set of clients assigned to each vehicle must satisfy the capacity constraint. The goal is to minimize the total distance traveled. When the capacity of the vehicles is large enough, this problem reduces to the famous traveling salesman problem (TSP). A variant of the problem in which each client is visited by at least one vehicle, called the graphical vehicle routing problem (GVRP), is also considered in this paper and used as a relaxation of CVRP. Our approach for CVRP and GVRP is to extend the polyhedral results known for TSP. For example, the subtour elimination constraints can be generalized to facets of both CVRP and GVRP. Interesting classes of facets arise as a generalization of the comb inequalities, depending on whether the depot is in a handle, a tooth, both or neither. We report on the optimal solution of two problem instances by a cutting plane algorithm that only uses inequalities from the above classes.",
"genre": "research_article",
"id": "sg:pub.10.1007/bf01580599",
"inLanguage": [
"en"
],
"isAccessibleForFree": false,
"isPartOf": [
{
"id": "sg:journal.1047630",
"issn": [
"0025-5610",
"1436-4646"
],
"name": "Mathematical Programming",
"type": "Periodical"
},
{
"issueNumber": "1-3",
"type": "PublicationIssue"
},
{
"type": "PublicationVolume",
"volumeNumber": "60"
}
],
"name": "Polyhedral study of the capacitated vehicle routing problem",
"pagination": "21-52",
"productId": [
{
"name": "readcube_id",
"type": "PropertyValue",
"value": [
"7218d04c8e481a767008cba3957f281cb1418580a8833c5ba5104e87c8374fce"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/bf01580599"
]
},
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1023949375"
]
}
],
"sameAs": [
"https://doi.org/10.1007/bf01580599",
"https://app.dimensions.ai/details/publication/pub.1023949375"
],
"sdDataset": "articles",
"sdDatePublished": "2019-04-11T13:32",
"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/0000000370_0000000370/records_46765_00000001.jsonl",
"type": "ScholarlyArticle",
"url": "http://link.springer.com/10.1007%2FBF01580599"
}
]Download the RDF metadata as: json-ld nt turtle xml License info
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/bf01580599'
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/bf01580599'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf01580599'
RDF/XML is a standard XML format for linked data.
curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bf01580599'
This table displays all metadata directly associated to this object as RDF triples.
135 TRIPLES
21 PREDICATES
46 URIs
19 LITERALS
7 BLANK NODES