A statistical analysis of simulated annealing applied to the p-median problem View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2000-11

AUTHORS

Fernando Chiyoshi, Roberto D. Galvão

ABSTRACT

We present a statistical analysis of simulated annealing applied to the p-median problem. The algorithm we use combines elements of the vertex substitution method of Teitz and Bart with the general methodology of simulated annealing. The cooling schedule adopted incorporates the notion of temperature adjustments rather than just temperature reductions. Computational results are given for test problems ranging from 100 to 900 vertices, retrieved from Beasley's OR-Library for combinatorial problems. Each problem was run for a maximum of 100 different streams of random numbers. Optimal solutions were found for 26 of the 40 problems tested, although high optimum hitting rates were obtained for only 20 of them. The worst gap in relation to the optimal solution was 1.62%, after all runs for each of the test problems were computed. More... »

PAGES

61-74

References to SciGraph publications

  • 1994-12. A heuristic for large-sizep-median location problems with application to school location in ANNALS OF OPERATIONS RESEARCH
  • 1992-05. General Purpose Simulated Annealing in JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY
  • 1989-12. A method for solving to optimality uncapacitated location problems in ANNALS OF OPERATIONS RESEARCH
  • Journal

    TITLE

    Annals of Operations Research

    ISSUE

    1-4

    VOLUME

    96

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1023/a:1018982914742

    DOI

    http://dx.doi.org/10.1023/a:1018982914742

    DIMENSIONS

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


    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/0104", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Statistics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Mathematical Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "familyName": "Chiyoshi", 
            "givenName": "Fernando", 
            "id": "sg:person.014227341551.36", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014227341551.36"
            ], 
            "type": "Person"
          }, 
          {
            "familyName": "Galv\u00e3o", 
            "givenName": "Roberto D.", 
            "id": "sg:person.014243226662.13", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014243226662.13"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/bf02097805", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002885420", 
              "https://doi.org/10.1007/bf02097805"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02097805", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002885420", 
              "https://doi.org/10.1007/bf02097805"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0966-8349(98)00030-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006655677"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0377-2217(82)90160-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008373140"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0377-2217(82)90160-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008373140"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0377-2217(97)00310-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1013598293"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0377-2217(96)00141-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022632629"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1080/03155986.1983.11731889", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027184169"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02085654", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029137171", 
              "https://doi.org/10.1007/bf02085654"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02085654", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029137171", 
              "https://doi.org/10.1007/bf02085654"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0304-4076(94)90038-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030000548"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1057/jors.1992.75", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033540622", 
              "https://doi.org/10.1057/jors.1992.75"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0377-2217(96)00100-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1039217222"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0377-2217(85)90012-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1042654345"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0377-2217(85)90012-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1042654345"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0377-2217(85)90096-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047271566"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0377-2217(85)90096-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047271566"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/29380.29864", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1052942382"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0969-6016(94)90032-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1054566933"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1063/1.1699114", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1057769646"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1287/ijoc.3.4.376", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064707391"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1287/mnsc.24.16.1763", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064718993"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1287/opre.16.5.955", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064727303"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1287/opre.25.4.709", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064728835"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1287/opre.28.5.1112", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064729135"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.2307/2582903", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1070008496"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.2307/3007214", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1102672040"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2000-11", 
        "datePublishedReg": "2000-11-01", 
        "description": "We present a statistical analysis of simulated annealing applied to the p-median problem. The algorithm we use combines elements of the vertex substitution method of Teitz and Bart with the general methodology of simulated annealing. The cooling schedule adopted incorporates the notion of temperature adjustments rather than just temperature reductions. Computational results are given for test problems ranging from 100 to 900 vertices, retrieved from Beasley's OR-Library for combinatorial problems. Each problem was run for a maximum of 100 different streams of random numbers. Optimal solutions were found for 26 of the 40 problems tested, although high optimum hitting rates were obtained for only 20 of them. The worst gap in relation to the optimal solution was 1.62%, after all runs for each of the test problems were computed.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1023/a:1018982914742", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1048429", 
            "issn": [
              "0254-5330", 
              "1572-9338"
            ], 
            "name": "Annals of Operations Research", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "1-4", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "96"
          }
        ], 
        "name": "A statistical analysis of simulated annealing applied to the p-median problem", 
        "pagination": "61-74", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "b35c5b27eee1c266d9b934e98eab328ca1603d7c7ae6ed650facda6ef36b2dc1"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1023/a:1018982914742"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1037651624"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1023/a:1018982914742", 
          "https://app.dimensions.ai/details/publication/pub.1037651624"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T00:14", 
        "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_8695_00000506.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1023%2FA%3A1018982914742"
      }
    ]
     

    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.1023/a:1018982914742'

    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.1023/a:1018982914742'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1023/a:1018982914742'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1023/a:1018982914742'


     

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

    132 TRIPLES      21 PREDICATES      49 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1023/a:1018982914742 schema:about anzsrc-for:01
    2 anzsrc-for:0104
    3 schema:author N2fc4df998bc44dbb90c290bf3ea6b921
    4 schema:citation sg:pub.10.1007/bf02085654
    5 sg:pub.10.1007/bf02097805
    6 sg:pub.10.1057/jors.1992.75
    7 https://doi.org/10.1016/0304-4076(94)90038-8
    8 https://doi.org/10.1016/0377-2217(82)90160-6
    9 https://doi.org/10.1016/0377-2217(85)90012-8
    10 https://doi.org/10.1016/0377-2217(85)90096-7
    11 https://doi.org/10.1016/0969-6016(94)90032-9
    12 https://doi.org/10.1016/s0377-2217(96)00100-2
    13 https://doi.org/10.1016/s0377-2217(96)00141-5
    14 https://doi.org/10.1016/s0377-2217(97)00310-x
    15 https://doi.org/10.1016/s0966-8349(98)00030-8
    16 https://doi.org/10.1063/1.1699114
    17 https://doi.org/10.1080/03155986.1983.11731889
    18 https://doi.org/10.1145/29380.29864
    19 https://doi.org/10.1287/ijoc.3.4.376
    20 https://doi.org/10.1287/mnsc.24.16.1763
    21 https://doi.org/10.1287/opre.16.5.955
    22 https://doi.org/10.1287/opre.25.4.709
    23 https://doi.org/10.1287/opre.28.5.1112
    24 https://doi.org/10.2307/2582903
    25 https://doi.org/10.2307/3007214
    26 schema:datePublished 2000-11
    27 schema:datePublishedReg 2000-11-01
    28 schema:description We present a statistical analysis of simulated annealing applied to the p-median problem. The algorithm we use combines elements of the vertex substitution method of Teitz and Bart with the general methodology of simulated annealing. The cooling schedule adopted incorporates the notion of temperature adjustments rather than just temperature reductions. Computational results are given for test problems ranging from 100 to 900 vertices, retrieved from Beasley's OR-Library for combinatorial problems. Each problem was run for a maximum of 100 different streams of random numbers. Optimal solutions were found for 26 of the 40 problems tested, although high optimum hitting rates were obtained for only 20 of them. The worst gap in relation to the optimal solution was 1.62%, after all runs for each of the test problems were computed.
    29 schema:genre research_article
    30 schema:inLanguage en
    31 schema:isAccessibleForFree false
    32 schema:isPartOf N1998362147e844f4b1f130e5ef16a183
    33 Nef18c0a927564ac49c856c7dbdd0dd9c
    34 sg:journal.1048429
    35 schema:name A statistical analysis of simulated annealing applied to the p-median problem
    36 schema:pagination 61-74
    37 schema:productId N393d521676b5491c872235baa1105b7b
    38 Na5397582d5e44c0092a8849fa58aa033
    39 Nf3a4eb1d844d4a5ca55d8031c6ef042e
    40 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037651624
    41 https://doi.org/10.1023/a:1018982914742
    42 schema:sdDatePublished 2019-04-11T00:14
    43 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    44 schema:sdPublisher N4b37d9abf5444d3197e5ac26f688095d
    45 schema:url http://link.springer.com/10.1023%2FA%3A1018982914742
    46 sgo:license sg:explorer/license/
    47 sgo:sdDataset articles
    48 rdf:type schema:ScholarlyArticle
    49 N1998362147e844f4b1f130e5ef16a183 schema:volumeNumber 96
    50 rdf:type schema:PublicationVolume
    51 N2fc4df998bc44dbb90c290bf3ea6b921 rdf:first sg:person.014227341551.36
    52 rdf:rest Na4666f5564804892a8d89b95ce3471ed
    53 N393d521676b5491c872235baa1105b7b schema:name readcube_id
    54 schema:value b35c5b27eee1c266d9b934e98eab328ca1603d7c7ae6ed650facda6ef36b2dc1
    55 rdf:type schema:PropertyValue
    56 N4b37d9abf5444d3197e5ac26f688095d schema:name Springer Nature - SN SciGraph project
    57 rdf:type schema:Organization
    58 Na4666f5564804892a8d89b95ce3471ed rdf:first sg:person.014243226662.13
    59 rdf:rest rdf:nil
    60 Na5397582d5e44c0092a8849fa58aa033 schema:name doi
    61 schema:value 10.1023/a:1018982914742
    62 rdf:type schema:PropertyValue
    63 Nef18c0a927564ac49c856c7dbdd0dd9c schema:issueNumber 1-4
    64 rdf:type schema:PublicationIssue
    65 Nf3a4eb1d844d4a5ca55d8031c6ef042e schema:name dimensions_id
    66 schema:value pub.1037651624
    67 rdf:type schema:PropertyValue
    68 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    69 schema:name Mathematical Sciences
    70 rdf:type schema:DefinedTerm
    71 anzsrc-for:0104 schema:inDefinedTermSet anzsrc-for:
    72 schema:name Statistics
    73 rdf:type schema:DefinedTerm
    74 sg:journal.1048429 schema:issn 0254-5330
    75 1572-9338
    76 schema:name Annals of Operations Research
    77 rdf:type schema:Periodical
    78 sg:person.014227341551.36 schema:familyName Chiyoshi
    79 schema:givenName Fernando
    80 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014227341551.36
    81 rdf:type schema:Person
    82 sg:person.014243226662.13 schema:familyName Galvão
    83 schema:givenName Roberto D.
    84 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014243226662.13
    85 rdf:type schema:Person
    86 sg:pub.10.1007/bf02085654 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029137171
    87 https://doi.org/10.1007/bf02085654
    88 rdf:type schema:CreativeWork
    89 sg:pub.10.1007/bf02097805 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002885420
    90 https://doi.org/10.1007/bf02097805
    91 rdf:type schema:CreativeWork
    92 sg:pub.10.1057/jors.1992.75 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033540622
    93 https://doi.org/10.1057/jors.1992.75
    94 rdf:type schema:CreativeWork
    95 https://doi.org/10.1016/0304-4076(94)90038-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030000548
    96 rdf:type schema:CreativeWork
    97 https://doi.org/10.1016/0377-2217(82)90160-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008373140
    98 rdf:type schema:CreativeWork
    99 https://doi.org/10.1016/0377-2217(85)90012-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042654345
    100 rdf:type schema:CreativeWork
    101 https://doi.org/10.1016/0377-2217(85)90096-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047271566
    102 rdf:type schema:CreativeWork
    103 https://doi.org/10.1016/0969-6016(94)90032-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1054566933
    104 rdf:type schema:CreativeWork
    105 https://doi.org/10.1016/s0377-2217(96)00100-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039217222
    106 rdf:type schema:CreativeWork
    107 https://doi.org/10.1016/s0377-2217(96)00141-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022632629
    108 rdf:type schema:CreativeWork
    109 https://doi.org/10.1016/s0377-2217(97)00310-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1013598293
    110 rdf:type schema:CreativeWork
    111 https://doi.org/10.1016/s0966-8349(98)00030-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006655677
    112 rdf:type schema:CreativeWork
    113 https://doi.org/10.1063/1.1699114 schema:sameAs https://app.dimensions.ai/details/publication/pub.1057769646
    114 rdf:type schema:CreativeWork
    115 https://doi.org/10.1080/03155986.1983.11731889 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027184169
    116 rdf:type schema:CreativeWork
    117 https://doi.org/10.1145/29380.29864 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052942382
    118 rdf:type schema:CreativeWork
    119 https://doi.org/10.1287/ijoc.3.4.376 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064707391
    120 rdf:type schema:CreativeWork
    121 https://doi.org/10.1287/mnsc.24.16.1763 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064718993
    122 rdf:type schema:CreativeWork
    123 https://doi.org/10.1287/opre.16.5.955 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064727303
    124 rdf:type schema:CreativeWork
    125 https://doi.org/10.1287/opre.25.4.709 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064728835
    126 rdf:type schema:CreativeWork
    127 https://doi.org/10.1287/opre.28.5.1112 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064729135
    128 rdf:type schema:CreativeWork
    129 https://doi.org/10.2307/2582903 schema:sameAs https://app.dimensions.ai/details/publication/pub.1070008496
    130 rdf:type schema:CreativeWork
    131 https://doi.org/10.2307/3007214 schema:sameAs https://app.dimensions.ai/details/publication/pub.1102672040
    132 rdf:type schema:CreativeWork
     




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


    ...