How to tackle this VRP variant?

Question

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:

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.

Answer 1

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

Answer 2

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

Answer 3

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.