On the Vehicle Routing Problem View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2005

AUTHORS

Piotr Berman , Surajit K. Das

ABSTRACT

In the Vehicle Routing Problem (VRP), as in the Traveling Salesman Problem (TSP), we have a metric space of customer points, and we have to visits all customers. Additionally, every customer has a demand, a quantity of a commodity that has to be delivered in our vehicle from a single point called the depot. Because the vehicle capacity is bounded, we need to return to the depot each time we run out of the commodity to distribute. We describe a fully polynomial time algorithm with approximation 2.5, we also modify this algorithm for the on-line version of VRP, the randomized version has competitive ratio of 2.5 on the average, and the deterministic version has ratio 4. We also describe 2 approximation for a restricted version of the problem. More... »

PAGES

360-371

Book

TITLE

Algorithms and Data Structures

ISBN

978-3-540-28101-6
978-3-540-31711-1

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11534273_32

DOI

http://dx.doi.org/10.1007/11534273_32

DIMENSIONS

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


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/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "The Pennsylvania State University", 
          "id": "http://www.grid.ac/institutes/grid.29857.31", 
          "name": [
            "The Pennsylvania State University"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Berman", 
        "givenName": "Piotr", 
        "id": "sg:person.01274506210.27", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Penske Logistics", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Penske Logistics"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Das", 
        "givenName": "Surajit K.", 
        "type": "Person"
      }
    ], 
    "datePublished": "2005", 
    "datePublishedReg": "2005-01-01", 
    "description": "In the Vehicle Routing Problem (VRP), as in the Traveling Salesman Problem (TSP), we have a metric space of customer points, and we have to visits all customers. Additionally, every customer has a demand, a quantity of a commodity that has to be delivered in our vehicle from a single point called the depot. Because the vehicle capacity is bounded, we need to return to the depot each time we run out of the commodity to distribute. We describe a fully polynomial time algorithm with approximation 2.5, we also modify this algorithm for the on-line version of VRP, the randomized version has competitive ratio of 2.5 on the average, and the deterministic version has ratio 4. We also describe 2 approximation for a restricted version of the problem.", 
    "editor": [
      {
        "familyName": "Dehne", 
        "givenName": "Frank", 
        "type": "Person"
      }, 
      {
        "familyName": "L\u00f3pez-Ortiz", 
        "givenName": "Alejandro", 
        "type": "Person"
      }, 
      {
        "familyName": "Sack", 
        "givenName": "J\u00f6rg-R\u00fcdiger", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/11534273_32", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-28101-6", 
        "978-3-540-31711-1"
      ], 
      "name": "Algorithms and Data Structures", 
      "type": "Book"
    }, 
    "keywords": [
      "customer point", 
      "vehicle capacity", 
      "vehicle routing problem", 
      "customers", 
      "commodities", 
      "routing problem", 
      "demand", 
      "VRP", 
      "deterministic version", 
      "vehicles", 
      "depots", 
      "problem", 
      "single point", 
      "point", 
      "restricted version", 
      "competitive ratio", 
      "version", 
      "quantity", 
      "capacity", 
      "time", 
      "average", 
      "visits", 
      "Traveling Salesman Problem", 
      "salesman problem", 
      "ratio", 
      "space", 
      "algorithm", 
      "polynomial time algorithm", 
      "ratio 4", 
      "line version", 
      "approximation", 
      "time algorithm", 
      "metric spaces"
    ], 
    "name": "On the Vehicle Routing Problem", 
    "pagination": "360-371", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1041178342"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/11534273_32"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/11534273_32", 
      "https://app.dimensions.ai/details/publication/pub.1041178342"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-10-01T06:55", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221001/entities/gbq_results/chapter/chapter_275.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/11534273_32"
  }
]
 

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/11534273_32'

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/11534273_32'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/11534273_32'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/11534273_32'


 

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

