A Simulated Annealing Algorithm for the Vehicle Routing Problem with Time Windows and Synchronization Constraints View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2013

AUTHORS

Sohaib Afifi , Duc-Cuong Dang , Aziz Moukrim

ABSTRACT

This paper focuses on solving a variant of the vehicle routing problem (VRP) in which a time window is associated with each customer service and some services require simultaneous visits from different vehicles to be accomplished. The problem is therefore called the VRP with time windows and synchronization constraints (VRPTWSyn). We present a simulated annealing algorithm (SA) that incorporates several local search techniques to deal with this problem. Experiments on the instances from the literature show that our SA is fast and outperforms the existing approaches. To the best of our knowledge, this is the first time that dedicated local search methods have been proposed and evaluated on this variant of VRP. More... »

PAGES

259-265

References to SciGraph publications

  • 2003-09. Local branching in MATHEMATICAL PROGRAMMING
  • Book

    TITLE

    Learning and Intelligent Optimization

    ISBN

    978-3-642-44972-7
    978-3-642-44973-4

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-642-44973-4_27

    DOI

    http://dx.doi.org/10.1007/978-3-642-44973-4_27

    DIMENSIONS

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


    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/0801", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Artificial Intelligence and Image Processing", 
            "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": "University of Technology of Compi\u00e8gne", 
              "id": "https://www.grid.ac/institutes/grid.6227.1", 
              "name": [
                "Universit\u00e9 de Technologie de Compi\u00e8gne, Laboratoire Heudiasyc, UMR 7253 CNRS, Compi\u00e8gne, 60205, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Afifi", 
            "givenName": "Sohaib", 
            "id": "sg:person.016457773337.57", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016457773337.57"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Technology of Compi\u00e8gne", 
              "id": "https://www.grid.ac/institutes/grid.6227.1", 
              "name": [
                "Universit\u00e9 de Technologie de Compi\u00e8gne, Laboratoire Heudiasyc, UMR 7253 CNRS, Compi\u00e8gne, 60205, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Dang", 
            "givenName": "Duc-Cuong", 
            "id": "sg:person.010450452545.61", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010450452545.61"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Technology of Compi\u00e8gne", 
              "id": "https://www.grid.ac/institutes/grid.6227.1", 
              "name": [
                "Universit\u00e9 de Technologie de Compi\u00e8gne, Laboratoire Heudiasyc, UMR 7253 CNRS, Compi\u00e8gne, 60205, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Moukrim", 
            "givenName": "Aziz", 
            "id": "sg:person.07422722115.73", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07422722115.73"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/s10107-003-0395-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1023883503", 
              "https://doi.org/10.1007/s10107-003-0395-5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.ejor.2007.07.033", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051301329"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1126/science.220.4598.671", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062526985"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1287/ijoc.8.2.158", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064707582"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1287/trsc.1110.0400", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064734449"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1287/trsc.22.1.1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064735081"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/1.9780898718515", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1095974320"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2013", 
        "datePublishedReg": "2013-01-01", 
        "description": "This paper focuses on solving a variant of the vehicle routing problem (VRP) in which a time window is associated with each customer service and some services require simultaneous visits from different vehicles to be accomplished. The problem is therefore called the VRP with time windows and synchronization constraints (VRPTWSyn). We present a simulated annealing algorithm (SA) that incorporates several local search techniques to deal with this problem. Experiments on the instances from the literature show that our SA is fast and outperforms the existing approaches. To the best of our knowledge, this is the first time that dedicated local search methods have been proposed and evaluated on this variant of VRP.", 
        "editor": [
          {
            "familyName": "Nicosia", 
            "givenName": "Giuseppe", 
            "type": "Person"
          }, 
          {
            "familyName": "Pardalos", 
            "givenName": "Panos", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-642-44973-4_27", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-642-44972-7", 
            "978-3-642-44973-4"
          ], 
          "name": "Learning and Intelligent Optimization", 
          "type": "Book"
        }, 
        "name": "A Simulated Annealing Algorithm for the Vehicle Routing Problem with Time Windows and Synchronization Constraints", 
        "pagination": "259-265", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-642-44973-4_27"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "560844d63d8af2266fba6284a501e1255e32eee449b0c5efe7f4c7f947c10168"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1018056213"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-642-44973-4_27", 
          "https://app.dimensions.ai/details/publication/pub.1018056213"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-15T22:54", 
        "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_00000254.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/10.1007/978-3-642-44973-4_27"
      }
    ]
     

    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/978-3-642-44973-4_27'

    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/978-3-642-44973-4_27'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-44973-4_27'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-44973-4_27'


     

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

    106 TRIPLES      23 PREDICATES      34 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-642-44973-4_27 schema:about anzsrc-for:08
    2 anzsrc-for:0801
    3 schema:author N9ce131ea47284091a08c75de8c2ed6fd
    4 schema:citation sg:pub.10.1007/s10107-003-0395-5
    5 https://doi.org/10.1016/j.ejor.2007.07.033
    6 https://doi.org/10.1126/science.220.4598.671
    7 https://doi.org/10.1137/1.9780898718515
    8 https://doi.org/10.1287/ijoc.8.2.158
    9 https://doi.org/10.1287/trsc.1110.0400
    10 https://doi.org/10.1287/trsc.22.1.1
    11 schema:datePublished 2013
    12 schema:datePublishedReg 2013-01-01
    13 schema:description This paper focuses on solving a variant of the vehicle routing problem (VRP) in which a time window is associated with each customer service and some services require simultaneous visits from different vehicles to be accomplished. The problem is therefore called the VRP with time windows and synchronization constraints (VRPTWSyn). We present a simulated annealing algorithm (SA) that incorporates several local search techniques to deal with this problem. Experiments on the instances from the literature show that our SA is fast and outperforms the existing approaches. To the best of our knowledge, this is the first time that dedicated local search methods have been proposed and evaluated on this variant of VRP.
    14 schema:editor N60d0872f5d324609b701e4d0ba775655
    15 schema:genre chapter
    16 schema:inLanguage en
    17 schema:isAccessibleForFree false
    18 schema:isPartOf N119e0aed4c7b4d97babbb752c7201da3
    19 schema:name A Simulated Annealing Algorithm for the Vehicle Routing Problem with Time Windows and Synchronization Constraints
    20 schema:pagination 259-265
    21 schema:productId N42935b3818e84156a0a7ec26131d2932
    22 N70eb1496fe9e46668eb1838e48a61eb5
    23 N75bf4dea2f5e481ea5bc93e94352dc6f
    24 schema:publisher N9c2b8bc9454744818a3fcd40b59f1d45
    25 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018056213
    26 https://doi.org/10.1007/978-3-642-44973-4_27
    27 schema:sdDatePublished 2019-04-15T22:54
    28 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    29 schema:sdPublisher Ne6bcf7ec098a40f0b672496bb1a1c28b
    30 schema:url http://link.springer.com/10.1007/978-3-642-44973-4_27
    31 sgo:license sg:explorer/license/
    32 sgo:sdDataset chapters
    33 rdf:type schema:Chapter
    34 N119e0aed4c7b4d97babbb752c7201da3 schema:isbn 978-3-642-44972-7
    35 978-3-642-44973-4
    36 schema:name Learning and Intelligent Optimization
    37 rdf:type schema:Book
    38 N12a9afcf33fb4e309708cb1f3e61e4d4 rdf:first sg:person.010450452545.61
    39 rdf:rest Nf87f3b97f24048899888b85d893f83a8
    40 N42935b3818e84156a0a7ec26131d2932 schema:name readcube_id
    41 schema:value 560844d63d8af2266fba6284a501e1255e32eee449b0c5efe7f4c7f947c10168
    42 rdf:type schema:PropertyValue
    43 N5d2c62e1d1bb4b89841411cedd6453ac schema:familyName Nicosia
    44 schema:givenName Giuseppe
    45 rdf:type schema:Person
    46 N60d0872f5d324609b701e4d0ba775655 rdf:first N5d2c62e1d1bb4b89841411cedd6453ac
    47 rdf:rest Nc372254291ca42f4af0afc02fb33d120
    48 N70eb1496fe9e46668eb1838e48a61eb5 schema:name dimensions_id
    49 schema:value pub.1018056213
    50 rdf:type schema:PropertyValue
    51 N75bf4dea2f5e481ea5bc93e94352dc6f schema:name doi
    52 schema:value 10.1007/978-3-642-44973-4_27
    53 rdf:type schema:PropertyValue
    54 N899c2f98ce284a9ca47cf301e407ed53 schema:familyName Pardalos
    55 schema:givenName Panos
    56 rdf:type schema:Person
    57 N9c2b8bc9454744818a3fcd40b59f1d45 schema:location Berlin, Heidelberg
    58 schema:name Springer Berlin Heidelberg
    59 rdf:type schema:Organisation
    60 N9ce131ea47284091a08c75de8c2ed6fd rdf:first sg:person.016457773337.57
    61 rdf:rest N12a9afcf33fb4e309708cb1f3e61e4d4
    62 Nc372254291ca42f4af0afc02fb33d120 rdf:first N899c2f98ce284a9ca47cf301e407ed53
    63 rdf:rest rdf:nil
    64 Ne6bcf7ec098a40f0b672496bb1a1c28b schema:name Springer Nature - SN SciGraph project
    65 rdf:type schema:Organization
    66 Nf87f3b97f24048899888b85d893f83a8 rdf:first sg:person.07422722115.73
    67 rdf:rest rdf:nil
    68 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    69 schema:name Information and Computing Sciences
    70 rdf:type schema:DefinedTerm
    71 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
    72 schema:name Artificial Intelligence and Image Processing
    73 rdf:type schema:DefinedTerm
    74 sg:person.010450452545.61 schema:affiliation https://www.grid.ac/institutes/grid.6227.1
    75 schema:familyName Dang
    76 schema:givenName Duc-Cuong
    77 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010450452545.61
    78 rdf:type schema:Person
    79 sg:person.016457773337.57 schema:affiliation https://www.grid.ac/institutes/grid.6227.1
    80 schema:familyName Afifi
    81 schema:givenName Sohaib
    82 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016457773337.57
    83 rdf:type schema:Person
    84 sg:person.07422722115.73 schema:affiliation https://www.grid.ac/institutes/grid.6227.1
    85 schema:familyName Moukrim
    86 schema:givenName Aziz
    87 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07422722115.73
    88 rdf:type schema:Person
    89 sg:pub.10.1007/s10107-003-0395-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023883503
    90 https://doi.org/10.1007/s10107-003-0395-5
    91 rdf:type schema:CreativeWork
    92 https://doi.org/10.1016/j.ejor.2007.07.033 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051301329
    93 rdf:type schema:CreativeWork
    94 https://doi.org/10.1126/science.220.4598.671 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062526985
    95 rdf:type schema:CreativeWork
    96 https://doi.org/10.1137/1.9780898718515 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095974320
    97 rdf:type schema:CreativeWork
    98 https://doi.org/10.1287/ijoc.8.2.158 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064707582
    99 rdf:type schema:CreativeWork
    100 https://doi.org/10.1287/trsc.1110.0400 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064734449
    101 rdf:type schema:CreativeWork
    102 https://doi.org/10.1287/trsc.22.1.1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064735081
    103 rdf:type schema:CreativeWork
    104 https://www.grid.ac/institutes/grid.6227.1 schema:alternateName University of Technology of Compiègne
    105 schema:name Université de Technologie de Compiègne, Laboratoire Heudiasyc, UMR 7253 CNRS, Compiègne, 60205, France
    106 rdf:type schema:Organization
     




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


    ...