Algorithms // Finance // CRM

The Financial Travelling Salesman Problem

The Financial Travelling Salesman Problem

The Travelling Salesman Problem (TSP) has been around for centuries and has been studied by mathematicians and scientists alike. It asks the following question:

What is the shortest route through a list of cities in which you visit each city exactly once and return to the starting city?

In computer science, the TSP is classed as an NP-hard problem and in simple terms, as the number of cities increases, it becomes harder to predict how long it will take to find the optimal route. There are, however, a number of approximate solutions which can return routes to within 3% of the optimal solution in polynomial time.

Asset and wealth management companies manage enormous amounts of money for their clients, which can range from government institutions to high net worth individuals. The salespeople in charge of managing the relationships with these clients travel a great deal as part of their role.

This leads us to an interesting crossroads between theoretical computer science and the investment management industry. To use the TSP in real life we’ll have to make a few considerations and adjust the problem statement to tailor it to the investment management space.

These adjustments will be covered by making the following considerations:

  1. We’re not using horse-drawn carriages or riding camels
  2. We’re not travelling to a marketplace
  3. Time matters more than distance
  4. Visiting a client doesn’t necessarily imply co-location
  5. Not all clients are equally valuable
  6. Not all clients want to meet
  7. Not everyone is a client yet

In the following sections, these considerations will be discussed, allowing us to understand a new flavour of the TSP.

We’re not using horse-drawn carriages or riding camels

Although the origins of the Travelling Salesman Problem are unclear, we know that it is from a bygone era. The days of horse-drawn carriages and camels as the primary mode of transport are long gone.

With cars come traffic jams, and with trains and air travel come delays and cancellations. It’s no good giving a route which would be marred by traffic jams and delays simply because it’s the shortest route. A modern day TSP would not only have to consider multiple modes of transport, but it would also have to factor in traffic jams and delays into its dynamic route planning.

In addition to different modes of transport, a salesperson can’t simply set up a tent on the side of the road. Travel planning must therefore also be scheduled around the availability of suitable accommodation for the salesperson. Although this is a non-issue for most cities, major events can throw a spanner in the works. For example, an international sporting event in a city could make it infeasible to book a hotel room or drive through. Given this, our route planner must factor such anomalies and plan accordingly.

We’re not travelling to a marketplace

The TSP in its raw form is concerned with finding the shortest total distance for a salesperson’s route. This is a useful problem to solve for a salesperson travelling from marketplace to marketplace.

The concept of a physical marketplace isn’t as relevant in the investment management industry. There isn’t a fixed marketplace where a salesperson can set up shop and have customers approach. The onus is on the salesperson to visit their clients and so instead of a single marketplace in a city, the city itself is effectively comprised of a multitude of different marketplaces, one for each client.

The concept of a marketplace is also an evolving concept. It is not necessarily a physical location, and increasingly the marketplace has moved online. Sales pitches that traditionally take place face-to-face can now happen virtually. With the large amount of regulation and paperwork involved in onboarding a client, the industry has been slow to adopt a completely online process, but this marketplace is shifting. As this continues to occur, travelling to a marketplace will also take on a different shape.

Time matters more than distance

The TSP has practical applications in fields such as microchip design, where the shortest path must be laid out inside microprocessors. The nanoseconds it takes signals to traverse these silicon mazes affect the speed of the hardware so it’s of paramount importance to have the shortest route in place.

tfl webcat
It is sometimes quicker to travel farther out due to transport links between certain locations. Above is a travel time map from Westminster, London (generated using TfL WebCAT) Key: Brown/Red/Orange — 0–45 minutes, Yellow — 45–60 minutes, Dark/Light Green — 60–90 minutes

Physical distance isn’t as important anymore. With multiple modes of transport, it sometimes takes the same amount of time to travel farther out due to the presence of train stations or regular flights between cities.

For a salesperson based in New York City, it takes slightly less time to fly to Washington DC as it does to take the train to Philadelphia. A naive application of a TSP algorithm might direct the salesperson to Philadelphia, thus highlighting the need for our route planning tool to consider temporal distance as opposed to spatial distance.

With this in mind, the TSP can now be restated as:

Given a list of clients, what is the shortest amount of time it takes to meet each client exactly once and return back to my starting location?

There are many pitfalls here that also need to be factored in. Flights have a significant amount of float time associated with them, such as travel to and from the airport and time lost in the boarding process. All of these factors must be accounted for when adjusting the TSP algorithm to work in the modern day.

Not all clients are equally valuable

For a salesperson with a large number of clients, it’s infeasible to go out and meet every single one. How does a salesperson choose? How does the salesperson create the list of clients to be fed into the TSP algorithm?

For asset and wealth managers, there are numerous ways of ranking their clients by order of precedence. The criteria by which clients are prioritized are typically of the following variety:

  • Amount of money the client has: the higher the client’s assets or net worth, the higher they are prioritized
  • Amount of revenue generated from a client: linked to the point above, the more revenue a client brings in, the higher their priority
  • Business at risk: a salesperson will prioritize a client who is at risk of withdrawing their holdings with their investment manager

