Problem Variants
The Vehicle Routing Scheduler Library currently supports the following 6 classical vehicle routing problem variants:
- Capacitated Vehicle Routing Problem (CVRP)
This is Vehicle Routing Problem (VRP) in which a fixed fleet of delivery vehicles of uniform capacity must service known customer demands for a single commodity from a common depot at minimum transit cost. That is, CVRP is like VRP with the additional constraint that every vehicle must have uniform capacity of a single commodity. - Vehicle Routing Problem with Time Windows (VRPTW)
VRPTW is the same problem as VRP with the additional restriction that in VRPTW, a time window is associated with each customer, defining an interval wherein customer has to be supplied. - Multiple Depots Vehicle Routing Problem (MDVRP)
In this problem, a company may have several depots from which it can serve its customers. MDVRP requires the assignment of customers to depots. A fleet of vehicles is based at each depot. Each vehicle originates from one depot, provides services to customers assigned to that depot, and returns to the same depot. - Vehicle Routing Problem with Stochastic Demands (VRPSD)
VRPSD is the extension of CVRP in which customer demand is unknown until it is visited by a vehicle. When the vehicle capacity constraint is violated, instead of deeming the solution or route infeasible, the vehicle is returned to the depot for refill before going to the next customer. As a result, the distance is longer. - Vehicle Routing Problem with Backhauls (VRPB)
VRPB is the extension of CVRP in which customer set is partitioned into two subsets. The first subset, L, contains n Linehaul customers, each requiring a given quantity of products to be delivered. The second subset, B, contains m Backhaul customers, where a given quantity of inbound products must be picked up. In VRPB, a precedence constraint between linehaul and backhaul customers exists: whenever a route serves both types of customers, all the linehaul customers must be served before any backhaul customers may be served. - Vehicle Routing Problem with Pickup and Delivery (VRPPD)
VRPPD can be considered to be the generalized case for VRPB in which goods are delivered to some customers and pickup from some other customers simultaneously.
The Vehicle Routing Scheduler Library is VRP domain driven, yet independent of the problem structure of any vehicle routing problem variants. This is to make vehicle routing algorithms in the library independent of any vehicle routing constraints and at the same time, to make the library and algorithms more easily extendable. In this way, constraints in different VRP variants can be smoothly combined to create vehicle routing solver for new problem without rewriting any parts of vehicle routing algorithms in the library.
For example, constraints in VRPB and VRPTW can be combined to create a new solver for vehicle routing problems with backhauls and time windows. Or user can combine MDVRP and VRPTW to create a solver that solves multiple depot vehicle routing problems with time windows, all without losing the efficiency of routing algorithms in the library.