Ontology type: schema:Chapter Open Access: True
1998
AUTHORS ABSTRACTWe use a local search method we term Large Neighbourhood Search (LNS) to solve vehicle routing problems. LNS is analogous to the shuffing technique of job-shop scheduling, and so meshes well with constraint programming technology. LNS explores a large neighbourhood of the current solution by selecting a number of “related” customer visits to remove from the set of planned routes, and re-inserting these visits using a constraint-based tree search. Unlike similar methods, we use Limited Discrepancy Search during the tree search to re-insert visits. We analyse the performance of our method on benchmark problems. We demonstrate that results produced are competitive with Operations Research meta-heuristic methods, indicating that constraint-based technology is directly applicable to vehicle routing problems More... »
PAGES417-431
Principles and Practice of Constraint Programming — CP98
ISBN
978-3-540-65224-3
978-3-540-49481-2
http://scigraph.springernature.com/pub.10.1007/3-540-49481-2_30
DOIhttp://dx.doi.org/10.1007/3-540-49481-2_30
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1030539804
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/0801",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Artificial Intelligence and Image Processing",
"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": "IBM (France)",
"id": "https://www.grid.ac/institutes/grid.424192.8",
"name": [
"ILOG S.A., 9, rue de Verdun, BP 85, 94253\u00a0Gentilly Cedex, France"
],
"type": "Organization"
},
"familyName": "Shaw",
"givenName": "Paul",
"id": "sg:person.012137210617.77",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012137210617.77"
],
"type": "Person"
}
],
"citation": [
{
"id": "sg:pub.10.1007/bf02430370",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1035752953",
"https://doi.org/10.1007/bf02430370"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf02430370",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1035752953",
"https://doi.org/10.1007/bf02430370"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1002/net.3230230804",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1039611850"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1287/ijoc.3.2.149",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1064707363"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1287/ijoc.4.2.146",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1064707405"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1287/opre.35.2.254",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1064729808"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1287/opre.40.2.342",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1064730422"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1287/opre.42.4.626",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1064730679"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1287/trsc.31.2.170",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1064735431"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1287/trsc.32.1.12",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1064735452"
],
"type": "CreativeWork"
}
],
"datePublished": "1998",
"datePublishedReg": "1998-01-01",
"description": "We use a local search method we term Large Neighbourhood Search (LNS) to solve vehicle routing problems. LNS is analogous to the shuffing technique of job-shop scheduling, and so meshes well with constraint programming technology. LNS explores a large neighbourhood of the current solution by selecting a number of \u201crelated\u201d customer visits to remove from the set of planned routes, and re-inserting these visits using a constraint-based tree search. Unlike similar methods, we use Limited Discrepancy Search during the tree search to re-insert visits. We analyse the performance of our method on benchmark problems. We demonstrate that results produced are competitive with Operations Research meta-heuristic methods, indicating that constraint-based technology is directly applicable to vehicle routing problems",
"editor": [
{
"familyName": "Maher",
"givenName": "Michael",
"type": "Person"
},
{
"familyName": "Puget",
"givenName": "Jean-Francois",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/3-540-49481-2_30",
"inLanguage": [
"en"
],
"isAccessibleForFree": true,
"isPartOf": {
"isbn": [
"978-3-540-65224-3",
"978-3-540-49481-2"
],
"name": "Principles and Practice of Constraint Programming \u2014 CP98",
"type": "Book"
},
"name": "Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems",
"pagination": "417-431",
"productId": [
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/3-540-49481-2_30"
]
},
{
"name": "readcube_id",
"type": "PropertyValue",
"value": [
"917ccb71a8c7b106480269ae7d8341e5b35404d07eb0af57011977b9fbb46b6f"
]
},
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1030539804"
]
}
],
"publisher": {
"location": "Berlin, Heidelberg",
"name": "Springer Berlin Heidelberg",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/3-540-49481-2_30",
"https://app.dimensions.ai/details/publication/pub.1030539804"
],
"sdDataset": "chapters",
"sdDatePublished": "2019-04-15T15:54",
"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_00000558.jsonl",
"type": "Chapter",
"url": "http://link.springer.com/10.1007/3-540-49481-2_30"
}
]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/3-540-49481-2_30'
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/3-540-49481-2_30'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-49481-2_30'
RDF/XML is a standard XML format for linked data.
curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-49481-2_30'
This table displays all metadata directly associated to this object as RDF triples.
98 TRIPLES
23 PREDICATES
36 URIs
20 LITERALS
8 BLANK NODES