Single Vehicle
Jimmy and Sally have just started a lighting company to service a number of commercial addresses. Lucky for them, their first major assignment is a government contract. They start and end their day at the White House, and here are the places they were assigned to service.
-
The Washington Monument: 38.889484, -77.035278
-
Ford’s Theatre: 38.8967, -77.0257
-
Abe Lincoln Memorial: 38.8893, -77.0502
-
The Vietnam Memorial: 38.8913, -77.0477
-
The Thomas Jefferson Memorial: 38.8814, -77.0365
We begin by building out a JSON payload and add the locations of the job sites as a simple array of locations objects:
Jimmy and Sally also think about the time they want to start and end their day. They estimate the amount of time (in seconds) required to service each order and add this as the duration. They also prioritize the orders since there is a chance they may not be able to service all the orders in a single day (shift). Note that an order is directly related to a location. Conceptually, orders represent a request for service (such as delivering goods to a store), and a higher priority indicates that if it is not possible to visit all orders, then the higher priority orders should be favored.
With the locations and orders specified, the next step is to define constraints. the Optimization API has an extensive library of constraints that allows you to very precisely define what a “good” solution looks like. In this case, the objective is simple: visit as many orders as possible, minimize travel time, and make sure that if we can’t visit all the orders, we at least visit the highest priority orders. Each constraint has a penalty which determines how important it is to satisfy. For many constraints, the degree of the constraint violation can also be included in the penalty via the
violation_increment
. We do this below with the travel_time constraint so that each second that a vehicle travels is assessed a penalty of 1. This gives us a standard way of thinking about penalties and is recommended in all use cases. The visit_range constraint tells the Optimization API that we want to visit as many orders as possible. Since the penalty for this constraint is 10,000, if we miss an order then the solution is assessed a penalty of 10,000. The
order_priority
constraint indicates that orders with higher priority should be favored if all orders cannot be serviced (see the documentationof this constraint for additional details).
Sally and Jimmy also need to specify a vehicle and their shift. The shift is how the Optimization API knows when the vehicle and associated workers are allowed to operate. In this case, Sally and Jimmy define the shift as being from 8:30am to 5:00pm, and they also specify where the shift must start and end (the White House). Note that a shift can start and end at somewhere other than an order, for example a worker’s home address. Also, they specify vehicle type “car”. If routes for trucks and other restricted vehicles are desired, then the vehicle type can be set to “truck” with other parameters in order to ensure that the routes returned by the Optimization API are compliant.
You’ll notice that the vehicles parameter is actually an array. This is because the Optimization API can support multiple vehicles for a given problem. Additionally, each vehicle can operate for multiple shifts so that the Optimization API is able to solve problem involving many disjoint shifts. We will return to this more advanced functionality in later examples. Putting it all together, the payload looks like this.
Expand to view request sample
Four of the five orders are visited. The lowest priority Vietnam Memorial (red pin) is missed, but otherwise the route is efficient in terms of travel and meets our objectives.
The urgencyconstraint is different from Order Priority in that it tries to satisfy visiting more urgent orders earlier during the planning period (represented by a vehicle’s shift object). In the original solution, we visited the Lincoln Memorial as the last order. Now suppose we need to visit the Lincoln Memorial and Ford’s Theater earlier in the planning horizon. We could either add time windows for these orders or use the urgency constraint to encourage visiting them earlier in the day. First we will demonstrate this capability by adding urgency values for these two orders and then adding a new constraint of type urgency. The new request is below (only change to first request is addition of urgency constraint).
Expand to view request sample
The high urgency orders at Ford’s Theater and the Lincoln Memorial are now visited earlier in the day. The route is less efficient from a travel perspective but the sequence better meets our objectives. The Vietnam memorial is still not visited since we still have the
order_priority
constraint in place.
Sally and Jimmy received some changes – they will also have to service the Ravens football stadium in Baltimore. They reflected on how they might change their trip around. Some of the job sites are more complex than others and require more time. Instead of spending one quick day in DC, they need to spread their trip over two days. As such, they reserve a night or two at a hotel north of DC. Sally appends this location (39.064295, -76.965838) to their list. They will start each day at the hotel, plan on ending at the White House on day 1 to do some sightseeing, and will also plan on celebrating the end of the DC work by going to a sushi restaurant in Annapolis – this will be the end_location of their shift on the second day.
Let’s summarize how these stipulations change the the Optimization API payload.
-
LOCATIONS —
Not much changes here. Sally just adds the latitude and longitude of the stadium, hotel and restaurant to the array.
-
SHIFTS —
Sally adds another shift to the shift array to account for the extra day. Additionally, with all this new work they will be hungry so lunch breaks are now added each day from noon to 1pm.
-
ORDERS —
The amount of work changes at each order, so the durations change, we add an appointment at the Lincoln Memorial and Vietnam Memorial, and also add a new long job at the Ravens stadium. Note that adding the appointment to the order doesn’t guarantee that we will visit it – we need a constraint to enforce that.
-
CONSTRAINTS —
Sally now specifies a
scheduled_appointment
constraint with a high penalty to ensure the appointments are met.
Expand to view request sample
Luckily it is still possible for the pair to complete all the work, do some sightseeing and finish with a celebration in Annapolis. Since the Optimization API accounts for predicted traffic in its routing calculations, the pair takes paths between locations that minimize the estimated travel time. Nevertheless, the pair expect their total travel time to be about 39 minutes longer due to traffic over the two day period (total_traffic_time in the response).
The first day in purple, the second day is in green. Note that the shifts are for the same vehicle but the Optimization API allows you to have different start or end locations for individual shifts.
Sally and Jimmy have now received word that some of the locations they are servicing have other events planned, and they must arrive at the orders only during certain times. These are referred to as time windows and the Optimization API allows us to ensure that service at an order only begins during a time window. We remove the appointments from the existing orders and now update each order with a time window. This will lead to a less efficient route from a travel perspective, but they will now be starting service at each order only during the allowed window.
-
Orders
: Each order now receives a time window.
-
Constraints
: The scheduled_appointment constraint is removed in favor of a time_window constraint. Note that we use a violation_increment of 3600 in this constraint which makes the penalty depend on by how much we violate a time window. For example, if we are 3 hours late for a time window, then we will be hit with a penalty of 5000 for the initial violation plus another 3*5000 = 15,000 to penalize the fact that we are 3 hours late. The total penalty in this case is then 20,000 – equivalent to about 6 hours of travel.
Expand to view request sample
Luckily it is still possible to service all the orders where the pair arrives during a time window, eat lunch, and start/end each day at the desired location. Now the workload is more spread out across each day with 3 orders serviced on each day.
The Full solution for the two-day situation where all time windows are honored.
Zoomed in view of the 5 orders visited in the city. Note that time windows often force us to visit orders in a less efficient sequence than we would do otherwise.
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.
