KB at your finger tips

This is one stop global knowledge base where you can learn about all the products, solutions and support features.

Routing Optimization

The Routing Optimization service is powered by an optimization engine designed to handle a huge variety of problems and aims to help you find your optimal business solution by giving you control over how your problem is solved. Your creativity only limits the variety of problems!

Basics

Routing optimization is a more complex version of point-to-point routing where the goal is instead to solve one of the most mathematically complicated problems known to humanity. Building the routes seen above is the outcome of submitting a simple (minimize distance) routing problem to our Routing Optimization service. So, how does one construct a routing problem? There are a few key ingredients one needs first:

VEHICLES — the cars, trucks, bikes, or pedestrians that comprise your fleet.
LOCATIONS — the physical places your vehicles are routed to provide service.
ORDERS — the requests for your services at a specific location over some time.
ITEMS — the units of work ordered at a location, e.g., a package delivery, one LTL pickup, four hours of service.
CONSTRAINTS — the knobs that tune the solution objective, e.g., maximize revenue, minimize vehicles.

Minimizing the total number of vehicles and total travel time are often a primary goal in most, if not all, routing optimization problems. However, there are other business objectives and tradeoffs to consider. For example, a salesperson might visit five more high-value leads in a day, but at the cost of reduced visits with high-priority customers. Instead of hiding tradeoffs from you, the Routing Optimization service gives you control via constraints that provide the ultimate — sometimes daunting — flexibility and power in solving your problem.

Constraints

Imagine the case where you want a routing solution that penalizes lateness to scheduled appointments. However, maybe you have the luxury of being an excellent customer service company and can be "a little late" without fear of damaging a customer relationship. In which case, it is acceptable to visit a big account lead before an appointment even if that means being late. In which case, you are looking for a solution like:

"Find the optimal routes for my sales team where they have penalized 25 penalty points for every 15 minutes they are late to a scheduled appointment."

Constraint Penalties

Behind the scenes, this is what our patented mathematical optimization algorithms do when they seek out the best solution based on the constraints you provide. Where the "best" solution is the one that captures most, and sometimes all, of your desired business logic and outcomes.

Constraints are given control over the routing solution by accruing penalty points every time the solution violates a constraint in some way. The concept is that the solution with the lowest number of penalty points is the best solution. Using constraints in this way results in having to tune your solutions, and is a bit of an art for your developers. However, once they get the hang of it, the options are limitless.

Visit the Constraint Library and the associated examples for each to see the full details.

For real-world business needs, the Routing Optimization service takes the approach of running a sophisticated optimization algorithm for a reasonable amount of time before returning a solution. To achieve this, we divide problems into synchronous and asynchronous jobs depending on the size and difficulty of the problem (request formats for asynchronous and synchronous calls are the same):

Synchronous jobs are for smaller requests (less than 50 locations) and are processed immediately.
Asynchronous jobs are for larger requests (more than 50 locations), and a jobid is returned once a request is received and validated. The user can then poll the API for job status and retrieve the results when the job completes. Once it completes, the responses are purged after 24 hours.

Salesforce Developers

Breaks

The optimization engine offers a wide variety of methods to express breaks in a route – these are periods during a shift which the vehicle/driver is not servicing any orders. The breaks are properties of the shift so that in problems where a vehicle has multiple shifts, different breaks can exist for the same vehicle across the different shifts. There are three types of breaks supported

BREAK — A period of time during which the vehicle is not moving and no orders are serviced. This type of break is useful to express events such as a lunch break at a known time. For the standard break, the start and end time are explicitly expressed, and the break is always honored. A shift can have multiple breaks but the breaks cannot overlap (since two overlapping breaks really just represent a single longer break).
SOFT BREAK — A period of time during which no orders are serviced, but the vehicle may or may not be moving. This type of break is useful to express events such as a pre-scheduled phone call that might take place while the vehicle is moving. For the soft break, the start and end time are explicitly expressed, and the soft break is always honored. A shift can have multiple soft breaks but the soft breaks cannot overlap (since two overlapping soft breaks really just represent a single longer soft break). A shift can have a mixture of breaks and soft breaks, but they cannot overlap.
FLOATING BREAK — The floating break has a fixed duration but can start at any time during a provided window. The vehicle is not allowed to be moving during a floating break. The floating break can be used to handle compliance requirements where a driver must receive a certain amount of rest during any continuous work period of a certain length. As with the other breaks, any route for the shift will always honor the floating break. Floating breaks can be used in conjunction with the other break types.

In the following three examples, we have a single vehicle with 6 total orders in the Washington, DC/Baltimore area. In each case, we have a different kind of 45-minute break that impacts the efficiency of the shift.

Hard Break

