This article is written like a personal reflection, personal essay, or argumentative essay that states a Wikipedia editor's personal feelings or presents an original argument about a topic. Please help improve it by rewriting it in an encyclopedic style.(December 2021) (Learn how and when to remove this message)
A figure illustrating the vehicle routing problem
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 travelling salesman problem (TSP). It first appeared in a paper by George Dantzig and John Ramser in 1959,[1] 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 algorithm called the savings algorithm.
Determining the optimal solution to VRP is NP-hard,[2] so the size of problems that can be optimally solved 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.
VRP has many direct applications in industry. Vendors of VRP routing tools often claim that they can offer cost savings of 5%–30%.[3]
^Dantzig, George Bernard; Ramser, John Hubert (October 1959). "The Truck Dispatching Problem" (PDF). Management Science. 6 (1): 80–91. doi:10.1287/mnsc.6.1.80.
^Toth, P.; Vigo, D., eds. (2002). The Vehicle Routing Problem. Monographs on Discrete Mathematics and Applications. Vol. 9. Philadelphia: Society for Industrial and Applied Mathematics. ISBN 0-89871-579-2.
^Geir Hasle; Knut-Andreas Lie; Ewald Quak, eds. (2007). Geometric Modelling, Numerical Simulation, and Optimization:: Applied Mathematics at SINTEF. Berlin: Springer Verlag. pp. 397–398. ISBN 978-3-540-68783-2.
and 23 Related for: Vehicle routing problem information
numerous optimization tasks involving some sort of graph, e.g., vehiclerouting and internet routing. As an example, ant colony optimization is a class of optimization...
efficient scheduling and routing of vehicles can save industry and government millions of dollars every year. Arc routingproblems have applications in school...
academic use. Concorde has been applied to problems of gene mapping, protein function prediction, vehiclerouting, conversion of bitmap images to continuous...
famous problems that are solved using constructive heuristics are the flow shop scheduling, the vehicleroutingproblem and the open shop problem. Evolutionary...
goods in order to reschedule the routes when demand substantially changes Combinatorial optimization Vehicleroutingproblem Fundamentals of Transportation/Timetabling...
purchaser problem include dynamic programming and tabu search algorithms. Vehicleroutingproblem "Heuristics for the traveling purchaser problem" (PDF)...
Indonesia, and Sea Group's Shopee. It uses vehicleroutingproblem algorithms to improve delivery routes. Ninja Van was founded in 2014 by Singaporeans...
The snow plow routingproblem is an application of the structure of Arc RoutingProblems (ARPs) and VehicleRoutingProblems (VRPs) to snow removal that...
Nurse scheduling problem Set cover problem Talent Scheduling Traveling salesman problemVehicle rescheduling problemVehicleroutingproblem Weapon target...
Routing is the process of selecting a path for traffic in a network or between or across multiple networks. Broadly, routing is performed in many types...
VRP may refer to: Vehicleroutingproblem, a problem in combinatorial optimization Virtual resource partitioning, an operating system-level virtualization...
research, and geographical routing algorithms to find the shortest path efficiently. The CARP is NP-hard arc routingproblem. The CARP can be solved with...
point-to-point routing, composite routingproblems are also common. The Traveling salesman problem asks for the optimal (least distance/cost) ordering and route to...
Supérieure. The vehicleroutingproblem: An overview of exact and approximate algorithms A tabu search heuristic for the vehicleroutingproblem A unified tabu...
optimization Test functions for optimization Calculus of variations Vehicleroutingproblem "The Nature of Mathematical Programming Archived 2014-03-05 at...
combinatorial optimization problems including the Job Shop Scheduling problems, Flow-Shop Problems, VehicleRoutingProblems as well as many others. Lourenço...
split in only one way according to its size. It is useful for the vehicleroutingproblem for example. In their paper, they provide the worst-case performance...
include: Problems in combinatorial optimization, such as: The vehicleroutingproblem, a form of shortest path problem The knapsack problem: Given a set...
traveling salesman problem, knapsack problem, job shop scheduling, and vehicleroutingproblems). The practice includes information processing and the engineering...
multi-coloring problem can be used to model a variety of applications including job scheduling and telecommunication channel assignment. Vehicleroutingproblems. Generalized...
Global Information
