Solving a VRP (google hashcode competition) using an off-the-shelf solver

Question

Problem summary :

A complete problem description is given here

Given a description of city streets and a number of Street View cars (cars that captures pictures as they move around) available for a period of time, your task is to schedule the movement of the cars to maximize the total length of city streets that were traversed at least once.

The city is represented by a graph, the nodes of which represent city junctions and are connected with edges representing the streets.

Streets are modeled as straight segments connecting two junctions. Each street has three properties: direction length( the distance in meters that a StreetView car covers while moving through the street) and the time in seconds that a StreetView car takes to traverse the street. Each pair of junctions is connected by at most one street. Each street connects two different junctions. The graph is not necessarily planar (due to bridges and tunnels).

We have a fleet of $N=8$ cars, all located at the junction $S$ at the beginning of the game. All car movement scheduled in the itinerary has to complete in $T$ seconds (or less) ­ a car cannot be in transit when the time runs out.

The objective function is the total length of all streets that were traversed by at least one car of their fleet at least once. Traversing a street that was already traversed multiple times (including traversing a bi­-directional street in the opposite direction) does not increase the objective function.

There is a single data file that is available here.(The number of junctions is $11348$ and the number of edges is $2\,\times$ number of streets (since I'm orienting them) which is equal to $2\times17958$)

---

Model for a single car :

The aim is to find a formulation that can lead to a solution using a commercial/open source solver. My idea is to write a model for a single car by taking $T := 8T$, then I need to divide the path obtained into 8 different paths for the 8 cars.

• $G= (V,E)$ is a graph where $V$ is the set of junctions in the city and $E$ is the set of oriented edges (I redefine it by setting $t_e = \infty$ if it's one way, it's not oriented in the statement)
• for every $e = (u,v) \in E$, $t_e$ is the cost(time) of the road ($t_e = \infty$ if it's one-way) and $l_e$ is its length.
• $T$ time limit for each car
• $v_s$ the starting junction

Variables:

• $\forall v \in V, f_v := 1$ if the car stops at $v$ and $0$ otherwise.
• $\forall e \in E, x_e :=1$ if the road $e$ is taken in picture and $0$ otherwise.
• $\forall e \in E, y_e$ indicates the number of times of passing this edge

Constraints for a single car:

• $\forall e = (u,v) \in E, x_e \leq y_e$ (to take a picture we must pass by the street !)

• $\forall e =(u,v) \in E, x_{(u,v)} + x_{(v,u)} \leq 1$

• $\sum\limits_{e \in E} y_e t_e \leq T$ (meaning that the path should be finished within $T$)

• $\forall v_i \in V, v_i \neq v_s,$ \begin{align}\sum\limits_{\,\,\,e \in E\\ e=(u,v_i)} y_e &= \sum\limits_{\,\,\,e' \in E, \\e' = (v_i,u)} y_{e'} + f_{v_i}\\\sum_{\,\,\,e \in E \\ e =(v_s,v)} y_e &= \sum_{\,\,\,e' \in E \\ e'=(v,v_s)} y_{e'} + f_{v_s} + 1\end{align}

• $\sum\limits_{v \in V} f_v = 1$ (a unique end)

The two last constraints but one guarantee that there is no "jumping".

Objective function: $\max \sum\limits_{e \in E} x_e l_e$

Questions

I have three questions:

1. If I set $T = 8T$, and implement the model, it will give one big path. How to split it to find a path for each car?

2. The number of junctions is $11348$ and the number of edges is $2\,\times$ number of streets (since I'm orienting them) which is equal to $2\times17958$. Someone told me that there is a lot of variables and it can't be solved with MIP solver. Do you think it's true? what are the limits of MIP solvers?

3. Is there a way to make the model better (from a computational point of view)?

Answer 1

This is the distance constrained multi-depot open arc routing problem. I doubt you will find any paper on this particular problem. You can use VRPSolver to solve it (vrpsolver.math.u-bordeaux.fr). However, the instance size is out of reach of this solver.

MIP solvers are bad for solving vehicle routing problems, even for much smaller instances (50-100 nodes).

There are some heuristic solvers which can be used for vehicle routing problems, for example LocalSolver. You will probably need to transform arc routing problem into more classic node routing. You can check this paper for comparative analysis of approaches how to do it: https://doi.org/10.1287/trsc.2019.0900

I do not think you will get a good heuristic solution based on your one vehicle model.

Answer 2

1. I think there may still be errors in your one car formulation, but in any event there is no obvious way to do a one car, $8T$ route and divide it up if all routes need to start at $S$. You would need to constraint your route to return to $S$ exactly seven times, and then figure out how to compute separate transit times for each return to $S$.
2. There is no simple answer to how large a MIP model commercial solvers can handle. For one thing, it depends on how dense the coefficient matrices are, how much memory you have (both RAM and disk), how many cores / CPUs / nodes (on a computing cluster), and how many lifetimes you are willing to wait. For another, some large problems solve quickly (because they have tight relaxations, or because you just get lucky) and some moderately small problems take forever (because they have weak relaxations, or because you get unlucky). I would not automatically conclude that your one-car model would be too big to solve, but I also would not bet money that it could be solved in "reasonable" time on "reasonable" hardware.
3. You could consider column generation. Rather than focusing on arcs, the master problem would look at complete paths (each starting at $S$ and having transit time no longer than $T$). The master problem would assign a binary variable ($x_p$) to each path $p$ (1 if used, 0 if not) with a constraint that $\sum_p x_p \le 8$ (one path per car). It would also contain your $y_e$ variables (and your current objective), with constraints saying that $y_e \le \sum_{e\in p}x_p$ (you traverse arc $e$ only if you drive at least one path containing it). If the cameras on the cars have 360 degree sweep (which I believe is the case), you should also say $y_e + y_{e'}\le 1$ where $e'$ is the reverse of arc $e$ (so that you don't get double credit for a street by hitting it both directions). The path generation subproblem would have a binary variable for each arc (used or not), a binary variable for each node (is this where the path ends?), and flow conservation constraints. The objective would be to maximize the "value" of the path, with the objective coefficients being based on something akin to shadow prices/dual values from the LP relaxation of the master problem.

There's not enough room here to enter into a discourse on column generation (plus I'd be the wrong person to do so), so I'll stop here. I will note that (a) there is "branch-price-and-cut", which is like branch-and-cut for column generation problems and gives optimal solutions if the problem cooperates, and (b) there are heuristics using column generation to get good but not provably optimal solutions.