About: Vehicle routing problem     Goto   Sponge   NotDistinct   Permalink

An Entity of Type : yago:WikicatNP-completeProblems, within Data Space : dbpedia.org associated with source document(s)

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.

AttributesValues
rdf:type
rdfs:label
  • Tourenplanung
  • Problema de enrutamiento de vehículos
  • Vehicle routing problem
  • Problème de tournées de véhicules
  • Vehicle routing problem
  • Problem marszrutyzacji
  • Problema de roteamento de veículos
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.
  • 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.
  • 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.
  • 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.
  • 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
  • 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).
  • 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.
sameAs
dct:subject
Wikipage page ID
Wikipage revision ID
Link from a Wikipage to another Wikipage
Link from a Wikipage to an external page
foaf:depiction
  • External Image
foaf:isPrimaryTopicOf
thumbnail
prov:wasDerivedFrom
has 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
http://purl.org/voc/vrank#hasRank
http://purl.org/li...ics/gold/hypernym
is Link from a Wikipage to another Wikipage of
Faceted Search & Find service v1.17_git39 as of Aug 09 2019


Alternative Linked Data Documents: PivotViewer | iSPARQL | ODE     Content Formats:       RDF       ODATA       Microdata      About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data] Valid XHTML + RDFa
OpenLink Virtuoso version 07.20.3235 as of Sep 1 2020, on Linux (x86_64-generic-linux-glibc25), Single-Server Edition (61 GB total memory)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2020 OpenLink Software