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-08-04T17:14", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220804/entities/gbq_results/chapter/chapter_124.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 Nd104bcc8add8428895bf2db618e8362e
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 N76494ac08a8c48cb83331a950ab05db6
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf N89bae8632c254ffc93286e43ec4ce45a
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 N36a27c54349f4df4a7275783640c3996
47 N5d177ed8fe1c44f2923038dda9098f46
48 schema:publisher Ncfb701cd9fbc49e09b8384eca09c4600
49 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041178342
50 https://doi.org/10.1007/11534273_32
51 schema:sdDatePublished 2022-08-04T17:14
52 schema:sdLicense https://scigraph.springernature.com/explorer/license/
53 schema:sdPublisher N20ac22a0cdd14172a126e98968cdf841
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 N05499b730e7e4ca1892094dfebab9f89 schema:affiliation grid-institutes:None
59 schema:familyName Das
60 schema:givenName Surajit K.
61 rdf:type schema:Person
62 N13de7c5ba9f84f30b55233095187aae3 rdf:first N52ce5d658bf446c4909225e05349d963
63 rdf:rest rdf:nil
64 N1a5c6420d6b84e429eb0962822abfd4a rdf:first N05499b730e7e4ca1892094dfebab9f89
65 rdf:rest rdf:nil
66 N20ac22a0cdd14172a126e98968cdf841 schema:name Springer Nature - SN SciGraph project
67 rdf:type schema:Organization
68 N36a27c54349f4df4a7275783640c3996 schema:name dimensions_id
69 schema:value pub.1041178342
70 rdf:type schema:PropertyValue
71 N52ce5d658bf446c4909225e05349d963 schema:familyName Sack
72 schema:givenName Jörg-Rüdiger
73 rdf:type schema:Person
74 N5d177ed8fe1c44f2923038dda9098f46 schema:name doi
75 schema:value 10.1007/11534273_32
76 rdf:type schema:PropertyValue
77 N6b3cb9f27a424b56bb9f016410062a52 schema:familyName López-Ortiz
78 schema:givenName Alejandro
79 rdf:type schema:Person
80 N76494ac08a8c48cb83331a950ab05db6 rdf:first Nd74585cdaacc4546a916bbb99c29164e
81 rdf:rest N9d8e3044a5644483bb4ab66d093059bc
82 N89bae8632c254ffc93286e43ec4ce45a schema:isbn 978-3-540-28101-6
83 978-3-540-31711-1
84 schema:name Algorithms and Data Structures
85 rdf:type schema:Book
86 N9d8e3044a5644483bb4ab66d093059bc rdf:first N6b3cb9f27a424b56bb9f016410062a52
87 rdf:rest N13de7c5ba9f84f30b55233095187aae3
88 Ncfb701cd9fbc49e09b8384eca09c4600 schema:name Springer Nature
89 rdf:type schema:Organisation
90 Nd104bcc8add8428895bf2db618e8362e rdf:first sg:person.01274506210.27
91 rdf:rest N1a5c6420d6b84e429eb0962822abfd4a
92 Nd74585cdaacc4546a916bbb99c29164e schema:familyName Dehne
93 schema:givenName Frank
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)


...