Fast algorithms for a large-scale multi-agent Travelling Salesman Problem

31 January 2020
Michael Ostroumov

Background: The traditional business models for B2B freight and distribution are struggling with underutilised transport capacities resulting in higher costs, excessive environmental damage and unnecessary congestion. The scale of the problem is captured by the European Environmental Agency: only 63% of journeys carry useful load and the average vehicle utilisation is under 60% (by weight or volume). Decarbonisation of vehicles would address only part of the problem. That is why leading sector researchers estimate that freight collaboration (co-shipment) will deliver a step change improvement in vehicle fill and thus remove unproductive journeys delivering over 20% of cost savings and >25% reduction in environmental footprint. However, these benefits can only be achieved at a scale that involves 100’s of players collaborating at a national or pan-regional level. Such scale and level of complexity creates a massive optimisation challenge that current market solutions are unable to handle (modern route planning solutions optimise deliveries only within the “4 walls” of a single business).

Maths challenge: The mentioned above optimisation challenge could be expressed as an extended version of the TSP, but with multiple optimisation objectives (other than distance). Moreover, besides the scale and multi-agent setup (many shippers, carriers and recipients engaged simultaneously) the model would have to operate a number of variables and constraints, which in addition to the obvious ones also include: time (despatch/delivery dates/slots and journey durations), volume (items to be delivered), transport equipment with respective rate-cards from different carriers, et al. With the possible variability of despatch locations (when clients have multi-warehouse setup) this potentially creates a very-large non-convex optimisation problem that would require development of new, much faster algorithms and approaches. Such algorithm should be capable of finding “local” optimums and subsequently improve them within a very short window i.e. in minutes, which would be required to drive and manage effective inter-company collaboration across many parties involved. We tried a few different approaches eg used Gurobi solver, which even with clustering was still too slow and lacked scalability, only to realise that we need to build such an algorithm in-house.

Ask: We started to investigate other approaches like Simulated Annealing or Gravitational Emulation Local Search but this work is preliminary and new and better ideas are of interest. So in support of our Technical Feasibility study we are looking for support in identification of the best approach and design of the actual algorithm that we’ll use in the development of our Proof of Concept.  

  • Industrial and Interdisciplinary Workshops