Probabilistic diversification and intensification in local search for vehicle routing View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

1995-09

AUTHORS

Yves Rochat, Éric D. Taillard

ABSTRACT

This article presents a probabilistic technique to diversify, intensify, and parallelize a local search adapted for solving vehicle routing problems. This technique may be applied to a very wide variety of vehicle routing problems and local searches. It is shown that efficient first-level tabu searches for vehicle routing problems may be significantly improved with this technique. Moreover, the solutions produced by this technique may often be improved by a postoptimization technique presented in this article, too. The solutions of nearly forty problem instances of the literature have been improved. More... »

PAGES

147-167

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/bf02430370

DOI

http://dx.doi.org/10.1007/bf02430370

DIMENSIONS

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


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": "\u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne", 
          "id": "https://www.grid.ac/institutes/grid.5333.6", 
          "name": [
            "Department of Mathematics, \u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne, 1015, Lausanne, Switzerland"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Rochat", 
        "givenName": "Yves", 
        "id": "sg:person.010446460267.10", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010446460267.10"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Montreal", 
          "id": "https://www.grid.ac/institutes/grid.14848.31", 
          "name": [
            "Center of Research on Transportation, Universit\u00e9 de Montr\u00e9al, succursale Centre-Ville, C.P. 6128, H3C 3J7, Montr\u00e9al, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Taillard", 
        "givenName": "\u00c9ric D.", 
        "id": "sg:person.011635155477.33", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011635155477.33"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/bf02023006", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1006074995", 
          "https://doi.org/10.1007/bf02023006"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02023006", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1006074995", 
          "https://doi.org/10.1007/bf02023006"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1057/jors.1994.197", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1017918133", 
          "https://doi.org/10.1057/jors.1994.197"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1111/j.1540-5915.1977.tb01074.x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1029929557"
        ], 
        "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.2.1.4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064707137"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1287/mnsc.40.10.1276", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064721172"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1287/opre.23.3.434", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064728604"
        ], 
        "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.41.5.935", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064730596"
        ], 
        "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.29.2.156", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064735333"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1995-09", 
    "datePublishedReg": "1995-09-01", 
    "description": "This article presents a probabilistic technique to diversify, intensify, and parallelize a local search adapted for solving vehicle routing problems. This technique may be applied to a very wide variety of vehicle routing problems and local searches. It is shown that efficient first-level tabu searches for vehicle routing problems may be significantly improved with this technique. Moreover, the solutions produced by this technique may often be improved by a postoptimization technique presented in this article, too. The solutions of nearly forty problem instances of the literature have been improved.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/bf02430370", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1136112", 
        "issn": [
          "1381-1231", 
          "1572-9397"
        ], 
        "name": "Journal of Heuristics", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "1", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "1"
      }
    ], 
    "name": "Probabilistic diversification and intensification in local search for vehicle routing", 
    "pagination": "147-167", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "aa506f5aafc8456e78e46a4a3714372a79659327cd3014e8a4f1b0827b40317b"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf02430370"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1035752953"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf02430370", 
      "https://app.dimensions.ai/details/publication/pub.1035752953"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T13:31", 
    "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_46757_00000001.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1007%2FBF02430370"
  }
]
 

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

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

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf02430370'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bf02430370'


 

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

