An Entity of Type: software, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

The vehicle routing problem (VRP) is a combinatorial optimization and integer programming problem which asks "What is the optimal set of routes for a fleet of vehicles to traverse in order to deliver to a given set of customers?". It generalises the well-known travelling salesman problem (TSP). It first appeared in a paper by George Dantzig and John Ramser in 1959, in which the first algorithmic approach was written and was applied to petrol deliveries. Often, the context is that of delivering goods located at a central depot to customers who have placed orders for such goods. The objective of the VRP is to minimize the total route cost. In 1964, Clarke and Wright improved on Dantzig and Ramser's approach using an effective greedy approach called the savings algorithm.

Property Value
dbo:abstract
  • Tourenplanung ist ein Planungsvorgang, bei dem (Transport-)Aufträge zu Touren gruppiert und in eine Reihenfolge gebracht werden. Dabei wird in der Regel eine Tour von einer Person oder einem Fahrzeug durchgeführt. Dieser Planungsprozess ist in allen Bereichen bedeutend, in denen eine Vielzahl von Aufträgen und Touren geplant werden muss. Beispiele sind die Belieferung von Filialen eines Händlers, die Abholung von Post, die Mülleinsammlung, die Personenbeförderung und der Einsatz von Servicepersonal. Bei regelmäßigen Strecken wie im Kurier-Express-Paket-Dienst bilden sich so Transportnetzstrukturen. Ein Auftrag besteht meist darin, eine bestimmte Anzahl Einheiten einer Sendung von einem Start zu einem Ziel zu bringen. Eine Lösung eines Tourenplanungsproblems hat daher meist zwei Aspekte: * die gibt an, welche Aufträge zu einer Tour zusammengefasst werden * das Routing definiert, in welcher Reihenfolge die Punkte innerhalb einer Tour bedient werden. Zielsetzung einer Tourenplanung ist zum Beispiel die Minimierung der Anzahl der eingesetzten Fahrzeuge, der zurückgelegten Strecke, der Einsatzzeit, des CO2-Ausstoßes oder einer komplexeren Kostenfunktion. Beim liegen alle Start- oder Zielpunkte in einem Depot und es steht dort eine begrenzte oder unbegrenzte Zahl von identischen Fahrzeugen mit beschränkter Kapazität zur Verfügung. Andere Varianten betrachten zusätzliche Restriktionen wie z. B. Zeitfenster, mehrere Depots oder beliebige Start- und Zielpunkte (sog. ). In der Realität wird die Aufgabenstellung noch durch viele Restriktionen erweitert. Beispielsweise betrachtet man mehrere Depots, einen heterogenen Fuhrpark oder Vorrangbeziehungen zwischen Aufträgen. Eine andere mögliche Zusatzaufgabe ist die Betrachtung von Zeitfenstern, innerhalb derer ein Fahrzeug beim Kunden eintreffen muss, um die von einem Zeitfenstermanagement vergebenen oder gebuchten Slots einzuhalten. Von einer dynamischen Tourenplanung spricht man dann, wenn sich die Auftragslage während der Planung dynamisch verändert (zum Beispiel durch neu hinzukommende oder stornierte Aufträge). Anwendungen existieren neben dem Logistikbereich in allen Wirtschaftszweigen, die ihre Kunden beliefern (zum Beispiel Möbelindustrie, Müllabfuhr oder Automatenbeschicker). In vielen Unternehmen wird eine Tourenplanungssoftware eingesetzt, um die anfallenden Touren zusammenzustellen und anhand von Kriterien, wie zum Beispiel der Einhaltung von Zeitvorgaben oder Gewichtschranken, sowie Transportkosten zu optimieren. (de)
  • Posible artículo duplicado: Problema de rutas de vehículos El problema de enrutamiento de vehículos (VRP, por su siglas en inglés) es un problema de optimización combinatoria y de programación de entero qué pregunta "¿Cuál es el conjunto óptimo de rutas para una flota de vehículos que debe satisfacer las demandas de un conjunto dado de clientes?". Es una generalización del conocido Problema del Viajante (TSP, por sus siglas en inglés). La primera definición aparece en una artículo de George Dantzig y John Ramser en 1959, en donde plantea una aproximación algorítmica y fue aplicado para entregas de gasolina.​ El problema, requiere la entrega de cierto producto, almacenado en un único local, a los clientes los cuales poseen cierta demanda; el objetivo fundamental es minimizar el coste total de las rutas trazadas. En 1964, Clarke y Wright mejoraron la aproximación de Dantzig y Ramser utilizando una aproximación “greedy” conocido como algoritmo de ahorros. Determinar la solución óptima es un problema NP-duro de optimización combinatoria.​ Las implementaciones más utilizadas para resolver el problema se basan en heurísticas debido a que para grandes instancias del problema, que como sucede en ejemplos reales, producen buenos resultados.El VRP tiene muchas aplicaciones obvias en industrias. De hecho el uso de programas de optimización puede dar ahorros de 5% a una compañía cuando el transporte es normalmente un componente significativo del coste de un producto (10%) - de hecho el sector de transporte hace 10% de PIB de la UE.​​ Consiguientemente, cualesquier ahorros crearon por el VRP, incluso aún, de un 5%, es significativo.​ Existen principalmente tres elementos involucrados en el VRP, que son los clientes, las bodegas o depósitos y la flota de vehículos.En los problemas reales de VRP aparecen muchas restricciones, entre las que cabe citar: * Cada vehículo tiene una capacidad limitada. * Cada cliente tiene que ser visitado dentro de una determinada franja horaria (problema VRP con ventanas de tiempo) * Varios puntos de suministro (problema VRP con múltiples depósitos) * Los clientes pueden ser atendidos por varios vehículos (problema VRP con suministro dividido) * Algunas variables del problema son aleatorias, tales como el número de clientes, sus demandas, etc. (problema VRP estocástico) * Las entregas se deben realizar en determinados días (problema VRP periódico) (es)
  • The vehicle routing problem (VRP) is a combinatorial optimization and integer programming problem which asks "What is the optimal set of routes for a fleet of vehicles to traverse in order to deliver to a given set of customers?". It generalises the well-known travelling salesman problem (TSP). It first appeared in a paper by George Dantzig and John Ramser in 1959, in which the first algorithmic approach was written and was applied to petrol deliveries. Often, the context is that of delivering goods located at a central depot to customers who have placed orders for such goods. The objective of the VRP is to minimize the total route cost. In 1964, Clarke and Wright improved on Dantzig and Ramser's approach using an effective greedy approach called the savings algorithm. Determining the optimal solution to VRP is NP-hard, so the size of problems that can be solved, optimally, using mathematical programming or combinatorial optimization may be limited. Therefore, commercial solvers tend to use heuristics due to the size and frequency of real world VRPs they need to solve. The VRP has many direct applications in industry. In fact, the use of computer optimization programs can give savings of 5% to a company as transportation is usually a significant component of the cost of a product (10%) - indeed, the transportation sector makes up 10% of the EU's GDP. Consequently, any savings created by the VRP, even less than 5%, are significant. (en)
  • Il Vehicle routing problem (VRP) è una classe di problemi nell'ambito della ricerca operativa. Questi problemi trattano tutti gli aspetti della gestione di una flotta dei veicoli nell'ambito della logistica. (it)
  • Problem marszrutyzacji – problem decyzyjny polegający na wyznaczeniu optymalnych tras przewozowych dla pewnej ściśle określonej liczby środków transportu, której zadaniem jest obsłużenie zbioru klientów znajdujących się w różnych punktach przy zachowaniu ograniczeń. Kryterium optymalizacji jest całkowity koszt transportu (wyrażony odległościowo, cenowo lub czasowo). Istnieją również rozwinięcia problemu uwzględniające więcej niż jedno kryterium optymalizacji. Problem marszrutyzacji należy do podstawowej problematyki zarządzania operacyjnego flotą środków transportu (rzadziej zarządzania na wyższym szczeblu). Problem ten jest rozwinięciem takich problemów, jak: * problem komiwojażera (ang. traveling salesman problem), * problem chińskiego listonosza (ang. Chinese postman problem), oraz zaliczany jest do problemów NP-trudnych. Z tego względu zazwyczaj jest rozwiązywany przy pomocy metod heurystycznych. Algorytmy dokładne mogą być wykorzystywane tylko dla problemów o stosunkowo niewielkiej liczbie klientów (do 135). Problem został po raz pierwszy zaprezentowany przez G.B. Dantziga oraz R.H. Ramsera w 1959 roku w pracy The Truck Dispatching Problem opublikowanej na łamach czasopisma . (pl)
  • O problema de roteamento de veículos (PRV) é um dos mais estudados problemas na área da otimização combinatória. Consiste no atendimento de um conjunto de consumidores por intermédio de uma frota de veículos, que partem de um ou mais pontos denominados depósitos. A restrição presente no PRV é que cada veículo possui uma capacidade e o somatório de todas as demandas dos consumidores atendidos por um veículo não pode ultrapassar . O PRV, apesar do seu enunciado relativamente simples, apresenta elevada complexidade computacional, pelo que é interessante como problema no teste de diversas heurísticas. Na literatura científica, Dantzig e Ramser foram os primeiros autores a formular o PRV, em 1959, quando estudaram a aplicação real na distribuição de gasolina para estações de venda de combustíveis no trabalho . A função objetivo depende da tipologia e das características do problema. Os mais comuns são minimizar o custo total da operação, minimizar o tempo total de transporte, minimizar a distância total percorrida, minimizar o tempo de espera, maximizar o benefício, maximizar o serviço ao cliente, minimizar a utilização de veículos, equilibrar a utilização dos recursos, etc. (pt)
  • 车辆路径问题(VRP)是一个组合优化和(回答了“为了交付给定的一组客户,车辆车队的最佳路线集是什么?”)。它概括了众所周知的旅行推销员问题(TSP)。它最初出现在1959年George Dantzig和John Ramser的论文中。这篇论文首先编写了算法,并将其应用于汽油交付。通常,这个问题的背景是将位于中央仓库的货物交付给已经订购此类货物的客户。 VRP的目标是最小化总路由成本。 1964年,Clarke和Wright使用一种称为储蓄算法的有效贪婪方法改进了Dantzig和Ramser的方法。 (zh)
