Periodic models
Periodic models are a specific class of tactical (or strategic) routing problems. In industry, these are often referred to as Nominated Visit Day (NVD) or Nominated Delivery Day (NDD) problems. NVD is a term used to describe periodic problems when scheduling salesforce visits (non-capacitated). NDD is used to describe periodic deliveries for vehicles (capacitated).
The big differentiator between routing models and periodic routing models is that decisions that require consistency over the planning period are often being made. For example, one may have a delivery made twice in a period to a particular customer - we refer to this as the frequency of a visit. The catch is that the days on which these two visits are made is constrained in some way. For example, these two visits may be required to be exactly 2 weeks apart (assuming that the total planning period is a 4-week cycle). Some customers may be visited once in the month, and others several times. What makes these problems tricky is finding a solution that minimises the cost of all the visits and adheres to the rules laid out by the visit structure.
Another common problem with NVD planning is that the most important objective is not necessarily just cost but also robustness or balance. Workloads often need to be assigned to sales reps in such a way as to ensure that the effort is balanced over the period. This ensures that there is space in the weekly schedules to accommodate potential new customer visits or deviations from the schedule which may occur. The problem is that the plan for the period that minimises the cost (and by this we mean the routing cost of distance + time) is very unlikely to be well balanced over the period. It’s quite easy to tell why since the marginal cost of adding an extra visit to a trip is always less than starting a new trip. So, more full daily routes (which are unbalanced) will tend to occur when you only minimise the routing cost. The story gets more complicated in that one cannot necessarily directly trade off routing cost against balance since they’re measured in incompatible units. The way this is handled in the NVD schema is through what is called Multi-Objective Optimisation - it’s a powerful technique which doesn’t directly require a relationship between multiple objectives (such as cost and balance) and will, as a result, return multiple solutions which are “optimal” - in this context, that are Pareto Optimal.
Pareto Optimality means that all the solutions returned by the API are in some way the best solution, in that no other solution exists which may return a lower level of a different objective term for a fixed objective term. For example, if the Pareto frontier has a solution with a cost of 100, and a balance of 10, this means that you won’t find a better schedule for the cost without increasing the balance term, and the opposite is also true; you won’t find a better schedule for balance without increasing the cost. This is okay, since you can now determine for yourself where the tradeoff is between cost and balance by selecting the schedule you want from the Pareto Frontier solutions.
The threshold for where one is willing to forgo x-units of cost for y-units of balance varies by use case and the API provides a great way for you to decide on a case-by-case basis.