"chapters" .
.
.
"https://doi.org/10.1007/11534273_32" .
_:Nf99075e8580d47db8f63517ed2d4095b .
"360-371" .
"ratio" .
"approximation" .
"algorithm" .
_:Nda33cb1e7e7b4aa88e09ce8d19fd81f1 "Algorithms and Data Structures" .
_:N97b0fbeb29c04790985f726ba631c7af .
.
"commodities" .
.
_:N33cfbb4f55034d44975b968c9367cc45 "Alejandro" .
.
_:N026bd384b4de4b40b2bbd36e78b59372 .
_:Nf8f6bb1ded5f4a0abcfa8bacb6ee1476 "Sack" .
"ratio 4" .
"Penske Logistics" .
_:Nda33cb1e7e7b4aa88e09ce8d19fd81f1 .
"visits" .
_:N9e001cd9a1d84d8e816463f1a5db92a7 "doi" .
"Numerical and Computational Mathematics" .
"average" .
"deterministic version" .
.
"false"^^ .
"vehicle routing problem" .
_:Nec9596ac3df646dbbed9965929a347a1 "Springer Nature" .
"2005-01-01" .
_:N01fcb0b1ec43401890ebe7da7d0f648b .
.
"competitive ratio" .
_:N9e001cd9a1d84d8e816463f1a5db92a7 "10.1007/11534273_32" .
"vehicles" .
_:Nf8f6bb1ded5f4a0abcfa8bacb6ee1476 .
"metric spaces" .
"Mathematical Sciences" .
_:N6d6e509c45654a7abee112554d6a7003 _:Neac05bc7eb9b4e918c37cc508e014c41 .
"problem" .
"quantity" .
_:Ne5b50ca0442743d3afe07467ac15d883 .
"time algorithm" .
"customer point" .
"Berman" .
"The Pennsylvania State University" .
_:Nf8f6bb1ded5f4a0abcfa8bacb6ee1476 "J\u00F6rg-R\u00FCdiger" .
.
.
.
"single point" .
_:Nf99075e8580d47db8f63517ed2d4095b "Das" .
_:Nda33cb1e7e7b4aa88e09ce8d19fd81f1 .
_:N33cfbb4f55034d44975b968c9367cc45 .
"Piotr" .
"depots" .
"Traveling Salesman Problem" .
"On the Vehicle Routing Problem" .
"time" .
"polynomial time algorithm" .
_:N7afac6a40b9f4ea09411405ca8e41e94 _:Nf99075e8580d47db8f63517ed2d4095b .
"routing problem" .
_:Ne5b50ca0442743d3afe07467ac15d883 .
"line version" .
_:Nf99075e8580d47db8f63517ed2d4095b "Surajit K." .
"space" .
_:Neac05bc7eb9b4e918c37cc508e014c41 .
_:Nec9596ac3df646dbbed9965929a347a1 .
_:Nda33cb1e7e7b4aa88e09ce8d19fd81f1 "978-3-540-28101-6" .
_:Ne5b50ca0442743d3afe07467ac15d883 _:N7afac6a40b9f4ea09411405ca8e41e94 .
"VRP" .
_:N9e001cd9a1d84d8e816463f1a5db92a7 .
_:N01fcb0b1ec43401890ebe7da7d0f648b _:N26693fd93ae54b59944a51bdb01691ea .
_:N26693fd93ae54b59944a51bdb01691ea "Frank" .
_:N026bd384b4de4b40b2bbd36e78b59372 "pub.1041178342" .
_:N7afac6a40b9f4ea09411405ca8e41e94 .
_:Nf99075e8580d47db8f63517ed2d4095b .
"vehicle capacity" .
"https://scigraph.springernature.com/explorer/license/" .
"salesman problem" .
"version" .
.
"chapter" .
_:N26693fd93ae54b59944a51bdb01691ea .
_:N9e001cd9a1d84d8e816463f1a5db92a7 .
.
.
"customers" .
_:N97b0fbeb29c04790985f726ba631c7af "Springer Nature - SN SciGraph project" .
_:Nec9596ac3df646dbbed9965929a347a1 .
_:Neac05bc7eb9b4e918c37cc508e014c41 _:Nf8f6bb1ded5f4a0abcfa8bacb6ee1476 .
"demand" .
"2022-10-01T06:55" .
"The Pennsylvania State University" .
"point" .
_:N97b0fbeb29c04790985f726ba631c7af .
"Penske Logistics" .
"restricted version" .
"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." .
_:N026bd384b4de4b40b2bbd36e78b59372 .
_:N33cfbb4f55034d44975b968c9367cc45 "L\u00F3pez-Ortiz" .
_:N6d6e509c45654a7abee112554d6a7003 _:N33cfbb4f55034d44975b968c9367cc45 .
_:Nda33cb1e7e7b4aa88e09ce8d19fd81f1 "978-3-540-31711-1" .
_:N26693fd93ae54b59944a51bdb01691ea "Dehne" .
"capacity" .
.
_:N01fcb0b1ec43401890ebe7da7d0f648b _:N6d6e509c45654a7abee112554d6a7003 .
"2005" .
.
_:N026bd384b4de4b40b2bbd36e78b59372 "dimensions_id" .