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 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 Clusterung 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 Standardproblem der Tourenplanung 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. Pickup-and-Delivery-Probleme). 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 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)
  • Le problème de tournées de véhicules est une classe de problèmes de recherche opérationnelle et d'optimisation combinatoire. Il s'agit de déterminer les tournées d'une flotte de véhicules afin de livrer une liste de clients, ou de réaliser des tournées d'interventions (maintenance, réparation, contrôles) ou de visites (visites médicales, commerciales, etc.). Le but est de minimiser le coût de livraison des biens. Ce problème est une extension classique du problème du voyageur de commerce, et fait partie de la classe des problèmes NP-complet. (fr)
  • 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)
  • 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 costo 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. (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 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 is an NP-hard problem in combinatorial optimization, so the size of problems that can be solved optimally is limited. The commercial solvers therefore tend to use heuristics due to the size & frequency of real world VRPs they need to solve. The VRP has many obvious 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)
  • 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 (traveling salesman problem), * problem chińskiego listonosza (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 Management Science. (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)
dbo:thumbnail
dbo:wikiPageExternalLink
dbo:wikiPageID
  • 7799668 (xsd:integer)
dbo:wikiPageRevisionID
  • 741301514 (xsd:integer)
dct:subject
http://purl.org/linguistics/gold/hypernym
rdf:type
rdfs:comment
  • Le problème de tournées de véhicules est une classe de problèmes de recherche opérationnelle et d'optimisation combinatoire. Il s'agit de déterminer les tournées d'une flotte de véhicules afin de livrer une liste de clients, ou de réaliser des tournées d'interventions (maintenance, réparation, contrôles) ou de visites (visites médicales, commerciales, etc.). Le but est de minimiser le coût de livraison des biens. Ce problème est une extension classique du problème du voyageur de commerce, et fait partie de la classe des problèmes NP-complet. (fr)
  • 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)
  • 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)
  • 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 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)
  • 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 costo total de las rutas trazadas. En 1964, Clarke y Wright mejoraron la (es)
  • 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 . O PRV, apesar do seu enunciado relativamente simples, apresenta elevada complexidade computacional, pelo que é interessante como problema no teste de diversas heurísticas. (pt)
rdfs:label
  • Tourenplanung (de)
  • Problema de enrutamiento de vehículos (es)
  • Vehicle routing problem (en)
  • Problème de tournées de véhicules (fr)
  • Vehicle routing problem (it)
  • Problem marszrutyzacji (pl)
  • Problema de roteamento de veículos (pt)
owl:sameAs
prov:wasDerivedFrom
foaf:depiction
foaf:isPrimaryTopicOf
is dbo:wikiPageDisambiguates of
is dbo:wikiPageRedirects of
is foaf:primaryTopic of