8
$\begingroup$

I am currently working on the following problem, which is a variation of a vehicle routing problem. I am looking for different ideas to tackle it.

Problem description

A set of nodes with a given demand must be visited. The driver uses his vehicle with capacity $Q$ to approach the nodes, finds a parking spot, transfers part of the commodities into a knapsack with capacity $q$, and services whichever nodes he can. Once he is done, he returns to his vehicle with the empty knapsack, and either services another subset of nodes without moving the vehicle, or either moves on to find the next parking spot. The Figure below illustrates an example:

enter image description here

The red square is the depot. The blue circles are the parking spots, which are unknown a priori. And the grey squares are the nodes with known demand.

So the problem involves finding big tours (in blue), where the positions of the blue nodes are not known in advance, and subtours (in dark grey), where the depots are the blue nodes. The big tours and subtours have different capacity constraints ($Q$ and $q$, respectively). Nodes are not organized into clusters as nicely as in the picture. The positions of the parking spots (blue nodes) obviously impact the quality of the subtours. And the idea is to have the right number of parking spots in order to maximize efficiency. This efficiency could be indirectly taken into account with appropriate costs on the arcs, and perhaps with time constraints. For example, it would very likely be inefficient to park in front of each node with known demand, and move on to the next one (this would result in a classical CVRP).

Is this a known problem ?

I am not sure if this is a known problem. Similar problems include the $k$-layer Location Routing Problem, and the Traveling Salesman Facility Location Problem.

How would you tackle this problem ?

A possible approach would be to decompose the problem into two subproblems. Subproblem $1$ would be some sort of facility location problem (FLP), where the facilities are the parking spots, and where the selected facilities must form a tour with minimum cost. And Subproblem $2$ would be the corresponding subtours, where each facility from phase 1 is a depot. Subproblem $1$ already seems hard though, as it is already a mix between two hard problems (TSP and FLP).

All ideas are welcome.

Improve this question
$\endgroup$

3 Answers 3

Reset to default
5
$\begingroup$

This problem is known as two-echelon location routing problem (LRP-2E). On different mathematical programming model of LRP-2E:

  • Boccia, M., Crainic, T.G., Sforza, A., Sterle, C., 2011. Location-routing models for designing a two-echelon freight distribution system (No. CIRRELT-2011-06). Centre interuniversitaire de recherche sur les reseaux d’entreprise, la logistique et le transport (CIRRELT).
Improve this answer
$\endgroup$
2
  • $\begingroup$ If I understand well, the difference with the VRP-2E is that there is a fixed cost on satellites $\endgroup$
    – fontanf
    Commented Mar 3, 2022 at 14:39
  • 1
    $\begingroup$ LRP(-2E) and VRP(-2E) are much more similar than different in terms of modeling and solving. What make LRP different from VRP is that __facility location__(this is also a well studied problem in OR) decisions are integrated. If facility costs are equal to zero, we can open all the facility without adding additional cost to the objective. Consequently, the LRP becomes VRP. $\endgroup$
    – Penghui Guo
    Commented Mar 3, 2022 at 14:50
7
$\begingroup$

This is a Two-Echelon Vehicle Routing Problem. Here is a recent review of the literature on this problem:

  • "Two-Echelon Vehicle Routing Problems: A Literature Review" (Sluijk et al., 2022) DOI
Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks for the reference, this helps. However, if my understand is correct, in the Two-Echelon VRP, the satellites/parking spots/first echelon nodes are known in advance. Am I wrong ? $\endgroup$
    – Kuifje
    Commented Mar 3, 2022 at 14:04
  • $\begingroup$ The possible satellites are given as input, but I don't think that there is a constraint that imposes to visit them all $\endgroup$
    – fontanf
    Commented Mar 3, 2022 at 14:12
  • $\begingroup$ I think that without this constraint, the problem becomes the LRP-2E mentioned by @Penghui Guo. $\endgroup$
    – Kuifje
    Commented Mar 3, 2022 at 14:24
  • $\begingroup$ It depends on whether or not there is a fixed cost on using a satellite $\endgroup$
    – fontanf
    Commented Mar 3, 2022 at 14:40
4
$\begingroup$

You can actually get good results by dealing with it relatively simply. We support what we call 'park-and-loop vehicle routing' in our commercial route optimiser engine ODL Live. Currently we just use a limit on number of stops in the walking loop rather than a capacity, but it's pretty much the same problem. Crucially, we get good results by using just a simple deterministic rule at each stop, where (a) if you're not already parked, the rule makes the choice whether to walk or drive to the next stop, and (b) if you are already parked, the rule makes the choice whether to continue walking to the next stop, or to return to the parking spot and drive to the next stop.

Using a simple rule has the advantage that you effectively transform the problem into a standard VRP, because whether to walk or not is no longer a decision variable. So many of the standard search heuristics used on VRPs can still be used on this problem without modification.

Presumably there's situations where using a simple rule will create sub-optimal solutions compared to solving it properly as say a two-echelon location routing problem. However from a practical point-of-view this scheme appears to work well, it's relatively simple to implement if you have a heuristic-based solver (probably less so for a MIP-based solver) and presumably it requires less computational resources to optimise compared to a two-echelon problem formulation.

The following image shows some experiments from one of our test cases, where time for parking the vehicle is also considered. The walking loops get bigger as vehicle parking time increases because its more efficient to do larger walking loops and therefore park the vehicle less often.

enter image description here

Improve this answer
$\endgroup$
2
  • $\begingroup$ Interesting ! What is the deterministic rule that you use ? Based on the distance ? And so you compute this rule for every possible edge of the complete graph before hand ? $\endgroup$
    – Kuifje
    Commented Mar 5, 2022 at 10:56
  • $\begingroup$ It's travel time based including the time to move the car and park at a new location, and also subject to the number of stops limit in a loop. It can't be precomputed, because when you're parked it's a function of (1) current parked location, (2) current location and (3) next location, which is too big to precompute and fit in memory for realistic sized problems. $\endgroup$
    – Open Door Logistics
    Commented Mar 6, 2022 at 22:27

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