FTL example: find next orders for vehicles

[Bernd Welter]

Hi there,

this week I was playing with a specific challenge provided by my polish colleague Tomasz. Maybe a good story to share with you: here is the given input data:

The last positions of a bunch of available FTL vehicles. I also know the country where they remain.

On the other hand we have a set of long distance FTL orders from Western to Eastern Europe.

Now the target is this

• Assign not more than 1 order to each vehicle to create a three stop tour:
  • vehicle position
  • order pickup
  • order delivery
• Minimize the sum of each vehicles distances

Now here's a first output:

On the left we see the gantt which shows the driving times being split into "vehicle position to pickup" and "pickup to delivery"

But of course we can add more potential parameters:

Now I also enabled break and rest rules (MultiDays) so we can regognize the interruption of the work because of the grey shift breaks. Important: as the expected tours are long distance tours I is important to allow this: dailyRestPositions = RestPositions.ANYWHERE. If not set the drivers shoudl take their breaks at Depots or at logical position between trips. As each Tour in this case is a single trip this won't work as long as you don't use ANYWHERE.

And now we can see that by enforcing the "vehicle position country" has to be equal to "pickup country". This causes some more unscheduled orders. The motivation behind this setting is Cabotage. Though we do not consider cabotage via API it is possible to define a matching between vehicles and orders on a generic level. You can always use the equipment feature for that if you can provide the matching restrictions from outside.

What we could also add to this:

• Distances and traveltimes are based on distance matrices. I used one matrix to rule them all. Of course the matrix could also be computed for each vehicle.
• Vehicles real quantities and orders occupied quantities haven't been considered. Possible.
• Most drivers might need a break earlier to what is applied here: we could also add a drivers work logbook, his history. Just wasn't given here
• For each order's locations we could imagine to add time constraints such as earliest pickup, latest delivery, ...

Want to add further constraints? Ask me!

PS:

• Cabotage on Wikipedia
• Rules on cabotage as applicable from 21 February 2022

[Tomasz Lotocki]

Thx Bernd, cool sample

[Bernd Welter]

If you liked this article don't forget to check this one about Backhaul calculation / Freight exchange !

[Tomasz Lotocki]

Hi Bernd, can we use the same logic using PTV Developer, Route Optimization API?

[Bernd Welter]

Hello Tomasz,

let's be careful with the API versions - also in the context of August 2024:

• The Route Optimization Optiflow API (aka "RouteOptimization v2") does not support "open" tour structures at the moment. As each vehicles end location must be known in advance the OPTIFLOW driven API does not apply here. Not today. We are aware of the need for open tour structures and it is on our priority list.
• The Route Optimization API (aka "RouteOptimization v1" powered by VRP solver) supports the following parameters which I used in the xTour2 approach I implemented in the client:

  xTour2	Dev.RO v1	Purpose
  planToursOptions .restrictions .maximumNumberOfCustomerStopsPerTour	RO .vehicle .maximumNumberOfCustomerStops	this is to ensure that a single trip is not dealing with more than one transport
  planToursOptions .singleTripPerTour	RO .restrictions .singleTripPerRoute	ensures that a vehicle does not return to start a second trip
  planToursOptions .restrictions .workingHours	various approaches possible	ensures required breaks based on rules and laws.
  planToursOptions .restrictions .enableMonetaryCostMinimization	not supported	would target the given vehicle costs as base for the optimal assignment.

So what is mainly missing in the ROuteOptimization v1 is the possibility to see the given cost vectors as the base for the optimizers target function.

Bernd