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

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 N316ce9b8447c4b9c9315a44c02ee2c94
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 Nf3f199d6a75a4803b708a01c7be4c746
17 schema:genre chapter
18 schema:inLanguage en
19 schema:isAccessibleForFree true
20 schema:isPartOf N50de2119beac48088cf8f4fe3ca7a13a
21 schema:name Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems
22 schema:pagination 417-431
23 schema:productId N1070e317b1154abaa32238a96badf1a1
24 N256d6d1ba1744539b852bb62a05a2778
25 N27d7fa9e355e45439f91e8d158d067fe
26 schema:publisher N4d4fc3a1095a4876af6298d039d17d1a
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 Ncd8340b46a2749708ed8a342dad9c1f8
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 N1070e317b1154abaa32238a96badf1a1 schema:name dimensions_id
37 schema:value pub.1030539804
38 rdf:type schema:PropertyValue
39 N256d6d1ba1744539b852bb62a05a2778 schema:name readcube_id
40 schema:value 917ccb71a8c7b106480269ae7d8341e5b35404d07eb0af57011977b9fbb46b6f
41 rdf:type schema:PropertyValue
42 N27d7fa9e355e45439f91e8d158d067fe schema:name doi
43 schema:value 10.1007/3-540-49481-2_30
44 rdf:type schema:PropertyValue
45 N316ce9b8447c4b9c9315a44c02ee2c94 rdf:first sg:person.012137210617.77
46 rdf:rest rdf:nil
47 N37d90c86614b49c199af0717a60eb369 schema:familyName Puget
48 schema:givenName Jean-Francois
49 rdf:type schema:Person
50 N4d4fc3a1095a4876af6298d039d17d1a schema:location Berlin, Heidelberg
51 schema:name Springer Berlin Heidelberg
52 rdf:type schema:Organisation
53 N50de2119beac48088cf8f4fe3ca7a13a schema:isbn 978-3-540-49481-2
54 978-3-540-65224-3
55 schema:name Principles and Practice of Constraint Programming — CP98
56 rdf:type schema:Book
57 N90ab27c4d3d24db0b6d72de1bc6da606 rdf:first N37d90c86614b49c199af0717a60eb369
58 rdf:rest rdf:nil
59 Nb34416abf26e4548aafa0dd205426244 schema:familyName Maher
60 schema:givenName Michael
61 rdf:type schema:Person
62 Ncd8340b46a2749708ed8a342dad9c1f8 schema:name Springer Nature - SN SciGraph project
63 rdf:type schema:Organization
64 Nf3f199d6a75a4803b708a01c7be4c746 rdf:first Nb34416abf26e4548aafa0dd205426244
65 rdf:rest N90ab27c4d3d24db0b6d72de1bc6da606
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)


...