The Route Optimisation service allows you to create routes to execute a set of vehicles. These created routes respect pre-existing boundary conditions. Those boundary conditions incorporate a limited number of vehicles with a given capacity, restricted opening intervals of locations, driving times between the locations as well as service times at the locations.
A route sub-divides into trips. A trip is a subsequence of a route, so a trip is a sequence of stops and rides between the locations, just like the route. There is always at least one trip per route, and a trip comprises at least two stops.
Route
A route is a sequence of stops and rides in between starting at the vehicle start location and ending at the vehicle end location. A route is linked to a specific vehicle, and a specific vehicle can be linked to at most one route. A route provides the information on which pick-ups and deliveries are carried out in which order by the specified vehicle and its driver within the planning horizon and within the driver's availability. Consecutive pickups and/or deliveries at the same location are grouped into stops.
Trips
The trips of a route do not overlap, a stop is always part of at most one trip. All other stops belong to a trip. We distinguish two kinds of stops:
- Transport stops
Stops for which a transport id is given, i.e., delivery IDs and pickup IDs are not both empty. - Non-transport stops or extra stops for short
Stops without a reference to a transport order.
Sometimes, there is no pickup or delivery to do immediately after the trip/route begins or before the trip/route ends. Then an extra stop is created.
Note: It is not necessary to specify extra stops as part of the input. They are generated in the output and can be easily discerned as their arrays with the transport IDs are empty.
Because of the extra stops, there are some simple rules:
- Every stop (extra stops and transport stops) is part of exactly one trip apart from the following exceptions:
- The first stop, if the second stop is at a depot and no pickup takes place at the first stop since it represents the vehicle start location.
- The last stop, if the next-to-last stop is at a depot and no delivery takes place at the last stop since it represents the vehicle end location.
- Every trip/route begins with a stop and ends with a stop.
- The way between two stops belongs to a trip if and only if both stop belong to the same trip.
Examples
- A trip may start at the vehicle start location or end at the vehicle end location. It may happen that there is no pickup or delivery at these locations, so an extra stop is created.
- A trip may begin at a depot but there may be no pickup work to do, so an extra stop is created.
- A trip may end at a depot but there may be no delivery work to do, so an extra stop is created.
Valid Route Structure
At trip start and trip end, there are no transports in execution. A trip always comprises both the pickup and the delivery of a transport. Routes planned with the Route Optimisation service always satisfy these route structures.
Note: If the route structure of an input route is invalid, a general validation error is thrown.
Start and end of a route
A vehicle start location can either be a customer or a depot location.
Note: The location type only matters if a pickup is served at this location.
Cases for the start of a route:
- The route starts at the vehicle start location without performing a pickup and is followed by a depot stop with pickup.
- The route starts at the vehicle start location without performing a pickup and is followed by a customer stop with pickup.
- The route starts at the vehicle start location with performing a pickup or no vehicle start location is set at all.
Cases for the first trip start:
- The first trip starts at the first stop if no vehicle location is defined or if no pickup takes place at the vehicle start location and the next stop is a customer location.
- The first trip starts at the second stop if a vehicle start location is defined and the next stop is at a depot location.
Note: The cases for the last trip end are symmetrical to the described ones, i.e. the last trip ends at its vehicle end location or at the next-to-last stop.
Transition to the next trip
When ends a trip?
- A trip ends whenever there are no more transports in execution after delivery at a depot location. In this case, the trip ends at this depot location and the last stop of this trip is at this depot location.
- A trip also ends after a ride to a depot location when there are no transports in execution. In this case, the trip ends when arriving at this depot location.
Cases between trips:
- Rides between trips are possible if only deliveries are carried out at a depot location.
- Rides between trips are possible if only pickups are carried out at a depot location.
- Rides between trips are possible if deliveries and pickups are carried out at a depot location.
Note: If both pickups and deliveries are performed at a depot location, the deliveries form the last stop of their trip. The first stop of the next trip is formed by the pickups at that depot location.
Info: Empty rides that belong to no trip are depicted with grey dashed arrows. Empty rides within trips are depicted as coloured dashed arrows.
Note: If only either pickups or deliveries for one of the adjacent trips are performed at a depot location, then there an extra stop is created in the other trip.
Valid loading sequence
Route structures where a location is visited multiple times for loading or for unloading are undesired. To avoid such route structures, the Route Optimisation service restricts the possible route structures to certain loading sequences.
The following sequences are invalid:
- A location is left although there is still a load for it on the vehicle.
- A location is reached again although there is still a load from it on the vehicle.
Note: If the loading sequence of an input route is not valid, a ROUTEOPTIMISATION_INVALID_LOADING_SEQUENCE error is thrown.
Examples
Starting position and valid loading sequence if there are three types of transport:
Starting Position
A valid loading sequence
______________________________________________________________________________________
The following changes would make the loading sequence above invalid (the violations are depicted with a black dashed arrow):
Unloading only transport 2 at location D, leaving location D and driving back to location D at the end of the trip to unload transport 3.
______________________________________________________________________________________
Loading only transport 1 at location A, leaving location A and driving back from location B to location A to load transport 2.
______________________________________________________________________________________
Another valid loading sequence:
In this loading sequence, location A is visited twice. However, when location A is visited for the second time no load from location A is on the vehicle any more. Therefore this loading sequence is valid.
General examples
In the multi-depot and single-depot examples, the vehicle starts and ends its route at the same vehicle location which differs from the locations where vehicles should be served.
Multi-depot example
The example contains the following locations where the vehicles should be served:
Trip 1:
- One vehicle from depot location A to customer location 1.
- One vehicle from depot location B to customer location 2.
- One vehicle from customer location 3 to depot location A.
Trip 2:
- Two vehicles from depot location B to customer locations 4 and 5.
______________________________________________________________________________________
The route begins at the vehicle start location. The empty ride to depot location A does not belong to any trip.
The goods of the first vehicle are picked up at depot location A. Here, the first trip starts.
The next stop is depot location B where the goods of the second vehicle are picked up. The subsequent stops are for the deliveries of the goods on the vehicle, followed by a pickup stop at customer location 3. The ride between customer location 2 and customer location 3 is an empty ride but the current trip cannot end here because neither customer location 2 nor customer location 3 is a depot location, and only depot location act as trip delimiters.
The vehicle returns to depot location A to deliver the goods from depot location 3. Since the vehicle has arrived at a depot location where the vehicle becomes empty, the first trip ends here.
The remaining vehicles are to be picked up at depot location B. Therefore, the vehicle heads towards depot location B. The empty ride between the depot locations is not a part of any trip, but only part of the route.
The second trip starts with a pickup stop at depot location B, followed by two delivery stops. As there are no pickups on the second trip, there is no need to approach a depot location after the delivery at customer location 5. Therefore, the vehicle heads towards the vehicle location. The empty ride between customer location 5 and the vehicle location is a part of the second trip because a trip can only end at a depot location or at a vehicle end location. The second trip ends as soon as the vehicle arrives at the vehicle end location.
______________________________________________________________________________________
Single depot example
The example contains the following locations where the vehicles should be served:
Trip 1:
- One vehicle from customer location 1 to customer location 2.
- One vehicle from customer location 2 to customer location 4.
- Two vehicles from customer locations 3 and 6 to depot location A.
Trip 2:
- Three vehicles from depot location A to customer locations 5, 6 and 7.
______________________________________________________________________________________
The route begins at the vehicle start location with an empty ride because the first location along the route is a customer location.
The goods from customer location 1 are delivered to customer location 2. The goods from customer location 2 are delivered to customer location 4. In between, goods are picked up at customer location 3 that need to be returned to the depot location A. The first trip ends after unloading these goods at depot location A.
Immediately after that, the second trip starts also at depot location A with the loading of the goods for customer locations 5, 6 and 7. At customer location 6, goods are picked up to be returned to depot location A. As soon as these goods are delivered at depot location A, the second trip ends.
The empty ride from depot location A to the vehicle location is not a part of any trip but only part of the route.