4

Business Case

I work for a non-profit that uses volunteers to deliver meals to their clients. Based on their volunteer-recurrence schedule, and the client's meal-recurrence schedule, each volunteer has a daily route of meals that they deliver. Currently, the routing is being done manually by our employees and that takes a lot of time. I'm planning to build a very custom apex class that handles Multi-Route processing.

What I mean by that is, using my own use case as an example, when I have for example, 5 volunteers and 40 meals scheduled for today, the class will give me the 5 best routes for those volunteers based on the location of the meal "delivery points", and the volunteer's own personal criteria (ability to climb steps, strength level, etc.).

Things to consider:

  • I built Meals as a custom object that has a Master-detail relationship to Contacts (One Client can have many Meals).
  • I built Routes as a custom object that has a lookup relationship to Volunteer Hours - The 'Volunteers For Salesforce' custom object - and a lookup relationship to Meals (There is one route for each volunteer hour in a day, and each route can have many meals).
  • Volunteers have certain criteria associated with them, such as their ability to climb steps, or their ability to lift & carry a certain number of meal trays. Each of these criteria are tracked both on the Contact object, and on the related object. ('No Steps' is a checkbox field on the Contact object, and 'Has Steps' is a checkbox on the Address object in the NPSP')
  • The Route object will be built and populated programmatically.
  • Routes (Deliveries) all start at the same time and at the same place.
  • I used Clean Rules to get the geolocation data for the Contact records.

My Approach

In the apex class, SOQL Queries create lists of Volunteers that have Volunteer Hours scheduled for that day, where that Volunteer Hour object doesn't have an associated Route and a particular criteria on the Volunteer ('No Steps', etc) is present, e.g. The first SOQL query would look for the Volunteers with the 'No Steps' checkbox checked since that's the highest priority criteria. The second SOQL query would look for the Volunteers with the second highest priority criteria, and so on.

The reason for this is to build and populate the routes for the most 'picky' and restricted volunteers first so as to limit the occurrence of Meals that cannot be routed because the final available Volunteers have too much criteria on them.

Immediately following each SOQL query, I intend to loop through all the volunteers in the each and build (Not populate) Route objects for each. During each iteration un-routed meals will assessed based on their compatibility with the route, their distance from the starting point and then their distance from each other. The route will be populated with the closest meal matching all the following criteria, and the meal will be marked as routed.

My Problem

After tracing the logic of the code (Hand-drawing points on a map and using the program's logic to create the routes), I realized that if meals are clustered together, around the general route (delivery) start-point for example, the first route would pick up all (and possibly only depending on how many there are) those clustered meals in that area and follow what I feel is an illogical path. I think checking the traveling direction of the current and next meal would allow me to be able to fix that, but I'm not sure how to tell direction in Salesforce.

Anyone with a solution to my problem, or any advice or critique of my approach is welcome to answer.

2

Nice problem description, very interesting!

What's wrong with the first route addressing all clustered (no-steps) meals in an area? It's an effect of the optimization you're doing. And in the end it will at least get you a reasonably optimized result. I don't see any simple ways of improving this.

Possible improvement points I see are:

  1. you're currently calculating a route for each volunteer one by one. You could consider taking all the volunteers with equal limitations and assigning a 'multiple travelling salesmen problem' algorithm to generate routes for them. That will most probably spread them into different directions, which addresses your issue. However, these are complicated algorithms so you might need an external library for it, with all technical complications.
  2. instead of purely using the geo-coordinates, you might want to use actual map data to make the routes more logical (e.g. not go through houses or against traffic). E.g. google maps api or something like that..
  • Thanks for the advice..To address improvement #2: I do intend to use the Google Maps API to get the turn by turn directions for each route after they're built, and then populate a text-area field on the route object with it. #1: I'll probably have to look at the 'multiple travelling salesmen problem' a bit more thoroughly, but I think I'm already grouping volunteers by limitations before building their routes...I use SOQL queries to find scheduled volunteers with certain limitations, then I recursively build their routes and assign their meals. Then I move on to the next criteria group. – versatgrant Dec 16 '16 at 19:11
  • ok, do you create the complete router for 1 volunteer and then move to the next, or do you create meal 1 for all volunteers in a group, and then move to meal 2? – Guy Clairbois Dec 19 '16 at 11:34
  • and, as you might expect, the result of a 'mtsp' algorithm will likely be very different still, as it will evaluate and compare complete routes instead of only the next step. – Guy Clairbois Dec 19 '16 at 11:35
  • I'm completing the route for volunteer 1 first..but I'm ordering the volunteers by priority level based on their restrictions before I start building...I took a look at the mTSP from the link in your answer and found that with my background in math, understanding it enough to implementing a solution as-is would take a greater investment of time than I have..but I kept searching and met upon Genetic Algorithms..I can say I understand it enough to implement it for TSP but not mTSP because I'm still unsure of how to go about performing crossover with multiple routes... – versatgrant Dec 20 '16 at 19:44
  • But after a weekend of racking my brain, I think I found a solution that will give somewhat optimal routes without huge and unnecessary disparities in travel distance for the volunteers....here's what I got: 1. After the structure of the route is built for the volunteer, find the farthest point that matches it's criteria and it to it's route. 2. Look for the closest point to the current farthest point where, a. The distance between the current and pontential point is not greater than the distance between the current point and the start point. b. The distance between the potential point and the – versatgrant Dec 20 '16 at 19:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.