Periodic VRP (PVRP)

In the classical VRP the planning period is a single day. In the Periodic Vehicle Routing Problem (PVRP), the classical VRP is generalized by extending the planning period to M days. Over this horizon, each customer must be visited a specified number of times, on days chosen from its set of allowable visit patterns.

Formal description

• Objective: minimize the vehicle fleet and the sum of the travel time needed to supply all customers over the whole planning period.
• Feasibility: a solution is feasible if all constraints of the VRP are satisfied for each day of the period. Furthermore, a vehicle may not return to the depot on the same day it departs. Over the M-day period, each customer must be visited at least once.
• Formulation: minimize the sum of the cost of all routes. Each customer has a known daily demand that must be completely satisfied in a single visit by exactly one vehicle. If the planning period M = 1, the PVRP becomes an instance of the classical VRP. Each customer must be visited k times, where . In the classical PVRP model the daily demand of a customer is fixed.

The PVRP can be seen as a problem of generating a set of routes for each day so that all constraints are satisfied and the global cost is minimized. It can also be viewed as a multi-level combinatorial optimization problem:

• At the first level, the goal is to generate the feasible visit-day combinations for each customer. For example, if the planning period has days , the possible combinations are: , , , , , , and . If a customer requests two visits, its visiting alternatives are , and (options 3, 5 and 6 in the table below).
• At the second level, one alternative is selected for each customer so that the daily constraints are satisfied — that is, the customers to visit on each day are chosen.
• At the third level, a vehicle routing problem is solved for each day.

See also: VRP formulation · Multi-Depot VRP · PVRP instances