7
$\begingroup$

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)?

$\endgroup$
  • $\begingroup$ I think this question needs lots of edits. @Best_fit can you please review and add more details to the question for further clarification. Also using MathJax (or.meta.stackexchange.com/q/5/39) will be helpful. $\endgroup$ – Oguz Toragay Nov 6 '19 at 3:47
  • 1
    $\begingroup$ Something is a bit off. Currently, the question says $f_v:=0$ if the car stops at $v$ and 0 otherwise (so, identically 0) and $x_e=0$ if a picture of road $e$ is taken (1 if not? -- possible but a bit odd). $\endgroup$ – prubin Nov 6 '19 at 22:49
  • $\begingroup$ @prubin Yes, you're right it's 1. $\endgroup$ – Best_fit Nov 7 '19 at 4:59
  • $\begingroup$ @prubin any ideas on how to improve the model ? $\endgroup$ – Best_fit Nov 8 '19 at 18:33
  • $\begingroup$ Maybe you need to make the post a little bit shorter. $\endgroup$ – Amira Zarglayoun Nov 10 '19 at 10:47
8
+25
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ From your experience, which problems are known to be hard for MIP solvers ? I guess scheduling problems also but I am not sure $\endgroup$ – Amira Zarglayoun Nov 11 '19 at 0:21
  • $\begingroup$ Scheduling problems are definitely hard for MIP solvers. Constraint programming solvers usually do much better. $\endgroup$ – Ruslan Sadykov Nov 11 '19 at 8:54
  • $\begingroup$ If I need a "proof" to this claim "MIP solvers are bad to solve scheduling or VRP problems", what would it be ? do you have same papers or references ? $\endgroup$ – Amira Zarglayoun Nov 11 '19 at 14:32
  • $\begingroup$ The best branch-and-cut for basic VRP (doi.org/10.1007/s10107-003-0481-8) already has difficulties with instances with 50 clients, and it does not solve more than 100 clients (usually in a very long time). This branch-and-cut is quite complicated and uses many families of specialized cutting planes and complicated separation algorithms. MIP solvers implement generic branch-and-cut and they would do much worse that that. $\endgroup$ – Ruslan Sadykov Nov 13 '19 at 8:35
  • $\begingroup$ For machine scheduling problems, MIP formulations can usually be used only for small instances. For example, in doi.org/10.1016/j.ejor.2017.01.004, instances with up to 25 jobs only are tested. In doi.org/10.1109/ACCESS.2019.2947685, MIP formulations already have difficulties with instances with 50 jobs. Larger instances can however be solved for some particular scheduling problems: doi.org/10.1016/j.cor.2018.07.007, but in a long time in with specialized valid inequalities $\endgroup$ – Ruslan Sadykov Nov 13 '19 at 8:54
4
$\begingroup$
  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.

$\endgroup$
  • $\begingroup$ VRPSolver I have mentioned above does exactly (state-of-the-art) branch-price-and-cut. However, the instance size is far too large for this approach. $\endgroup$ – Ruslan Sadykov Nov 13 '19 at 8:32
  • $\begingroup$ Why do you think there still some errors ? could you give an example please ? $\endgroup$ – Best_fit Nov 15 '19 at 18:44
  • $\begingroup$ The penultimate constraint says that the number of times you exit $v_s$ is either one or two greater than the number of times you enter $v_s$. $\endgroup$ – prubin Nov 16 '19 at 17:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.