Solving Permanent Journey Planning at Locus

Author: Abhishek Goyal; Edited by: Kewal Krishna

PJP aka Permanent Journey Planning – What is it? 

PJP refers to the day-level route planning mechanism for a fixed duration that a company or a distributor creates to visit several outlets in a specified region via several delivery partners for different products. Outlets can range from 500 to 10000 or even more. Regions can range from a 10km region in Indonesia (highly dense) to a 200 km region in Dubai (very sparse).  

Key parts of a PJP plan 

• Which outlets will be visited on which day
• Which salesmen will visit which outlet
• Which salesmen will carry what product 
• Constraints being met based on outlets preference

PJPs are essentially how you always find that pack of toothpaste or  that soap you love always stacked in your favourite grocery store.  Yes, you can thank us for this. 

Understanding the details

The primary PJP demands come from the huge Retail FMCG (Fast Moving Consumer Goods) market where distribution is a major challenge. Companies end up spending significant parts of their value supply chain on warehouse to distributor and distributor to retail network. Locus attempts to automate this step entirely from weeks worth of network planning to minutes. 

How FMCG market operates 

Let us see how that humble pack of toothpaste moves around from the manufacturing unit to your hand.  

Locus can play a significant role in Warehouse to Distributor and Distributor to Retail legs of this chain. Ideally we are looking to solve the four questions we’ve discussed above. 

Now what exactly goes into a PJP. Let us say we have 100 outlets to visit (Distributor to Retail) in 7 days using 2 salesmen and they have to follow some constraints. The plan contains a list of day wise tasks for the salesmen which is called a beat. This is represented as below.

• Day 1 ::  Salesmen 1 :: (Start point + Start time)→ Outlet 1→ Outlet 5→ Outlet 10→ ……….. → Outlet n→ (End location + End time) 
• Day 1 ::  Salesmen 2 :: (Start point + Start time)→ Outlet 2→ Outlet 6→ Outlet 11→ ……….. → Outlet m→ (End location + End time) 
• Similarly for all the days and all the salesmen following all the constraints. 

This end-to-end tour on a given day that a salesman/rider will take is referred to as a beat plan in the PJP universe.  Below you can see an example of an ideal beat as well as a realistic beat. Why do we have complicated, overlapping schedules in the realistic beat ? Well, read on.

CONSTRAINTS : 

Constraints are what turns an on-paper perfect beat into, well, a realistic beat. There are two main types of constraints that Locus employs:

Hard Constraints

A hard constraint is one where the Locus PJP product will work towards meeting these constraints at the cost of the optimality of a solution. These constraints are treated as mandatory. If this constraint cannot be met, it will be left unallocated. For example:

• Holidays – If a given day is declared as a holiday for a rider/outlet, we cannot assign that day to the rider/outlet at any cost
• Same Sales-Executive for the outlet :  If the outlet needs to be visited >1 times in a given plan duration, then every time the same salesperson should visit the outlet.
• Even Spacing :  This is an interesting concept around giving an equal gap in the number of days for every consecutive outlet visit. For eg: if in a four-week plan , Outlet1 needs to be visited four times, then every time the gap should be seven days.  

Soft Constraints

A soft constraint is one where the Locus PJP product will try not to breach, i.e. it will give you a solution where the soft constraints are maximized. These constraints are not treated as mandatory. In the event a soft constraint can’t be met, the PJP algorithm will still allocate the tasks that don’t meet the constraint. For example:

• Allocations : Now we can only try to make every outlet visited given the frequency it needs to be visited but we sometimes cannot ensure either mathematically or given other constraints. 
• Familiarity :  While we would only like to send the salesperson to the outlets they are familiar with, in reality we can try achieving this number as high as possible but not a mandatory condition.
• Distance among clusters :  This is kept as a soft constraint as we try to minimize the distance travelled by a salesperson/rider in a single beat. 

PJP ALGORITHM: 

We have formulated the entire problem as a Mixed Integer Programming (MIP) problem within the Linear Programming domain. The motivation was quite simple. The use case wanted us to optimize a given route planning situation based on certain definable constraints. Now we will break down the algorithm like a classic optimization problem.

We formulate this optimization problem as below.

1. SETS/INDICES: Here we list the different entities or sets used in our problem definition. These are basically the building blocks of the problem. 
   1. Location(L) : These are the fundamental lat,long combinations of the stores that we want to visit.
   2. Product Category (P) : Product or service that needs to be done at the location.
   3. Outlet(O) : The combination of Location X Product is defined as an Outlet.  
   4. Rider(R) : The vehicle/rider/salesperson who does the visit. 
   5. Time(T) : A day is a time unit for us. This is the list of days in the plan duration.
      
2. PARAMETERS : We will have some list of parameters which we will use to define objectives and constraints. Some parameters (not a comprehensive list) are as follows:
   1. Frequency : The repeat count against an outlet during the plan duration.
   2. Product demand :  Volume of quantity required by a given outlet.
   3. Total Transaction time : Sum of transaction time across all the outlets for a given beat.
   4. Task Fairness – The max difference between task count across different riders.
      
3. DECISION VARIABLES : Search space for us is all the possible assignments for the plan. This is the super set of feasible solutions. An assignment is defined as a product/service(p) served on a particular time(t)  by a vehicle/rider(r) to a location(l). A point in search space is a list of binaries indicating which assignment is active and which is not.
   
   var(p,r,l,t) ={  0   if assignment is inactive ; 1 if assignment is active } 

Consider a system which constitutes of: 

• P Product Categories
• R Riders
• L Locations
• T Time periods

Do note we have some other (trade-secret) decision variables as well but this should be good enough to drive home the point. The maximum possible assignments in the above case are P x R x L x T, which means: 

• All locations L can take all the products P, which means P x L Outlets 
• All riders R can deliver all the products P
•  All locations L can be visited at all times T
• All riders R can work on all times T

This number can turn out to be humongous and to solve this with a limited set of computing resources and time is the need of the hour. While this is the maximum possible combinations, we use some intelligent design and solutioning around this search space to remove the obvious non possible situations. What are those ? Well, head out to our careers page, join us and then we will discuss and work on them together.

4. CONSTRAINTS : Some sample constraints are defined below.
   1. Flow balance constraints – We balance the flow balance of quantity at every node. 
   2. Frequency balance – We need to adhere to the frequency across every outlet.
   3. Even spacing – We will adhere to the fixed gap between consecutive outlet visits.
      
5. OBJECTIVE FUNCTION : We define 2 things here, constraints to be included in cost function and their respective weights. Two samples are defined below.
   1. Unallocations : We want to penalize our system for leaving out any outlet. 
   2. Fixed Vehicle cost : We want to keep the count of salesperson/Vehicle minimum as it increases the practical cost on the ground. 

Once we have created this well-defined map of the problem statement we pass it to a solver which returns the optimum combination of vehicle, day, outlet information. It is then treated as Travelling Salesman Problem (TSP) to effectively order and schedule the list of outlets on any given day.  Yes, we play around with not one, but two NP-Hard problems. 

The end result of this is a visually beautiful representation of the sales beat. Here is a sneak peak.

Until next time, Cheers!

First Published Source: Solving Permanent Journey Planning at Locus