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