In classical VRPs, typically the planning period is a single day. In the case of the Period Vehicle Routing Problem (PVRP), the classical VRP is generalized by extending the planning period to M days.

We define the problem as follows:

Objective

The objective is to minimize the vehicle fleet and the sum of travel time needed to supply all customers.

Feasibility

A solution is feasible if all constraints of VRP are satisfied. Furthermore a vehicle may not return to the depot in 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 only one visit by exactly one vehicle. If the planning period ${M = 1}$, then PVRP becomes an instance of the classical VRP. Each customer in PVRP must be visited ${k}$ times, where ${1 \leq k \leq M}$. In the classical model of PVRP, the daily demand of a customer is always fixed. The PVRP can be seen as a problem of generating a group of routes for each day so that the constraints involved are satisfied and the global costs are minimized. PVRP can also be seen as a multi-level combinatorial optimization problem:

• In the first level, the objective is to generate a group of feasible alternatives (combinations) for each customer. For example, if the planning period has ${t = 3}$ days ${ \left\lbrace d1, d2, d3 \right\rbrace}$ then the possible combinations are: ${0 \rightarrow 000}$; ${1 \rightarrow 001}$; ${2 \rightarrow 010}$; ${3 \rightarrow 011}$; ${4 \rightarrow 100}$; ${5 \rightarrow 101}$; ${6 \rightarrow 110}$; and ${7 \rightarrow 111}$. If a customer requests two visits, then this customer has the following visiting alternatives: ${ \left\lbrace d1, d2 \right\rbrace }$, ${ \left\lbrace d1, d3 \right\rbrace }$, and ${ \left\lbrace d2, d3 \right\rbrace }$ (or the options: 3, 5, and 6 of the table below).
• In the second level, we must select one of the alternatives for each customer, so that the daily constraints are satisfied. Thus we must select the customers to be visited in each day.
• In the third level, we solve the vehicle routing problem for each day.