Performance of KEP usecase

[Bernd Welter]

Cheers,

I've been asked about the performance of a sequencing usecase (KEP to be more precise). Well, the answer is not that simple so I decided to write this forum post. I'll start with an assumption and also mention some factors with impact on performance.

Here's the story:

Imagine the requirement is to optimize a sequence of 100 parcels supposed to be delivered in an urban area. A single vehicle is used

Under the roof the usecase is splitted into several steps:

• DistanceMatrix calculation
  • Best case: the DIMA is already available (or AIRLINE is sufficient) : 0 seconds
  • Average case: DIMA is supposed to be calculated based on HPR : <2 seconds
  • Worst case: No DIMA available, time dependency applies, conventional approach... : could take 10 seconds or more
  • PS: the performance boost we achieve in DIMA calculation is getting bigger with the size of the distance matrices. For very small distance matrices (e.g. <10²) you may encounter a stable overhead when you use the cloud based services. This is because of some network latency and internal file handling on the shared space in Azure For larger sizes you would not recognize this overhead compared to the overall calculation time.
• Optimization via the core algorithm (VRP solver)
  • Best case: performance mode, pure sequence (no constraints, no unscheduled orders): < 1 second
  • Medium case: < 5 seconds
  • Worst case: many, many time window constraints: 10 seconds
• The routing:
  • Best case: not required (no visualization): 0 seconds
  • Medium case: simple route, no time dependency: 1 sec
  • Worst case: time dependency, no search graph available...: 3-5 seconds
• Visualization / Mapping
  • Best case: no visualization needed: 0 seconds
  • Medium case: cache available, small image size: <1 second
  • Worst case: large screen, no cache: about 2-5 seconds

As mentioned above there are many factors with an impact on performance:

• On Premise versus cloud service
• xDima: DIMA available or not?
• xDima/xRoute: time dependency needed?
• xDima/xRoute: geographic area
• xDima/xRoute: HPR possible?
• xTour: structure of time window constraints
• xTour: Performance versus Quality
• xTour: AvoidOverlap
• xRoute: result fields - each requested element raises computation time and network latency due to increased response size
• xMap: Display size (number of tiles) - cache available

List is subject to grow Feedback is welcome!

Bernd