Blog
Token
About Us
AiDOOS Wiki
Project Cost Estimation

Welcome to Knowledge Base!

KB at your finger tips

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

Categories
All
CRM
Salesforce
ERP
SAP
Storage and Backups
Purestorage Netapp Nutanix
Cloud
AWS
Computing
IBM
Database
MongoDB MySQL PostgreSQL
DevOps
Docker Kubernetes Jenkins GitLab
Mobile
React Native Android
Web
React Angular PHP
Programming
Python
CRM-Salesforce
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

img

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.

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

img

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

img

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

img

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.

img

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

img 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.

img

Read article
Salesforce Developers

Pickup and Delivery Problems

The optimization engine provides the ability to solve complex logistical problems that involve pickups, deliveries, dropoffs, unloading, and replenishment of multiple item types. To be clear on exactly what these events are, we first clarify the specification of these problems and precisely define the event types that are supported.

An item is simply a physical object that is involved in the routing problem. The items are presented as top-level objects in the request that are then referenced elsewhere. An example of the JSON specification for two item types:

One can express the capacity of a vehicle in three ways:

One can express the capacity of vehicles in three ways: by quantity of each item type, by weight, or by volume. Note that any time that the optimization engine returns a solution, all routes will adhere to each dimension of the vehicle capacity. When specifying the capacity of a vehicle, volume_capacity and weight_capacity are optional and allow you to specify a capacity that involves multiple item_types that have different weights and volumes. However, if a vehicle is to carry a certain item_type, then that item type must be contained in the capacity_by_item array. Regarding the units for weight and volume, these are completely arbitrary and are just treated as numeric values by the optimization algorithm -- just make sure that you use consistent units for weight and volume when specifying your items and caapcities. The example below shows all of the different ways to express the capacity of a vehicle.

Demand for a pickup/delivery event is specified inside the orders. There are four different event types that can occur in our pickup/delivery problems

Delivery

In a delivery event, items are delivered to a customer location as part of the servicing of the order. It is important to note that the optimization determines the amount of each item that each route starts with - this is given in the start_items array in the response and is equal to the smallest amount of items necessary to fully satisfy all demand on the route. When servicing an order that involves a delivery, the item must be on the vehicle prior to servicing the order, and the amount carried on the vehicle will be decreased by the amount delivered upon completing the service. Also, if both a pickup and delivery or dropoff occur at the same order, then for the purposes of tracking the items carried on the vehicle, we assume that the delivery or dropoff always occurs before the pickup event. An example delivery demand is expressed as follows:

Pickup

Items are picked up at an order and placed in the vehicle. As mentioned previously, if a delivery or dropoff event also occurs at a stop, these events are assumed to occur before the pickup. The items picked up may be carried on the vehicle for the remainder of the route, or they may be dropped off at another location or order if a dropoff location is specified or if the route services another order that has a delivery demand for the same item type. Upon picking up the item, the vehicle’s amount carried will be increased appropriately and compared against the relevant capacity dimensions. In cases where items of the same general type are picked up and delivered, but one does not want to deliver the items picked up on the route, then a descriptive item_type can be used to guarantee this behavior. For example, if you are picking up portable toilets, it is highly recommended to use "dirty toilets" and "clean toilets" as separate item types to guarantee that a customer receives a toilet in the expected condition! A pickup demand is expressed as follows

Replenishment

In problems that involve the delivery of the same item type(s) to multiple locations, it may be beneficial to replenish the supply of that item mid-route so as to service more orders over the course of the shift. There may be multiple replenishment sites available that are different from a central depot where the routes may start. A replenishment event involves re-supplying the vehicle with an amount of item(s) determined by the optimization. This is accomplished by adding a separate order that has a replenishment capacity as shown below. Note that replenishment orders are only visited if the optimization determines it is beneficial to do so, so that a default value of min_visits =0 is set for these orders. That way there is no penalty for the visit_range constraint if we do not visit these orders. An example replenishment order is provided below – as with standard orders, one can specify a duration and a maximum # of visits.

Unloading

In a case where items are picked up at customer locations, one can specify certain orders where a vehicle can unload its contents so that more items can be picked up. For example, a waste disposal company may have different dump sites so that the route optimization can select where to unload the contents. The vehicle can then continue to pick up more items at subsequent stops. As with replenishment orders, min_visits is forced to be 0 for these orders and they are only visited when it helps to improve the solution.

Dropoff

In our terminology, a dropoff is different from a delivery in that a specific item picked up during the course of a route can be dropped off at a specified stop along the way prior to the end of a route. For example, passengers may be picked up at the airport and be transported to a hotel with intermediate stops potentially on the way. In contrast, for an order that specifies a delivery event via delivery_item_quantities , one has no control over where a delivered item came from -- the items could be from the initial loading of the vehicle, a replenishment event, or items picked up at a different order. In general, when "point to point" shipment of an item is needed then an order should be specified with a dropoff_location_id to specify this behavior. More details on this distinction are available in the Pickup and Dropoff tutorial

Read article
Salesforce Developers

Pickup and Dropoff Problems

In our routing problems, items are loaded onto our vehicles in a variety of ways: they may be loaded onto the vehicle at the start of the route, items may be picked up at a customer order, or supply can be replenished at a specially designated "replenishment order". Once an item is onboard the vehicle, then it is eligible for a delivery event for orders that specify this item type in delivery_item_quantities . However, when these items are delivered, there is no way to specify that a specific item of that type should be delivered to a specific location. In other words, if the items are boxes, then with the typical usage of pickup_item_quantities and delivery_item_quantities there is no way to guarantee that a specific box is delivered to a specific location. However, this behavior can be guaranteed with the notion of a dropoff .

Given an order with items to be picked up, one can designate that these items are dropped off later in the route at a specific location by specifying a dropoff_location_id as part of the order object. An optional dropoff_deadline can be specified inside the order object to specify the latest time that the dropoff occurs. Adherence to this deadline is enforced via the dropoff_deadline constraint. Additionally, in cases where a deadline is less important than the amount of time an item spends on the vehicle (as in passenger pickup and dropoff or the transport of perishable goods), one can use the journey_time to limit the time between the pickup event and the eventual dropoff. The example order below demonstrates how to specify this sort of dropoff event.

For all problems involving the pickup of items that are then dropped off at a subsequent stop later in the same route, the optimization keeps track of the items on the vehicle and ensures that a vehicle's load never exceeds its capacity (specified in the vehicle object via capacity_by_item , weight_capacity , and/or volume_capacity ).

In the example request below, we have a fleet of three passenger vans that can each carry up to 6 people (this limit is set via the capacity_by_item for each vehicle). The vans start and end at different hotels in Atlanta, and the task is to pickup a variety of individuals and groups at locations throughout the city and drop them off later on at a different location. Many orders consist of multiple passengers and many orders also have a dropoff_deadline that is enforced with the dropoff_deadline constraint. In order to provide high quality service and to try to ensure that customers do not remain on the vehicle too long, we also provide a journey_time constraint that penalizes any route that has a customer on the vehicle for longer than 60 minutes.

Expand to view request sample
Read article