Vehicle Routing Problem (VRP) is a transportation problem in Operation Research similar to Travelling Salesman Problem. This problem starts with a set of transportation requests and a set of vehicles and the goal is determining the routes for vehicles that deliver the request with the minimum cost. VRP has many variations that reflect real-world situations; However, the simplest and most studied version of the Vehicle Routing Problem is called Capacitated Vehicle Routing Problem.
Capacitated Vehicle Routing Problem (CVRP) consists of one depot where every vehicle starts their delivery to set of customers and return back to depot once finished. Every vehicle is homogeneous which means it has the same capacity with identical operating cost and travel cost is applied for each movement from one place to another.
Moreover, customers have distinct demands that need to be fulfilled. Based on this information, this problem can be modeled by Integer Programming models with polynomial numbers. Here is one example of the CVRP model.
The Objective Function of CVRP is minimizing cost, hence it could be expressed as:
CVRP has four main constraints: predecessor constraint, successor constraint, depot constraint, and capacity constraints. The predecessor and successor constraints in CVRP is similar to TSP with the purpose of limiting visit to only one per customer.
The depot constraint ensures that every vehicle starts and ends its delivery at the depot and exactly |đž| numbers of routes are constructed.
The capacity constraint describes that each vehicle has only limited capacity but also needs to fulfill every demand in their routes.
This is just a simple example of CVRP modeling with only four constraints. Note that, one problem can be represented by different models depending on the purpose, depth or focus of the research. For example, we could add more constraints for preventing sub-cycle, costs every vehicle deployed, time windows variable, pick up or delivery options, etc.
ĐОПонŃĐ°ŃŃ