Real-time heuristic algorithms for the static weapon target assignment problem View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2018-11-29

AUTHORS

Alexander G. Kline, Darryl K. Ahner, Brian J. Lunday

ABSTRACT

The problem of targeting and engaging individual missiles (targets) with an arsenal of interceptors (weapons) is known as the weapon target assignment problem. Many optimal solution techniques are applied to solve problem variants having linear approximations of the objective function, and their final solutions rarely yield optimal solutions to the original problem. Herein, we propose a nonlinear branch and bound algorithm to solve the untransformed problem. We also develop two heuristics respectively based on a branch and bound algorithm and the optimal solution to the quiz problem, and we compare them to a well-embraced heuristic from the literature. We test the three heuristics to solve a set of 15 problem sizes and 20 instances for each size, comparing their performance with respect to solution quality and required computational effort. The heuristic based upon the optimal solution to the quiz problem finds solutions within 6% of optimal for small problems and provides statistically similar results as one of the best heuristics found in the literature for larger problems, while solving these problems in ten thousandths of the time. More... »

PAGES

1-21

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s10732-018-9401-1

DOI

http://dx.doi.org/10.1007/s10732-018-9401-1

DIMENSIONS

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


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/0103", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Numerical and Computational Mathematics", 
        "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": [
      {
        "affiliation": {
          "alternateName": "Air Force Institute of Technology", 
          "id": "https://www.grid.ac/institutes/grid.427848.5", 
          "name": [
            "Air Force Institute of Technology, 2950 Hobson Way, 45433-7765, Wright-Patterson AFB, OH, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kline", 
        "givenName": "Alexander G.", 
        "id": "sg:person.010513751533.14", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010513751533.14"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Air Force Institute of Technology", 
          "id": "https://www.grid.ac/institutes/grid.427848.5", 
          "name": [
            "Air Force Institute of Technology, 2950 Hobson Way, 45433-7765, Wright-Patterson AFB, OH, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ahner", 
        "givenName": "Darryl K.", 
        "id": "sg:person.011377067477.63", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011377067477.63"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Air Force Institute of Technology", 
          "id": "https://www.grid.ac/institutes/grid.427848.5", 
          "name": [
            "Air Force Institute of Technology, 2950 Hobson Way, 45433-7765, Wright-Patterson AFB, OH, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lunday", 
        "givenName": "Brian J.", 
        "id": "sg:person.012436003107.02", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012436003107.02"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1080/00207540600988105", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1008113626"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.ijleo.2015.12.122", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1031388303"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s1568-4946(02)00027-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033222831"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02430363", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1035449866", 
          "https://doi.org/10.1007/bf02430363"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf02430363", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1035449866", 
          "https://doi.org/10.1007/bf02430363"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1023/a:1009634810396", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1044731504", 
          "https://doi.org/10.1023/a:1009634810396"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1287/ijoc.1.4.232", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064706395"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1287/opre.1070.0440", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064725913"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1287/opre.14.6.992", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064727049"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1287/opre.18.2.334", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064727452"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1287/opre.6.3.346", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064731720"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1287/opre.7.3.322", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064731809"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.14569/ijacsa.2017.080412", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1085302672"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/cdc.1987.272755", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1086203685"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.21236/ad0602672", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1091770826"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/wcica.2016.7578704", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1093511962"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/icinfa.2015.7279633", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1095430934"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2018-11-29", 
    "datePublishedReg": "2018-11-29", 
    "description": "The problem of targeting and engaging individual missiles (targets) with an arsenal of interceptors (weapons) is known as the weapon target assignment problem. Many optimal solution techniques are applied to solve problem variants having linear approximations of the objective function, and their final solutions rarely yield optimal solutions to the original problem. Herein, we propose a nonlinear branch and bound algorithm to solve the untransformed problem. We also develop two heuristics respectively based on a branch and bound algorithm and the optimal solution to the quiz problem, and we compare them to a well-embraced heuristic from the literature. We test the three heuristics to solve a set of 15 problem sizes and 20 instances for each size, comparing their performance with respect to solution quality and required computational effort. The heuristic based upon the optimal solution to the quiz problem finds solutions within 6% of optimal for small problems and provides statistically similar results as one of the best heuristics found in the literature for larger problems, while solving these problems in ten thousandths of the time.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s10732-018-9401-1", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1136112", 
        "issn": [
          "1381-1231", 
          "1572-9397"
        ], 
        "name": "Journal of Heuristics", 
        "type": "Periodical"
      }
    ], 
    "name": "Real-time heuristic algorithms for the static weapon target assignment problem", 
    "pagination": "1-21", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "976eea55a31f2a5b3e5963eb57e213a0c4bd60394f2b181b34c03199d6dd09b8"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s10732-018-9401-1"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1110271486"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s10732-018-9401-1", 
      "https://app.dimensions.ai/details/publication/pub.1110271486"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T08:16", 
    "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/0000000278_0000000278/records_79653_00000000.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://link.springer.com/10.1007%2Fs10732-018-9401-1"
  }
]
 

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/s10732-018-9401-1'

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/s10732-018-9401-1'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10732-018-9401-1'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s10732-018-9401-1'


 

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

119 TRIPLES      21 PREDICATES      40 URIs      16 LITERALS      5 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s10732-018-9401-1 schema:about anzsrc-for:01
2 anzsrc-for:0103
3 schema:author N0623b630815646298ed0141874ebbda8
4 schema:citation sg:pub.10.1007/bf02430363
5 sg:pub.10.1023/a:1009634810396
6 https://doi.org/10.1016/j.ijleo.2015.12.122
7 https://doi.org/10.1016/s1568-4946(02)00027-3
8 https://doi.org/10.1080/00207540600988105
9 https://doi.org/10.1109/cdc.1987.272755
10 https://doi.org/10.1109/icinfa.2015.7279633
11 https://doi.org/10.1109/wcica.2016.7578704
12 https://doi.org/10.1287/ijoc.1.4.232
13 https://doi.org/10.1287/opre.1070.0440
14 https://doi.org/10.1287/opre.14.6.992
15 https://doi.org/10.1287/opre.18.2.334
16 https://doi.org/10.1287/opre.6.3.346
17 https://doi.org/10.1287/opre.7.3.322
18 https://doi.org/10.14569/ijacsa.2017.080412
19 https://doi.org/10.21236/ad0602672
20 schema:datePublished 2018-11-29
21 schema:datePublishedReg 2018-11-29
22 schema:description The problem of targeting and engaging individual missiles (targets) with an arsenal of interceptors (weapons) is known as the weapon target assignment problem. Many optimal solution techniques are applied to solve problem variants having linear approximations of the objective function, and their final solutions rarely yield optimal solutions to the original problem. Herein, we propose a nonlinear branch and bound algorithm to solve the untransformed problem. We also develop two heuristics respectively based on a branch and bound algorithm and the optimal solution to the quiz problem, and we compare them to a well-embraced heuristic from the literature. We test the three heuristics to solve a set of 15 problem sizes and 20 instances for each size, comparing their performance with respect to solution quality and required computational effort. The heuristic based upon the optimal solution to the quiz problem finds solutions within 6% of optimal for small problems and provides statistically similar results as one of the best heuristics found in the literature for larger problems, while solving these problems in ten thousandths of the time.
23 schema:genre research_article
24 schema:inLanguage en
25 schema:isAccessibleForFree false
26 schema:isPartOf sg:journal.1136112
27 schema:name Real-time heuristic algorithms for the static weapon target assignment problem
28 schema:pagination 1-21
29 schema:productId N1055019d2abe44fc8752fc78ba6ff0d4
30 N816373d896e041548cf253971cf01241
31 N8b4510d2b49348ecb35462f8f5c8e6b5
32 schema:sameAs https://app.dimensions.ai/details/publication/pub.1110271486
33 https://doi.org/10.1007/s10732-018-9401-1
34 schema:sdDatePublished 2019-04-11T08:16
35 schema:sdLicense https://scigraph.springernature.com/explorer/license/
36 schema:sdPublisher N039fa6f3bcda408fa0662df91a88f469
37 schema:url https://link.springer.com/10.1007%2Fs10732-018-9401-1
38 sgo:license sg:explorer/license/
39 sgo:sdDataset articles
40 rdf:type schema:ScholarlyArticle
41 N039fa6f3bcda408fa0662df91a88f469 schema:name Springer Nature - SN SciGraph project
42 rdf:type schema:Organization
43 N0623b630815646298ed0141874ebbda8 rdf:first sg:person.010513751533.14
44 rdf:rest Nd18dc913d3244433b124f8c87b889495
45 N1055019d2abe44fc8752fc78ba6ff0d4 schema:name readcube_id
46 schema:value 976eea55a31f2a5b3e5963eb57e213a0c4bd60394f2b181b34c03199d6dd09b8
47 rdf:type schema:PropertyValue
48 N816373d896e041548cf253971cf01241 schema:name dimensions_id
49 schema:value pub.1110271486
50 rdf:type schema:PropertyValue
51 N8b4510d2b49348ecb35462f8f5c8e6b5 schema:name doi
52 schema:value 10.1007/s10732-018-9401-1
53 rdf:type schema:PropertyValue
54 Nd18dc913d3244433b124f8c87b889495 rdf:first sg:person.011377067477.63
55 rdf:rest Nda47303fdc484ccbaefc2bda71d7a4fc
56 Nda47303fdc484ccbaefc2bda71d7a4fc rdf:first sg:person.012436003107.02
57 rdf:rest rdf:nil
58 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
59 schema:name Mathematical Sciences
60 rdf:type schema:DefinedTerm
61 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
62 schema:name Numerical and Computational 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.010513751533.14 schema:affiliation https://www.grid.ac/institutes/grid.427848.5
69 schema:familyName Kline
70 schema:givenName Alexander G.
71 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010513751533.14
72 rdf:type schema:Person
73 sg:person.011377067477.63 schema:affiliation https://www.grid.ac/institutes/grid.427848.5
74 schema:familyName Ahner
75 schema:givenName Darryl K.
76 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011377067477.63
77 rdf:type schema:Person
78 sg:person.012436003107.02 schema:affiliation https://www.grid.ac/institutes/grid.427848.5
79 schema:familyName Lunday
80 schema:givenName Brian J.
81 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012436003107.02
82 rdf:type schema:Person
83 sg:pub.10.1007/bf02430363 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035449866
84 https://doi.org/10.1007/bf02430363
85 rdf:type schema:CreativeWork
86 sg:pub.10.1023/a:1009634810396 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044731504
87 https://doi.org/10.1023/a:1009634810396
88 rdf:type schema:CreativeWork
89 https://doi.org/10.1016/j.ijleo.2015.12.122 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031388303
90 rdf:type schema:CreativeWork
91 https://doi.org/10.1016/s1568-4946(02)00027-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033222831
92 rdf:type schema:CreativeWork
93 https://doi.org/10.1080/00207540600988105 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008113626
94 rdf:type schema:CreativeWork
95 https://doi.org/10.1109/cdc.1987.272755 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086203685
96 rdf:type schema:CreativeWork
97 https://doi.org/10.1109/icinfa.2015.7279633 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095430934
98 rdf:type schema:CreativeWork
99 https://doi.org/10.1109/wcica.2016.7578704 schema:sameAs https://app.dimensions.ai/details/publication/pub.1093511962
100 rdf:type schema:CreativeWork
101 https://doi.org/10.1287/ijoc.1.4.232 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064706395
102 rdf:type schema:CreativeWork
103 https://doi.org/10.1287/opre.1070.0440 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064725913
104 rdf:type schema:CreativeWork
105 https://doi.org/10.1287/opre.14.6.992 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064727049
106 rdf:type schema:CreativeWork
107 https://doi.org/10.1287/opre.18.2.334 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064727452
108 rdf:type schema:CreativeWork
109 https://doi.org/10.1287/opre.6.3.346 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064731720
110 rdf:type schema:CreativeWork
111 https://doi.org/10.1287/opre.7.3.322 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064731809
112 rdf:type schema:CreativeWork
113 https://doi.org/10.14569/ijacsa.2017.080412 schema:sameAs https://app.dimensions.ai/details/publication/pub.1085302672
114 rdf:type schema:CreativeWork
115 https://doi.org/10.21236/ad0602672 schema:sameAs https://app.dimensions.ai/details/publication/pub.1091770826
116 rdf:type schema:CreativeWork
117 https://www.grid.ac/institutes/grid.427848.5 schema:alternateName Air Force Institute of Technology
118 schema:name Air Force Institute of Technology, 2950 Hobson Way, 45433-7765, Wright-Patterson AFB, OH, USA
119 rdf:type schema:Organization
 




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


...