111 TRIPLES      22 PREDICATES      58 URIs      51 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/11534273_32 schema:about anzsrc-for:01
2 anzsrc-for:0103
3 schema:author Ne7e9570184c440528b4484afdcaf144c
4 schema:datePublished 2005
5 schema:datePublishedReg 2005-01-01
6 schema:description In the Vehicle Routing Problem (VRP), as in the Traveling Salesman Problem (TSP), we have a metric space of customer points, and we have to visits all customers. Additionally, every customer has a demand, a quantity of a commodity that has to be delivered in our vehicle from a single point called the depot. Because the vehicle capacity is bounded, we need to return to the depot each time we run out of the commodity to distribute. We describe a fully polynomial time algorithm with approximation 2.5, we also modify this algorithm for the on-line version of VRP, the randomized version has competitive ratio of 2.5 on the average, and the deterministic version has ratio 4. We also describe 2 approximation for a restricted version of the problem.
7 schema:editor N86bc92b5f947430f88d334a295d39912
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf Na857141f06f04adbb338cc864d3df643
11 schema:keywords Traveling Salesman Problem
12 VRP
13 algorithm
14 approximation
15 average
16 capacity
17 commodities
18 competitive ratio
19 customer point
20 customers
21 demand
22 depots
23 deterministic version
24 line version
25 metric spaces
26 point
27 polynomial time algorithm
28 problem
29 quantity
30 ratio
31 ratio 4
32 restricted version
33 routing problem
34 salesman problem
35 single point
36 space
37 time
38 time algorithm
39 vehicle capacity
40 vehicle routing problem
41 vehicles
42 version
43 visits
44 schema:name On the Vehicle Routing Problem
45 schema:pagination 360-371
46 schema:productId Nc09df506152d4114ab589f0237e69df4
47 Nd5f1d67aefe74f8c9d948516f1c4a7e4
48 schema:publisher Nf4d439113e5247dea3d6555c72570923
49 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041178342
50 https://doi.org/10.1007/11534273_32
51 schema:sdDatePublished 2022-10-01T06:55
52 schema:sdLicense https://scigraph.springernature.com/explorer/license/
53 schema:sdPublisher Ne1b1b072e3a8436295d467369a00ffc4
54 schema:url https://doi.org/10.1007/11534273_32
55 sgo:license sg:explorer/license/
56 sgo:sdDataset chapters
57 rdf:type schema:Chapter
58 N00bfdf98e4da42d8af193230fecab0ae schema:familyName Sack
59 schema:givenName Jörg-Rüdiger
60 rdf:type schema:Person
61 N3473dfc6cd8d4a6eb4e47ad3c77c5afd rdf:first Nffb42d3fa02b403f9116f8b8f4e120a7
62 rdf:rest Nb3a788cabd8e42178f059a165450a6b0
63 N535f119c6a2e42d79414dd153d0022a0 schema:affiliation grid-institutes:None
64 schema:familyName Das
65 schema:givenName Surajit K.
66 rdf:type schema:Person
67 N86bc92b5f947430f88d334a295d39912 rdf:first N99cd36a0d2464d858a1bce88774a7f27
68 rdf:rest N3473dfc6cd8d4a6eb4e47ad3c77c5afd
69 N99cd36a0d2464d858a1bce88774a7f27 schema:familyName Dehne
70 schema:givenName Frank
71 rdf:type schema:Person
72 Na857141f06f04adbb338cc864d3df643 schema:isbn 978-3-540-28101-6
73 978-3-540-31711-1
74 schema:name Algorithms and Data Structures
75 rdf:type schema:Book
76 Nb3530e1ed63b43358f10cc376ca37779 rdf:first N535f119c6a2e42d79414dd153d0022a0
77 rdf:rest rdf:nil
78 Nb3a788cabd8e42178f059a165450a6b0 rdf:first N00bfdf98e4da42d8af193230fecab0ae
79 rdf:rest rdf:nil
80 Nc09df506152d4114ab589f0237e69df4 schema:name dimensions_id
81 schema:value pub.1041178342
82 rdf:type schema:PropertyValue
83 Nd5f1d67aefe74f8c9d948516f1c4a7e4 schema:name doi
84 schema:value 10.1007/11534273_32
85 rdf:type schema:PropertyValue
86 Ne1b1b072e3a8436295d467369a00ffc4 schema:name Springer Nature - SN SciGraph project
87 rdf:type schema:Organization
88 Ne7e9570184c440528b4484afdcaf144c rdf:first sg:person.01274506210.27
89 rdf:rest Nb3530e1ed63b43358f10cc376ca37779
90 Nf4d439113e5247dea3d6555c72570923 schema:name Springer Nature
91 rdf:type schema:Organisation
92 Nffb42d3fa02b403f9116f8b8f4e120a7 schema:familyName López-Ortiz
93 schema:givenName Alejandro
94 rdf:type schema:Person
95 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
96 schema:name Mathematical Sciences
97 rdf:type schema:DefinedTerm
98 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
99 schema:name Numerical and Computational Mathematics
100 rdf:type schema:DefinedTerm
101 sg:person.01274506210.27 schema:affiliation grid-institutes:grid.29857.31
102 schema:familyName Berman
103 schema:givenName Piotr
104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274506210.27
105 rdf:type schema:Person
106 grid-institutes:None schema:alternateName Penske Logistics
107 schema:name Penske Logistics
108 rdf:type schema:Organization
109 grid-institutes:grid.29857.31 schema:alternateName The Pennsylvania State University
110 schema:name The Pennsylvania State University
111 rdf:type schema:Organization
 




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


...