In this first example, we have a hard break from 12:30 to 1:15. As the vehicle cannot be traveling during this period, it turns out that it is not possible to visit all 6 orders in this case and the Baltimore order is not visited. The route ends at 3:22, and there are more than 2 hours of time remaining in the shift. However, that does not provide sufficient time to complete a round trip to Baltimore to service the final order.

Expand to view request sample

With a hard break of 45 minutes starting at 12:30, it is not possible to visit all 6 orders.

Soft Break

In a soft break, recall that the vehicle is allowed to be moving during the break. This additional level of flexibility allows us to now visit all 6 orders as the soft break is taken after servicing the Baltimore order and returning to DC. The route concludes with about 40 minutes to spare before the end of the shift.

Expand to view request sample

The soft break is taken on the way back down to DC after the Baltimore order (stop 3 in the route).

Floating Break

The floating break allows us an additional degree of flexibility as we are now allowed to take the 45-minute break at any time during the day. Even though the break is similar to a hard break in that the vehicle cannot be moving, the freedom to scheduled this break any time during the shift allows sufficient freedom that we are now able to visit all 6 orders. The floating break occurs immediately after the final order at the Vietnam Memorial, and we complete the route with less than 2 minutes to spare in the shift.

Expand to view request sample

The floating break allows us to visit all 6 orders even though the vehicle does not move during the break. Note that we traverse the orders in a slightly different sequence than with the soft break. With the optimization engine’s ability to incorporate predicted traffic into the route optimization, the floating break can be a powerful way to add some additional flexibility into the route.

Read article

Salesforce Developers

Delivery Only Problem with Replenishment and Balanced Routes

In this example, we have a fictitious company that delivers various sizes of pallets to customer locations. The fleet is not large enough to carry all the pallets for the day in a single load, so the vehicles can return to various locations throughout the day to replenish their supply of pallets. The three types of pallets to be delivered are described in the items array below

The vehicles are constrained in terms of how much of each item they can carry as well as by volume and weight. Each vehicle’s capacity is expressed separately as part of the vehicle object, and an example vehicle object now looks like this. Note that we are specifying the "type": "truck" so that the paths over the street network between stops are compliant with the dimensions of the truck.

As in other delivery problems, we express the amount to be delivered to each order with delivery_item_quantities . In problems involving deliveries, the vehicle may become empty during the shift and be therefore unable to service any more orders. By specifying certain orders to have the ability to replenish the supply, we can extend the shift since the vehicle can refill an amount so that more orders can be serviced. An example of such a replenishment order is below. Note that the amount that can be replenished must be set – typically this should be a very large value if essentially limitless replenishment can occur at this stop. If the replenishment stop has a limited supply of items, then that can be specified as well, and the total amount of supply added to the vehicles at this stop will not exceed the amount specified. Additionally, a duration is specified for the replenishment, and a maximum number of visits (enforced by the visit_range constraint)

A full request involving deliveries, replenishment events, and a num_stops constraint to balance the routes is given below.

Expand to view request sample

All replenishments occur at the central depot (boxed in red). In the purple route, the vehicle visits stop 1 and stop 2, replenishes in stop 3, then services stops 4, 5, and 6 in the western portion and returns to replenish in stop 7. The route concludes by servicing stops 8 and 9 south of the depot before returning home. The output JSON contains the full details of the stops and specifies when the replenishments occur.

In the routes returned in the API response, any stop where items are delivered will have details of what is delivered, and how much of each item is in the vehicle at that time. An example is below:

For every replenishment stop, an items_replenished array is included to describe the activity at the stop.

As with unloading problems, other features of the pickup/delivery aspects of the route are also included in the route object, such as max_volume_in_vehicle , max_num_items_in_vehicle , and max_weight_in_vehicle . Since vehicle capacity constraints are never violated, the optimization engine ensures that no vehicle will ever be carrying more than its capacity at any point during the route (in terms of weight/volume/number of items). The replenishment stops are strategically inserted by the algorithm in order to satisfy as many orders as possible while still respecting the vehicle capacities.

Read article

Salesforce Developers

Forced Routes

In some cases, one may have a routing problem where the sequence of stops is already known and only the desired travel times, polylines, and driving directions are desired. In the first example, we have only a single vehicle with a single shift and we force it to visit a sequence of stops. Note that it would be very easy to add more stops to this route, but no optimization is done in this case. One important note is that the sequence of stops must be feasible for the associated shift – in other words, if the optimization engine computes the travel time and determines that it is not possible to visit the provided sequence of stops within the time for the shift, then no route is returned. In this case, a simple solution may be to increase the length of the shift.

Expand to view request sample

The sequence of stops could be made more efficient but no re-ordering of a forced route is allowed.

