Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

1998

AUTHORS

Paul Shaw

ABSTRACT

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 “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... »

PAGES

417-431

References to SciGraph publications

Book

TITLE

Principles and Practice of Constraint Programming — CP98

ISBN

978-3-540-65224-3
978-3-540-49481-2

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-49481-2_30

DOI

http://dx.doi.org/10.1007/3-540-49481-2_30

DIMENSIONS

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


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/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

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/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

Subject Predicate Object
1 sg:pub.10.1007/3-540-49481-2_30 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author N3ff6ed630dd54fb1a92ca06fae866e49
4 schema:citation sg:pub.10.1007/bf02430370
5 https://doi.org/10.1002/net.3230230804
6 https://doi.org/10.1287/ijoc.3.2.149
7 https://doi.org/10.1287/ijoc.4.2.146
8 https://doi.org/10.1287/opre.35.2.254
9 https://doi.org/10.1287/opre.40.2.342
10 https://doi.org/10.1287/opre.42.4.626
11 https://doi.org/10.1287/trsc.31.2.170
12 https://doi.org/10.1287/trsc.32.1.12
13 schema:datePublished 1998
14 schema:datePublishedReg 1998-01-01
15 schema: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 “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
16 schema:editor N88fc135677244fc7bdadf537691d10be
17 schema:genre chapter
18 schema:inLanguage en
19 schema:isAccessibleForFree true
20 schema:isPartOf N59bd48d4266542de859afd94df05633e
21 schema:name Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems
22 schema:pagination 417-431
23 schema:productId Na01e725cb04b43219b241931f19efca3
24 Nba162632b7334153ba152b6a23ccd5c8
25 Ne076e380cf294cf1b6d7d1b112c96a56
26 schema:publisher N0d01852cde1c4ee49b2c2d39453e39bc
27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030539804
28 https://doi.org/10.1007/3-540-49481-2_30
29 schema:sdDatePublished 2019-04-15T15:54
30 schema:sdLicense https://scigraph.springernature.com/explorer/license/
31 schema:sdPublisher N8194e848e1334273bcf214af7faad176
32 schema:url http://link.springer.com/10.1007/3-540-49481-2_30
33 sgo:license sg:explorer/license/
34 sgo:sdDataset chapters
35 rdf:type schema:Chapter
36 N0d01852cde1c4ee49b2c2d39453e39bc schema:location Berlin, Heidelberg
37 schema:name Springer Berlin Heidelberg
38 rdf:type schema:Organisation
39 N176566ecb545426d97253bbd485a0532 rdf:first Nf5065096ade9420ba24fc00d65f420f9
40 rdf:rest rdf:nil
41 N3ff6ed630dd54fb1a92ca06fae866e49 rdf:first sg:person.012137210617.77
42 rdf:rest rdf:nil
43 N59bd48d4266542de859afd94df05633e schema:isbn 978-3-540-49481-2
44 978-3-540-65224-3
45 schema:name Principles and Practice of Constraint Programming — CP98
46 rdf:type schema:Book
47 N8194e848e1334273bcf214af7faad176 schema:name Springer Nature - SN SciGraph project
48 rdf:type schema:Organization
49 N88fc135677244fc7bdadf537691d10be rdf:first Ne85998daf82b448f9eaec14958622088
50 rdf:rest N176566ecb545426d97253bbd485a0532
51 Na01e725cb04b43219b241931f19efca3 schema:name dimensions_id
52 schema:value pub.1030539804
53 rdf:type schema:PropertyValue
54 Nba162632b7334153ba152b6a23ccd5c8 schema:name doi
55 schema:value 10.1007/3-540-49481-2_30
56 rdf:type schema:PropertyValue
57 Ne076e380cf294cf1b6d7d1b112c96a56 schema:name readcube_id
58 schema:value 917ccb71a8c7b106480269ae7d8341e5b35404d07eb0af57011977b9fbb46b6f
59 rdf:type schema:PropertyValue
60 Ne85998daf82b448f9eaec14958622088 schema:familyName Maher
61 schema:givenName Michael
62 rdf:type schema:Person
63 Nf5065096ade9420ba24fc00d65f420f9 schema:familyName Puget
64 schema:givenName Jean-Francois
65 rdf:type schema:Person
66 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
67 schema:name Information and Computing Sciences
68 rdf:type schema:DefinedTerm
69 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
70 schema:name Artificial Intelligence and Image Processing
71 rdf:type schema:DefinedTerm
72 sg:person.012137210617.77 schema:affiliation https://www.grid.ac/institutes/grid.424192.8
73 schema:familyName Shaw
74 schema:givenName Paul
75 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012137210617.77
76 rdf:type schema:Person
77 sg:pub.10.1007/bf02430370 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035752953
78 https://doi.org/10.1007/bf02430370
79 rdf:type schema:CreativeWork
80 https://doi.org/10.1002/net.3230230804 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039611850
81 rdf:type schema:CreativeWork
82 https://doi.org/10.1287/ijoc.3.2.149 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064707363
83 rdf:type schema:CreativeWork
84 https://doi.org/10.1287/ijoc.4.2.146 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064707405
85 rdf:type schema:CreativeWork
86 https://doi.org/10.1287/opre.35.2.254 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064729808
87 rdf:type schema:CreativeWork
88 https://doi.org/10.1287/opre.40.2.342 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064730422
89 rdf:type schema:CreativeWork
90 https://doi.org/10.1287/opre.42.4.626 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064730679
91 rdf:type schema:CreativeWork
92 https://doi.org/10.1287/trsc.31.2.170 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064735431
93 rdf:type schema:CreativeWork
94 https://doi.org/10.1287/trsc.32.1.12 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064735452
95 rdf:type schema:CreativeWork
96 https://www.grid.ac/institutes/grid.424192.8 schema:alternateName IBM (France)
97 schema:name ILOG S.A., 9, rue de Verdun, BP 85, 94253 Gentilly Cedex, France
98 rdf:type schema:Organization
 




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


...