In addition there are a large number of other factors which come into play, such as the client’s global presence and sales potential, number of employees, their product interests, marketing engagement… the list goes on.

Given these rankings (with appropriate weightings), our TSP algorithm must discard clients with a low rank from consideration to allow for both the effective use of the salesperson’s time, and the prioritization of which clients are seen in the given timeframe.

This is a classic machine learning problem. Given a corpus of data, a combination of algorithms could be used to determine and select the most appropriate criteria to be used in the ranking process. Then, using feature scaling this can be refined to produce intelligent rankings for clients.

Automating this process and leveraging machine learning techniques allow for a new twist on the TSP. Previously a salesperson would have to create a list of clients that they wanted to go and see. With the new ranking system, they would no longer be tasked with the manual process of finding the best clients to visit — machine learning could do the heavy lifting for them.

An extension of this is that a salesperson can reframe their query to the TSP. Instead of asking for the shortest route given a list of clients, a salesperson can now ask:

Which clients should I see and what route should I take for a three-day trip to Boston next week?

This is a vastly different question, which combines a sales planning tool with a route planning tool, but it starts to demonstrate the power and flexibility of modifying the TSP to fit the needs of a modern-day salesperson.

Visiting a client doesn’t necessarily imply co-location

Face-to-face meetings should be scheduled with only the highest ranked clients. This raises an interesting problem — which clients are worth the salesperson’s time? If a meeting is only going to take half an hour, but takes a four-hour round trip, our algorithm should allow the option to selectively deprioritize them and suggest alternatives.

A video or phone call may be the more appropriate mode of connecting with such clients, who could be ‘e-visited’ at any stage in the route, for example, the salesperson can talk to them while in transit, allowing them to squeeze more value out of their time.

The ability to filter clients out of a face-to-face meeting greatly improves the performance of the algorithm since it becomes much easier to find an efficient route when there are fewer stops to make.

In addition to this, the previously wasted float time (the time between two meetings, typically used to travel between locations) doubles up as time to meet clients via other avenues, be it phone calls, emails or video conferencing. This allows for new ways to increase the productivity and efficiency of salespeople.

Not all clients want to meet

Where some clients won’t have a face-to-face meeting due to the difficulty in planning a route around them, there are other reasons to not include a client in a route.

Each different client will have their preferred frequency of communication, both electronically and face-to-face. A client that was last met with one week ago should be ranked lower (in the list of clients by priority) than a client that was last met with 8 months ago. Meeting clients too regularly leads to a point of diminishing returns and may be off-putting. The inverse can also be true.

An extremely difficult addition to the Travelling Salesman Problem is to check that the client can meet. Assuming an optimized route, there is no indication that the client will actually be able to meet at the suggested time. This means that there will need to be multiple steps in defining an optimized route for the salesperson.

The availability of all clients will have to be determined and entered as an input, which is a difficult scheduling problem. If a client isn’t free, what happens then? Do we completely re-route so that we can coincide with the client when they are free? Or, do we de-prioritize them based on their lack of availability? Both, maybe.

There are multiple ways of solving this problem. The route planner could be run without client availability as a parameter. Then, given a first pass of the route, client’s availabilities at the set time can be determined. Based upon this, the route planner can swap people around or reroute accordingly.

If that re-routing fails, then a client can be pushed down the list of priorities and be saved until a later date. If a client is important enough that even after this de-prioritization they remain on the list, then they must be included in the route, resulting in other clients being pushed down the list to accommodate.

This is only one approach to solving the scheduling problem and may not be feasible in general (e.g. if a client isn’t available for the next month, but the salesperson is going on a trip next week). As previously discussed, the fallback could be to schedule a video conference or something of that sort, as opposed to relying on a physical meeting. The exact solution to the client’s availability is a hard one and in an industry where the client can dictate terms, there isn’t one simple solution.

The ideal TSP algorithm will highlight concerns in the route planning, but shouldn’t be over-burdened by it either.

Not everyone is a client yet

One thing we haven’t discussed yet is the importance for salespeople to travel to meet prospects and to close sales opportunities. Where we have previously discussed narrowing down the list, this will act to increase the size of the list.

As mentioned in the end of the ‘Not all clients are equally valuable’ section, a route can be planned given a set of criteria and parameters. An example would be a salesperson heading out to meet a prospect in a final stage of negotiation before closing a sale. The TSP algorithm would be able to suggest other clients/prospects to see along the way to maximize the utility in making the journey.

The result of all of our modifications to the TSP is that a salesperson could simply input a location and a time period, and an optimal route would be created, allowing the salesperson to meet with both clients and prospects along the way.

The Travelling Salesman Problem is an interesting mathematical curiosity and remains difficult problem to solve. The application and requisite modifications to fit it to the investment management industry lead us down many interesting avenues, turning it from a simple route planner into a fully fledged sales assistant.

Financial institutions of the future will have to race to build out this technology to remain competitive in an industry that is ripe for disruption.

Subscribe to my blog!

Get all the latest & greatest articles delivered straight to your inbox