Vehicle Routing Problem (VRP) has a wide variety reflecting on real-world situations. The classification of VRP could be based on different criteria from logistical context, transportation mode, to objective function. However, this article explores one type of taxonomy in VRP: Type of VRP problems.
According to its character, VRP has four different combinations: static and deterministic (SD), static and stochastic (SS), dynamic and deterministic (DD), and dynamic and stochastic (DS). Static means that all inputs are given at the start and solutions are generated before the deployment. On the other hand, dynamic means pre-determined routes can be adjusted depending on incoming inputs in real-time.
Deterministic problems mean every input is known with certainty; However, Stochastic problems have inputs with a degree of uncertainty (usually represented in a probability distribution).
Static-Deterministic VRP is a type of problem where all inputs are known with certainty before and these inputs are received before generating the solution. The most popular example of this type of problem is Capacitated Vehicle Routing Problem (CVRP) and Travelling Salesman Problem (TSP).
Static-Stochastic type is a problem where the inputs are given in a form of probability distribution with the example of Probabilistic TSP (PTSP). Each customer in PTSP is either absent or present with a certain degree of probability. Since the route are generated before the information of the customer’s presence is revealed, it is considered as a static problem.
Dynamic-Deterministic VRP is a problem where all inputs are certain about the future but some of them are unknown at the start. For example, in taxi services, a customer location is unknown until the customer request the service, or in food-delivery services, both customer location and demand are unknown until they order the delivery service.
On the other hand, a VRP is considered dynamic and stochastic when the inputs evolve over time but with probabilistic information. The demand of one customer is assumed to follow a certain probability distribution and revealed once the vehicle visits the customers. Another example, is a customer location are described in distribution and only revealed when the demand occurs. Determining the type of problem is crucial for modeling and solving the problem since every type requires a different approach for obtaining the best solution available.
Comments