The Vehicle Routing Problem (VRP) is a generic term used to indicate a family of combinatorial optimisation problems arising from applications in logistics. Generally speaking, a solution to a vehicle routing problem is a set of routes, one for each vehicle of a given fleet, that fulfil transportation requests.[1] It can be considered a generalisation of the Travelling Salesman Problem using multiple vehicles rather than just one.
In the most frequent variants, the fleet's size is fixed, and its vehicles (often assumed identical) start and end their routes at a central depot. Customers place transportation requests; for example, they can request that a parcel be delivered to a given address. All requests are known in advance and must be fulfilled exactly once. The routes comprising a solution to the problem must satisfy feasibility requirements. For example, they might be required to visit customer locations during predetermined time windows. Finally, operating the vehicles incurs travel costs, which the problem aims to minimise.[2]
Each of the above aspects might be forgone in particular problem variants. For example, in the Heterogeneous VRP, there can be different types of vehicles;[3] in the sub-class of VRP with Profits, it is not mandatory to fulfil all requests;[4] in Dynamic VRPs, the requests are not known in advance and keep coming over time.[5]
A typical application of the VRP is in distribution logistics. Consider a supplier who must deliver several shipments to customers during the day. The supplier operates a fleet of trucks, and both the trucks and the shipments are located in a central warehouse. The shipment sizes are such that the same truck can hold multiple shipments simultaneously, up to a maximum determined by the truck's capacity. The supplier must decide which shipments to load on each truck without exceeding capacity. In other words, assuming that there is exactly one shipment per customer, the supplier must decide which customers each truck will visit. However, assigning customers to vehicles is insufficient to produce a complete routing plan that guides the drivers along their daily routes. For each vehicle, the supplier must also decide the order in which customers are visited. Different orderings result in longer or shorter routes. The supplier is usually interested in finding a set of routes whose total length is as short as possible. The reason is that the shorter the routes, the lower the operating costs (for example, fuel or electric energy costs).
References
edit- ^ Toth, Paolo; Vigo, Daniele (2014). Vehicle Routing: Problems, Methods, and Applications (2nd ed.). SIAM. ISBN 978-1-61197-358-7.
- ^ Irnich, Stefan; Toth, Paolo; Vigo, Daniele (2014). "The Family of Vehicle Routing Problems". In Toth, Paolo; Vigo, Daniele (eds.). Vehicle Routing: Problems, Methods, and Applications (2nd ed.). SIAM. doi:10.1137/1.9781611973594.ch1.
- ^ Golden, Bruce; Assad, Arjang; Levy, Larry; Gheysens, Filip (1984). "The fleet size and mix vehicle routing problem". Computers & Operations Research. 11 (1): 49–66. doi:10.1016/0305-0548(84)90007-8.
- ^ Archetti, Claudia; Speranza, Maria Grazia; Vigo, Daniele (2014). "Vehicle Routing Problems with Profits". In Toth, Paolo; Vigo, Daniele (eds.). Vehicle Routing: Problems, Methods, and Applications (2nd ed.). SIAM. doi:10.1137/1.9781611973594.ch10.
- ^ Psarafitis, Harilaos; Wen, Min; Knotovas, Christos (2015). "Dynamic vehicle routing problems: Three decades and counting". Networks. 67 (1): 3–31. doi:10.1002/net.21628.