A note on a mixed routing and scheduling problem on a grid graph View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2017-11

AUTHORS

Marisa Cenci, Mirko Di Giacomo, Francesco Mason

ABSTRACT

We consider a particular case of the Fleet Quickest Routing Problem (FQRP) on a grid graph of m × n nodes that are placed in m levels and n columns. Starting nodes are placed at the first (bottom) level, and nodes of arrival are placed at the mth level. A feasible solution of FQRP consists in n Manhattan paths, one for each vehicle, such that capacity constraints are respected. We establish m*, i.e. the number of levels that ensures the existence of a solution to FQRP in any possible permutation of n destinations. In particular, m* is the minimum number of levels sufficient to solve any instance of FQRP involving n vehicles, when they move in the ways that the literature has until now assumed. Existing algorithms give solutions that require, for some values of n, more levels than m*. For this reason, we provide algorithm CaR, which gives a solution in a graph m* × n, as a minor contribution. More... »

PAGES

1363-1376

References to SciGraph publications

  • 2006-03. Airport management: taxi planning in ANNALS OF OPERATIONS RESEARCH
  • 2014-10. A more realistic approach for airport ground movement optimisation with stand holding in JOURNAL OF SCHEDULING
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1057/s41274-016-0152-9

    DOI

    http://dx.doi.org/10.1057/s41274-016-0152-9

    DIMENSIONS

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


    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": "Roma Tre University", 
              "id": "https://www.grid.ac/institutes/grid.8509.4", 
              "name": [
                "Department of Business Studies, University of Rome III, Via Silvio D\u2019Amico 77, 00145, Rome, Italy"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Cenci", 
            "givenName": "Marisa", 
            "id": "sg:person.011654336515.86", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011654336515.86"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Roma Tre University", 
              "id": "https://www.grid.ac/institutes/grid.8509.4", 
              "name": [
                "Department of Business Studies, University of Rome III, Via Silvio D\u2019Amico 77, 00145, Rome, Italy"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Di Giacomo", 
            "givenName": "Mirko", 
            "id": "sg:person.012665462157.01", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012665462157.01"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Ca Foscari University of Venice", 
              "id": "https://www.grid.ac/institutes/grid.7240.1", 
              "name": [
                "Department of Management, University of Venice, S.Giobbe Cannaregio 873, 30121, Venice, Italy"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Mason", 
            "givenName": "Francesco", 
            "id": "sg:person.015653364157.39", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015653364157.39"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1155/2008/732828", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1001833243"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.2514/6.2009-6933", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006348828"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10479-006-7381-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026767188", 
              "https://doi.org/10.1007/s10479-006-7381-2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10479-006-7381-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026767188", 
              "https://doi.org/10.1007/s10479-006-7381-2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.2514/6.2007-6553", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040559099"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10951-013-0323-3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051050487", 
              "https://doi.org/10.1007/s10951-013-0323-3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tits.2011.2131650", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061657784"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2017-11", 
        "datePublishedReg": "2017-11-01", 
        "description": "We consider a particular case of the Fleet Quickest Routing Problem (FQRP) on a grid graph of m \u00d7 n nodes that are placed in m levels and n columns. Starting nodes are placed at the first (bottom) level, and nodes of arrival are placed at the mth level. A feasible solution of FQRP consists in n Manhattan paths, one for each vehicle, such that capacity constraints are respected. We establish m*, i.e. the number of levels that ensures the existence of a solution to FQRP in any possible permutation of n destinations. In particular, m* is the minimum number of levels sufficient to solve any instance of FQRP involving n vehicles, when they move in the ways that the literature has until now assumed. Existing algorithms give solutions that require, for some values of n, more levels than m*. For this reason, we provide algorithm CaR, which gives a solution in a graph m* \u00d7 n, as a minor contribution.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1057/s41274-016-0152-9", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": [
          {
            "id": "sg:journal.1087747", 
            "issn": [
              "0160-5682", 
              "1476-9360"
            ], 
            "name": "Journal of the Operational Research Society", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "11", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "68"
          }
        ], 
        "name": "A note on a mixed routing and scheduling problem on a grid graph", 
        "pagination": "1363-1376", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "84291c70a529bd84a959eb874ea829a758d86a535f78a20d26bd345244d40cbb"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1057/s41274-016-0152-9"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1053923865"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1057/s41274-016-0152-9", 
          "https://app.dimensions.ai/details/publication/pub.1053923865"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-10T19:56", 
        "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_8681_00000508.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1057/s41274-016-0152-9"
      }
    ]
     

    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.1057/s41274-016-0152-9'

    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.1057/s41274-016-0152-9'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1057/s41274-016-0152-9'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1057/s41274-016-0152-9'


     

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

    98 TRIPLES      21 PREDICATES      33 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1057/s41274-016-0152-9 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author Nb8aa5326f3974780ae23e1edb5979c92
    4 schema:citation sg:pub.10.1007/s10479-006-7381-2
    5 sg:pub.10.1007/s10951-013-0323-3
    6 https://doi.org/10.1109/tits.2011.2131650
    7 https://doi.org/10.1155/2008/732828
    8 https://doi.org/10.2514/6.2007-6553
    9 https://doi.org/10.2514/6.2009-6933
    10 schema:datePublished 2017-11
    11 schema:datePublishedReg 2017-11-01
    12 schema:description We consider a particular case of the Fleet Quickest Routing Problem (FQRP) on a grid graph of m × n nodes that are placed in m levels and n columns. Starting nodes are placed at the first (bottom) level, and nodes of arrival are placed at the mth level. A feasible solution of FQRP consists in n Manhattan paths, one for each vehicle, such that capacity constraints are respected. We establish m*, i.e. the number of levels that ensures the existence of a solution to FQRP in any possible permutation of n destinations. In particular, m* is the minimum number of levels sufficient to solve any instance of FQRP involving n vehicles, when they move in the ways that the literature has until now assumed. Existing algorithms give solutions that require, for some values of n, more levels than m*. For this reason, we provide algorithm CaR, which gives a solution in a graph m* × n, as a minor contribution.
    13 schema:genre research_article
    14 schema:inLanguage en
    15 schema:isAccessibleForFree true
    16 schema:isPartOf N64b2248496e6496087c10f32d79a37d6
    17 N9f00be2595734d8b9d63192661fe81bb
    18 sg:journal.1087747
    19 schema:name A note on a mixed routing and scheduling problem on a grid graph
    20 schema:pagination 1363-1376
    21 schema:productId N049db63737f04087a41737d56d3a9919
    22 Na708c1a406944a139efa46563e151344
    23 Nd0e96ffc201e42fb89a8dced3ecd031e
    24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053923865
    25 https://doi.org/10.1057/s41274-016-0152-9
    26 schema:sdDatePublished 2019-04-10T19:56
    27 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    28 schema:sdPublisher Ncbd0abca291b4392bf6add478290c7f5
    29 schema:url http://link.springer.com/10.1057/s41274-016-0152-9
    30 sgo:license sg:explorer/license/
    31 sgo:sdDataset articles
    32 rdf:type schema:ScholarlyArticle
    33 N049db63737f04087a41737d56d3a9919 schema:name doi
    34 schema:value 10.1057/s41274-016-0152-9
    35 rdf:type schema:PropertyValue
    36 N64b2248496e6496087c10f32d79a37d6 schema:volumeNumber 68
    37 rdf:type schema:PublicationVolume
    38 N750dfe1b4fbd4115a17a7140d42fd7de rdf:first sg:person.015653364157.39
    39 rdf:rest rdf:nil
    40 N9f00be2595734d8b9d63192661fe81bb schema:issueNumber 11
    41 rdf:type schema:PublicationIssue
    42 Na708c1a406944a139efa46563e151344 schema:name dimensions_id
    43 schema:value pub.1053923865
    44 rdf:type schema:PropertyValue
    45 Nb8aa5326f3974780ae23e1edb5979c92 rdf:first sg:person.011654336515.86
    46 rdf:rest Ncbd6e0ea25ca49e48b75013133251091
    47 Ncbd0abca291b4392bf6add478290c7f5 schema:name Springer Nature - SN SciGraph project
    48 rdf:type schema:Organization
    49 Ncbd6e0ea25ca49e48b75013133251091 rdf:first sg:person.012665462157.01
    50 rdf:rest N750dfe1b4fbd4115a17a7140d42fd7de
    51 Nd0e96ffc201e42fb89a8dced3ecd031e schema:name readcube_id
    52 schema:value 84291c70a529bd84a959eb874ea829a758d86a535f78a20d26bd345244d40cbb
    53 rdf:type schema:PropertyValue
    54 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    55 schema:name Information and Computing Sciences
    56 rdf:type schema:DefinedTerm
    57 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    58 schema:name Computation Theory and Mathematics
    59 rdf:type schema:DefinedTerm
    60 sg:journal.1087747 schema:issn 0160-5682
    61 1476-9360
    62 schema:name Journal of the Operational Research Society
    63 rdf:type schema:Periodical
    64 sg:person.011654336515.86 schema:affiliation https://www.grid.ac/institutes/grid.8509.4
    65 schema:familyName Cenci
    66 schema:givenName Marisa
    67 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011654336515.86
    68 rdf:type schema:Person
    69 sg:person.012665462157.01 schema:affiliation https://www.grid.ac/institutes/grid.8509.4
    70 schema:familyName Di Giacomo
    71 schema:givenName Mirko
    72 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012665462157.01
    73 rdf:type schema:Person
    74 sg:person.015653364157.39 schema:affiliation https://www.grid.ac/institutes/grid.7240.1
    75 schema:familyName Mason
    76 schema:givenName Francesco
    77 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015653364157.39
    78 rdf:type schema:Person
    79 sg:pub.10.1007/s10479-006-7381-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026767188
    80 https://doi.org/10.1007/s10479-006-7381-2
    81 rdf:type schema:CreativeWork
    82 sg:pub.10.1007/s10951-013-0323-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051050487
    83 https://doi.org/10.1007/s10951-013-0323-3
    84 rdf:type schema:CreativeWork
    85 https://doi.org/10.1109/tits.2011.2131650 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061657784
    86 rdf:type schema:CreativeWork
    87 https://doi.org/10.1155/2008/732828 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001833243
    88 rdf:type schema:CreativeWork
    89 https://doi.org/10.2514/6.2007-6553 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040559099
    90 rdf:type schema:CreativeWork
    91 https://doi.org/10.2514/6.2009-6933 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006348828
    92 rdf:type schema:CreativeWork
    93 https://www.grid.ac/institutes/grid.7240.1 schema:alternateName Ca Foscari University of Venice
    94 schema:name Department of Management, University of Venice, S.Giobbe Cannaregio 873, 30121, Venice, Italy
    95 rdf:type schema:Organization
    96 https://www.grid.ac/institutes/grid.8509.4 schema:alternateName Roma Tre University
    97 schema:name Department of Business Studies, University of Rome III, Via Silvio D’Amico 77, 00145, Rome, Italy
    98 rdf:type schema:Organization
     




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


    ...