Today, traveler salesman problem gives up with the capacity of 22 cities. That is the theoretical limit. The commercial limit with reasonable execution time must be somewhere around 10.

What is the area that's hitting the these practical limit today? I'll have a series in exploring different industries.

Traveler salesman problems span over many applications from computer printing boards to soldering. But let us first start with the biggest, most obvious of all, the delivery driver.

Canada Post

I started from diving into Canada Post: the mammoth of delivery monopoly in Canada. They have 64,000 employees with $8.2 billion revenue.

I dived into Indeed's job reviews to understand their work schedule.

The biggest complaints involve around:

  • Toxic work environment
  • Job insecurity for on-call staff
  • New routes expectation
  • Physically demanding walking hours

I am surprised to hear the job insecurity as the problem in the semi nationalized monopoly company with such huge brand. That's the downside of union jobs. Those that are in are heaven. Those that are out is hell. It's crazy the media only talks of gig workers of Uber's ignoring the big established ones right in their nose.

I can go on poking on corrupted established institutions. But today's about traveler salesman problem which involve new routes.

It turns out there's a big difference between new guys and old. The senior ones get the same good route over and over. I'm guessing good routes as the houses are concentrated and walk is easy from the street.  New guys however has to fill in the routes that has absence. That means they have to adopt to new routes every time. I imagined it would be as simple as following Google Map. But apparently it involves a lot of memorization. New routes take them 60-80% as much time one mentioned.

That's a whole new insight I didn't know before. They are not the algorithmic problem but much more the human issues.  When someone leaves, another has to fulfill that route. The route is relatively stable and that makes drivers more efficient because there's more to delivery than a simple GPS.

In terms of delivery loads, it ranges to 1000-1800 mailbox every day. And sometimes they need to deliver parcels to individual houses on foot. Those numbers certainly pass way beyond the traveler sales man capacity. No computers today can handle traveler salesman of that scale without any estimation. The possibility of routing if infinite if to do it properly.

It seems that the company updates routes every few years as well. It is to accomodate changing demands and find optimal routes for employees. That's the place traveler salesman is used.

I still wonder if there's a dynamic routing that makes delivery more efficient that evens out human resources (so if one person has less load, that person expands the route more). Or the delivery route if there's no mail delivery at certain post that day. I'm really curious of how their routing looks.

Delivery is such a big industry with growing demand, I'll do another series the next day looking at Amazon delivery.