109 TRIPLES      21 PREDICATES      39 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf02430370 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N5fbaa2efc8ca449f9c28121b70ea01dd
4 schema:citation sg:pub.10.1007/bf02023006
5 sg:pub.10.1057/jors.1994.197
6 https://doi.org/10.1002/net.3230230804
7 https://doi.org/10.1111/j.1540-5915.1977.tb01074.x
8 https://doi.org/10.1287/ijoc.2.1.4
9 https://doi.org/10.1287/mnsc.40.10.1276
10 https://doi.org/10.1287/opre.23.3.434
11 https://doi.org/10.1287/opre.35.2.254
12 https://doi.org/10.1287/opre.40.2.342
13 https://doi.org/10.1287/opre.41.5.935
14 https://doi.org/10.1287/opre.42.4.626
15 https://doi.org/10.1287/trsc.29.2.156
16 schema:datePublished 1995-09
17 schema:datePublishedReg 1995-09-01
18 schema:description This article presents a probabilistic technique to diversify, intensify, and parallelize a local search adapted for solving vehicle routing problems. This technique may be applied to a very wide variety of vehicle routing problems and local searches. It is shown that efficient first-level tabu searches for vehicle routing problems may be significantly improved with this technique. Moreover, the solutions produced by this technique may often be improved by a postoptimization technique presented in this article, too. The solutions of nearly forty problem instances of the literature have been improved.
19 schema:genre research_article
20 schema:inLanguage en
21 schema:isAccessibleForFree true
22 schema:isPartOf N4d9bbeff7c1945bc86c3c4effd824a69
23 N6280ad9612a04064a0440813b8906336
24 sg:journal.1136112
25 schema:name Probabilistic diversification and intensification in local search for vehicle routing
26 schema:pagination 147-167
27 schema:productId N11f4e855539d4168b7e395d9792abc76
28 Na5856365f9b2410cb243f2a118b1a378
29 Naa98d78c86774a3fba4a6868013c57f9
30 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035752953
31 https://doi.org/10.1007/bf02430370
32 schema:sdDatePublished 2019-04-11T13:31
33 schema:sdLicense https://scigraph.springernature.com/explorer/license/
34 schema:sdPublisher Nca2e7a70ac1146c4abd1f47f0807e63e
35 schema:url http://link.springer.com/10.1007%2FBF02430370
36 sgo:license sg:explorer/license/
37 sgo:sdDataset articles
38 rdf:type schema:ScholarlyArticle
39 N11f4e855539d4168b7e395d9792abc76 schema:name doi
40 schema:value 10.1007/bf02430370
41 rdf:type schema:PropertyValue
42 N16f1df5674a94635b292bfa4cf00cbd6 rdf:first sg:person.011635155477.33
43 rdf:rest rdf:nil
44 N4d9bbeff7c1945bc86c3c4effd824a69 schema:issueNumber 1
45 rdf:type schema:PublicationIssue
46 N5fbaa2efc8ca449f9c28121b70ea01dd rdf:first sg:person.010446460267.10
47 rdf:rest N16f1df5674a94635b292bfa4cf00cbd6
48 N6280ad9612a04064a0440813b8906336 schema:volumeNumber 1
49 rdf:type schema:PublicationVolume
50 Na5856365f9b2410cb243f2a118b1a378 schema:name readcube_id
51 schema:value aa506f5aafc8456e78e46a4a3714372a79659327cd3014e8a4f1b0827b40317b
52 rdf:type schema:PropertyValue
53 Naa98d78c86774a3fba4a6868013c57f9 schema:name dimensions_id
54 schema:value pub.1035752953
55 rdf:type schema:PropertyValue
56 Nca2e7a70ac1146c4abd1f47f0807e63e schema:name Springer Nature - SN SciGraph project
57 rdf:type schema:Organization
58 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
59 schema:name Information and Computing Sciences
60 rdf:type schema:DefinedTerm
61 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
62 schema:name Computation Theory and Mathematics
63 rdf:type schema:DefinedTerm
64 sg:journal.1136112 schema:issn 1381-1231
65 1572-9397
66 schema:name Journal of Heuristics
67 rdf:type schema:Periodical
68 sg:person.010446460267.10 schema:affiliation https://www.grid.ac/institutes/grid.5333.6
69 schema:familyName Rochat
70 schema:givenName Yves
71 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010446460267.10
72 rdf:type schema:Person
73 sg:person.011635155477.33 schema:affiliation https://www.grid.ac/institutes/grid.14848.31
74 schema:familyName Taillard
75 schema:givenName Éric D.
76 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011635155477.33
77 rdf:type schema:Person
78 sg:pub.10.1007/bf02023006 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006074995
79 https://doi.org/10.1007/bf02023006
80 rdf:type schema:CreativeWork
81 sg:pub.10.1057/jors.1994.197 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017918133
82 https://doi.org/10.1057/jors.1994.197
83 rdf:type schema:CreativeWork
84 https://doi.org/10.1002/net.3230230804 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039611850
85 rdf:type schema:CreativeWork
86 https://doi.org/10.1111/j.1540-5915.1977.tb01074.x schema:sameAs https://app.dimensions.ai/details/publication/pub.1029929557
87 rdf:type schema:CreativeWork
88 https://doi.org/10.1287/ijoc.2.1.4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064707137
89 rdf:type schema:CreativeWork
90 https://doi.org/10.1287/mnsc.40.10.1276 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064721172
91 rdf:type schema:CreativeWork
92 https://doi.org/10.1287/opre.23.3.434 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064728604
93 rdf:type schema:CreativeWork
94 https://doi.org/10.1287/opre.35.2.254 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064729808
95 rdf:type schema:CreativeWork
96 https://doi.org/10.1287/opre.40.2.342 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064730422
97 rdf:type schema:CreativeWork
98 https://doi.org/10.1287/opre.41.5.935 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064730596
99 rdf:type schema:CreativeWork
100 https://doi.org/10.1287/opre.42.4.626 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064730679
101 rdf:type schema:CreativeWork
102 https://doi.org/10.1287/trsc.29.2.156 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064735333
103 rdf:type schema:CreativeWork
104 https://www.grid.ac/institutes/grid.14848.31 schema:alternateName University of Montreal
105 schema:name Center of Research on Transportation, Université de Montréal, succursale Centre-Ville, C.P. 6128, H3C 3J7, Montréal, Canada
106 rdf:type schema:Organization
107 https://www.grid.ac/institutes/grid.5333.6 schema:alternateName École Polytechnique Fédérale de Lausanne
108 schema:name Department of Mathematics, École Polytechnique Fédérale de Lausanne, 1015, Lausanne, Switzerland
109 rdf:type schema:Organization
 




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


...