Traveling salesman (TSP) for line routes, snowplowing

Question

In a typical TSP algorithm, we have multiple points and we want to travel in the optimal order of travel. Points being households, customers, and etc. basically a dot on the map.

Instead of points, I have lines to optimize. Snowplowing is a good example, where you have multiple streets to travel. And the biggest difference is that for each travel, the point you end is different than your start point. My attempt was to just assume starting point as the only node in each travel. But apparently, whenever your route/line is quite long, you end up at a distant point from your start. And the solution is nowhere close to optimal anymore.

I looked at some companies that provide route optimization. Their solution is just to break lines into close points; and treat each line as nodes close to each other. I think that won't work when you have to travel two sides of the street, or whenever you get close to another street.

I wonder if there is a modeling trick, or any other way to solve this problem?

Answer 1

You've actually presented four entirely different challenges in your question, composed of two primary challenges with two sub-challenges each.

Challenge 1: uni-directional street traversal

In this case, the challenge is to find the optimal route given a set of streets that only need to be traversed in one direction. This challenge itself can be further sub-divided into two challenges.

Challenge 1A: uni-directional street traversal with mandatory completion

In this challenge, the salesman is required to traverse the entire length of a street before going to the next street. For this challenge, each street can be modeled by its two end points, and the problem can be solved with the TSP algorithm with one modification. When the algorithm chooses one endpoint of a street for consideration, the salesman is repositioned to the other endpoint of the street, and both endpoints are marked as fulfilled.

Challenge 1B: uni-directional street traversal with optional side trips

Similar to Challenge 1A, with the exception that the salesman is allowed to leave a street, so as to traverse one or more other streets, before returning to complete the current street. For this challenge, each street can be modeled as a series of points to be visited, and the solution is the standard TSP algorithm.

Challenge 2: bi-directional street traversal

In this case, the the challenge is to find the optimal route given a set of streets that need to be traversed in both directions, or at least have points of interest on both sides. This challenge itself can be further sub-divided into two challenges.

Challenge 2A: bi-directional street traversal with mandatory completion

This is the postman problem and/or the mixed-mode-of-transportation problem. Consider an imaginary postman who starts with a truck full of mail. At each street, some of the mail is loaded into a bag that the postman carries on foot to each house. The postman delivers mail on one side of the street, and then returns to the truck while delivering mail on the other side of the street. To put it another way, the traveling salesman is required to return to his point of origin, in order to continue using an alternate mode of transportation. For this challenge, each street can be modeled by its two end points, and the problem can be solved with the TSP algorithm with one modification. Once the algorithm has considered one end-point of a street, the other end-point is removed from consideration.

Challenge 2B: bi-directional street traversal with jaywalking

This is the most difficult of the four challenges. The issue here is that traveling to a point that is geographically close may not provide the optimal solution. For example, on a rural road, jaywalking may be legal and safe. However, on a four lane boulevard, jaywalking could be illegal and extremely dangerous. Furthermore, there could be considerable time delay while waiting for a break in traffic that would allow jaywalking to be attempted. To solve this problem, the TSP algorithm must be modified to include a cost function. In a normal TSP algorithm, the cost of traveling between two points is proportional to the distance between them. But for this challenge, the algorithm must first consider each pair of points, and compute the cost to travel between those two points. Then the standard TSP algorithm can be used to find the optimal route based on those costs.

Answer 2

I don't think that TSP is the right problem. You are looking for an Eulerian Path - a path that goes through all edges of a graph. In TSP, you're looking for a Hamiltonian Path - a path that goes through all vertices.

The good news is that finding an Eulerian Path is relatively easy. There might not be one that goes through each edge exactly once, but that's also very easy to detect.