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 N737bd68d57f34fe28edb189d9b60c29c
    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 Nd3c23b3a76bf4a389f9ac0ec7d1db7f6
    33 Nfbe9ea33907f4d04a61e465ded6cac47
    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 N1920b262f45e43fbbd1a663d50eed405
    38 N5631ac06be55413dbaf6a11dd5cef76d
    39 N65f2e8f5aa65469f82de61c41c8005fe
    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 Nb5a38578260844f782aeb18e2992f0ad
    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 N1920b262f45e43fbbd1a663d50eed405 schema:name dimensions_id
    50 schema:value pub.1037651624
    51 rdf:type schema:PropertyValue
    52 N5631ac06be55413dbaf6a11dd5cef76d schema:name doi
    53 schema:value 10.1023/a:1018982914742
    54 rdf:type schema:PropertyValue
    55 N65f2e8f5aa65469f82de61c41c8005fe schema:name readcube_id
    56 schema:value b35c5b27eee1c266d9b934e98eab328ca1603d7c7ae6ed650facda6ef36b2dc1
    57 rdf:type schema:PropertyValue
    58 N737bd68d57f34fe28edb189d9b60c29c rdf:first sg:person.014227341551.36
    59 rdf:rest N91d4cf38ac41475db1132e99b288dc94
    60 N91d4cf38ac41475db1132e99b288dc94 rdf:first sg:person.014243226662.13
    61 rdf:rest rdf:nil
    62 Nb5a38578260844f782aeb18e2992f0ad schema:name Springer Nature - SN SciGraph project
    63 rdf:type schema:Organization
    64 Nd3c23b3a76bf4a389f9ac0ec7d1db7f6 schema:issueNumber 1-4
    65 rdf:type schema:PublicationIssue
    66 Nfbe9ea33907f4d04a61e465ded6cac47 schema:volumeNumber 96
    67 rdf:type schema:PublicationVolume
    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)


    ...