In this example, we force the routes for all four shifts. Note that breaks can be incorporated but again the sequence of stops in the route cannot be changed.

Expand to view request sample

Read article

Salesforce Developers

Multiple Vehicles, Multiple Shifts

Subsequent examples focus on multiple vehicles servicing orders over a longer planning horizon consisting of multiple shifts (typically a shift is a day but it can be longer if desired). Each vehicle can have its own shifts so that vehicles can be operating during the same planning period or different periods. This can be useful when different vehicles are available on different days due to vehicle maintenance or employee availability.

When routing across multiple days in multiple vehicles, you may often have some orders that require periodic visits. Rather than specifying a separate order for each visit, the optimization engine allows you to specify a single order that has requirements for multiple visits. The visit_range constraint allows you to ensure the correct number of visits across the planning period. Additionally, since orders should generally be spaced out over the planning period, the visit_gap constraint provides control over how much time separates one visit from the next. These constraints operate at the order level regardless of which vehicle visits the order.

Back to our example of Jimmy and Sally’s expanding business in the DC Metro Area, based on their great success in matching the right worker for the right job at the embassies, they have now obtained contracts for cleaning the embassies along with the other work. The various embassies have different requirements for how often the service should occur. They will operate on a weekly cycle with the visit count requirements and visit spacing requirements now incorporated into the orders

ORDERS — All of the orders now receive a value of min_visits – the minimum number of times we must visit them in the solution to the routing problem. This is enforced via the visit_range constraint. Since all these orders must now be visited multiple times, the desired spacing of visits is expressed with min_days and max_days – the minimum and the maximum number of days between service events. This spacing is enforced via the visit_gap constraint. Also, note that we add a few additional locations and orders to make sure the fleet has enough work to remain busy on most days.

CONSTRAINTS — Since the visit_range is present in all examples to achieve the default min_visits of 1, the only addition is the visit_gap constraint. This constraint references the data present in each order object.

Expand to view request sample

Part of the solution for the multi-shift, multi-vehicle problem. We now have 15 total routes (3 vehicles, 5 days each), so it is difficult to make sense of all days and all vehicles at once. Each vehicle is active on all 5 days except for Vehicle 2 on Day 2 and Vehicle 3 on Day 4

Day 1 of the solution when all 3 vehicles are active.

Read article

Salesforce Developers

Multiple Vehicles, Single Shift

Jimmy and Sally have been wildly successful and have new contracts with a few embassies in and around Washington, DC. Unfortunately, these embassies require native speakers of their respective languages, and so they also had to hire some new crew members. Luckily they were able to hire some linguistic geniuses that speak several languages. The examples below illustrate how the optimization engine can handle multiple vehicles on the same day and also match attributes so that the right vehicle services certain orders. This capability can be useful in a variety of "skill matching" use cases.

VEHICLES — The vehicles can have shifts that are completely independent of the other vehicles in terms of their start/end location and start/end times. Additionally, we can associate attributes with each vehicle and then force attribute matching with constraints. In this example, the vehicles will all be operating on the same day with the same shift times. Note that an individual vehicle cannot have shifts that overlap.
CONSTRAINTS — We will make use of the match_attributes constraint in this example to illustrate skill/vehicle matching with various orders.
ORDERS — We have some new orders in DC at various embassies. We associate attributes with each order using arbitrary strings.

Expand to view request sample

The fleet of three vehicles is able to visit all orders as we can see below. However, now that we are forcing attribute matching the routes inside the city appear inefficient as the green (Finnish speaking) vehicle comes into the "Embassy Row" area to service only a single order that is very near the routes of the other vehicles. However, since these vehicles don't match the attributes of the order at the Finnish assembly, they are not eligible to service the order.

The full 3 vehicle, single day solution where we enforce the attribute matching.

A zoomed in view to show the travel inefficiencies that can result from enforcing the attribute matching. In this case, the green (Finnish speaking) vehicle services the green order #4 by going out of the way into the Embassy Row area. The orange and pink vehicles are nearby but do not match the attributes of the order at the Finnish Embassy, so they cannot service the order.

To illustrate the impact of this skill matching, we can simply remove the attributes and the match_attributes constraint to quickly find a new solution. In this case we service all the orders but now reduce the total travel time by about 30 minutes. Zooming in on the same area as in the above image, we can see that all six embassies in this area are serviced by the same vehicle.

Read article

Welcome to Knowledge Base!

KB at your finger tips

Routing Optimization

Basics

Constraints

Breaks

Hard Break

Soft Break

Floating Break

Delivery Only Problem with Replenishment and Balanced Routes

Forced Routes

Multiple Vehicles, Multiple Shifts

Multiple Vehicles, Single Shift

Thank you for subscribing to AiDOOS! Stay connected for updates!