Question

How to include travel time and time-windows into the Traveling Salesman Problem in FME?

  • 21 December 2023
  • 2 replies
  • 2 views

Badge +6

I'm working on a Traveling Salesman Problem. I've included the background and goals I'm trying to achieve.

 

Background:

  • I have a topological network that I can create a route over.
  • I have locations on the network that require maintenance.
  • Each location has a unique minimum and maximum number of days allowed between maintenance visits.
  • I have the speed in which the maintenance team can travel, the length of time maintenance requires, the hours per day that maintenance works, and days per week worked.
  • The maintenance staff do not return to a starting point between visits, but travel directly from one location to the next.

Goal:

  • I want to create the ShortestPath for the maintenance vehicle that ensures that each location is visited during the timeframe allowed.

Problem:

  • I am able to create a ShortestPath between the locations, but I can not figure out how to include the earliest and last dates that the locations should be visited in the algorithm.

2 replies

Badge +6

I'm back from vacation and back on this, any suggestions?

Badge +14

Hi @Matthew Boyter​  Looks like we don't currently support solving the Traveling Salesman Problem with Time Windows. However, we could support this in the future if you were to create an idea to gather some interest.

 

A workaround a colleague mentioned is you could assign each stop to a particular timeframe, and then do a group-by using that timeframe. So you'd have - for example - the best route for all calls between 8am and noon, then another best route for calls between noon and 4pm. However, if you want the afternoon run to start from the last stop of the morning, that complicates things. You'd probably need to run each as a separate process, so you could take feed the last stop in a previous run into the first stop in the next run.

 

Hope this helps!

Reply