dbo:thumbnail
dbo:wikiPageExternalLink
dbo:wikiPageID
  • 7799668 (xsd:integer)
dbo:wikiPageLength
  • 20010 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID
  • 1041440435 (xsd:integer)
dbo:wikiPageWikiLink
dbp:wikiPageUsesTemplate
dct:isPartOf
dct:subject
gold:hypernym
rdf:type
rdfs:comment
  • Il Vehicle routing problem (VRP) è una classe di problemi nell'ambito della ricerca operativa. Questi problemi trattano tutti gli aspetti della gestione di una flotta dei veicoli nell'ambito della logistica. (it)
  • 车辆路径问题(VRP)是一个组合优化和(回答了“为了交付给定的一组客户,车辆车队的最佳路线集是什么?”)。它概括了众所周知的旅行推销员问题(TSP)。它最初出现在1959年George Dantzig和John Ramser的论文中。这篇论文首先编写了算法,并将其应用于汽油交付。通常,这个问题的背景是将位于中央仓库的货物交付给已经订购此类货物的客户。 VRP的目标是最小化总路由成本。 1964年,Clarke和Wright使用一种称为储蓄算法的有效贪婪方法改进了Dantzig和Ramser的方法。 (zh)
  • Tourenplanung ist ein Planungsvorgang, bei dem (Transport-)Aufträge zu Touren gruppiert und in eine Reihenfolge gebracht werden. Dabei wird in der Regel eine Tour von einer Person oder einem Fahrzeug durchgeführt. Dieser Planungsprozess ist in allen Bereichen bedeutend, in denen eine Vielzahl von Aufträgen und Touren geplant werden muss. Beispiele sind die Belieferung von Filialen eines Händlers, die Abholung von Post, die Mülleinsammlung, die Personenbeförderung und der Einsatz von Servicepersonal. Bei regelmäßigen Strecken wie im Kurier-Express-Paket-Dienst bilden sich so Transportnetzstrukturen. (de)
  • Posible artículo duplicado: Problema de rutas de vehículos El problema de enrutamiento de vehículos (VRP, por su siglas en inglés) es un problema de optimización combinatoria y de programación de entero qué pregunta "¿Cuál es el conjunto óptimo de rutas para una flota de vehículos que debe satisfacer las demandas de un conjunto dado de clientes?". Es una generalización del conocido Problema del Viajante (TSP, por sus siglas en inglés). La primera definición aparece en una artículo de George Dantzig y John Ramser en 1959, en donde plantea una aproximación algorítmica y fue aplicado para entregas de gasolina.​ El problema, requiere la entrega de cierto producto, almacenado en un único local, a los clientes los cuales poseen cierta demanda; el objetivo fundamental es minimizar el coste total (es)
  • The vehicle routing problem (VRP) is a combinatorial optimization and integer programming problem which asks "What is the optimal set of routes for a fleet of vehicles to traverse in order to deliver to a given set of customers?". It generalises the well-known travelling salesman problem (TSP). It first appeared in a paper by George Dantzig and John Ramser in 1959, in which the first algorithmic approach was written and was applied to petrol deliveries. Often, the context is that of delivering goods located at a central depot to customers who have placed orders for such goods. The objective of the VRP is to minimize the total route cost. In 1964, Clarke and Wright improved on Dantzig and Ramser's approach using an effective greedy approach called the savings algorithm. (en)
  • Problem marszrutyzacji – problem decyzyjny polegający na wyznaczeniu optymalnych tras przewozowych dla pewnej ściśle określonej liczby środków transportu, której zadaniem jest obsłużenie zbioru klientów znajdujących się w różnych punktach przy zachowaniu ograniczeń. Kryterium optymalizacji jest całkowity koszt transportu (wyrażony odległościowo, cenowo lub czasowo). Istnieją również rozwinięcia problemu uwzględniające więcej niż jedno kryterium optymalizacji. Problem marszrutyzacji należy do podstawowej problematyki zarządzania operacyjnego flotą środków transportu (rzadziej zarządzania na wyższym szczeblu). (pl)
  • O problema de roteamento de veículos (PRV) é um dos mais estudados problemas na área da otimização combinatória. Consiste no atendimento de um conjunto de consumidores por intermédio de uma frota de veículos, que partem de um ou mais pontos denominados depósitos. A restrição presente no PRV é que cada veículo possui uma capacidade e o somatório de todas as demandas dos consumidores atendidos por um veículo não pode ultrapassar . (pt)
rdfs:label
  • Tourenplanung (de)
  • Vehicle routing problem (en)
  • Problema de enrutamiento de vehículos (es)
  • Vehicle routing problem (it)
  • Problème de tournées de véhicules (fr)
  • Problem marszrutyzacji (pl)
  • Problema de roteamento de veículos (pt)
  • 车辆路径问题 (zh)
owl:sameAs
skos:closeMatch
prov:wasDerivedFrom
foaf:depiction
foaf:isPrimaryTopicOf
is dbo:wikiPageDisambiguates of
is dbo:wikiPageRedirects of
is dbo:wikiPageWikiLink of
is foaf:primaryTopic of
Powered by OpenLink Virtuoso    This material is Open Knowledge     W3C Semantic Web Technology     This material is Open Knowledge    Valid XHTML + RDFa
This content was extracted from Wikipedia and is licensed under the Creative Commons Attribution-ShareAlike 3.0 Unported License